APX-Hardness of Computing Lipschitz Constants for Multi-Parametric Quadratic Programs
2026-06-02 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study how hard it is to compute the Lipschitz constant, a measure of sensitivity, for solutions to a certain type of optimization problem called a multi-parametric quadratic program. They prove that this computation is very difficult in general (NP-hard and APX-hard), meaning it cannot be done quickly with existing algorithms. However, they also show that if the number of constraints or decision variables is fixed, the problem becomes easier and can be solved in polynomial time. Their findings clarify that the main difficulty comes from the number of constraints and variables, not the dimension of the parameters. They support their theoretical results with numerical experiments.
Lipschitz constantmulti-parametric quadratic programNP-hardAPX-hardoptimization-based controlcomplexity theorypolynomial-time solvabledecision variablesconstraintsparameter dimension
Authors
Xingchen Li, Kunpeng Liu, Keyou You
Abstract
Computing the Lipschitz constant of the solution map of a multi-parametric quadratic program is important for the analysis of optimization-based control. This problem is governed by three factors: the parameter dimension, the number of decision variables, and the number of constraints. While empirical evidence has long suggested exponential complexity, a rigorous complexity-theoretic proof has been lacking. In this paper, we fill this gap by proving that this problem is not only NP-hard but also APX-hard. Furthermore, we reveal that: (a) the problem becomes polynomial-time solvable when the number of constraints or decision variables is fixed; and (b) both NP-hardness and APX-hardness persist even in the scalar parameter case. These results confirm that the complexity stems from the number of constraints and variables, rather than the parameter dimension. Numerical experiments further validate these theoretical findings.