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

作     者：余谦 黄崇超 江燕 

作者机构：Institute of Systems Engineering of Wuhan University Wuhan 430072China School of Mathematics and Statistics Wuhan UniversityWuhan 430072China 

出 版 物：《Acta Mathematica Scientia》 (数学物理学报（B辑英文版）)

年 卷 期：2006年第26卷第2期

页      面：265-270页

核心收录：

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Project supported by the National Science Foundation of China (60574071) the Foundation for University Key Teacher by the Ministry of Education 

主　　题：Convex quadratic programming predictor-corrector interior-point algorithm 

摘      要：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 O（√nL） iteration complexity which is the best result for convex quadratic programming so far.