半定规划的一个新的宽邻域非可行内点算法

Abstract

Abstract: A new infeasible interior-point algorithm for solving semidefinite programming is proposed, based on a new wide neighborhood. Under suitable assumptions, it shows that the algorithm's iterate complexity bound is O(\sqrt{n}L), which is better than the best result O(n\sqrt{n}L) in this class algorithm so far, and is the same as the best known bound of feasible interior point algorithms.

Key words: semidefinite programming, infeasible interior-point algorithm, wide neighborhood, iteration complexity bound

CLC Number:

O221.2

FENG Zengzhe, ZHANG Xixue, LIU Jianbo$, FANG Liang. A new wide neighborhood infeasible interior-point algorithm for semidefinite programming[J]. Operations Research Transactions, 2014, 18(2): 49-58.

References

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.

Vandenberghe L, Boyd S. A primal-dual potential reduction method for problems involving matrix inequalities [J]. Mathematical Programming, 1995, 69: 205-236.
Zhang Y. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming [J]. SIAM Journal on Optimization, 1998, 8: 365-386.
Nesterov Y E, Nemirovsky A S. Interior Point Methods in Convex Programming: Theory and Applications [M]. Philadelphia PA: SIAM, 1994.
Nesterov Y E, Nemirovsky A S. Interior Point Methods in Convex Programming: Theory and Applications [M]. Philadelphia PA: SIAM, 1994.
艾文宝. 线性规划的邻域跟踪算法 [J]. 中国科学, 2004, 34(1): 40-47.
Ai W B, Zhang S Z. An O(nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP [J]. SIAM Journal on Optimization, 2005, 16: 400-417.
Feng Z Z, Fang L. A wide neighborhood interior-point method with O(nL) iteration-complexity bound for semidefinite programming [J]. Optimization, 2010, 59(8): 1235-1246.
Feng Z Z. A new iteration large update primal-dual interior-point method for second-order cone programming [J]. Numerical Functional Analysis and Optimization, 2012, 33(4): 397-414.
Alizadeh F, Haeberly J A, Overton N. Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results [J]. SIAM Journal on Optimization, 1998, 8: 746-768.
Helmberg C, Rendl F, Vanderbei R J, et al. An interior-point method for semidefinite programming [J]. SIAM Journal on Optimization, 1996, 6: 342-361.
Kojima M, Shindoh S, Hara S. Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices [J]. SIAM Journal on Optimization, 1997, 7: 86-125.
Monteiro R D C. Primal-dual path-following algorithms for semidefinite programming [J]. SIAM Journal on Optimization, 1997, 7: 663-678.
Nesterov Y E, Todd M J. Primal-dual interior point methods for self-scaled cones [J]. Mathematics of Operations Research, 1997, 22: 1-42.
迟晓妮, 刘三阳, 李炳杰. 二次锥规划的不可行内点算法 [J]. 兰州大学学报, 2007, 43(4): 136-139.
Chi X N, Liu S Y. An infeasible-interior-point predictor-corrector algorithm for the second-order cone programming [J]. Acta Mathematica Scientia, 2008, 28B(3): 551-559.
Chi X N, Liu S Y. An infeasible-interior-point predictor-corrector algorithm for the second-order cone programming [J]. Acta Mathematica Scientia, 2008, 28B(3): 551-559.

[1]	LI Jianling, ZHANG Hui, YANG Zhenping, JIAN Jinbao. A globally convergent SSDP algorithm without a penalty function or a filter for nonlinear semidefinite programming [J]. Operations Research Transactions, 2018, 22(4): 1-16.
[2]	WANG Yishui, XU Dachuan, WU Chenchen. A semidefinite programming rounding algorithm for correlation clustering problem [J]. Operations Research Transactions, 2018, 22(1): 67-76.
[3]	CHEN Zhongwen, ZHAO Qi, BIAN Kai. A successive linearization method with flexible penalty for nonlinear semidefinite programming [J]. Operations Research Transactions, 2017, 21(2): 84-100.
[4]	YUAN Chunhong. The epsilon-weak proper efficiency of multiobjective semidefinite programming with set-valued maps [J]. Operations Research Transactions, 2017, 21(1): 23-32.
[5]	LI Yongling, YANG Yang, LUO Honglin. The optimality conditions and duality theory for multiobjective semidefinite programming [J]. Operations Research Transactions, 2016, 20(3): 68-78.
[6]	SUN Ting, LI Gaidi, XU Wenqing. Approximation algorithms for max cut and max bisection problems using semi-definite programming relaxations [J]. Operations Research Transactions, 2016, 20(3): 21-32.
[7]	LI Jianling, YANG Zhenping, JIAN Jinbao. Introduction of some algorithms for nonlinear semidefinite programming [J]. Operations Research Transactions, 2016, 20(2): 1-22.
[8]	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.
[9]	LIU Changhe, SHANG Youlin, LI Jinrui. Path-following interior point algorithms based on wide neighborhoods and a new class of directions [J]. Operations Research Transactions, 2016, 20(1): 43-53.
[10]	HAN Yingwei, XIA Yong. A dual method for the pose estimation problem [J]. Operations Research Transactions, 2013, 17(3): 86-92.

A new wide neighborhood infeasible interior-point algorithm for semidefinite programming

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics

Comments