Predictor-Corrector Algorithm for Convex Quadratic Programming with Upper Bounds

Abstract

Predictor-corrector algorithm for linear programming, proposed by Mizuno et al.$^{[1]}$, becomes the best well known in the interior point methods. The purpose of this paper is to extend these results in two directions. First, we modify the algorithm in order to solve convex quadratic programming with upper bounds. Second, we replace the corrector step with an iteration of Monteiro and Adler's algorithm$^{[2]}$. With these modifications, the duality gap is reduced by a constant factor after each corrector step for convex quadratic programming. It is shown that the new algorithm has a $O(\sqrt nL)$-iteration complexity.