水平线性互补问题的广义中心路径跟踪算法(英文)

General Central Path Following Algorithm for Horizontal Linear Complementarity Problem

对水平线性互补问题提出了一种广义中心路径跟踪算法.任意的原始-对偶可行内点均可作为算法的初始点.每步迭代选择"仿射步"与"中心步"的凸组合为新的迭代方向,采用使对偶间隙尽可能减小的最大步长.算法的迭代复杂性为O(nL).

In this paper, a general central path following algorithm for monotone horizontal linear complementarity problem is presented. Any primal-dual feasible interior point can be taken as initial point of the algorithm. At each iteration, we choose a new direction with the convex combination of the affine-scaling step and centering step, and use a pure Newton step with the largest possible reduction in complementarity measure （duality gap）. The algorithm maintains the O（√nL ） iteration comolexitv.