凸二次规划的一种宽邻域预估-校正算法

摘要

Zhao对线性规划提出了一种基于邻近度量函数最小值的宽邻域预估-校正算法,并证明了算法的多项式复杂性。基于他的思路,将此方法拓展到凸二次规划,设计了一种新的基于邻近度量函数最小值的宽邻域预估-校正算法。由于新算法的迭代方向向量Δx,Δs不再满足正交性,因此算法的收敛性分析不同于线性规划的情形,同时也证明了新算法具有已知的最好迭代复杂性O (n^(1/2)ln〔((x0)Ts0/ε)〕,初步数值实验验证了算法的有效性。