摘要
针对二阶Mehrotra型预估-校正算法的一种变型算法,本文介绍一种新的自适应障碍参数更新法。利用该更新方法提出了相应的算法。新算法与之前的二阶Mehrotra型预估-校正算法相比,不用根据预估步和校正步的步长来确定参数的更新,而是在每步迭代中都采用自适应更新。最后证明了该算法在没有引进任何"保障措施"的情况下也具有相同的多项式时间复杂度。
This paper introduce a new adaptive updating technique of the barrier parameter in a variant of second order Mehrotra-type predictor-corrector algorithms.A new algorithm is presented with this updating method.Compared with previous second order Mehrotra-type predictor-corrector algorithms,new algorithm is not necessary to update barrier parameter according to the step size in predictor and corrector,it make adaptive updating in each iteration.Finally,this paper prove the polynomial iteration complexity of Mehrotra’s algorithm without employing any safeguards.
出处
《长春理工大学学报（自然科学版）》
2012年第3期93-96,101,共5页
Journal of Changchun University of Science and Technology(Natural Science Edition)
关键词
线性规划
Mehrotra型算法
二阶预估-校正
新障碍参数更新
多项式复杂性
linear programming
Mehrotra-type algorithms
second-order predictor-corrector
new barrier parameterupdating, polynomial time complexity
