Articles

A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

  • Yu Qian ,
  • Huang Chongchao ,
  • Jiang Yan
Expand
  • Institute of Systems Engineering of Wuhan University, Wuhan 430072, China

Received date: 2003-07-10

  Revised date: 2004-07-08

  Online published: 2006-04-20

Abstract

This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has ${\rm O}(\sqrt n L)$ iteration complexity which is the best result for convex quadratic programming so far.

Cite this article

Yu Qian , Huang Chongchao , Jiang Yan . A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING[J]. Acta mathematica scientia, Series B, 2006 , 26(2) : 265 -270 . DOI: 10.1016/S0252-9602(06)60048-9

Outlines

/