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

• 作者: 刘红卫 吴岳 谢迪
• 来源期刊: 中国科学院大学学报
• 学科: 数学
• 关键词: 齐次不可行内点算法 单调互补问题 半定规划
• 年，卷（期）: 2016,（3）
• 所属期刊栏目: 数学与物理学
• 页码范围: 317-328
• 分类号: O221.1
• 语种: 中文
• DOI: 10.7523/j.issn.2095-6134.2016.03.006

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘红卫	西安电子科技大学数学与统计学院	63	222	8.0	12.0
2	谢迪	兰州理工大学理学院	3	1	1.0	1.0
3	吴岳	西安电子科技大学数学与统计学院	1	0	0.0	0.0