Positivity Certificates in Optimal Control

Edouard Pauwels, Didier Henrion, Jean-Bernard Lasserre

TL;DR

This paper presents a tutorial on using "positivity certificates" derived from semidefinite programming to approximate solutions for optimal control problems. This approach offers a unified framework for tackling diverse problems like region of attraction estimation, direct optimal control, and inverse optimal control, providing powerful, mathematically rigorous certificates of sub-optimality.

What Problem Does This Paper Address?

Optimal control problems, which aim to find the best way to steer a system from an initial state to a desired state while minimizing a cost, are notoriously difficult to solve, especially for complex, nonlinear systems. Traditional methods often struggle with finding global optima or providing guarantees on the quality of approximate solutions. This paper addresses the challenge of developing computationally tractable methods for optimal control that can provide rigorous guarantees, particularly for engineers and roboticists. It focuses on a specific class of techniques that leverage "positivity certificates" to approximate the value function of an optimal control problem, thereby enabling the analysis and solution of these problems.

Methods

The core of the paper revolves around using positivity constraints on surrogate value functions to derive certificates for optimal control problems. These constraints are then approximated using Sum-of-Squares (SOS) hierarchies, which are amenable to semidefinite programming (SDP).

Here's a breakdown of the key methodological elements:

  • Weak Formulation of Optimal Control: The paper starts by referencing the "weak formulation" of optimal control problems, which involves concepts like occupation measures. While not delving deeply into the mathematical intricacies, it sets the stage for the duality-based approach.
  • Positivity Certificates: The central idea is to use inequalities that express the non-negativity of certain functions related to the value function and the system dynamics. These are called "positivity certificates."
    • Global Lower Bounds (Condition 1): These conditions provide a lower bound on the optimal value function. If a function v satisfies these conditions, then v(to, xo) <= v*(to, xo), meaning v is a lower bound for the true optimal value.
  • Local Upper Bounds (Condition 2): These conditions provide an upper bound on the value function along a specific trajectory. If a function v satisfies these, then v*(t, x(t)) <= v(t, x(t)) + epsilon, indicating that the trajectory is at most epsilon-suboptimal.
  • Sum-of-Squares (SOS) Reinforcement: For practical computation, especially when system dynamics and costs are polynomials, the continuous positivity constraints are approximated by SOS constraints. This involves representing polynomials as sums of squares of other polynomials, which can be checked using semidefinite programming. This process is called "SOS reinforcement" and provides a hierarchy of approximations.
  • Semidefinite Programming (SDP): The SOS approximations translate into semidefinite programs, which are a class of convex optimization problems that can be solved efficiently by specialized software.
  • Applications: The paper demonstrates how these positivity certificates and SOS approximations can be applied to:
  • Region of Attraction Approximation: Estimating the set of initial states from which a system can reach a target state.
  • Direct Optimal Control: Finding the optimal control policy and value function.
  • Inverse Optimal Control: Inferring the cost function (Lagrangian) that explains observed optimal trajectories.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical illustrations using a standard benchmark system (Brockett's integrator) rather than large-scale datasets.

Key Insights and Ideas

  • Unified Framework: The concept of positivity certificates provides a remarkably unified way to approach seemingly disparate problems in optimal control (region of attraction, direct control, inverse control). The same core mathematical conditions form the basis for all these applications.
  • Elementary Proofs, Powerful Results: A striking feature is that the proofs for the main propositions (e.g., Proposition 1 on global lower bounds) are elementary, relying on basic calculus and integration. Despite their simplicity, they yield powerful results for certifying sub-optimality.
  • Approximation Guarantees: The SOS reinforcement technique, while an approximation, provides a systematic way to obtain provably convergent hierarchies of solutions. By increasing the degree of the SOS polynomials, the approximations get arbitrarily close to the true solution.
  • Bridging Theory and Practice: The paper effectively bridges the gap between theoretical optimal control concepts (like value functions and optimality conditions) and practical computational tools (SDP and SOS programming).
  • Positivity as a Key: The paper highlights how simple notions of positivity, when applied to surrogate value functions, can encode rich information about the optimal control problem.

Key Results

  • Global Lower Bounds: Proposition 1 shows that if a function v satisfies certain positivity conditions, it provides a global lower bound on the optimal value function v*. This means v(to, xo) <= v*(to, xo).
  • Local Upper Bounds and Sub-optimality Certificates: Proposition 2 demonstrates that if a function v satisfies other positivity conditions along a specific trajectory, then that trajectory is guaranteed to be epsilon-suboptimal, meaning its cost is at most epsilon greater than the optimal cost.
  • Application to Region of Attraction: Corollary 1 shows that positivity conditions can be used to derive outer approximations of the region of attraction.
  • Numerical Illustrations: The paper presents numerical results for Brockett's integrator, demonstrating that the SOS reinforcement technique can provide accurate approximations for optimal time and region of attraction. Table 1 shows comparisons between SOS reinforcement results and exact optimal times, indicating reasonable accuracy. Figure 2 visually demonstrates the outer approximation of the region of attraction. Figure 3 shows error metrics for the inverse optimal control problem.

Limitations and Future Work

  • Approximation Gap: The SOS reinforcement technique provides approximations, not exact solutions. While the approximations converge as the degree increases, there's always a potential gap between the approximated and true optimal values.
  • Computational Complexity: While SDPs are tractable, the computational cost of SOS hierarchies can grow significantly with the degree of the polynomials and the dimension of the state space.
  • Existence of Optimal Trajectories: The paper notes that while the methods can approximate the optimal value, they don't always directly provide the optimal trajectory itself, as the existence of such trajectories is not always guaranteed without further assumptions.
  • Future Work: The authors suggest exploring more advanced aspects like the moment-SOS hierarchy for a more complete picture, and refer readers to other works for deeper dives into specific applications and computational details. They also mention the need for additional constraints and prior knowledge in inverse optimal control to avoid trivial solutions.

Summary updated

Abstract

We propose a tutorial on relaxations and weak formulations of optimal control with their semidefinite approximations. We present this approach solely through the prism of positivity certificates which we consider to be the most accessible for a broad audience, in particular in the engineering and robotics communities. This simple concept allows to express very concisely powerful approximation certificates in control. The relevance of this technique is illustrated on three applications: region of attraction approximation, direct optimal control and inverse optimal control, for which it constitutes a common denominator. In a first step, we highlight the core mechanisms underpinning the application of positivity in control and how they appear in the different control applications. This relies on simple mathematical concepts and gives a unified treatment of the applications considered. This presentation is based on the combination and simplification of published materials. In a second step, we describe briefly relations with broader literature, in particular, occupation measures and Hamilton-Jacobi-Bellman equation which are important elements of the global picture. We describe the Sum-Of-Squares (SOS) semidefinite hierarchy in the semialgebraic case and briefly mention its convergence properties. Numerical experiments on a classical example in robotics, namely the nonholonomic vehicle, illustrate the concepts presented in the text for the three applications considered.
BibTeX
@inproceedings{pauwels2017positivity,
  author = {Edouard Pauwels and Didier Henrion and Jean-Bernard Lasserre},
  title = {{Positivity Certificates in Optimal Control}},
  booktitle = {Geometric and Numerical Foundations of Movements},
  year = {2017},
  url = {https://openreview.net/forum?id=8EwvEMb7U93},
}
Figure