半定规划的齐次不可行内点算法

doi:10.7523/j.issn.2095-6134.2016.03.006

中国科学院大学学报 ›› 2016, Vol. 33 ›› Issue (3): 317-328.DOI: 10.7523/j.issn.2095-6134.2016.03.006

半定规划的齐次不可行内点算法

吴岳¹, 刘红卫¹, 谢迪²

1. 西安电子科技大学数学与统计学院, 西安 710126;
2. 兰州理工大学理学院, 兰州 730050

收稿日期:2015-03-18 修回日期:2015-09-15 发布日期:2016-05-15
通讯作者: 吴岳
基金资助:
国家自然科学基金(61072144,61179040)和中央高校基本科研业务费专项基金(K50513100007)资助

A homogeneous infeasible-interior-point algorithm for semidefinite programming

WU Yue¹, LIU Hongwei¹, XIE Di²

1. School of Mathematics and Statistics, Xidian University, Xi'an 710126, China;
2. School of Sciences, Lanzhou University of Technology, Lanzhou 730050, China

Received:2015-03-18 Revised:2015-09-15 Published:2016-05-15

摘要/Abstract

摘要：

为降低半定规划(SDP)问题的迭代复杂度,并且有更好的数值实验结果,提出一种新的宽邻域上的齐次不可行内点算法.半定规划的KKT条件是单调互补问题(MCP),通过构造齐次模型(HMCP)以及提出新的宽邻域来解这个齐次模型,得到半定规划问题的最优解.这种算法容易判定原问题是否可行.在NT方向,证明迭代点在新的宽邻域内是收敛的,且迭代复杂度为O(√nlogL),其中n是SDP问题的维数,L=Tr(X⁰S⁰)/ε,其中ε是需要的精度,(X⁰,S⁰)是迭代起始点.这个复杂度比一般的半定规划不可行算法的迭代复杂度低.提供了数值实验,证明此算法比其他不可行算法具有更好的数值实验结果.

关键词: 齐次不可行内点算法, 单调互补问题, 半定规划

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

中图分类号:

O221.1

吴岳, 刘红卫, 谢迪. 半定规划的齐次不可行内点算法[J]. 中国科学院大学学报, 2016, 33(3): 317-328.

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

参考文献

[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.

半定规划的齐次不可行内点算法

A homogeneous infeasible-interior-point algorithm for semidefinite programming

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

访问统计

联系我们

[1]	田雷霞, 杨文国, 高随祥, 姜志鹏. 不确定传输速率下无线资源调度问题的鲁棒优化模型[J]. 中国科学院大学学报, 2018, 35(1): 18-25.
[2]	刘鹏飞, 杨文国. 对鲁棒线性规划保守性的进一步讨论[J]. 中国科学院大学学报, 2015, 32(5): 577-581.