CAJ | 학술논문

Mehrotra型预估-校正算法是众多基于内点算法的优化软件包的核心算法.最近,Salahi等人对线性规划提出一种新的Mehrotra型预估-校正算法.该算法不仅有多项式复杂性还具有良好的实际计算效果.本文将其算法推广至凸二次规划,这种算法在预估步最大可行步长高于某一阈值时将其削减,若首次削减仍没得到合适的校正步长,则将预估步长进行再削减,从而保证校正步步长有合适下界.算法在最坏情况下的迭代复杂性为O(n3/2 logn/ε).最后,Matlab仿真实验验证了算法的可行性.
Mehrotra형예고-교정산법시음다기우내점산법적우화연건포적핵심산법.최근,Salahi등인대선성규화제출일충신적Mehrotra형예고-교정산법.해산법불부유다항식복잡성환구유량호적실제계산효과.본문장기산법추엄지철이차규화,저충산법재예고보최대가행보장고우모일역치시장기삭감,약수차삭감잉몰득도합괄적교정보장,칙장예고보장진행재삭감,종이보증교정보보장유합괄하계.산법재최배정황하적질대복잡성위O(n3/2 logn/ε).최후,Matlab방진실험험증료산법적가행성.
Mehrotra-type predictor-corrector algorithms are the core of most interior point methods.Salahi et alrecently proposed a new Mehrotra-type predictor-corrector algorithm for linear optimization,which is a polynomial time algorithm,their algorithm maintains its efficiency in practice.This algorithm is extended in this paper to convex quadratic optimization problems.The new algorithm cuts the maximum step size in the predictor step when it is above a certain threshold.If this cut doesn't provide a desirable step size,we cut it again and deduce a lower bound for the step size in the corrector step.It is shown that the iteration complexity of the algorithm is O(n3/2 log(((x0)Ts0)/ε)),where(x0,s0)is the initial point and ε is the tolerance.Furthermore,the numerical example indicates that our algorithm is efficient.