Positivity certificates in optimal control

Edouard Pauwels, Didier Henrion, Jean B. Lasserre

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 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.

Introduction

Optimal control is a cornerstone of modern robotics and engineering, yet solving it for nonlinear systems remains a formidable challenge. The core difficulty typically involves finding a "value function"—the minimum cost-to-go from any given state. In nonlinear settings, this function is often non-smooth and mathematically complex, causing traditional methods like the Hamilton-Jacobi-Bellman (HJB) partial differential equations to hit computational or regularity walls.

This paper bridges the gap between abstract mathematical theory and practical engineering by introducing a unified numerical framework based on "positivity certificates." By reframing control challenges as semidefinite programs, we provide a tractable approach to three distinct tasks: approximating the Region of Attraction (ROA), solving direct optimal control, and performing inverse optimal control.

The Weak Formulation and Positivity Certificates

The methodology centers on the "weak formulation" of optimal control. Rather than searching for a single optimal trajectory, we look at functional positivity constraints. The fundamental insight is that if a "surrogate" function satisfies specific inequalities related to the system's dynamics and costs, it acts as a certified lower or upper bound on the true value function.

Sum-of-Squares (SOS) and Semidefinite Programming

Checking if a general function is positive everywhere is an NP-hard problem. To make this computationally feasible, we restrict our search to Sum-of-Squares (SOS) polynomials. If a polynomial can be expressed as a sum of squared terms, it is guaranteed to be non-negative. This restriction allows us to transform complex control problems into Semidefinite Programs (SDP)—a class of convex optimization problems that can be solved efficiently using standard numerical software.

To ensure accuracy, we utilize the Lasserre Hierarchy. By increasing the degree of the SOS polynomials, the numerical solution is guaranteed to converge toward the true global optimum, providing a systematic way to refine approximations.

A Unified Framework for Control Applications

A key contribution of this work is demonstrating that ROA, direct control, and inverse control are essentially the same mathematical problem viewed from different angles, all sharing the same core positivity constraints.

  1. Region of Attraction (ROA): The goal is to find the set of initial states from which a system can reach a target. The SOS framework allows us to compute "outer approximations" of this set that grow increasingly tight as the polynomial degree increases.
  2. Direct Optimal Control: Here, we seek the best trajectory and its associated cost. The framework provides global lower bounds on the cost, offering a "quality check" for any specific trajectory.
  3. Inverse Optimal Control: In this scenario, the trajectories are known, but the underlying cost function (Lagrangian) is not. The SOS framework handles this by swapping the knowns and unknowns in the optimization, allowing us to infer the cost function that makes the observed behavior optimal.

Numerical Illustration: Brockett’s Integrator

We evaluated these methods using Brockett’s Integrator, a classic 3-dimensional nonlinear system modeling a nonholonomic vehicle (e.g., a car that cannot move sideways). This benchmark serves as a non-trivial test case to compare SOS approximations against known analytical solutions.

  • ROA Accuracy: For the nonholonomic vehicle, increasing the SOS polynomial degree from $d=6$ to $d=10$ resulted in significantly tighter outer approximations of the true region of attraction.
  • Performance Bounds: In minimum-time control tests, the SOS reinforcement provided lower bounds remarkably close to exact values. For instance, the SOS estimate reached 1.7979 against an exact analytical value of 1.8257.
  • Cost Recovery: Inverse control experiments successfully recovered the original cost function from optimal trajectories, provided that regularization was applied to prevent trivial solutions (such as a zero cost function).

Discussion and Limitations

While the SOS-SDP framework is powerful, it faces the "curse of dimensionality." The number of variables in an SOS program grows rapidly with the number of system states and the polynomial degree, making it challenging to scale to high-dimensional systems like humanoid robots. Additionally, the framework currently assumes polynomial dynamics and costs.

Furthermore, inverse optimal control remains numerically sensitive; small errors in input trajectories can lead to large errors in the inferred cost. Future work will focus on extending these positivity certificates to non-polynomial or hybrid systems and improving the robustness of the inverse formulation through sparsity-enforcing priors.

Conclusion

By focusing on positivity certificates, we provide a simplified yet rigorous path to solving complex nonlinear control problems. This unified treatment not only clarifies the relationships between different control tasks but also provides engineers with a robust set of tools for certification and optimization in robotics.

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 B. Lasserre},
  title = {{Positivity certificates in optimal control}},
  booktitle = {Geometric and Numerical Foundations of Movements},
  year = {2017},
  url = {https://openreview.net/forum?id=8EwvEMb7U93},
}
Figure