An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices

This paper considers the multi-parametric linear complementarity problem (pLCP) with sufficient matrices. The main result is an algorithm to find a polyhedral decomposition of the set of feasible parameters and to construct a piecewise affine function that maps each feasible parameter to a solution of the associated LCP in such a way that the function is affine over each cell of the decomposition. The algorithm is output-sensive in the sense that its time complexity is polynomial in the size of the input and linear in the size of the output, when the problem is non-degenerate. We give a lexicographic perturbation technique to resolve degeneracy as well. Unlike for the non-parametric case, the resolution turns out to be nontrivial, and in particular, it involves linear programming (LP) duality and multi-objective LP.

Published in:
AMS CRM Proceedings and Lecture Notes, 48, 73-102

 Record created 2011-03-14, last modified 2019-12-05

Publisher's version:
Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)