A primal feasible active set method is presented for finding the unique solution of a Linear Complementarity Problem (LCP) with a P-matrix, which extends the globally convergent active set method for strictly convex quadratic problems with simple bounds proposed by [P. Hungerlaender and F. Rendl. 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,u) is computed that satisfies stationarity and the complementary condition. If x is not feasible, the variables connected to the infeasibilities are added to the active set and a new primal-dual pair (x,u) is computed. This process is iterated until a primal feasible solution is generated. Then a new active set is determined based on the feasibility information of the dual variable u. 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 experience indicates that these approaches are very efficient for solving large-scale LCPs and BLCPs in practice.
Citation
Technical report, Alpen-Adria Universität Klagenfurt, Mathematics, Optimization Group, TR-AAUK-M-O-16-09-21, 2016.