Subspace accelerated matrix splitting algorithms for asymmetric and symmetric linear complementarity problems (Q2866190)

The paper deals with two-phase matrix splitting methods for solving asymmetric and symmetric Linear Complementarity Problems (LCP) that consist of an active set prediction phase and an acceleration phase. Two algorithms are presented, the first one is designed to solve the asymmetric LCP and the second one to solve the symmetric Bound-constrained Quadratic Program (BQP) due to the equivalence between the symmetric LCP and the strictly convex BQP. The work is motivated by the paper [\textit{L. Feng} et al., Optim. Methods Softw. 26, No. 4--5, 813--825 (2011; Zbl 1229.90230)] where an efficient method for solving the LCP is introduced, however, with no convergence proof.NEWLINENEWLINETo obtain a provably convergent method, a new modified algorithm with similar efficiency is proposed. The authors formulate a two-phase matrix splitting algorithm by combining a contraction argument with a merit function based directly on the structure of LCP and include conditions that determine when the subspace step may be accepted. Concerning BQP, the authors present a two-phase method with convergence guarantees for both convex and nonconvex problems that utilizes sophisticated matrix splittings and projected searches which leads to improved optimal active set identification.