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

一种求解P * （κ）阵线性互补问题的宽邻域内点算法 A Wide-Neighborhood Interior-Point Algorithm for the P * （κ）-Matrix Linear Complementarity Problem 张明望 ZHANG Mingwang 1 2 first-author 吕艳丽 L Yanli 1 2 三峡大学理学院 三峡大学理学院 College of Science, China Three Gorges University College of Science, China Three Gorges University 三峡大学理学院,湖北,宜昌,443002 三峡大学理学院,湖北,宜昌,443002 基于线性规划宽邻域内点算法的基本思想,对P*（κ）阵线性互补问题提出了一种基于宽邻域N∞-（β）的势函数约减算法.该算法的每一次迭代都通过求解一个线性方程组得到迭代方向,并利用势函数来选取步长,使得迭代前后势函数按一固定量减少,从而使对偶间隙有固定的减少.证明了算法的迭代复杂性为O（（κ+1）nt）. This paper describes a new wide-neighborhood potential reduction interior-point algorithm for P*（κ）-matrix linear complementarity problem, using the neighborhood N-∞（β） which is much wider. The algorithm is based on the idea of wide-neighborhood algorithm for linear programming. At each iteration, search direction can be computed as a solution of a linear system, and uses a potential function to choose a step size, so this algorithm decreases the potential function by a fixed amount, under the condition that the duality gap decreases at the same. Finally, we prove that its iteration complexity is O（（κ+1）nt） under general conditions. P*（κ）阵线性互补问题 内点算法 宽邻域 势函数 多项式复杂性 P*（κ）-matrix linear complementarity problem interior-point algorithm wide-neighborhood potential reduction polynomial complexity O221 湖北省教育厅自然科学重点科研基金（D200613009）资助项目 2008-01-01 2021-04-01 1