Mathematics – Optimization and Control
Scientific paper
2008-07-15
Mathematics
Optimization and Control
Scientific paper
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.
Columbano Sebastiano
Fukuda Komei
Jones Colin
No associations
LandOfFree
An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-595920