A note on a wide neighborhood infeasible interior-point algorithm for semidefinite programming

Expand
  • 1. School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China; 2. Huidong Middle School, Huidong 615200,  Sichuan, China

Received date: 2015-10-26

  Online published: 2016-06-15

Abstract

Combing Newton method with predictor-corrector method, a new search direction is applied to a wide neighborhood infeasible-interior point algorithm for solving semidefinite programming. It is shown that this algorithm is a polynomial-time algorithm, which requires that all iterative points are in the neighborhood of the infeasible central path, but does not require the feasibility of the initial and iterative points.Under some mild assumptions, we show that the iteration-complexity bound is O(\sqrt{n}L).Numerical analysis are also presented in this paper.Preliminary numerical results demonstrate the effectiveness of our method in both KM direction and NT direction.

Cite this article

YANG Yang, LUO Honglin, LUO Huilin . A note on a wide neighborhood infeasible interior-point algorithm for semidefinite programming[J]. Operations Research Transactions, 2016 , 20(2) : 79 -87 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.007

References

[1] 艾文宝. 线性规划的邻域跟踪算法 [J].中国科学, 2004, 34(1): 40-47.
[2] Henry W, Romesh S, Lieven V. Handbook of Semidefinite Programming [M]. Boston: Kluwer Academic Publishers, 1999, 267-306.
[3] Zhang Y. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming [J].Optimization, 1998, 8: 365-386.
[4] Zhou G, Toh K C.Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming [R].Singapore: National University of Singapore, 2004, 261-282.
[5] Alizadeh F, Haeberly J P A, Overton M L.Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results [J].Optimization, 1998, 8: 746-768.
[6] Monteiro R D C, Zhang Y.A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming [J].Mathematical Programming, 1998, 81: 281-299.
[7] Nesterov Y E, Todd M J.Self-scaled barriers and interior-point methods for convex programming [J].Mathematical Operation Research, 1997, 22: 1-42.
[8] 冯增哲, 张西学, 刘建波, 等. 半定规划的一个新的宽邻域非可行内点算法 [J].运筹学学报, 2014, 18(2): 49-58.
[9] 迟晓妮, 刘三阳, 李炳杰.二次锥规划的一不可行内点算法 [J].兰州大学学报(自然科学版), 2007, 43(4): 136-139.

 

Outlines

/