Complexity Analysis of a Full-Newton Step Interior-Point Method for Monotone Weighted Linear Complementarity Problems

In this paper, we present a full-Newton step interior-point method for solving monotone Weighted Linear Complementarity Problem. We use the technique of algebraic equivalent transformation (AET) of the nonlinear equation of the system which defines the central path. The AET is based on the square root function which plays an important role in computing the new search directions. The algorithm uses only full-Newton steps at each iteration, and hence, line searches are no longer needed. We prove that the algorithm has a quadratic rate of convergence to the target point on the central path. The obtained iteration bound coincides with the best known iteration bound for these types of problems.

Automated summary

This paper presents a full-Newton step interior-point method for solving monotone Weighted Linear Complementarity Problem, utilizing the technique of algebraic equivalent transformation (AET) and achieving a quadratic rate of convergence to the target point on the central path.