Source-linked AI summary
Nonlinear optimal control via occupation measures and LMI-relaxations
Jean-Bernard Lasserre, Didier Henrion, Christophe Prieur, Emmanuel Trélat
TL;DR
Nonlinear OCPs with polynomial or smooth data and state or control constraints are difficult to solve directly. The paper reformulates them through occupation-measure LPs and develops a hierarchy of finite LMI relaxations. The resulting lower bounds converge to the OCP value under convexity assumptions, while preliminary examples indicate useful approximations with few moments.
Problem
General nonlinear OCPs, especially with state constraints, are difficult to solve despite existing theoretical and numerical methods.
Method
The paper uses occupation-measure LPs and a hierarchy of finite semidefinite-programming or LMI relaxations for polynomial data, with an extension to smooth data and compact sets.
Results
The hierarchy produces monotone nondecreasing lower bounds that converge to the OCP value under convexity assumptions.
Takeaways & Limitations
The approach can complement shooting and direct methods and can sometimes certify OCP infeasibility early with very few moments.
Takeaways & Limitations
Depending on the problem data, high polynomial degrees may make the LMI hierarchy inefficient to implement with currently available public SDP solvers.
Abstract
from arXiv · showhide
We consider the class of nonlinear optimal control problems (OCP) with polynomial data, i.e., the differential equation, state and control con- straints and cost are all described by polynomials, and more generally for OCPs with smooth data. In addition, state constraints as well as state and/or action constraints are allowed. We provide a simple hierarchy of LMI (lin- ear matrix inequality)-relaxations whose optimal values form a nondecreasing sequence of lower bounds on the optimal value. Under some convexity assump- tions, the sequence converges to the optimal value of the OCP. Preliminary results show that good approximations are obtained with few moments.
MEASURES AND LMI-RELAXATIONS
The passage lists Jean B. Lasserre, Didier Henrion, and Christophe Prieur.
- Jean B. Lasserre is listed among the authors.
- Didier Henrion is listed among the authors.
- Christophe Prieur is listed among the authors.
1. INTRODUCTION
The paper addresses difficult nonlinear OCPs with state or control constraints by exploiting occupation-measure LPs and polynomial moment relaxations. Its LMI hierarchy supplies monotone lower bounds, converging under assumptions and sometimes certifying infeasibility early.
- Nonlinear OCPs with state constraints remain difficult despite maximum-principle and HJB tools, while general numerical methods can be hard to implement.
- Occupation-measure LPs make state, action, and state-action constraints support constraints, providing an alternative to maximum-principle methods for state constraints.
- The paper studies polynomial OCP data with state and/or control constraints, extending its approach to smooth data and compact sets.
- Truncated moment LPs or SDPs are solvable and yield a monotone nondecreasing sequence of lower bounds on the OCP value.
- The LMI hierarchy can provide an infeasibility certificate at an early stage, sometimes with very few moments.
2. Occupation measures and the LP approach
The paper reformulates nonlinear OCPs as infinite-dimensional LPs over occupation measures, whose constraints encode dynamics, terminal conditions, and support restrictions. Under convexity, the LP and OCP values coincide, motivating finite LMI relaxations.
- An admissible OCP consists of a constrained trajectory generated from x(0)=x0, satisfying a terminal condition, with fixed or free final time.
- The state-action occupation measure records (t, x(t), u(t)) up to T, while the terminal occupation measure records x(T).
- Support constraints on occupation measures encode state, control, and terminal admissibility conditions.
- The occupation-measure LP imposes an adjoint constraint and minimizes the pairing of occupation measures with running and terminal costs.
- If the LP is feasible, it is solvable and has no duality gap; under convexity of f(t, x, U) and the relevant set, its value matches the OCP value.
3. Semidefinite programming relaxations of P
The paper converts the occupation-measure LP for polynomial optimal control into finite SDP/LMI relaxations using moment and localizing matrices. Their values provide lower bounds, converge under stated assumptions, and can support dual approximations and uncontrollability certificates.
- Relaxation construction: The infinite-dimensional LP is relaxed into finite SDP/LMI problems Qr with finitely many variables and constraints.Each relaxation is formed by restricting polynomial tests to monomials of degree less than r, then increasing r.
- Moment formulation: Polynomial dynamics, costs, and semialgebraic constraints make the LP objective and constraints expressible through moments of occupation measures.Polynomial identities produce linear moment constraints, while support conditions are represented using moment and localizing matrices.
- Moment formulation: Putinar-type positivity conditions provide sufficient moment representations for measures supported on the compact state, target, and control sets.The construction uses moment and localizing matrix positivity to encode support constraints.
- Dual interpretation: Dual polynomials Λr approximate nearly optimal dual solutions, while the zero set of h + AΛr may indicate states and controls from an optimal trajectory.These interpretations are presented as candidate approximations and require further investigation beyond the paper’s scope.
- Uncontrollability certificates: For minimum-time problems, infeasible low-order LMI relaxations certify that an initial state cannot reach the target within finite or prescribed time.The paper illustrates such certificates on the Zermelo problem and other examples, sometimes using few moments.
4. Generalization to smooth optimal control problems
The paper extends the occupation-measure and LMI-relaxation framework from polynomial to smooth optimal control data. Under convexity conditions, the resulting approximations converge to the optimal control value, although high polynomial degrees may limit practical efficiency.
- Smooth-data extension: Smooth dynamics, running costs, and terminal costs are approximated in C1 by polynomial sequences on the relevant compact sets.The approximations use polynomials of increasing degree p.
- Smooth-data extension: For each polynomial degree p, the smooth problem yields a linear program Pp and associated finite-dimensional LMI-relaxations Qr,p.The relaxation is defined for r ≥ max(p/2, d(X, K, U)).
- Convergence: Under Putinar’s condition, inf Qr,p increases to min Pp as r tends to infinity.This is the fixed-p convergence result inherited from Theorem 3.6.
- Convergence: The generalized result allows the polynomial degree p to tend to infinity, extending the hierarchy toward the smooth optimal control problem.The values are denoted vr,p = inf Qr,p, vp = min Pp, and v = min P.
- Convergence: If f(t, x, U) is convex for every (t, x) in Σ, the limiting value equals the optimal control value J∗(0, T, x0).The equality is stated under the theorem’s assumptions on the compact semialgebraic sets and Putinar’s condition.
- Numerical limitation: High polynomial degrees may be required for some smooth data, making the LMI hierarchy difficult to implement efficiently with currently available public semidefinite-programming solvers.This is a numerical limitation rather than a failure of the convergence result.
- Manifold extension: The construction extends to smooth optimal control problems on Riemannian manifolds through smooth isometric embeddings into Euclidean spaces.This matters for global control systems that cannot generally be represented in a single global Euclidean chart.
5. Illustrative examples
The examples apply the LMI-relaxation hierarchy to minimum-time double-integrator, Brockett-integrator, and Zermelo problems, comparing relaxations with exact or known controllability results. Low-order moments give good approximations in several cases, although convergence guarantees require compact state sets and regularity remains open.
- Minimum-time test problems: The minimum-time experiments use double and Brockett integrators with exactly computable optimal values, implemented using GloptiPoly 3.The double-integrator example includes bounded control and the state constraint x2(t) ≥ −1; the Brockett control lies in the closed unit ball.
- Scope and limitations: The convergence theorem may fail in the double-integrator and Brockett examples because their state sets are not compact, and regularity of the minimum-time function remains for further investigation.The numerical experiments nevertheless retain the original unbounded state sets rather than adding bounding constraints.
- Double integrator: The double-integrator minimum time is available in closed form across regions defined by x1, x2, and the state constraint x2 ≥ −1.The supplied expressions split according to inequalities involving x1 and −x2^2/2 sign x2.
- Double integrator: The double-integrator hierarchy evaluates inf Qr(x0)/T(x0) for r = 2, 3, and 5 using tables and level sets.The known minimum-time function is used as the comparison baseline, and the approximation Λ5 is also compared with T along an optimal trajectory.
- Brockett integrator: For the Brockett integrator, the exact minimum-time function is continuous and analytic away from x1 = x2 = 0, where it is not C1.Its gradients with respect to x1 and x2 are discontinuous at every point (0, 0, x3) with x3 ≠ 0.
- Brockett integrator: Brockett-relaxation results are very good with low-order moments when the first two coordinates of the initial state are away from zero, improving farther from zero.The tables report inf Qr for 16 initial states, with occasional solver numerical issues producing slightly nonmonotone displayed lower bounds.
- Zermelo problem: For the Zermelo problem, infeasibility of an LMI relaxation certifies that an initial state cannot reach the target while remaining within the state set.Using Q1 already gives a very good approximation of the controllable set, while Q2 adds only a small set of uncontrollable states.
Appendix
The appendix establishes feasibility, boundedness, and convergence properties for the moment and SDP relaxations. Under compactness and support conditions, limiting moment sequences correspond to admissible measures, yielding convergence to the original optimal value.
- Measure LP: Feasible occupation-measure pairs form a compact set, so the infinite-dimensional linear program attains its minimum.Normalization identities bound the measures, while continuity of the constraint operator makes the feasible set closed.
- Moment bounds: The relaxation variables satisfy normalization and bounded-moment constraints, ensuring finite lower bounds for sufficiently large relaxation orders.Moment and localizing matrix constraints imply bounds such as |zγ| ≤ 1 for moments up to the relevant order.
- Measure representation: A diagonal subsequence argument converts feasible finite moment vectors into infinite moment sequences representing probability measures on the prescribed compact supports.Positive semidefinite moment and localizing matrices, together with Putinar’s condition, identify measures supported on K, X, U, and [0,1].
- Feasibility: The limiting measures satisfy the occupation-measure dynamics and support constraints, so they form a feasible solution of the original linear program.The moment equalities pass to the limit and identify the required marginals and support containment.
- Convergence: The SDP relaxation values increase monotonically to the optimal value of the original problem.The limiting feasible measures are optimal, establishing min Qr ↑ min P.
- Smooth data: For smooth-data approximations, strong convergence of the approximating operators and costs preserves feasibility and yields convergence of optimal values.A weak-* convergent subsequence of optimal measure pairs remains feasible and attains the limiting objective value.