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

Tian-De Guo & Shi-Quan Wu

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

Published online: 1995-04

Export citation
  • 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

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-13-161, author = {Guo , Tian-De and Wu , Shi-Quan}, 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 AU - Guo , Tian-De AU - Wu , Shi-Quan 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.

Tian-De Guo & Shi-Quan Wu. (1970). Predictor-Corrector Algorithm for Convex Quadratic Programming with Upper Bounds. Journal of Computational Mathematics. 13 (2). 161-171. doi:
Copy to clipboard
The citation has been copied to your clipboard