河北师范大学学报(自然科学版)
河北師範大學學報(自然科學版)
하북사범대학학보(자연과학판)
JOURNAL OF HEBEI NORMAL UNIVERSITY(NATURAL SCIENCE)
2010年
6期
636-643
,共8页
Mehrotra型算法%预估校正算法%多项式复杂性%削减策略%凸二次规划
Mehrotra型算法%預估校正算法%多項式複雜性%削減策略%凸二次規劃
Mehrotra형산법%예고교정산법%다항식복잡성%삭감책략%철이차규화
2008年,Salahi等对线性规划提出一种新的Mehrotra型预估校正算法.基于削减(cut)策略,该算法保证校正步长有下界,从而具有多项式复杂性.基于这种思路,将此方法推广到凸二次规划.由于新算法的迭代方向不再正交,因此算法的复杂性分析与线性规划时不同.通过一些新的技术引理,证明了算法在最坏情况下,至多经过O(n52lognε)次迭代终止.最后,利用数值实验验证了算法的可行性与有效性.
2008年,Salahi等對線性規劃提齣一種新的Mehrotra型預估校正算法.基于削減(cut)策略,該算法保證校正步長有下界,從而具有多項式複雜性.基于這種思路,將此方法推廣到凸二次規劃.由于新算法的迭代方嚮不再正交,因此算法的複雜性分析與線性規劃時不同.通過一些新的技術引理,證明瞭算法在最壞情況下,至多經過O(n52lognε)次迭代終止.最後,利用數值實驗驗證瞭算法的可行性與有效性.
2008년,Salahi등대선성규화제출일충신적Mehrotra형예고교정산법.기우삭감(cut)책략,해산법보증교정보장유하계,종이구유다항식복잡성.기우저충사로,장차방법추엄도철이차규화.유우신산법적질대방향불재정교,인차산법적복잡성분석여선성규화시불동.통과일사신적기술인리,증명료산법재최배정황하,지다경과O(n52lognε)차질대종지.최후,이용수치실험험증료산법적가행성여유효성.