| 半定规划的齐次不可行内点算法 |
| |
| 作者姓名： | 吴岳 刘红卫 谢迪 |
| |
| 作者单位： | 1. 西安电子科技大学数学与统计学院, 西安 710126;
2. 兰州理工大学理学院, 兰州 730050 |
| |
| 基金项目： | 国家自然科学基金(61072144,61179040)和中央高校基本科研业务费专项基金(K50513100007)资助 |
| |
| 摘 要： | 为降低半定规划(SDP)问题的迭代复杂度,并且有更好的数值实验结果,提出一种新的宽邻域上的齐次不可行内点算法.半定规划的KKT条件是单调互补问题(MCP),通过构造齐次模型(HMCP)以及提出新的宽邻域来解这个齐次模型,得到半定规划问题的最优解.这种算法容易判定原问题是否可行.在NT方向,证明迭代点在新的宽邻域内是收敛的,且迭代复杂度为O(√nlogL),其中n是SDP问题的维数,L=Tr(X0S0)/ε,其中ε是需要的精度,(X0,S0)是迭代起始点.这个复杂度比一般的半定规划不可行算法的迭代复杂度低.提供了数值实验,证明此算法比其他不可行算法具有更好的数值实验结果.
|
| 关 键 词： | 齐次不可行内点算法 单调互补问题 半定规划 |
| 收稿时间： | 2015-03-18 |
| 修稿时间： | 2015-09-15 |
A homogeneous infeasible-interior-point algorithm for semidefinite programming |
| |
| Authors: | WU Yue LIU Hongwei XIE Di |
| |
| Institution: | 1. School of Mathematics and Statistics, Xidian University, Xi'an 710126, China;
2. School of Sciences, Lanzhou University of Technology, Lanzhou 730050, China |
| |
| 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(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. |
| |
| Keywords: | homogeneous infeasible-starting interior-point algorithm monotone complementarity problem semidefinite programming |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《》浏览原始摘要信息 |
| 点击此处可从《》下载免费的PDF全文 |
|
