Source-linked AI summary
Convex computation of the maximum controlled invariant set for polynomial control systems
Milan Korda, Didier Henrion, Colin N. Jones
TL;DR
Computing maximum controlled invariant sets for nonlinear systems is difficult, especially with polynomial dynamics and semialgebraic constraints. The paper formulates the MCI set through occupation-measure linear programming and develops SDP/LMI and SOS relaxations. The resulting outer approximations converge, while the approximations are generated by a single SDP from the problem description.
Problem
Maximum controlled invariant sets characterize which initial states can remain within constraints forever, but nonlinear computation commonly leads to difficult non-convex optimization or restrictive predefined set classes.
Method
The paper uses occupation measures to formulate an infinite-dimensional convex LP, then derives finite-dimensional moment/LMI relaxations and dual SOS problems for polynomial systems.
Results
The SDP hierarchy converges to the volume of the MCI set, while dual SOS solutions yield converging polynomial outer approximations.
Takeaways & Limitations
The approximations are readily computable by a single SDP using no additional data beyond the problem description.
Takeaways & Limitations
The resulting semidefinite programs scale relatively unfavorably as the number of variables grows with state dimension, control dimension, and polynomial degree.
Abstract
from arXiv · showhide
We characterize the maximum controlled invariant (MCI) set for discrete- as well as continuous-time nonlinear dynamical systems as the solution of an infinite-dimensional linear programming problem. For systems with polynomial dynamics and compact semialgebraic state and control constraints, we describe a hierarchy of finite-dimensional linear matrix inequality (LMI) relaxations whose optimal values converge to the volume of the MCI set; dual to these LMI relaxations are sum-of-squares (SOS) problems providing a converging sequence of outer approximations to the MCI set. The approach is simple and readily applicable in the sense that the approximations are the outcome of a single semidefinite program with no additional input apart from the problem description. A number of numerical examples illustrate the approach.
1 Introduction
The paper develops a convex, measure-based method to compute maximum controlled invariant sets for continuous- and discrete-time polynomial systems under semialgebraic constraints. Its SDP hierarchy produces converging polynomial outer approximations without state-space discretization or hand-tuned additional data.
- Motivation: Maximum controlled invariant sets contain initial states that can remain within the constraint set indefinitely under admissible controls.The MCI set is also known as the viability kernel or, in linear systems, an (A, B)-invariant set.
- Method: Occupation measures represent the evolution of an ensemble of initial conditions, replacing separate trajectory analysis with an infinite-dimensional convex LP characterization.The approach studies time evolution through measures and is presented as a first use of occupation measures for approximate MCI computation.
- Scope: The paper addresses general continuous- and discrete-time polynomial dynamics with semialgebraic state and control constraints.This extends the treatment beyond continuous-time systems and finite-horizon formulations considered in related previous work.
- Method: A hierarchy of finite-dimensional SDPs and dual SOS problems computes polynomial super-level-set outer approximations with convergence guarantees.Moment and localizing matrix LMIs arise from truncated moment sequences, while SOS formulations provide the dual approximations.
- Practical contribution: The resulting approximations are obtained from a single SDP using only the problem description, and they can represent intersections of polynomial super-level sets.The framework includes more restrictive classes such as polytopes and ellipsoids.
- Limitation: The method produces outer approximations that are not invariant, so it complements rather than replaces inner-approximation techniques.Accurate outer approximations can still inform control-system performance limitations and applications such as collision avoidance.
2 Problem statement
The paper formulates discrete- and continuous-time polynomial control systems with compact basic semialgebraic state and input constraints, and defines the MCI set as states that can remain in the constraint set indefinitely. For continuous time, it uses a convexified differential inclusion whose trajectories approximate those of the classical control system.
- The approach treats discrete- and continuous-time control systems in parallel.
- Discrete-time dynamics follow xt+1 = f(xt, ut) under polynomial dynamics and compact basic semialgebraic state and input constraints.
- The discrete-time MCI set contains initial states that can be kept inside X forever using admissible controls.
- Continuous-time dynamics are modeled by a convexified differential inclusion with polynomial vector fields and compact basic semialgebraic constraints.
- The continuous-time MCI set contains initial states with a trajectory of the convexified inclusion that remains in X indefinitely.
3 Occupation measures
Occupation measures encode discounted visits of state-control trajectories and replace the original dynamics with infinite-dimensional linear equations. Their feasible initial measures are linked to the MCI set through support and volume properties.
- Occupation measures record discounted visits of state-control trajectories while ensuring finite total measure.For discrete time, the total mass is (1 − α)^−1; for continuous time, it is β^−1.
- Average occupation measures aggregate discounted visits over trajectories starting from an initial measure.
- The measure equations linking initial and occupation measures replace the discrete- and continuous-time dynamics equations in the formulation.
- Discrete time: Any discrete-time feasible initial measure supported in X is supported in the MCI set.
- Continuous time: The continuous-time construction uses relaxed controls, with trajectories remaining in X and control measures supported on U.
- Continuous time: For continuous time, any feasible initial measure has support volume no greater than the volume of the MCI set.
4 Primal LP
The MCI computation is cast as an infinite-dimensional LP maximizing the mass of an initial measure dominated by Lebesgue measure, subject to occupation-measure dynamics and support constraints. In both time settings, the optimal value equals the MCI-set volume.
- The primal LP maximizes the mass of an initial measure constrained by µ0 ≤ λ, while dynamics and constraints are encoded through measure equations and supports.
- Discrete time: The discrete-time primal problem is an infinite-dimensional LP over nonnegative measures on X × U and X.
- Discrete time: The discrete-time LP has optimal value p∗ = λ(XI), attained by restricting Lebesgue measure to the MCI set.
- Continuous time: The continuous-time primal problem is likewise an infinite-dimensional LP over nonnegative measures with state-control support constraints.
- Continuous time: The continuous-time LP has optimal value p∗ = λ(XI), attained by restricting Lebesgue measure to the MCI set.
5 Dual LP
The dual LPs use continuous functions, and their feasible solutions produce outer approximations of the MCI set through unit super-level sets. Discrete- and continuous-time primal and dual problems have no duality gap.
- Dual LPs on continuous functions are derived from the measure-based primal LPs, and feasible super-level sets outer-approximate the MCI sets.
- Discrete time: In discrete time, the dual constraints impose αv(f(x, u)) ≤ v(x), w(x) ≥ v(x) + 1, and w(x) ≥ 0.
- Discrete time: Any feasible discrete-time dual solution satisfies w ≥ 1 on the MCI set, so its unit super-level set contains that set.
- Discrete time: The discrete-time primal and dual LPs have no duality gap: p∗ = d∗.
- Continuous time: In continuous time, the dual constraints use grad v · f(x, u) ≤ βv(x), together with w(x) ≥ v(x) + 1 and w(x) ≥ 0.
- Continuous time: Any feasible continuous-time dual solution satisfies w ≥ 1 on the MCI set, so its unit super-level set is an outer approximation.
- Continuous time: The continuous-time primal and dual LPs have no duality gap: p∗ = d∗.
6 LMI relaxations
Finite-dimensional moment relaxations convert the infinite-dimensional LPs into primal and dual SDPs. Their optimal values converge to the MCI-set volume, while dual SOS solutions yield outer approximations converging to the MCI set.
- LMI relaxations: Finite-dimensional primal relaxations become truncated moment SDPs, while their duals become SOS problems also representable as SDPs.The construction uses moments, moment and localizing matrices, and polynomial positivity certificates.
- LMI relaxations: Relaxation order k truncates moments to monomials of total degree at most 2k and imposes positive-semidefinite moment and localizing matrix constraints.These constraints provide necessary conditions for truncated sequences to represent measures supported on the compact semialgebraic sets.
- Convergence results: The finite-dimensional primal and dual optimal values coincide and converge to the infinite-dimensional LP values, which equal the MCI-set volume.The convergence is monotone from above, and primal-dual equality follows from the absence of a duality gap.
- Convergence results: Dual functions w_k converge from above to the MCI-set indicator in L1, while running minima additionally converge almost uniformly.The resulting functions over-approximate the indicator on the state constraint set.
- Convergence results: The outer-approximation sets X_I^k contain the MCI set and their volume discrepancy tends to zero.Thus the SOS-derived sets converge set-wise from outside to the MCI set.
7 Numerical examples
Numerical examples illustrate the proposed results using primal SDP relaxations and dual SOS problems. The computations use Gloptipoly 3, Yalmip, and SeDuMi, with scaling recommended for higher relaxation orders.
- Implementation: Numerical examples use Gloptipoly 3 for primal SDP relaxations and Yalmip for dual SOS problems.The resulting semidefinite programs are solved with SeDuMi.
- Implementation: SeDuMi also returns the dual solution providing outer approximations when solving the primal relaxations.The implementation therefore supplies the approximation objects alongside the primal computation.
- Implementation: Problem data should be scaled so the constraint sets are within a numerically suitable range, especially at higher relaxation orders.The paper points to the conclusion and the acrobot-on-a-cart example for scalability and solver-performance discussion.
7.1 Discrete time
The discrete-time examples show that polynomial outer approximations can be fairly tight at modest degrees, while complex filled Julia boundaries remain harder to capture. The controlled Hénon example also indicates that allowing control enlarges the estimated MCI set.
- Double integrator: Degree-8 and degree-12 polynomial outer approximations are fairly tight for the discrete-time double integrator.The reference MCI set was computed using standard polyhedral projections.
- Filled Julia sets: Degree-12 outer approximations are computed for filled Julia sets with parameters c = −0.7 + i0.2 and c = −0.9 + i0.2.The approximate true sets were obtained by randomly sampling initial conditions in the unit ball and iterating for one hundred steps.
- Filled Julia sets: Higher polynomial degrees do not significantly improve the filled Julia estimates when monomials are used, although alternative bases could better capture fractal boundaries.The paper specifically mentions Chebyshev polynomials as an alternative basis.
- Controlled Hénon map: Degree-eight outer approximations for the controlled Hénon map are larger with control than without control.The uncontrolled and controlled approximations are shown in darker and lighter red, respectively.
7.2 Continuous time
The continuous-time examples apply polynomial outer approximations to systems ranging from double integrators and spider-web dynamics to an acrobot on a cart. The examples show how degree choices and additional actuation affect approximations, while the largest example also exposes computational and accuracy limits.
- Spider-web system: For the spider-web system, using degree 16 for v and degree 8 for w yields a low-complexity outer approximation without significant loss in tightness.The alternative uses degree 16 for both v and w.
- Double integrator: Continuous-time double-integrator outer approximations are shown for degrees 8 and 14.The approximations target the MCI set.
- Acrobot on a cart: The acrobot-on-a-cart example compares a system with only the middle joint actuated against one where the cart is also actuated.The state constraint set is six-dimensional, and the two input sets differ in whether cart force is available.
- Acrobot on a cart: Allowing cart actuation produces a larger, or at least equal, MCI set in the degree-four outer-approximation sections.The comparison fixes (x1, x4, x5) = (0, 0, 0).
- Acrobot on a cart: The largest example took 110 seconds with SeDuMi and 10 seconds with MOSEK at degree 4, while the degree-6 MOSEK solution had poor accuracy and was not reported.The reported times are pure solver times, excluding Yalmip preprocessing.
- Approximation caveat: Optimal values are ordered across relaxation levels, but the outer approximating sets themselves are not guaranteed to be ordered by inclusion.This distinction applies to the finite-dimensional optimization problems and their set approximations.
8 Conclusion
The paper gives a convex characterization of the maximum controlled invariant set and derives converging semidefinite-program relaxations that produce semialgebraic outer approximations. The approach is readily applicable but scales unfavorably with state, control, and polynomial degree.
- Contributions: The maximum controlled invariant set is characterized through an infinite-dimensional convex formulation whose finite-dimensional dual approximations converge to semialgebraic outer approximations.These approximations are obtained from a single semidefinite program using only the problem description.
- Applicability: The outer approximations require no additional data beyond the problem description and can be computed with freely available modeling tools.
- Limitations: The semidefinite programs have relatively unfavorable scalability, with the number of variables growing as O((n + m)d).Here n and m are the state and control dimensions, and d is the degree of the approximating polynomial.
- Limitations: For dimensions exceeding roughly m + n = 6, users must trade accuracy for smaller d or use parallel or commercial SDP solvers.The paper identifies parallelization and MOSEK as alternatives to standard freely available solvers.
- Future work: Future work includes inner approximations of MCI sets and extensions to stochastic and uncertain systems.Existing partial results for inner approximations concern the related uncontrolled region-of-attraction problem.
Appendix A
Appendix A establishes the discrete-time measure-theoretic link between occupation measures and invariant supports. It shows that feasible measure pairs correspond to randomized controls, while measurable selections yield deterministic policies whose invariant support lies inside the MCI set.
- Markov formulation: The discrete-time construction embeds polynomial dynamics in Markov control processes using stochastic kernels as stationary randomized control policies.The state transition kernel and discounted occupation measures are defined from these policies.
- Occupation measures: Any feasible measure pair has a stationary randomized control policy whose discounted occupation measure equals the prescribed measure.The proof disintegrates the joint measure into a state marginal and a stochastic kernel.
- Occupation measures: The x-marginal of the discounted occupation measure coincides with the x-marginal of the initial measure.This follows after iterating the transition relation and using α ∈ (0, 1) together with finiteness of the measure.
- Invariant support: The support of the state marginal is invariant under the randomized policy, and measurable selections from its control supports produce admissible deterministic policies.Continuity of f ensures the selected closed-loop successor remains in the support.
- Invariant support: Consequently, the support of the initial measure is contained in the maximum controlled invariant set.
9 Appendix B
Appendix B extends the occupation-measure argument to continuous-time systems through relaxed martingale problems and superposition principles. It connects feasible measure pairs to trajectories of a convexified inclusion and uses this connection to bound initial support by the MCI set.
- Occupation measures: Any measure pair solving the continuous-time constraint admits a family of trajectories of the convexified inclusion whose discounted occupation measure has the same state marginal.The argument uses Fubini’s theorem and Ambrosio’s superposition principle.
- Continuous-time formulation: The continuous-time proof embeds the dynamics in an extended state space and defines a generator on continuously differentiable functions vanishing at infinity.Polynomial dynamics provide local Lipschitz continuity, supporting the associated ODE construction.
- Continuous-time formulation: A relaxed martingale problem represents continuous-time dynamics using a stationary relaxed Markov control and the generator’s martingale property.
- MCI bound: If the initial support had positive volume outside the MCI set, those trajectories would contradict the requirement that the occupation measure remain supported in the constraint set.Therefore the initial support has volume no greater than the MCI set.