A homogeneous infeasible-interior-point algorithm for semidefinite programming

doi:10.7523/j.issn.2095-6134.2016.03.006

Abstract

Abstract:

We propose a homogeneous infeasible-interior-point algorithm for semidefinite programming(SDP) in a new wide neighborhood in order to achieve low iteration complexity and get better experiement numerical results. Complementarity problem (MCP) is the KKT condition of SDP. We sovle MCP by constructing a homogeneous MCP model (HMCP) and proposing a new wide neighborhood. Then we derive the optimal solution of SDP. This algorithm can be easily used to determine whether SDP is feasible or not. At the direction of NT, we prove that the iteration poin is convergent in new wide neighborhood and the iteration complexity is O(√nlogL), where n is the dimension of SDP and L=Tr(X⁰S⁰)/ε with ε being the required precision and (X⁰,S⁰) the initial point. This algorithm has lower complexity degree than other algorithms for SDP. The numerical experiment is provided. We have proved that this algorithm is better than other infeasible-interior-point algorithms in numerical experimentel results.

Key words: homogeneous infeasible-starting interior-point algorithm, monotone complementarity problem, semidefinite programming

CLC Number:

O221.1

WU Yue, LIU Hongwei, XIE Di . A homogeneous infeasible-interior-point algorithm for semidefinite programming[J]. , 2016, 33(3): 317-328.

References

[1] Liu H, Yang X, Liu C. A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming[J]. Journal of Optimization Theory and Applications, 2013, 158(3):796-815.
[2] Rangarajan B K. Polynomial convergence of infeasible-interior-point methods over symmetric cones[J]. Siam Journal on Optimization, 2006, 16(4):1 211-1 229.
[3] Andersen E D, Ye Y. On a homogeneous algorithm for the monotone complementarity problem[J]. Mathematical Programming, 1995, 84(2): 375-399.
[4] Cottle R W, Pang J S, Stone R E. The linear complementarity problem[J]. Computer Science and Scientific Computing, 1992, 1: 132-133.
[5] Güler O. Existence of interior points and interior paths in nonlinear monotone complementarity problems[J]. Mathematics of Operations Research, 1993, 18(1):128-147.
[6] Kojima M, Mizuno S, Yoshise A. A convex property of monotone complementarity problems . Department of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan:1993.
[7] 韩继业, 修乃华, 戚厚铎. 非线性互补理论与算法[M]. 上海:上海科学技术出版社, 2006.
[8] Klerk E. Aspects of semidefinite programming[M]. New York, Boston, Dordrecht, London, Moscow: Kluwer Academic Publishers, 2004.
[9] Zhang Y. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming[J]. Siam Journal on Optimization, 1998, 8(2):365-386.
[10] Shida M, Shindoh S, Kojima M. Existence and uniqueness of search directions in interior-point algorithms for the SDP and the monotone SDLCP[J]. Siam Journal on Optimization, 1998, 8(2): 387-396.
[11] Ai W, Zhang S. An O( n L) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP[J]. Siam Journal on Optimization, 2005, 16(2): 400-417.
[12] Li Y, Terlaky T. A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with O n log Tr(X⁰S⁰) ε iteration complexity[J]. Siam Journal on Optimization, 2010, 20(6):2 853-2 875.
[13] 刘新泽. 对称锥互补问题若干内点算法的复杂性研究 . 西安: 西安电子科技大学, 2014.
[14] Jin S, Ariyawansa K A, Zhu Y. Homogeneous self-dual algorithms for stochastic semidefinite programming[J]. Journal of Optimization Theory and Applications, 2012, 155(3):1 073-1 083.
[15] 杨喜美. 对称锥规划的宽邻域内点算法研究 . 西安: 西安电子科技大学, 2014.
[16] 刘长河. 锥规划中若干内点算法的复杂性研究 .西安: 西安电子科技大学, 2012.
[17] Todd M J, Toh K C, T R H. On the Nesterov-Todd direction in semidefinite programming[J]. Siam Journal on Optimization, 1997, 8(3):769-796.