A recursive complementarity primal feasible semi-smooth Newton method for linear complementarity problems
P. Hungerländer, J. Júdice, F. Rendl and C. Truden
Abstract
A
recursive complementarity primal feasible semi-smooth Newton (SN)
method is presented for finding the unique solution of a Linear
Complementarity Problem (LCP) with a P-matrix, which extends the
finitely convergent recursive SN method for strictly convex quadratic
problems with simple bounds proposed by [P. Hungerländer and F. Rend. A
Feasible Active Set Method for Strictly Convex Problems with Simple
Bounds. SIAM Journal on Optimization, 25(3):1633-1659,2015].
Based on a guess of the active set, a primal-dual pair (x,α) is
computed that satisfies the complementarity condition. If x is not
feasible, a finitely convergent procedure is used to recover primal
feasibility.
Given a primal feasible solution x, a new active set is determined
based on the feasibility information of the dual variable α and the
process is repeated. We prove that the algorithm stops after a finite
number of steps with the unique solution of the LCP. An extension of
the algorithm with similar convergence properties is also introduced
for finding the unique solution of the Bound Linear Complementarity
Problem (BLCP) with a P-matrix.
Computational experiments indicate that these approaches are very efficient for solving large-scale LCPs and BLCPs in practice.