Welcome To WUJNS
武汉大学学报 英文版 | Wuhan University Journal of Natural Sciences
Wan Fang
CNKI
CSCD
Wuhan University
Latest Article
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.
Key words:arc-search; interior-point algorithm; polynomial complexity; convex quadratic programming
CLC number:O 221
References:
[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.
Welcome To WUJNS

HOME | Aim and Scope | Editoral Board | Current Issue | Back Issue | Subscribe | Crosscheck | Polishing | Contact us Copyright © 1997-2017 All right reserved