%0 Journal Article
%T 半定规划的齐次不可行内点算法<br>A homogeneous infeasible-interior-point algorithm for semidefinite programming
%A 吴岳
%A 刘红卫
%A 谢迪
%J 中国科学院大学学报
%D 2016
%R 10.7523/j.issn.2095-6134.2016.03.006
%X 摘要 为降低半定规划(SDP)问题的迭代复杂度,并且有更好的数值实验结果,提出一种新的宽邻域上的齐次不可行内点算法.半定规划的KKT条件是单调互补问题(MCP),通过构造齐次模型(HMCP)以及提出新的宽邻域来解这个齐次模型,得到半定规划问题的最优解.这种算法容易判定原问题是否可行.在NT方向,证明迭代点在新的宽邻域内是收敛的,且迭代复杂度为O(√nlogL),其中n是SDP问题的维数,L=Tr(X0S0)/ε,其中ε是需要的精度,(X0,S0)是迭代起始点.这个复杂度比一般的半定规划不可行算法的迭代复杂度低.提供了数值实验,证明此算法比其他不可行算法具有更好的数值实验结果.<br>
%K 齐次不可行内点算法
%K 单调互补问题
%K 半定规划&lt
%K br&gt
%K homogeneous infeasible-starting interior-point algorithm
%K monotone complementarity problem
%K semidefinite programming
%U http://journal.ucas.ac.cn/CN/abstract/abstract12351.shtml