收稿日期: 2015-03-18
修回日期: 2015-09-15
网络出版日期: 2016-05-15
基金资助
国家自然科学基金(61072144,61179040)和中央高校基本科研业务费专项基金(K50513100007)资助
A homogeneous infeasible-interior-point algorithm for semidefinite programming
Received date: 2015-03-18
Revised date: 2015-09-15
Online published: 2016-05-15
为降低半定规划(SDP)问题的迭代复杂度,并且有更好的数值实验结果,提出一种新的宽邻域上的齐次不可行内点算法.半定规划的KKT条件是单调互补问题(MCP),通过构造齐次模型(HMCP)以及提出新的宽邻域来解这个齐次模型,得到半定规划问题的最优解.这种算法容易判定原问题是否可行.在NT方向,证明迭代点在新的宽邻域内是收敛的,且迭代复杂度为O(√nlogL),其中n是SDP问题的维数,L=Tr(X0S0)/ε,其中ε是需要的精度,(X0,S0)是迭代起始点.这个复杂度比一般的半定规划不可行算法的迭代复杂度低.提供了数值实验,证明此算法比其他不可行算法具有更好的数值实验结果.
吴岳 , 刘红卫 , 谢迪 . 半定规划的齐次不可行内点算法[J]. 中国科学院大学学报, 2016 , 33(3) : 317 -328 . DOI: 10.7523/j.issn.2095-6134.2016.03.006
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(X0S0)/ε with ε being the required precision and (X0,S0) 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.
[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(X0S0) ε 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.
/
| 〈 |
|
〉 |
