Volume 13, Issue 2
Predictor-Corrector Algorithm for Convex Quadratic Programming with Upper Bounds

J. Comp. Math., 13 (1995), pp. 161-171

Published online: 1995-04

Preview Full PDF 159 1748
Export citation

Cited by

• 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.

• Keywords

@Article{JCM-13-161, author = {}, title = {Predictor-Corrector Algorithm for Convex Quadratic Programming with Upper Bounds}, journal = {Journal of Computational Mathematics}, year = {1995}, volume = {13}, number = {2}, pages = {161--171}, 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. }, issn = {1991-7139}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/jcm/9259.html} }
TY - JOUR T1 - Predictor-Corrector Algorithm for Convex Quadratic Programming with Upper Bounds JO - Journal of Computational Mathematics VL - 2 SP - 161 EP - 171 PY - 1995 DA - 1995/04 SN - 13 DO - http://doi.org/ UR - https://global-sci.org/intro/article_detail/jcm/9259.html KW - AB - 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.