$P_*(\kappa)$线性互补问题的Mehrotra型预估-校正算法
A Mehrotra-Type Predictor-Corrector Algorithm for $P_*(\kappa)$ Linear Complementarity Problems

DOI：10.3770/j.issn:2095-2651.2012.03.004

 作者 单位 李卫滑 三峡大学理学院, 湖北 宜昌 443002 张明望 三峡大学理学院, 湖北 宜昌 443002 周意元 三峡大学理学院, 湖北 宜昌 443002

作为最有效的内点算法之一, Mehrotra型预估-校正算法作已成为众多优化软件包的核心算法. 2008年, Salahi等人对线性规划提出一种基于削减(cut)策略的Mehrotra型预估-校正算法.该算法在具有多项式复杂性的同时还保持了实际有效性.通过选择与Salahi文中不同的校正方向,本文将该算法推广到$P_*(\kappa)$线性互补问题,并证明了在最坏情况下新算法的迭代复杂性界为$O((1+4\kappa)(17+19\kappa)\sqrt{1+2\kappa}n^\frac{3}{2}\log\frac{(x^0)^\T s^0}{\varepsilon})$.数值实验验证了算法的可行性.

Mehrotra-type predictor-corrector algorithm, as one of most efficient interior point methods, has become the backbones of most optimization packages. Salahi et al. proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice. We extend their algorithm to $P_*(\kappa)$ linear complementarity problems. The way of choosing corrector direction for our algorithm is different from theirs. The new algorithm has been proved to have an ${\mathcal O}((1+4\kappa)(17+19\kappa)\sqrt{1+2\kappa}n^\frac{3}{2}\log \frac{(x^0)^\T s^0}{\varepsilon})$ worst case iteration complexity bound. An numerical experiment verifies the feasibility of the new algorithm.