A two-phase algorithm for the multiparametric linear complementarity problem

•A new solution method is given for multiparametric linear complementarity problems.•The method provides an initial feasible solution or determines that none exists.•The method has a better worstcase complexity than previously proposed methods.

A new two-phase method for solving the multi-parametric linear complementarity problem (mpLCP) with sufficient matrices is presented. In the first phase an initial feasible solution to mpLCP which satisfies certain criteria is determined. In the second phase the set of feasible parameters is partitioned into polyhedral regions such that the solution of the mpLCP, as a function of the parameters, is invariant over each region. The worst-case complexity of the presented algorithms matches that of current methods for nondegenerate problems and is lower than that of current methods for degenerate problems.