$P_*(\kappa)$线性互补问题的Mehrotra型预估-校正算法

A Mehrotra-Type Predictor-Corrector Algorithm for $P_*(\kappa)$ Linear Complementarity Problems

中文关键词:  $P_*(\kappa)$线性互补问题  Mehrotra型预估-校正算法  多项式复杂性  内点算法.

英文关键词:$P_*(\kappa)$ linear complementarity problems  Mehrotra-type predictor-corrector algorithm  polynomial iteration complexity  interior point method.

中文摘要:

      作为最有效的内点算法之一, 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.