单调线性互补问题的Mehrotra型预估-校正算法的迭代复杂性

Mehrotra型预估-校正算法是很多内点算法软件包的算法基础,但它的多项式迭代复杂性直到2007年才被Salahi等人证明.通过选择一个固定的预估步长及与Salahi文中不同的校正方向,本文把Salahi等人的算法拓展到单调线性互补问题,使得新算法的迭代复杂性为O(n log((x0)T s0/ε)),同时,初步的数值实验证明了新算法是有效的.

Complexity of Mehrotra's Predictor-corrector Algorithm for Monotone Linear Complementarity Problems

Methrotra-type predictor-corrector algorithms are the backbone of most interior point methods software packages,the polynomial iteration complexity was first proved by Salahi et al. in 2007. In this paper,their algorithm is extended to monotone linear complementarity problems (MLCPs). The new algorithm is different from theirs in the way of choosing corrector direction and using a default predictor step size. It is shown that the iteratiomcomplexity bound of our algorithm is O(n log ((x0)T s0/ε)) ,which is similar to that of the corresponding algorithm for linear optimization. The numerical result indicates that new algorithm is efficient.