An extension of Karmarkar’s projective algorithm for convex quadratic programming

The authors present an extension of Karmarkar’s linear programming algorithm for solving a more general group of optimization problems: convex quadratic programs. The extension is based on the iterated application of the objective augmentation and the projective transformation, followed by optimization over an inscribing ellipsoid centered at the current solution. It creates a sequence of interior feasible points that converge to the optimal feasible solution in O(Ln) iterations; each iteration can be computed in O(Ln³) arithmetic operations, where n is the number of variables and L is the number of bits in the input. In this paper, the authors emphasize its convergence property, practical efficiency, and relation to the ellipsoid method.