对称锥规划的邻域跟踪算法

• 作者: 刘红卫 刘长河 尚有林
• 来源期刊: 中国科学（数学）
• 关键词: 对称锥规划 Euclid Jordan 代数 邻域跟踪算法 宽邻域 内点法 多项式复杂性
• 年，卷（期）: 2013,（7）
• 所属期刊栏目: 论文
• 页码范围: 691-702
• 页数: 12页
• 语种: 中文
• DOI: 10.1360/012011-577

摘要

本文把艾文宝的邻域跟踪算法推广到对称锥规划,定义中心路径的宽邻域N(τ,β),并证明该邻域的一个重要性质,该性质在算法的复杂性分析中起到关键作用.取宽邻域N(τ,β)中一点为初始点并采用Nesterov-Todd (NT)搜索方向,则该算法的迭代复杂界为O((√)rlogε-1),其中,r是Euclid Jordan代数的秩,ε是允许误差.这是对称锥规划的宽邻域内点算法最好的复杂界.