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

A homogeneous infeasible-interior-point algorithm for semidefinite programming

作　　者：吴岳[1] 刘红卫[1] 谢迪[2] 

机构地区：[1]西安电子科技大学数学与统计学院,西安710126 [2]兰州理工大学理学院,兰州730050

出　　处：《中国科学院大学学报（中英文）》2016年第3期317-328,共12页Journal of University of Chinese Academy of Sciences

基　　金：国家自然科学基金(61072144;61179040);中央高校基本科研业务费专项基金(K50513100007)资助

摘　　要：为降低半定规划(SDP)问题的迭代复杂度,并且有更好的数值实验结果,提出一种新的宽邻域上的齐次不可行内点算法.半定规划的KKT条件是单调互补问题(MCP),通过构造齐次模型(HMCP)以及提出新的宽邻域来解这个齐次模型,得到半定规划问题的最优解.这种算法容易判定原问题是否可行.在NT方向,证明迭代点在新的宽邻域内是收敛的,且迭代复杂度为O(n^(1/2)log L),其中n是SDP问题的维数,L=Tr(X^0S^0)/ε,其中ε是需要的精度,(X^0,S^0)是迭代起始点.这个复杂度比一般的半定规划不可行算法的迭代复杂度低.提供了数值实验,证明此算法比其他不可行算法具有更好的数值实验结果.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（√nlog L） , where n is the dimension of SDP andL=Tr（X^0S^0）/εwith 6 being the required precision and （X^0 ,S^0） 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-interiorpoint algorithms in numerical experimentel results.

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

分 类 号：O221.1[理学—运筹学与控制论]