The Max-Plus Finite Element Method for Solving Deterministic Optimal Control Problems: Basic Properties and Convergence Analysis

Marianne Akian, Stephane Gaubert, Asma Lakhoua

TL;DR

This paper introduces a novel "max-plus finite element method" (MFEM) for solving deterministic optimal control problems with finite horizons. The MFEM offers a systematic way to approximate the value function, providing convergence guarantees and error estimates that are competitive with existing methods, particularly for problems where the value function might be non-smooth.

What Problem Does This Paper Address?

Deterministic optimal control problems, often formulated as Hamilton-Jacobi-Bellman (HJB) equations, are fundamental in many fields like economics, engineering, and robotics. Finding the exact solution (the value function) can be computationally challenging, especially in higher dimensions or when the value function is not smooth. While various numerical methods exist (finite differences, semi-Lagrangian methods, etc.), this paper focuses on extending the power of max-plus algebra, which has shown promise for these types of problems, by developing a finite element approach within this framework. The goal is to leverage the structural properties of max-plus algebra to create a robust and accurate numerical solver.

Methods

The core of the paper is the development of the "max-plus finite element method" (MFEM). This method builds upon the max-plus algebra, where addition is replaced by the maximum operation and multiplication by addition.

Key methodological contributions include:

  • Max-Plus Variational Formulation: Adapting the concept of variational formulation from classical finite element methods to the max-plus setting. This involves defining a "weak" formulation of the HJB equation using max-plus scalar products.
  • Finite Elements and Test Functions: The MFEM approximates the value function using a linear combination of "finite elements" (basis functions) within a max-plus semimodule. A separate set of "test functions" is used to enforce the variational formulation. The choice of these functions (e.g., quadratic or Lipschitz) is crucial for convergence.
  • Projection-Based Approximation: The method relies heavily on the concept of projectors in max-plus semimodules. These projectors are used to approximate the value function and to derive error estimates, analogous to orthogonal projectors in classical finite element methods.
  • Approximation of the Semigroup: The paper proposes two ways to approximate the action of the evolution semigroup (Lax-Oleinik semigroup) on finite elements, using the Hamiltonian. This is a key step for practical implementation.
  • Convergence Analysis: Rigorous mathematical analysis is provided to bound the error between the true value function and its approximation. This includes deriving error estimates in terms of the time and space discretization steps.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical examples with analytically known solutions.

Key Insights and Ideas

  • Max-Plus Algebra for Optimal Control: The paper demonstrates that max-plus algebra, with its unique properties (idempotent addition, associative multiplication), provides a powerful framework for analyzing and solving optimal control problems, especially those involving Hamilton-Jacobi equations.
  • Finite Element Analogy: The MFEM successfully translates the well-established finite element method into the max-plus domain, offering a systematic way to construct approximations and analyze errors.
  • Projection Errors as Error Bounds: A key insight is that the error in the MFEM can be understood and bounded in terms of "projection errors" onto specific semimodules. This provides a geometric interpretation of the approximation quality.
  • Handling Non-Smoothness: The method is designed to handle cases where the value function might not be smooth, which is a common challenge in optimal control. The choice of test functions plays a critical role here.
  • Connection to Game Theory: The recursive update for the coefficients in the MFEM can be interpreted as a dynamic programming equation for a deterministic zero-sum two-player game, offering an alternative perspective.

Key Results

  • Convergence Guarantees: The paper establishes convergence results for the MFEM, showing that the approximation converges to the true value function as the discretization steps (time and space) go to zero.
  • Error Estimates: Specific error estimates are derived. For a class of problems, the error is shown to be of order $\delta + \Delta x(\delta)^{-1}$ or $\sqrt{\delta} + \Delta x(\delta)^{-1}$, where $\delta$ is the time step and $\Delta x$ is the space discretization step. These estimates are competitive with existing methods.
  • Numerical Examples: The paper presents numerical experiments in dimensions 1 and 2, demonstrating the method's effectiveness on various problems, including those with known analytical solutions and those that do not strictly satisfy all assumptions. The numerical results generally align with the theoretical error bounds.

Limitations and Future Work

  • Computational Cost: The paper notes that the computation of the matrices $M_h$ and $K_h$ can be computationally intensive, especially for higher dimensions or a large number of discretization points. This limits the scalability of the current implementation.
  • Higher-Dimensional Examples: The authors suggest that for higher-dimensional examples, higher-order approximations might be necessary, especially if the value function is sufficiently regular. This is identified as an area for future work.
  • Assumptions: While the method is shown to work even when some assumptions are not strictly met, the theoretical guarantees are strongest when standard assumptions (e.g., Lipschitz continuity of dynamics and cost) hold.
  • Choice of Finite Elements and Test Functions: The performance and error bounds are sensitive to the choice of finite elements and test functions. Further research could explore optimal choices for different problem classes.

Summary updated

Abstract

We introduce a max-plus analogue of the Petrov-Galerkin finite element method to solve finite horizon deterministic optimal control problems. The method relies on a max-plus variational formulation. We show that the error in the sup norm can be bounded from the difference between the value function and its projections on max-plus and min-plus semimodules, when the max-plus analogue of the stiffness matrix is exactly known. In general, the stiffness matrix must be approximated: this requires approximating the operation of the Lax-Oleinik semigroup on finite elements. We consider two approximations relying on the Hamiltonian. We derive a convergence result, in arbitrary dimension, showing that for a class of problems, the error estimate is of order $δ+Δx(δ)^{-1}$ or $\sqrtδ+Δx(δ)^{-1}$, depending on the choice of the approximation, where $δ$ and $Δx$ are respectively the time and space discretization steps. We compare our method with another max-plus based discretization method previously introduced by Fleming and McEneaney. We give numerical examples in dimension 1 and 2.
BibTeX
@article{akian2008max,
  author = {Marianne Akian and Stephane Gaubert and Asma Lakhoua},
  title = {{The Max-Plus Finite Element Method for Solving Deterministic Optimal Control Problems: Basic Properties and Convergence Analysis}},
  journal = {SIAM J. Control. Optim.},
  year = {2008},
  url = {https://openreview.net/forum?id=WgfmQS129m},
}
Figure