⚡ electrical engineering

Over-Approximating Minimizer Sets of Constrained Convex Programs with Parametric Uncertainty via Reachability Analysis

This paper proposes a method to compute certified, low-conservative outer approximations of the minimizer sets for strongly convex programs with parametric uncertainty by interpreting projected gradient descent iterates as an uncertain dynamical system and analyzing their forward reachable sets using system-level synthesis.

Original authors: Brendan Gould, Chih-Yuan Chiu, Antoine P. Leeman, Kyriakos G. Vamvoudakis, Samuel Coogan, Glen Chou

Published 2026-05-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Brendan Gould, Chih-Yuan Chiu, Antoine P. Leeman, Kyriakos G. Vamvoudakis, Samuel Coogan, Glen Chou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the absolute lowest point in a vast, foggy valley. This valley represents a mathematical problem where you want to minimize a cost (like fuel usage or time). However, there is a catch: the shape of the valley isn't perfectly known. It changes slightly depending on hidden factors, like the weight of a passenger or the friction of the road. These hidden factors are the "uncertain parameters."

Because the valley's shape is uncertain, the "lowest point" isn't a single spot; it's a cloud of possible spots. Your goal is to draw a fence around this entire cloud to guarantee that the true lowest point is always inside, no matter how the hidden factors shift.

Here is how the paper solves this problem, using simple analogies:

1. The Problem: A Moving Target in the Fog

In many real-world situations (like a self-driving car predicting where a pedestrian will go), we don't know the exact rules of the game. We know the rules are somewhere within a certain range.

The Challenge: If you try to guess the answer using standard math, you often end up drawing a fence that is way too big (too conservative) or you can't draw one at all because the math gets too hard.
The Goal: Draw the smallest, tightest fence possible that guarantees it catches every possible "best answer."

2. The Strategy: The "Hill-Climbing" Robot

The authors use a method called Projected Gradient Descent (PGD). Imagine a robot trying to find the bottom of the valley.

The robot takes a step downhill.
If it hits a wall (a constraint), it slides along the wall instead of going through it.
It keeps taking steps until it stops.

The paper's big idea is to treat this robot's journey not just as a math calculation, but as a dynamical system—like a car driving on a road.

The Twist: The robot's starting position is fixed, but the "map" (the cost function) is slightly different for every possible scenario.
The Insight: If you run the robot for a few steps, it gets closer and closer to the true bottom. The paper proves that if you track all the possible paths the robot could take (due to the uncertainty), these paths form a "tube" that shrinks exponentially as the robot walks.

3. The Tool: System-Level Synthesis (SLS) as a "Traffic Controller"

To calculate the exact size of this "tube" without getting lost in complex math, the authors use a technique called System-Level Synthesis (SLS).

The Analogy: Think of SLS as a super-smart traffic controller. Instead of trying to predict every single car's movement individually (which is impossible), the controller designs a set of rules for how the cars should react to each other.
How it works here: The controller designs a "step-size" plan for the robot. It asks: "If the robot takes steps of size X, Y, and Z, how far could it possibly drift from the center path?"
By optimizing these steps, the controller creates a very tight, accurate fence around the robot's possible locations.

4. Handling the "Bumpy Roads" (Non-Differentiable Dynamics)

Sometimes, the valley has sharp cliffs or jagged edges (mathematically, the function isn't smooth). The robot might stumble or get stuck.

The Fix: The authors use a "smoothing" technique. Imagine taking a photo of a jagged rock and applying a blur filter. The rock looks round and smooth, making it easy to calculate the path.
They calculate the path on this "blurred" version and then mathematically account for the difference between the blurry rock and the real jagged rock. This ensures their fence is still safe, even if the terrain is rough.

5. The Result: A Tighter, Safer Fence

The paper tested this method on two types of problems:

Simple Curves: A basic valley where the math is easy to check.
Complex Systems: A high-dimensional problem (like controlling a complex machine with 64 moving parts) where the math is usually impossible to solve exactly.

The Outcome:

Their method produced a fence that was much tighter than previous methods.
It was able to handle high-dimensional problems (64 variables) that other methods couldn't touch.
It provided a certified guarantee: You can be 100% sure the true answer is inside the fence, and the fence isn't unnecessarily huge.

Summary

The paper presents a new way to find the "safe zone" for the best possible answers in uncertain situations. Instead of guessing or using overly cautious estimates, they treat the search for the answer as a robot walking through a foggy landscape. By using advanced control theory (SLS) to plan the robot's steps, they can draw a precise, mathematically guaranteed fence around all possible "best answers," ensuring safety and efficiency in decision-making.

1. Problem Statement

The paper addresses the challenge of characterizing the set of optimal solutions (minimizers) for a strongly convex optimization problem where the cost function depends on uncertain, bounded parameters.

Context: In robotics and control (e.g., autonomous driving, robotic manipulation), decision-making often relies on optimization. However, the data driving these decisions (e.g., intent of other agents, mass matrices) is uncertain.
Goal: Instead of finding a single "robust" solution that minimizes the worst-case cost (standard robust optimization), the authors aim to compute a certified outer approximation (over-approximation) of the entire set of minimizers ( $S^\star_\xi$ ) across all possible realizations of the uncertain parameter $\theta \in \Theta$ .
Challenge: Existing methods, such as sensitivity analysis or closed-form solutions, are often either intractable for high-dimensional problems or highly conservative (producing overly large bounds), limiting their utility for downstream safe planning.

2. Methodology

The core innovation is reframing the optimization problem as a dynamical system reachability problem.

A. Projected Gradient Descent (PGD) as a Dynamical System

The authors treat the Projected Gradient Descent (PGD) algorithm not just as a solver, but as a discrete-time dynamical system:
$\xi_{k+1} = \text{proj}_{S_C}(\xi_k - \alpha_k \nabla_\xi J(\xi_k, \theta))$

Key Insight: For a fixed parameter $\theta$ , PGD converges exponentially to the unique minimizer $\xi^\star(\theta)$ .
Uncertainty Modeling: The parameter $\theta$ is treated as a constant but unknown initial state. The set of all possible PGD trajectories starting from a fixed initial point $\xi_0$ but varying over $\theta \in \Theta$ forms a forward reachable set.
Convergence Guarantee: The authors prove that the distance between the PGD iterates at step $k$ and the true minimizer set decays exponentially with rate $\gamma^k$ . Therefore, the reachable set at step $k$ , inflated by this exponential error bound, provides a certified outer approximation of the minimizer set.

B. System-Level Synthesis (SLS) for Reachability

To compute these reachable sets efficiently (especially for high-dimensional systems), the authors employ System-Level Synthesis (SLS):

Nominal Trajectory & Error Dynamics: They define a nominal trajectory $(\hat{\xi}, \hat{\theta})$ and analyze the error dynamics ( $\Delta \xi, \Delta \theta$ ) between the true system and the nominal one.
Linear Time-Varying (LTV) Approximation: The nonlinear PGD dynamics are linearized around the nominal trajectory. The error propagation is modeled as an LTV system driven by disturbances (linearization errors).
Feedback Design: Instead of fixed step sizes, they design a causal affine output feedback law (using SLS) to optimize the step-size sequence $\alpha_k$ . This feedback minimizes the propagation of uncertainty, resulting in tighter reachable set bounds compared to fixed-step approaches.
Optimization: They formulate a Nonlinear Program (NLP) to find the system response matrices that minimize the final reachable set size while ensuring robust satisfaction of step-size constraints.

C. Handling Non-Differentiability

For constrained problems where the projection operator $\text{proj}_{S_C}$ is non-differentiable (e.g., non-affine constraint sets):

Smoothing: They apply a sampling-based smoothing technique. The non-smooth PGD update is approximated by a smoothed version $\tilde{f}$ via convolution with a uniform distribution.
Error Bounds: The method accounts for both the linearization error of the smoothed dynamics and the approximation error between the true and smoothed dynamics, ensuring the final bounds remain valid and certified.

3. Key Contributions

Theoretical Recasting: Proved that over-approximating the minimizer set is equivalent to computing the forward reachable sets of PGD dynamics with an unknown parameter, leveraging the exponential convergence of PGD to provide explicit error bounds.
SLS-Based Reachability: Developed a tractable framework using SLS to compute forward reachable sets for high-dimensional, smooth PGD dynamics with low conservativeness.
Non-Smooth Extension: Extended the framework to non-differentiable PGD dynamics (common in constrained optimization) via a smoothing technique, deriving rigorous bounds for the approximation error.
Optimization of Step Sizes: Demonstrated that optimizing the step-size sequence via SLS yields significantly tighter bounds than fixed-step baselines or traditional sensitivity analysis.

4. Results and Simulations

The authors validated their method on three scenarios:

Scalar Quadratic Optimization: A simple unconstrained problem where the true minimizer set is known analytically. The SLS-based bounds were tight and correctly contained the true set.
High-Dimensional LQR with Intent Uncertainty: A 64-dimensional Linear Quadratic Regulator problem.
- Comparison: Compared against classical Implicit Function Theorem (sensitivity analysis) methods.
- Performance: The SLS method produced bounds with a maximum width of 0.2, whereas the sensitivity analysis baseline produced a bound width of ~35. This highlights a massive reduction in conservativeness.
Constrained Quadratic Optimization: A problem with non-affine constraints (non-smooth PGD).
- The smoothing technique successfully handled the non-differentiability. While slightly more conservative than the smooth case due to the smoothing error, the method still provided valid, certified over-approximations.

5. Significance

Safety-Critical Planning: By providing tight, certified bounds on the set of possible optimal decisions under uncertainty, this method enables safer downstream planning in robotics and autonomous systems. It avoids the "pessimism" of worst-case robust optimization while avoiding the "risk" of ignoring uncertainty.
Scalability: The use of SLS allows the method to scale tractably to high-dimensional decision spaces (demonstrated up to 64 dimensions), a regime where traditional set-based reachability or sensitivity analysis often fails or becomes too conservative.
Novel Intersection: The paper successfully bridges convex optimization theory (convergence of PGD) with control theory (reachability analysis and SLS), offering a new paradigm for analyzing parametric optimization problems.

In summary, this work offers a mathematically rigorous, computationally efficient, and low-conservatism approach to understanding how uncertainty in problem parameters propagates to the set of optimal solutions, a critical capability for robust autonomous decision-making.