一种求解P_*(κ)阵线性互补问题的宽邻域内点算法

摘要

基于线性规划宽邻域内点算法的基本思想,对P*(κ)阵线性互补问题提出了一种基于宽邻域N∞-(β)的势函数约减算法.该算法的每一次迭代都通过求解一个线性方程组得到迭代方向,并利用势函数来选取步长,使得迭代前后势函数按一固定量减少,从而使对偶间隙有固定的减少.证明了算法的迭代复杂性为O((κ+1)nt).