P_*(κ)线性互补问题的预估-校正内点算法

A Predictor-Corrector Interior-Point Algorithm for P_*(κ)-Linear Complementarity Problems

通过修正大邻域跟踪算法的搜索方向,提出一种新的求解P*(κ)线性互补问题(LCP)的不可行预估-校正内点算法,并对算法进行了收敛性分析,证明了该算法具有目前最好的理论复杂度O((1+κ)5/2nL).数值结果验证了算法的有效性.

Based on modifying the search direction of neighborhood-following interior-point algorithm for linear programming, a new infeasible predictor-corrector interior-point algorithm for P＊（κ）-linear complementarity problem （LCP） was presented. The facts that P＊（κ）-LCP is nonmonotone and the corresponding search directions is non-orthogonal make the convergence analysis of the presented algorithm more complex. We have obtained the best known iteration complexity bound of the proposed algorithm so far, i.e. , O（（1＋κ）5/2nL）, where κ is the handicap of the problem. Numerical results show that the algorithm is feasible.