A polynomial time interior-point path-following algorithm for the linear complementarity problem based on Chen–Harker–Kanzow smoothing techniques

A polynomial complexity bound is established for an interior-point path-following algorithm for the monotone linear complementarity problem that is based on the Chen–Harker–Kanzow smoothing techniques. The fundamental difference with the Chen–Harker and Kanzow algorithms is the introduction of a rescaled Newton direction. The rescaling requires the iterates to remain in the interior of the positive orthant. To compensate for this restriction, the iterates are not required to remain feasible with respect to the affine constraints. If the method is initiated at an interior point that is also feasible with respect to the affine constraints, then the complexity bound is O(√(n)L); otherwise, the complexity bound is O(nL). The relations between our search direction and the one used in the standard interior-point algorithm are also discussed.