A Wide Neighborhood Arc-Search Interior-Point Algorithm for Convex Quadratic Programming

Time:2017-11-15

YUAN Beibei1, ZHANG Mingwang1†, HUANG Zhengwei2 1. College of Science, China Three Gorges University, Yi-chang 443002, Hubei, China; 2. College of Economics and Management, China Three Gorges University, Yichang 443002, Hubei, China

Abstract:

In this paper, we propose an arc-search interior-point algorithm for convex quadratic programming with a wide neighborhood of the central path, which searches the optimizers along the ellipses that approximate the entire central path. The favorable polynomial complexity bound of the algorithm is obtained, namely which is as good as the linear programming analogue. Finally, the numerical experiments show that the proposed algorithm is efficient.

[1] Karmarkar N K. A new polynomial-time algorithm for linear programming[J]. Combinatorica, 1984, 4: 373-395.
[2] Goldfarb D, Liu S. An primal interior point algo-rithm for convex quadratic programming [J]. Math Program, 1990, 49: 325-340.
[3] Ye Y, Tse E. An extension of Karmarkar’s projective algo-rithm for convex quadratic programming[J]. Math Program, 1989, 44: 157-179.
[4] Montriro R, Adler I. Interior path following primal-dual algorithms. Part II: Convex quadratic programming[J]. Math Program, 1989, 44: 43-66.
[5] Roos C, Terlaky T, Vial J-Ph. Theory and Algorithms for Linear Optimization: An Interior Approach[M]. Chichester: John Wiley Sons, 1997.
[6] Wright S J. Primal-Dual Interior-Point Methods [M]. Philade- lphia: SIAM, 1997.
[7] Nesterov Y. Long-step strategies in interior-point primal-dual methods [J]. Math Program, 1996, 76: 47-94.
[8] Hung P, Ye Y. An asymptotical -iteration path- fol-lowing linear programming algorithm that use wide neigh-borhoods [J]. SIAM J Optim, 1996, 6: 570-586.
[9] Jansen B, Roos C, Terlaky T. Improved complexity using higher-order correctors for primal-dual Dikin affine scal-ing[J]. Math Program, 1996, 76: 117-130.
[10] Monteiro R D, Adler I, Resende M G C. A polynomial-time primal-dual affine scaling algorithm for linear and convex-quadratic programming and its power series extension[J]. Math Oper Res, 1990, 151: 191-214.
[11] Yang Y G. Arc-search path-following interior-point algo-rithms forlinear programming[C]// Optim Online. Philadel-phia: Optimization Community, 2009: 1-9.
[12] Yang Y G. A polynomial arc-search interior-point algorithms for linear programming[J]. J Optim Theory Appl, 2013, 158: 859-873.
[13] Yang Y G, Yamashita M. An arc-search O(nL) infeasible- interior-point algorithm for linear programming [J]. Optim Lett, 2017: doi:10.1007/s11590-017-1142-9.
[14] Yang Y G. A polynomial arc-search interior-point algorithms for convex quadratic programming[J]. Eur J Oper Res, 2011, 215: 25-38.
[15] Pirhaji M, Zangiabadi M, Mansouri H. An -neighborhood infeasible interior-point algorithm for linear complementa-ri-ty problems [J]. 4OR-Q J Oper Res, 2016: doi:10.1007/s 10288- 016- 0325.
[16] Yang X M, Zhang Y K, Liu H M. A wide neighborhood infeasible interior-point method with arc-search for linear programming[J]. J Appl Math Comput, 2016, 51: 209-225.
[17] Yang X M, Liu H W, Zhang Y K. An arc-search infeasible interior-point method for symmetric optimization in a wide neighborhood of the central path[J]. Optim Lett, 2016: doi:10. 1007/s11590-016-0997-5.
[18] Carmo M P. Differential Geometry of Curves and Surfac-es[M]. New Jersey: Prentice-Hall, 1976.
[19] Mizuno S, Todd M J, Ye Y. On adaptive-step primal-dual interior-point algorithm for linear programming [J]. Math-matics of Operations Research, 1990, 944: 1-18.
[20] Zhang Y, Zhang D T. On polynomiality of the methrotra- predictor-corrector interior-point algorithms[J]. Math Progr- am, 1995, 68: 303-318.