The steepest-descent barrier-projection method for linear complementarity problems

The linear complementarity problem with a positive definite matrix is examined. A numerical method for solving this problem is proposed that is an extension of the barrier-projection method originally used for linear and nonlinear programs. The initial approximation and all the subsequent approximations in the proposed method belong to the feasible set. The choice of the step size is based on the idea of the steepest descent. It is shown that the basic variant of the method has additional stationary points apart from the solution of the problem. If a certain nondegeneracy condition is fulfilled, then these stationary points coincide with the vertices of the feasible set. The local convergence of the basic variant is proved, and it is shown that the number of iteration steps does not exceed the dimension of the problem. A modified variant of the method is described in which no additional stationary points appear, and its finite nonlocal convergence is proved.