Global Convergence of the Affine Scaling Method for Convex Quadratic Programming
Renato D. C. Monteiro and Takashi Tsuchiya
In this paper we give a global convergence proof of
the second order affine scaling algorithm for convex quadratic
programming problems, where the next iterate is the point which minimizes
the objective function over the intersection of the feasible
region with the ellipsoid centered at the current point and whose
radius is a fixed fraction $\beta \in (0,1]$ of the radius of the
largest ``scaled'' ellipsoid inscribed in the nonnegative orthant.
The analysis is based on the local Karmarkar potential function introduced
by Tsuchiya. For any $\beta \in (0, 2/3]$ and without assuming any
nondegeneracy assumption on the problem, it is shown that
the sequences of primal iterates and dual estimates
converge to optimal solutions of the quadratic program and its
Preprint, Georgia Institute of Technology, March, 1995.