PaperlayerView exact revision on arXiv

Source-linked AI summary

Convex computation of the region of attraction of polynomial control systems

Didier Henrion, Milan Korda

arXiv:1208.1751v2math.OC

TL;DR

The paper addresses computation of the controlled ROA for nonlinear polynomial systems with semialgebraic constraints. It formulates the problem as a convex infinite-dimensional LP over occupation measures and approximates it with converging LMI relaxations. The resulting hierarchy provides semialgebraic outer approximations with asymptotically vanishing conservatism, while the method is currently limited to moderate system dimensions.

  • Problem

    Computing the controlled ROA of nonlinear systems with constrained trajectories is difficult, especially when existing Lyapunov approaches require conservative LMIs or nonconvex BMIs.

  • Method

    The paper optimizes directly over controlled trajectories represented by occupation measures, producing an infinite-dimensional LP and finite-dimensional LMI relaxations for polynomial and semialgebraic problems.

  • Results

    The measure LP computes the ROA volume, while the dual LMI hierarchy yields semialgebraic outer approximations converging asymptotically to the ROA.

  • Takeaways & Limitations

    The approach provides a convex and constructive ROA computation procedure using standard LMI hierarchies and publicly available software.

  • Takeaways & Limitations

    The approach is currently limited to systems of moderate size, typically n + m ≤ 6, unless lower relaxation accuracy is accepted.

Abstract

from arXiv · show

We address the long-standing problem of computing the region of attraction (ROA) of a target set (e.g., a neighborhood of an equilibrium point) of a controlled nonlinear system with polynomial dynamics and semialgebraic state and input constraints. We show that the ROA can be computed by solving an infinite-dimensional convex linear programming (LP) problem over the space of measures. In turn, this problem can be solved approximately via a classical converging hierarchy of convex finite-dimensional linear matrix inequalities (LMIs). Our approach is genuinely primal in the sense that convexity of the problem of computing the ROA is an outcome of optimizing directly over system trajectories. The dual infinite-dimensional LP on nonnegative continuous functions (approximated by polynomial sum-of-squares) allows us to generate a hierarchy of semialgebraic outer approximations of the ROA at the price of solving a sequence of LMI problems with asymptotically vanishing conservatism. This sharply contrasts with the existing literature which follows an exclusively dual Lyapunov approach yielding either nonconvex bilinear matrix inequalities or conservative LMI conditions. The approach is simple and readily applicable as the outer approximations are the outcome of a single semidefinite program with no additional data required besides the problem description.

1 Introduction

The paper introduces a convex, trajectory-based approach to computing controlled regions of attraction for nonlinear systems, with converging semialgebraic outer approximations for polynomial systems and semialgebraic constraints.

  • The constrained ROA contains initial states that can reach a target set through admissible trajectories while remaining within state constraints.
  • The paper formulates ROA computation as an infinite-dimensional LP over nonnegative occupation measures, optimizing directly over controlled trajectories.
  • For polynomial dynamics and semialgebraic sets, a hierarchy of convex LMI relaxations yields nested semialgebraic outer approximations converging asymptotically to the ROA.
  • The occupation-measure formulation makes ROA computation convex and can be implemented with publicly available software for the LMI hierarchy.
  • Unlike Lyapunov-based approaches using conservative LMIs or nonconvex BMIs, this method obtains convexity through a primal optimization over trajectories.
  • The approach extends set-approximation techniques to an ROA defined implicitly by differential equations rather than specified in advance.

2 Problem statement

The paper studies finite-time controlled ROA computation for polynomial dynamics subject to compact semialgebraic state, input, and target constraints.

  • The system has state x(t) ∈ R^n, control input u(t) ∈ R^m, and terminal time T > 0, with polynomial vector-field entries.
  • State and control inputs satisfy basic semialgebraic constraints, while the terminal state belongs to a semialgebraic target set.
  • The state, input, and target sets X, U, and X_T are assumed compact.
  • The finite-time controlled ROA consists of initial conditions admitting an admissible trajectory that reaches the target set without violating state constraints.
  • The paper first poses ROA computation as an infinite-dimensional LP and then approximates it with LMI problems having asymptotically vanishing conservatism.

3 Occupation measures

Occupation measures encode the time spent by controlled trajectories in state-input regions, while Liouville constraints provide a linear measure-based representation of trajectory evolution.

  • An occupation measure records how much time a trajectory spends in measurable subsets of time, state, and control space.
  • The occupation measure encodes trajectory information through integration of measurable functions along the state and control path.
  • For an initial-state distribution, the average occupation measure aggregates trajectory time across that distribution, and the final measure gives the transported terminal-state distribution.
  • Liouville’s equation is a linear relation linking initial, occupation, and terminal measures through the differential operator and test functions.
  • Relaxed ROA: Measures satisfying Liouville’s equation generally correspond to trajectories of a convexified differential inclusion rather than a one-to-one family of original controlled trajectories.
  • Relaxed ROA: The relaxed ROA can strictly contain the original ROA, although Filippov–Ważewski relaxation makes original trajectories dense in the convexified trajectories.
  • ROA via optimization: The ROA computation is reformulated as an optimization over nonnegative measures whose supports enforce state, input, and target constraints.
  • ROA via optimization: The optimal value of this measure LP equals the volume of the ROA.

4 Primal infinite-dimensional LP on measures

The primal LP replaces direct support maximization with mass maximization under domination by Lebesgue measure, preserving the ROA volume while enabling dualization.

  • The resulting outer approximations remain valid everywhere even though the optimal initial-measure support may differ from the ROA on a zero-volume set.
  • Constraining the initial measure below Lebesgue measure is equivalent to requiring its density to be at most one.
  • The primal formulation maximizes the initial measure’s mass subject to Liouville dynamics, nonnegativity, support constraints, and domination by Lebesgue measure.
  • The optimal value of the primal LP equals the ROA volume, attained when the initial measure is Lebesgue measure restricted to the ROA.
  • A complementary slack measure converts the domination inequality into two nonnegative measures summing to Lebesgue measure.

5 Dual infinite-dimensional LP on functions

The dual LP uses continuous functions to produce outer approximations of the ROA, with no duality gap and convergence toward the ROA indicator.

  • Dual formulation: Feasibility forces v(0, ·) ≥ 0 and w ≥ 1 on the ROA, so w defines an outer approximation through a super-level set.These inequalities follow from applying the trajectory constraints to any admissible trajectory reaching the target set.
  • Duality: There is no duality gap between the primal measure LPs and the continuous-function dual LP.The theorem states equality of the primal and dual optimal values, p*=d*; the proof uses weak-* continuity and compactness.
  • Duality: The primal supremum is attained, but the dual infimum is not attained in C1([0, T] × X) × C(X).A feasible sequence exists whose w-component converges to the discontinuous indicator IX0.
  • Convergence: A feasible dual sequence has w converging from above to IX0 in L1 norm and almost uniformly.Since each w is at least IX0, the convergence provides increasingly accurate outer approximations in these senses.

6 LMI relaxations and SOS approximations

The infinite-dimensional measure LP is truncated into convex LMI relaxations, while SOS duals generate outer approximations whose conservatism vanishes with relaxation order.

  • LMI relaxations: The infinite-dimensional LP is approximated by a hierarchy of finite-dimensional LMI problems with approximation error vanishing as the relaxation order increases.The dual LMI problem is formulated as a sum-of-squares problem and yields converging outer approximations to the ROA.
  • Moment formulation: Moment sequences encode the measures, and polynomial test functions convert the measure constraints into an infinite-dimensional linear system.Monomials t^αx^β and x^β are used as test functions, then truncated to total degree at most 2k.
  • Primal SDP: The order-k primal relaxation maximizes the initial-measure mass subject to linear equalities and positive-semidefinite moment and localizing matrices.The matrix constraints represent measure nonnegativity and support on the state, input, and target sets.
  • Primal SDP: Each relaxation is a semidefinite program with a linear objective and convex LMI constraints.The feasible set is looser than the original measure LP, but the discrepancy monotonically vanishes as k tends to infinity.
  • Dual SOS approximation: The dual relaxation uses polynomial v and w together with SOS certificates, whose constraints can be expressed as LMIs and whose objective is linear in w's coefficients.The objective coefficients are weighted by the moments of Lebesgue measure over X.
  • Duality: The primal and dual finite-dimensional LMI problems have no duality gap.Theorem 4 states equality of their optimal values.

7 Outer approximations and convergence results

The dual LMI hierarchy produces outer approximations of the ROA whose polynomial functions, optimal values, and set volumes converge from above to the exact ROA quantities.

  • Outer approximations: The dual LMI problem generates outer approximations X0k and ¯X0k satisfying X0k ⊃ ¯X0k ⊃ X0 for every relaxation order.These sets are constructed from optimal polynomial solutions and their running minima.
  • Functional convergence: The polynomial w-components wk and their running minima ¯wk converge from above to the ROA indicator IX0 in L1 norm, with ¯wk also converging almost uniformly.The running-minimum sequence strengthens the convergence guarantee beyond L1 convergence.
  • Optimal-value convergence: The primal and dual LMI optimal values converge monotonically from above to the corresponding infinite-dimensional LP optima.The dual values converge to d∗, while the primal values converge to p∗.
  • Optimal-value convergence: The LMI optimal values converge to the volume of the ROA, λ(X0) = p∗ = d∗.This identifies the limiting primal and dual objective values with the ROA volume.
  • Set-wise convergence: The set excesses λ(X0k \ X0) and λ(¯X0k \ X0) vanish as k→∞, while ¯X0k converges monotonically through nested outer approximations.The inclusion chain bounds both approximating volumes relative to λ(X0).

8 Free final time

The approach extends to reaching a target set at any time before a finite horizon, without requiring trajectories to remain there afterward. The reachable initial-state set is obtained from an optimal occupation-measure solution, and the preceding convergence results continue to hold.

  • Free final time: The extension computes initial states from which the target set XT can be reached at some time t ≤ T.The trajectories need not remain in XT after reaching it.
  • Measure formulation: The reachable initial-state set is obtained as the support of the optimal initial measure µ0∗.The measure formulation uses nonnegative initial, occupation, and terminal measures with terminal support in [0,T]×XT.
  • Dual formulation: The modified dual problem differs from the earlier formulation by requiring v(t,x) ≥ 0 on XT for every t ∈ [0,T].This is the only stated change in the dual constraints.
  • Convergence: All results from the preceding sections, including convergence results, hold for this extension.The paper states that the proofs are almost verbatim copies.

9 Numerical examples

Five examples illustrate the approach across increasing complexity, with outer approximations generally converging relatively quickly or showing good tightness. The acrobot example instead examines how actuation affects approximation size, while solver timings compare SeDuMi and MOSEK.

  • Examples: Five examples span a univariate cubic system, Van der Pol oscillator, double integrator, Brockett integrator, and acrobot.Implementations use Gloptipoly 3, YALMIP, or SOSTOOLS, with SeDuMi for the first three examples and MOSEK for the last two.
  • Univariate cubic dynamics: The cubic system has analytically known ROA X0 = [−0.5, 0.5], and its set-wise approximations converge very quickly despite slow functional convergence.The volume error need not decrease monotonically because the guaranteed monotone quantity is the integral of the approximating polynomial.
  • Van der Pol oscillator: Van der Pol super-level-set approximations converge relatively quickly to the ROA for degrees d ∈{10, 12, 14, 16}.The relative volume error confirms this behavior, and degree-18 polynomial approximation is also shown.
  • Double integrator: Double-integrator super-level-set approximations converge relatively quickly for degrees d ∈{6, 8, 10, 12}, as confirmed by relative volume errors.The target is the origin at final time T = 1, with state constraint set X = [−0.7, 0.7] × [−1.2, 1.2].
  • Brockett integrator: Brockett-integrator approximations are not monotone, so the reported monotone estimates for degrees d ∈{6, 10} show fairly good tightness.The true ROA is analytically available for comparison.
  • Acrobot: The acrobot study compares approximation sizes under single-joint versus both-joint actuation rather than against a readily available true ROA.Solver timings report that MOSEK is much faster than SeDuMi across the presented ROA problems.

10 Conclusion

The paper presents a convex, constructive approach to controlled ROA computation for polynomial systems with semialgebraic constraints, producing outer approximations through converging LMI relaxations. It also identifies applicability extensions and practical limits of the hierarchy.

  • The paper proposes a convex formulation for computing the controlled region of attraction.
  • Standard finite-dimensional LMI relaxations provide theoretically convergent outer approximations with public-domain interfaces and solvers.
  • The method covers polynomial dynamics with semialgebraic input and state constraints, and additional approximation properties can be imposed through polynomial constraints.
  • The outer approximations result from a single semidefinite program requiring no additional data beyond the problem description.
  • The approach can address forward reachable sets through time reversal and can characterize outer approximations of maximum controlled invariant sets.
  • Extensions to piecewise polynomial, stochastic, and uncertain systems are described as possible, while controlled-system results for inner approximations remain future work.
  • The hierarchy is currently limited to moderate dimensions, with moment counts scaling as O(k^(n+m)) for fixed n+m and O((n+m)^k) for fixed k.The authors mention sparsity exploitation and parallelization as directions for scaling to larger systems.
  • Monomial bases can suffer numerical ill-conditioning, so alternative bases such as Chebyshev polynomials are recommended for better approximation performance.

Appendix A

Appendix A establishes the correspondence between measure-based Liouville equations and families of admissible trajectories. The proof uses disintegration, stochastic kernels, continuity equations, and a trajectory-measure representation.

  • The appendix proves correspondence between the Liouville PDE on measures and the convexified differential inclusion.
  • Disintegrating the occupation measure over inputs yields a stochastic control kernel and an averaged vector field governing the associated differential equation.
  • A nonnegative measure on trajectory space represents a family of absolutely continuous solutions whose occupation, initial, and terminal measures coincide with the prescribed measures.
  • The averaged vector field is only measurable, so the associated differential equation may not admit a unique solution.
  • The time marginal of the occupation measure equals scaled Lebesgue measure on [0,T], with scale ρ = µ0(X) = µT(X).
  • An occupation measure is disintegrated into time-indexed state kernels, with each kernel interpreted as the state distribution at that time.
  • The disintegrated kernels satisfy a continuity equation almost everywhere, with absolute continuity established for integrals against continuously differentiable test functions.

Appendix B

Appendix B relates the classical and relaxed ROAs through convexified dynamics and trajectory relaxation. Under compactness and Lipschitz assumptions, the two are closely connected, but strict gaps can occur.

  • The classical ROA consists of absolutely continuous trajectories reaching the target while remaining in the state constraints.
  • The relaxed ROA replaces the original dynamics by the convexified inclusion and satisfies the inclusion of the classical ROA.
  • With compact constraint sets and Lipschitz dynamics, Filippov–Ważewski relaxation connects relaxed trajectories to limits of admissible classical trajectories in dilated sets.

Appendix C

Appendix C gives examples where relaxed ROAs differ from classical ROAs and develops the finite-dimensional LMI duality argument. The examples expose relaxation gaps, while the proof establishes strong duality under boundedness conditions.

  • The appendix constructs control systems whose relaxed ROA is strictly larger than the classical ROA.
  • For a scalar system with controls {−1,+1} and singleton constraints, the classical ROA is empty while the relaxed ROA contains the singleton through infinitely fast control chattering.
  • A two-dimensional example produces an arbitrarily large volume gap between classical and relaxed ROAs, because chattering enables passage that regular trajectories cannot achieve.
  • The finite-dimensional primal LMI uses moment and localizing matrix constraints represented as a direct product of positive semidefinite cones.
  • The corresponding dual LMI maximizes a linear objective subject to affine cone constraints involving the moment and localizing matrices.
  • A lemma of alternatives yields either an interior dual certificate or a feasible ray in the primal problem, but not both.
  • Because the primal feasibility set is nonempty and bounded, standard semidefinite-programming duality gives equality of the primal and dual optimal values.
Loading 1208.1751v2…