{"id":"arxiv/2606.03862","url":"https://arxiv.org/abs/2606.03862","tags":["eess.SY","cs.CC","math.OC"],"score":0,"title":"APX-Hardness of Computing Lipschitz Constants for Multi-Parametric Quadratic Programs","domain":"eess.SY","source":"arxiv","authors":["Xingchen Li","Kunpeng Liu","Keyou You"],"reviews":0,"subject":"eess.SY","summary":"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…","category":"research","comments":0,"disputed":false,"division":"eess","mentions":0,"discussed":0,"published":"2026-06-02","reactions":{}}