|
|
- 2016
半定规划的齐次不可行内点算法
|
Abstract:
摘要 为降低半定规划(SDP)问题的迭代复杂度,并且有更好的数值实验结果,提出一种新的宽邻域上的齐次不可行内点算法.半定规划的KKT条件是单调互补问题(MCP),通过构造齐次模型(HMCP)以及提出新的宽邻域来解这个齐次模型,得到半定规划问题的最优解.这种算法容易判定原问题是否可行.在NT方向,证明迭代点在新的宽邻域内是收敛的,且迭代复杂度为O(√nlogL),其中n是SDP问题的维数,L=Tr(X0S0)/ε,其中ε是需要的精度,(X0,S0)是迭代起始点.这个复杂度比一般的半定规划不可行算法的迭代复杂度低.提供了数值实验,证明此算法比其他不可行算法具有更好的数值实验结果.
| [1] | 杨喜美. 对称锥规划的宽邻域内点算法研究 . 西安: 西安电子科技大学, 2014. |
| [2] | 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.</p> |
| [3] | <p> 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. |
| [4] | 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. |
| [5] | 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. |
| [6] | Andersen E D, Ye Y. On a homogeneous algorithm for the monotone complementarity problem[J]. Mathematical Programming, 1995, 84(2): 375-399. |
| [7] | Cottle R W, Pang J S, Stone R E. The linear complementarity problem[J]. Computer Science and Scientific Computing, 1992, 1: 132-133. |
| [8] | 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. |
| [9] | Kojima M, Mizuno S, Yoshise A. A convex property of monotone complementarity problems . Department of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan:1993. |
| [10] | 韩继业, 修乃华, 戚厚铎. 非线性互补理论与算法[M]. 上海:上海科学技术出版社, 2006. |
| [11] | Klerk E. Aspects of semidefinite programming[M]. New York, Boston, Dordrecht, London, Moscow: Kluwer Academic Publishers, 2004. |
| [12] | 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. |
| [13] | 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. |
| [14] | 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. |
| [15] | Li Y, Terlaky T. A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with O n <em>log</em> Tr(X<sup>0</sup>S<sup>0</sup>) ε iteration complexity[J]. Siam Journal on Optimization, 2010, 20(6):2 853-2 875. |
| [16] | 刘新泽. 对称锥互补问题若干内点算法的复杂性研究 . 西安: 西安电子科技大学, 2014. |
| [17] | 刘长河. 锥规划中若干内点算法的复杂性研究 .西安: 西安电子科技大学, 2012. |
