求解$P_*(\kappa)$阵线性互补问题的宽邻域Dikin型高阶内点算法

A High-Order Dikin-Type Algorithm for $P_*(\kappa)$-LCPs in a Wide Neighborhood of the Central Path

中文关键词:  互补问题  高阶仿射尺度  多项式复杂性  内点算法  $P_*(\kappa)$矩阵.

英文关键词:complementarity problem  high-order affine scaling  polynomial-time complexity  interior-point algorithm  $P_*(\kappa)$-matrix.

中文摘要:

      基于求解线性规划的Dikin型原始-对偶仿射尺度算法的思想,本文对$P_*(\kappa)$线性互补问题提出了一种宽邻域$(N_\infty^-(\beta))$Dikin型高阶内点算法,并证明了算法的多项式复杂性.通过数值实验,验证了该方法的有效性.

英文摘要:

      Based on the idea of Dikin-type primal-dual affine scaling method for linear programming, we describe a high-order Dikin-type algorithm for $P_*(\kappa)$-matrix linear complementarity problem in a wide neighborhood of the central path, and its polynomial-time complexity bound is given. Finally, two numerical experiments are provided to show the effectiveness of the proposed algorithms.