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

MaRDI QIDQ3622256zbMATH OpenFDO

Authors Sebastiano Columbano, Komei Fukuda, Colin N. Jones

Publication date 28 April 2009

Full work available at URL https://arxiv.org/abs/0807.2318

Mathematics Subject Classification ID

Sensitivity, stability, parametric optimization (90C31) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Abstract: 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.

Recommendations

• A two-phase algorithm for the multiparametric linear complementarity problem
• scientific article; zbMATH DE number 2150958
• A procedure for the one-parametric linear complementarity problem
• The linear complementarity problem with a parametric input
• scientific article; zbMATH DE number 1560356

Cited in

(7)

• An algorithm for global solution to bi-parametric linear complementarity constrained linear programs
• A two-phase algorithm for the multiparametric linear complementarity problem
• A new algorithm for solving convex parametric quadratic programs based on graphical derivatives of solution mappings
• Global resolution of the support vector machine regression parameters selection problem with LPCC
• Online constraint removal: accelerating MPC with a Lyapunov function
• Enumeration-based approach to solving parametric linear complementarity problems
• Multiobjective model predictive control

This page was built for publication: An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3622256)