Over-approximating minimizer sets of constrained convex programs with parametric uncertainty via reachability analysis
B. Gould, C.-Y. Chiu, A. Leeman, K. Vamvoudakis, S. Coogan, G. Chou
IEEE Conference on Decision and Control, 2026, to appear
Abstract
We study the solution set of a strongly convex optimization problem whose cost depends on uncertain, bounded parameters. We compute a certified outer approximation of the corresponding set of optimizers, using convergence properties of the projected gradient descent (PGD) algorithm. By treating the cost parameter as constant but unknown, we interpret PGD as an uncertain dynamical system and analyze its forward reachable sets. Since PGD converges exponentially to the unique optimizer for each fixed parameter, these reachable sets provide outer approximations of the optimizer set, with an exponentially decaying error bound. We apply system-level synthesis (SLS) on the PGD dynamics to optimize the step-size sequence and obtain reachable-set over-approximations. Our method outperforms existing baselines in over-approximating, with low conservativeness, the minimizer sets of convex programs with uncertain costs and high-dimensional decision variables.