Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints
summary
The gist
In this paper, we present an equivalent convex optimization formulation for discrete-time stochastic linear systems subject to linear chance constraints…
In short
The paper presents a method to create an exact deterministic convex formulation for discrete-time stochastic linear systems with linear chance constraints. It achieves this by lifting the state vector to include moment information, allowing exact representation of linear chance constraints as second-order cone constraints and providing less conservative approximations for quadratic chance constraints.
Key concepts
- Lifted Representation
- This technique involves redefining the state and control variables at each time step ($x_k$ and $u_k$) by adding auxiliary terms ($ ilde{oldsymbol{ u}}_k$ and $ ilde{oldsymbol{ u}}_k$). This new representation explicitly encodes the first moments of the system's uncertainty, which is crucial for accurately modeling chance constraints.
- Second-Order Cone (SOC) Constraints
- Linear chance constraints are exactly translated into SOC constraints. SOC constraints are a specific type of convex constraint that defines a region bounded by a cone in higher dimensions. Using this transformation allows the authors to represent linear uncertainty conditions precisely within the convex optimization framework.
- Quadratic Chance Constraint Approximations
- Quadratic chance constraints, which are common in control problems, are approximated using two methods: linear-matrix constraints and quadratic constraints. The paper proves these approximations are provably less conservative than previous methods, meaning they provide a tighter feasible region for the optimization.
- Deterministic Convex Formulation
- The ultimate goal is to transform the original stochastic optimal control problem into a deterministic convex problem. This means that instead of optimizing over uncertain future states, the new formulation optimizes over decision variables ($oldsymbol{ u}, oldsymbol{ ho}$) while ensuring all chance constraints are satisfied deterministically.
Terminology used across episodes
This episode discusses
- Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints · Paper Radio
The paper
Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints · Read on arXiv
Tanmay Dokania, Yashwanth Kumar Nakka
Daniel Guggenheim School of Aerospace Engineering at the Georgia Institute of Technology
In this paper, we present an equivalent convex optimization formulation for discrete-time stochastic linear systems subject to linear chance constraints, alongside a tight convex relaxation for quadratic chance constraints. By lifting the state vector to encode moment information explicitly, the formulation captures linear chance constraints on states and controls across multiple time steps exactly, without conservatism, yielding strict improvements in both feasibility and optimality. For quadratic chance constraints, we derive convex approximations that are provably less conservative than existing methods. We validate the framework on minimum-snap trajectory generation for a quadrotor, demonstrating that the proposed approach remains feasible at noise levels an order of magnitude beyond the operating range of prior formulations.
DOI: 10.1109/LCSYS.2026.3701076
Transcript
Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.
Rosa: I'm Rosa.
Dev: And I'm Dev, here with Taro.
Rosa: We're looking at the paper: "Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints".
Dev: Here's the gist of the paper. In this paper, we present an equivalent convex optimization formulation for discrete-time stochastic linear systems subject to linear chance constraints, alongside a tight convex relaxation for quadratic chance constraints<ref:2603.19454#pg2>.
Rosa: Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints is a novel method that lifts the state vector to explicitly encode moment information, enabling exact representation of linear chance constraints as second-order cone constraints and less conservative approximate representations of quadratic chance constraints as linear-matrix or quadratic constraints over the decision variables<ref:2603.19454#pg4>.
Dev: This approach leads to a deterministic convex formulation of the original stochastic optimal control problem.
Rosa: Stochastic System and Constraints The paper considers a linear stochastic time-varying system defined by the dynamics (1) and Assumption 1.
Title and authors: Rosa: So, we're looking at this paper, "Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints," and the authors are talking about lifting the state vector to explicitly encode moment information. That means they're trying to get an exact representation of linear chance constraints as second-order cone constraints.
Dev: Exactly. It sounds like they're taking a stochastic system and making it deterministic by encoding that moment information directly into the state representation, which is represented by these vectors mu and psi.
Taro: So, if we look at how they represent the state at step k, xk equals mu k plus psi ke (k), where psi ke (k) is the vectorized form of a matrix Psi k in R nx times n e(k). That’s a lot of information encoded there.
Rosa: Right. And for quadratic chance constraints, they are using some convex approximations—linear-matrix or quadratic constraints over the decision variables—and they claim those are provably less conservative than existing methods <ref:2603.19454#pg4>.
Dev: That's a big deal because it means we can use these approximations without worrying that the resulting solution is way too pessimistic compared to what a truly exact method would give us.
Taro: I wonder if that less conservative part really holds up when you look at real-world failure modes, like in those complex environments we test outside the lab.
Rosa: That’s what we’re going to check. The paper validates this framework on minimum-snap trajectory generation for a quadrotor in the Circle Arena, where they showed cost reductions of up to thirty-five percent over prior work seven.
Dev: Thirty-five percent is significant, especially when you look at the noise levels they used. They kept it feasible at sigma equals zero point eight five, while other methods like seven and eleven became infeasible beyond sigma equals zero point zero six.
Taro: Feasibility across that wide range of noise is important for real autonomy because things rarely operate in perfect conditions, Rosa. It shows the system can handle much more uncertainty than the baseline approaches we usually see in simulations.
Title and authors: Rosa: It does, and it maintains feasibility even when the noise standard deviation is an order of magnitude higher than what those prior methods could handle eleven <ref:2603.19454#pg1>. That suggests a much more robust formulation for real flight scenarios.
Dev: From a control perspective, they established Theorem one showing that Problem two restricted to dynamics one three and linear chance constraints sixteen and covariance constraint eighteen is an exact deterministic convex reformulation of Problem one.
Taro: So the equivalence holds for both cost equivalence and feasible set equivalence, which means we can trust that what the solver finds is actually what the original stochastic control problem would find.
Rosa: That's a strong claim. But they also have to be careful about those approximations for quadratic chance constraints; Proposition one says both the LMI and QC are conservative approximations of constraint three and neither dominates the other, with tightness depending on the spread of psi i psi top i <ref:2603.19454#pg1>.
Dev: So it's not a perfect match for quadratics, but it’s provably better than what we currently have for those specific constraints. That trade-off is something we need to keep in mind when deploying these solvers in real-time loops, because the tightness depends on that spread of psi i psi top i.
Taro: If that spread gets too wide, the approximation might not be tight enough to guarantee safety when the world misbehaves. That’s a key point for testing this framework outside of textbook scenarios.
Rosa: Exactly. And looking at those numerical simulations on the quadrotor, they also showed cost improvements up to forty-three percent in the Funnel Corridor under moderate noise, with feasibility at sigma equals zero point six, while both baselines failed beyond sigma equals zero point zero six seven and eleven.
Dev: So we see these gains not just in theory but across different environments, showing that this formulation handles the dynamics of a quadrotor quite well under various noise conditions. How does this change the constraints on our real-time solvers?
Title and authors: Taro: It suggests that for trajectory planning, we might be able to push the noise tolerance much higher before we run into immediate infeasibility problems with these types of convex reformulations.
Rosa: And it also means that if we can keep the formulation deterministic and convex over variables like mu, nu, psi, v, it simplifies the real-time control loop design a lot because you don't need those initial guesses for covariances or feedback matrices that other solvers require seven, eleven <ref:2603.19454#pg1>.
Dev: That’s a huge reduction in complexity for the implementation side. If we can skip needing an initial guess of those matrices, it makes the deployment much more practical for real-time applications.
Taro: I just wonder what happens when the system hits a truly extreme noise level beyond what they tested, say ten times higher than sigma equals zero point eight five? The paper doesn't really test that extreme boundary on this quadrotor example.
Rosa: That’s a fair question. The paper shows it works an order of magnitude beyond the operating range of prior formulations, which is promising, but we need more testing on those very high noise standards to truly characterize its limits.
Dev: So to wrap up the main points about this "Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints," the core idea is lifting the state vector to encode moment information explicitly for exact linear chance constraints, and providing provably less conservative approximations for quadratic ones.
Taro: It gives us a deterministic convex problem over mu, nu, psi, v by using that moment encoding.
Rosa: And it lets us validate this on trajectory generation for a quadrotor across challenging environments like the Circle Arena and Funnel Corridor with significant noise tolerance improvements.
Dev: This approach offers improved feasibility and optimality compared to existing solvers like seven and eleven, particularly regarding their robustness against high noise levels <ref:2603.19454#pg1>.
Taro: It means we can potentially design systems that operate safely in much more uncertain conditions than previously thought possible for these types of trajectory optimization problems.
The paper's summary: Rosa: So, we're looking at how they've taken these stochastic systems—the ones where things are random—and turned them into something deterministic using this new way of looking at the math, which is lifting the state vector to carry all that moment information.
Dev: Exactly. It means they’re encoding every piece of uncertainty right into the state representation, using vectors like mu and psi, so they can handle linear chance constraints exactly as second-order cone constraints.
Taro: That’s a big deal because it removes the conservatism you often have to accept when dealing with those linear constraints in the first place.
Rosa: And for those quadratic chance constraints, they're using these approximations—linear-matrix or quadratic ones—and they claim those are provably less conservative than what we currently have available.
Dev: So, the whole point is they’ve created a deterministic convex formulation over variables like mu, nu, psi, and v by explicitly encoding those moments in the state lift.
Taro: That formulation equivalence means that if you solve this new math problem on the lifted system dynamics and constraints, you get the exact same answer as solving the original stochastic control problem.
Rosa: The validation they did was on minimum-snap trajectory generation for a quadrotor in an arena setting, where they saw cost reductions of up to thirty-five percent over prior work.
Dev: Thirty-five percent is significant, especially when you look at the noise levels they used; it kept the system feasible at sigma equals zero point eight five, while previous methods failed past zero point zero six.
Taro: That wide range of noise tolerance is what really stands out; it shows the formulation handles uncertainty much better than existing solvers can manage.
Rosa: It also means you don't need those initial guesses for covariances or feedback matrices that other solvers require, which makes the deployment side way simpler and faster.
Dev: So, to put it plainly, they’ve given us a deterministic convex problem over mu, nu, psi, v that is equivalent to the original stochastic optimal control problem.
Taro: It’s about proving that you can capture those linear chance constraints exactly without having to guess or rely on overly conservative approximations for the quadratic ones.
Rosa: This approach offers improved feasibility and optimality compared to existing solvers like those we talked about, particularly regarding how well they handle high noise levels.
Dev: We still have to keep in mind that for the quadratic chance constraints, the tightness of those linear-matrix or quadratic approximations depends on the spread of psi i psi top i.
Taro: That’s a caveat; if that spread gets too wide, you lose some of that provable tightness in your solution.
Rosa: So, it gives us a deterministic convex problem over mu, nu, psi, v by using that moment encoding and providing better approximations for those quadratic constraints.
Dev: And they've shown this works on a quadrotor trajectory generation task with significant improvements in feasibility across challenging environments like the Circle Arena and Funnel Corridor.
Taro: So the implication is that we can potentially design systems that operate safely in much more uncertain conditions than previously thought possible for these types of trajectory optimization problems.
The paper's improvements: Taro: So, we're going over the specific improvements this paper suggests for their reformulation technique. What exactly are they proposing to do differently?
Rosa: Basically, they’re suggesting that by lifting the state vector to carry moment information explicitly, you can get an exact representation of linear chance constraints as second-order cone constraints.
Dev: That means for those linear constraints, we get an exact match without any conservatism in the calculation.
Taro: And for the quadratic chance constraints, they’re suggesting using these approximations—linear-matrix or quadratic ones—as long as you understand how tight they are.
Rosa: The authors are making a claim about these approximations; Proposition one says both the LMI and QC are conservative approximations of constraint three.
Dev: So, it’s not perfect for quadratics either, but they prove that neither approximation dominates the other in terms of conservatism, depending on how much spread there is in those psi i psi top i terms.
Taro: That dependence on the spread of those terms is a key caveat; if that spread gets too big, the approximation might not be tight enough for guaranteed safety when things go sideways.
Rosa: The biggest thing they’re pushing here is that this entire process leads to a deterministic convex problem over variables like mu, nu, psi, and v.
Dev: That means you don't have to worry about stochasticity in your final optimization step; it becomes a standard deterministic convex program.
Taro: And because they showed cost equivalence and feasible set equivalence with the original problem, we can trust that what we solve is actually what the original stochastic system would find.
Rosa: So, the implication for us is that we can use this framework to build more robust control systems where we have to deal with uncertainty in linear constraints exactly.
Dev: It simplifies things because it removes the need for those initial guesses of covariances or feedback matrices that other solvers often require in their real-time loops.
Taro: And for autonomy researchers, it means you can push the noise tolerance much higher on your trajectory planning problems before you run into immediate infeasibility issues.
Rosa: This method is about getting a deterministic convex formulation over mu, nu, psi, and v by explicitly encoding those moments in the state lift.
Dev: And they’ve shown this works on a quadrotor trajectory generation task with significant improvements in feasibility across challenging environments like the Circle Arena and Funnel Corridor.
Taro: So the implication is that we can potentially design systems that operate safely in much more uncertain conditions than previously thought possible for these types of trajectory optimization problems.
Conclusion: Rosa: So we're wrapping up this discussion on "Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints."
Dev: We’ve covered how they lift the state vector to handle moments, making linear chance constraints exact, and how they use approximations for quadratic ones.
Taro: It seems like the main thing here is moving from a complex stochastic problem to a deterministic convex one over variables like mu, nu, psi, and v.
Rosa: That’s right; it gives us that deterministic formulation equivalence with the original stochastic optimal control problem.
Dev: And we saw how this translates into real-world performance improvements on trajectory generation for a quadrotor under high noise levels.
Taro: It really changes things for someone who only listens to the show because it suggests we can design systems that operate safely in much more uncertain conditions than we thought possible.
Rosa: Yes, it’s about getting a deterministic convex formulation over mu, nu, psi, and v by explicitly encoding those moments in the state lift.
Dev: And they showed this works on a quadrotor trajectory generation task with significant improvements in feasibility across challenging environments like the Circle Arena and Funnel Corridor.
Taro: It really changes things for someone who only listens to the show because it suggests we can design systems that operate safely in much more uncertain conditions than we thought possible for these types of trajectory optimization problems.
Rosa: So, this paper offers a deterministic convex formulation over mu, nu, psi, and v by explicitly encoding those moments in the state lift.
Dev: And they showed this works on a quadrotor trajectory generation task with significant improvements in feasibility across challenging environments like the Circle Arena and Funnel Corridor.
Taro: It really changes things for someone who only listens to the show because it suggests we can design systems that operate safely in much more uncertain conditions than we thought possible for these types of trajectory optimization problems.
Rosa: So, this paper offers a deterministic convex formulation over mu, nu, psi, and v by explicitly encoding those moments in the state lift.
Dev: And they showed this works on a quadrotor trajectory generation task with significant improvements in feasibility across challenging environments like the Circle Arena and Funnel Corridor.
Taro: It really changes things for someone who only listens to the show because it suggests we can design systems that operate safely in much more uncertain conditions than we thought possible for these types of trajectory optimization problems.
More episodes
- 2608.13438-ContactGuard: Pre-Contact Execution Monitoring with Action-Conditioned Latent World Models
- 2610.34593-Future Prediction as Training-Only Video Supervision for Pretrained VLA Policies
- 2610.35385-EmbodiedLab: Beyond Manipulation, Benchmarking Embodied Agents That Act to Know
- 2610.36378-Data-Driven Hamiltonian for Neural Optimal Control
- 2610.37275-A Heuristic for Scheduling Autonomous Vehicles at Intersections
- 2610.37288-Dynamic Coordination of Autonomous Vehicles at Intersections
- 2610.37632-Real-Time Coordination of Autonomous Vehicles at Intersections
- 2611.13779-Softness is something you also need! Why compliance helps control: information metrics of a passive walker with compliant ankle
- 2611.13411-Residual-Corrected Physics-Informed Neural Network KKL Observers with Input-to-State Stability Guarantees
- 2611.14488-Is Your Robot's Memory Just a Clock? Temporal Shortcuts in Memory-Augmented VLA Policies