A Feasible Active Set Method for Asymmetric Complementarity Problems

A primal feasible active set method is presented which extends the globally convergent semismooth Newton method for strictly convex quadratic problems with simple bounds proposed by [P. Hungerländer and F. Rendl. A feasible active set method for strictly convex problems with simple bounds. SIAM Journal on Optimization, 25(3):1633–1659, 2015] to linear complementarity problems with P-matrices. 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 an optimal solution if the linear complementarity problem has a unique solution. Computational experience indicates that this approach performs very well in practice.