半定规划的一种Mehrotra型预估-校正算法

摘要：

将一种Mehrotra型预估-校正算法推广到半定规划.首先给出了半定规划基于Mehrotra型预估-校正算法的一些基本理论,尤其是对称化技术;随后通过分析这种算法的迭代复杂性,给出算法的重要思想:在校长步中采用安全策略,给出新算法的最大预估步长的上界,算法过程中对最大预估步长进行削减策略:当最大预估步长大于某个阈值时,对此步长进行削减(可重复),从而得到合适的校正步长下界;最终通过采用以上策略及NT搜索方向,得到了该算法的多项式复杂界.

关键词：大步校正算法、Mehrotra型预估-校正算法、半定规划、多项式复杂性

所属期刊栏目：32

分类号：O221.2(运筹学)

资助基金：贵州省科学技术基金No.黔科合J字LKLS”2013”14

在线出版日期：2015-06-15（万方平台首次上网日期，不代表论文的发表时间）

页码：11-16