| A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING |
| |
| 作者姓名： | 余谦 黄崇超 江燕 |
| |
| 作者单位： | Institute of Systems Engineering of Wuhan University Wuhan 430072 China，School of Mathematics and Statistics Wuhan University，Wuhan 430072，China，School of Mathematics and Statistics Wuhan University，Wuhan 430072，China |
| |
| 基金项目： | Project supported by the National Science Foundation of China (60574071)
the Foundation for University Key Teacher by the Ministry of Education. |
| |
| 摘 要： | 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(n~(1/2)L) iteration complexity which is the best result for convex quadratic programming so far.
|
| 关 键 词： | 凸二次规划 预估校正子 内点算法 多项式 |
| 收稿时间： | 2003-07-10 |
| 修稿时间： | 2004-07-08 |
A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING |
| |
| Yu Qian,Huang Chongchao,Jiang Yan.A POLYNOMIAL PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING[J].Acta Mathematica Scientia,2006,26(2):265-270. |
| |
| Authors: | Yu Qian Huang Chongchao Jiang Yan |
| |
| 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 O(n~(1/2)L) iteration complexity which is the best result for convex quadratic programming so far. |
| |
| Keywords: | Convex quadratic programming predictor-corrector interior-point algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
