一种新的凸二次规划的Mehrotra型预估-校正算法

摘要：

Mehrotra型预估-校正算法是众多基于内点算法的优化软件包的核心算法.最近,Salahi等人对线性规划提出一种新的Mehrotra型预估-校正算法.该算法不仅有多项式复杂性还具有良好的实际计算效果.本文将其算法推广至凸二次规划,这种算法在预估步最大可行步长高于某一阈值时将其削减,若首次削减仍没得到合适的校正步长,则将预估步长进行再削减,从而保证校正步步长有合适下界.算法在最坏情况下的迭代复杂性为O(n3/2 logn/ε).最后,Matlab仿真实验验证了算法的可行性.

关键词：凸二次规划、内点算法、Mehrotra型预估-校正算法、多项式复杂性

所属期刊栏目：28

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

资助基金：The Natural Science Foundation of Hubei Province2008CDZ047

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

页数：共11页

页码：736-746