ICODE workshop on numerical solution of HJB equations

8 janv. 2020, 09:00 → 10 janv. 2020, 18:00 Europe/Paris

Amphi Turing in Sophie Germain building (Paris Diderot University)

Hasnaa Zidani (ENSTA Paris), Marianne AKIAN (Inria and CMAP), Stephane Gaubert (INRIA and Ecole polytechnique)

Hamilton-Jacobi-Bellman (HJB) equations arise as the dynamic programming equations of deterministic or stochastic optimal control problems. They allow to obtain the global optimum of these problems and to synthesize an optimal feedback control, leading to a solution robust against system perturbations. This is why, although HJB equations suffer from the curse of dimensionality, there remains an important effort for their numerical solution.

 

The aim of the workshop is to gather researchers who work on different numerical methods for  HJB equations or more generally PDE, with the aim to bypass the curse of dimensionality or at least to improve complexity: max-plus or tropical, Monte Carlo, machine learning, fast marching, computational geometry.

The workshop will take place in Amphi Turing of bat. Sophie Germain of Paris Diderot University.

You can find the Programme here and the slides of the talks below.

 

Confirmed list of speakers:

• Yves Achdou, UPMC & Université Paris Diderot
• Guillaume Carlier, Université Paris-Dauphine
• Jerome Darbon, Brown University: slides
• Maurizio Falcone, Universita di Roma La Sapienza: slides
• Roberto Ferretti, Rome tre: slides
• Thomas Gallouët, Inria and Université Paris-Dauphine: slides
• Stéphane Gaubert, Inria & CMAP, École polytechnique, IPP: slides
• Maximilien Germain, EDF R&D & Université Paris Diderot: slides
• Emmanuel Gobet, CMAP, Ecole polytechnique, IPP
• Laura Grigori, Inria & UPMC
• Lars Grüne, Universität Bayreuth: slides
• William McEneaney, University of California San Diego
• Yvon Maday, UPMC: slides
• Quentin Mérigot, Université Paris-Sud: slides
• Jean-Marie Mirebeau, Université Paris-Sud
• Mathias Oster, TU Berlin: slides
• Laurent Pfeiffer, Inria & CMAP, École polytechnique, IPP: slides
• Huyên Pham, Université Paris Diderot
• Luca Saluzzi, GSSI, L’Aquila: slides

 

Organizing and Scientific Committee:

• Marianne Akian, Inria & CMAP
• Frédéric Bonnans, Inria & CMAP
• Stéphane Gaubert, Inria & CMAP
• Quentin Mérigot, Université Paris-Sud
• Jean-Marie Mirebeau, Université Paris-Sud
• Hasnaa Zidani, ENSTA Paris
• Olivier Bokanowski, Université Paris Diderot

 

---

---

Programme

Slides

• Jerome_Darbon-slides.pdf
• Lars_Gruene-slides.pdf
• Laurent_Pfeiffer-slides.pdf
• Luca_Saluzzi-slides.pdf
• Mathias_Oster-slides.pdf
• Maurizio_Falcone-slides.pdf
• Maximilien_Germain-slides.pdf
• Quentin_Merigot-slides.pdf
• Roberto_Ferretti-slides.pdf
• Stephane_Gaubert-slides.pdf
• Thomas_Gallouet-slides.pdf
• Yvon_Maday-slides.pdf

mercredi 8 janvier

09:30 Introduction

1 Some Approaches to Complexity Reduction: Application to Computational Chemistry

Abstract: Complexity reduction methods for the numerical simulation of partial differential equations have reached a level of maturity that allows their use for the solution of large parameterized problems in which the number of dimensions is very large.
In this short talk I will give some examples of complexity reduction methods such as reduced base methods, PGD methods ... which allow to propose approximations of the solution in very short times.
To be fully usable, these approaches must be combined with error estimators that allow to quantify the error and to check their accuracy.
I will give some ideas on the use of these approaches for problems typical of computational numerical chemistry.

Orateur: Yvon Maday (UPMC)

10:30 Coffee break

2 Some machine learning schemes for high-dimensional non linear PDEs

Orateur: Huyên Pham (Paris Diderot University)

3 Optimal control of conditioned processes

Abstract: We consider a class of closed loop stochastic optimal control problems in finite time horizon, in which the cost is an expectation conditional on the event that the process has not exited a given bounded domain. An important difficulty is that the probability of the event that conditionates the strategy decays as time grows. The optimality conditions consist of a system of partial differential equations, including a Hamilton-Jacobi-Bellman equation (backward w.r.t. time) and a (forward w.r.t. time) Fokker-Planck equation for the law of the conditioned process. The two equations are supplemented with Dirichlet conditions.
Next, we discuss the asymptotic behavior as the time horizon tends to $+\infty$. This leads to a new kind of optimal control problem driven by an eigenvalue problem related to a continuity equation with Dirichlet conditions on the boundary. We prove existence for the latter.
We also propose numerical methods and supplement the various theoretical aspects with numerical simulations.

This is a joint work with M. Laurière (Princeton) and P-L Lions (Collège de France). The topic was introduced by P-L Lions in his lectures in Collège de France in 2016, and there is a preprint "Optimal control of conditioned processes with feedback controls." arXiv preprint arXiv:1912.08738 (2019)

Orateur: Yves Achdou (UPMC & Université Paris Diderot)

12:40 Lunch

4 Taylor expansions of the value function associated with stabilization problems

Abstract: We propose to approximate the value function of a nonlinear stabilization problem with a Taylor expansion around the equilibrium point. For such problems, it can be shown that the second-order derivative of the value function is the solution to an algebraic Riccati equation and that all derivatives of order greater or equal to 3 are solutions to well-posed linear equations. Some theoretical and numerical results for the resulting feedback laws will be presented for a control problem of the Fokker-Planck equation.

Orateur: Laurent Pfeiffer (Inria & CMAP, École polytechnique, IPP)

5 Numerical resolution of McKean-Vlasov FBSDEs using neural networks

Abstract: We propose several algorithms to solve McKean-Vlasov Forward Backward Stochastic Differential Equations. Our schemes rely on the approximating power of neural networks to estimate the solution or its gradient through minimization problems. As a consequence, we obtain methods able to tackle both mean field games and mean field control problems in high dimension. We analyze the numerical behavior of our algorithms on several examples including non linear quadratic models. This is a joint work with Joseph MIKAEL (EDF R&D) and Xavier WARIN (EDF R&D, FIME).

Orateur: Maximilien Germain (EDF R&D and Université Paris Diderot )

15:30 Coffee break

6 A variational finite volume scheme for Wasserstein gradient flows

Abstract: The talk will propose a variational finite volume scheme to approximate the solutions to Wasserstein gradient flows. The time discretization is based on an implicit linearization of the Wasserstein distance expressed thanks to Benamou-Brenier formula, whereas space discretization relies on upstream mobility two-point flux approximation finite volumes. The scheme is based on a first discretize then optimize approach in order to preserve the variational structure of the continuous model at the discrete level.

Join work with Clément Cancès and Gabriele Todeschi

Orateur: Thomas Gallouët (Inria and Université Paris-Dauphine)

7 Convergence rates for discretized optimal transport problems

Orateur: Quentin Mérigot (Université Paris-Sud)

jeudi 9 janvier

8 Fundamental Solutions of Nonlinear Hamilton-Jacobi PDEs

Abstract: We consider nonlinear control problems of both deterministic and stochastic type. In the latter class, we consider only the case of dynamics driven by Brownian motion. We seek fundamental solutions of the associated Hamilton-Jacobi PDE problems, where here, these are defined to be solutions such that changes in the terminal-cost data require only a stat-convolution of the fundamental solution with an object determined by the specific terminal-cost data. The fundamental solutions are generated by solution of first-order Hamilton-Jacobi PDE problems over a certain dual space.

Orateur: William McEneaney (University of California, San Diego)

10:20 Coffee break

9 Sensitivity and turnpike results for the optimal control of PDEs and their use for model predictive control

Abstract: Model predictive control (MPC) is a popular control method, in which a feedback control is computed from the successive numerical solution of optimal control problems. For large scale systems including numerically discretized PDEs this method is computationally challenging, because the optimal control problems must be solved within one sampling period, i.e., in a potentially relatively short time.
A particular feature of MPC is that typically the optimal control problems are solved on overlapping horizons, implying that only a small portion of the computed optimal control function is actually used. This suggests that an adapted discretization in time and/or space may offer a large benefit for MPC of PDEs. In this talk we first explain the theoretical justification of this approach based on novel sensitivity and turnpike results for the optimal control of general evolution equations. Then the efficiency of the proposed method is illustrated by numerical experiments.
The talk is based on joint work with Manuel Schaller and Anton Schiela (both University of Bayreuth).

Orateur: Lars Grüne (Universität Bayreuth)

10 Overcoming the curse of dimensionality for some Hamilton-Jacobi partial differential equations via neural network architectures

Abstract: We propose new and original mathematical connections between Hamilton-Jacobi (HJ) partial differential equations (PDEs) with initial data and neural network architectures. Specifically, we prove that some classes of neural networks correspond to representation formulas of HJ PDE solutions whose Hamiltonians and initial data are obtained from the parameters of the neural networks. These results do not rely on universal approximation properties of neural networks; rather, our results show that some classes of neural network architectures naturally encode the physics contained in some HJ PDEs. Our results naturally yield efficient neural network-based methods for evaluating solutions of some HJ PDEs in high dimension without using grids or numerical approximations. We also present some numerical results for solving some inverse problems involving HJ PDEs using our proposed architectures.
This is a joint work with Gabriel P. Langlois and Tingwei Meng.

Orateur: Jerome Darbon (Brown University)

12:30 Lunch

11 A discrete time Dynamic Programming approach on a tree structure for finite horizon optimal control problem

Abstract: The classical Dynamic Programming (DP) approach to optimal control problems is based on the characterization of the value function as the unique viscosity solution of a Hamilton-Jacobi-Bellman (HJB) equation. The DP scheme for the numerical approximation of viscosity solutions of those equations is typically based on a time discretization which is projected on a fixed space triangulation of the numerical domain. The time discretization can be done by a one-step scheme for the dynamics and the projection on the grid typically uses a polynomial interpolation. This approach, which allows to get information on optimal controls in feedback form, works in any dimension although its practical application has been limited to rather low dimensional problems. Several methods have been proposed to mitigate the curse of dimensionality of DP schemes, e.g. static and dynamic domain decomposition, fast-marching and fast-sweeping methods and discrete
representation formulas.
We will discuss a new approach for ?nite horizon optimal control problems where we compute the value function on a tree structure constructed directly by the time discrete dynamics and we do not use a space discretization to solve the HJB equation. This allows to drop the cost of space interpolation, moreover the tree will guarantee a perfect matching with the discrete dynamics. We prove convergence and a-priori error estimates. In the simple case, we discretize the dynamics with an Euler scheme and we will prove first order convergence to the value function in the framework of viscosity solutions. We will also discuss how this approach can be extended to high-order schemes, show some examples of second order approximation schemes and applications to the control of evolutive PDEs.
Based on joint works with Alessandro Alla (PUC, Rio de Janeiro) and Luca Saluzzi (Gran Sasso Science Institute, L'Aquila, Italy).

Orateur: Maurizio Falcone (Universita di Roma La Sapienza)

single_abstract_Falcone.pdf

12 A HJB-POD approach for the control of nonlinear PDEs on a tree structure

Orateur: Luca Saluzzi (Gran Sasso Science Institute, L’Aquila)

15:25 Coffee break

13 Dynamic programming operators over noncommutative spaces: an approach to optimal control of switched systems

Abstract: McEneaney’s max-plus basis method allows one to approximate the value function of a deterministic optimal control problem by a supremum of elementary functions like quadratic forms. Recently, Ahmadi et al. developed an approximation method for Barabanov norms of switched linear systems, relying also on the approximation by suprema of quadratic forms. Related methods were developed in computer science, they allow one to compute program invariants, represented as intersections or unions or ellipsoids. In all these approaches, the solution of large scale linear matrix inequalities by semidefinite programming methods is the computational bottleneck. We will show that the recourse to semidefinite programming can be avoided by expressing piecewise quadratic invariant generation and value function approximation as a fixed point problem in the space of positive semidefinite matrices.
To do so, we introduce “noncommutative” analogues of Bellman operators, acting on spaces of matrices, instead of spaces of functions. The minima and maxima of functions are now replaced by selections of minimal upper bounds and maximal upper bounds, with respect to the Loewner order. By a theorem of Kadison, such selections are not unique. They are also not order preserving. However, the Bellman type operators which arise in this way retain a remarkable structure. Indeed, they appear as the tropicalizations of the completely positive maps representing quantum channels, and the convergence of numerical schemes can be established by exploiting metric properties of the cone of positive definite matrices. This allows us to obtain relaxed solutions for very large scale instances (e.g., approximations of the joint spectra radius in dimension 500). We finally refine this approach in the special case of positive switched linear systems; then, the tropical Kraus map is replaced by a risk sensitive ergodic operator, whose eigenvalue bounds the joint spectral radius.
This is a joint work with Nikolas Stott.

Orateur: Stéphane Gaubert (Inria and CMAP, Ecole polytechnique,IPP)

vendredi 10 janvier

14 Regression Monte Carlo methods for HJB type equations: which approximation space?

Abstract: Regression-based methods constitute a standard approach to solve dynamic programming stochastic equations. Their theoretical accuracies can be quantified in terms of local approximation errors, statistical errors and propagation errors. There is an subtle interplay between these three sources of error, which should lead to determine well the approximation space according to the sampling effort. In this talk, I will discuss
- the pros/cons of using Discontinuous Galerkin type space and Neural Network approximation spaces;
- statistical learning results to adaptively choose the approximation space.

Orateur: Emmanuel Gobet (CMAP, École polytechnique, IPP)

10:20 Coffee break

15 Quadratic mean-field games and entropy minimization

Abstract: It is well-known since the seminal work of Lasry and Lions that a large class of MFG can be seen as the optimality system for an optimal control problem for the Fokker-Planck equation. In this talk, in the case of a quadratic Hamiltonian, I will describe an alternative (Lagrangian) formulation which can be viewed as an entropy minimization at the level of measures on trajectories. This formulation is reminiscent of the Schrödinger bridge problem and can lead to numerical methods thanks to the celebrated Sinkhorn algorithm. I will also sketch connections with incompressible flows. The talk will be based on joint works with J.-D. Benamou, S. Di Marino and L. Nenna.

Orateur: Guillaume Carlier (U. Dauphine)

16 An overview of recent algorithms for computing low rank approximations of matrices and tensors

Abstract: In this talk we will discuss recent approaches for dealing with large volumes of data by exploiting data sparsity, which allows data to be compressed without significant loss of information. We discuss first recent algorithms for computing the low rank approximation of a matrix based on deterministic or randomized approaches, that are able to minimize communication on a parallel computer.

We discuss then the approximation of data in larger dimensions which is represented by tensors, or multilinear arrays. We discuss a numerical method to compress a tensor by constructing a piece-wise tensor approximation. This is defined by partitioning a tensor into sub-tensors and by computing a low-rank tensor approximation (in a given format) in each sub-tensor. Neither the partition nor the ranks are fixed a priori, but, instead, are obtained in order to fulfill a prescribed accuracy and optimize, to some extent, the storage. The different steps of the method are detailed and some numerical experiments that consider the Coulomb and the Gibbs potential are proposed to assess its performances.
This work on tensors is joint work with V. Ehrlacher and D. Lombardi.

Orateur: Laura Grigori (Inria et UPMC)

12:30 Lunch

17 Route Planning Problems and Hybrid Control

Abstract: In its simplest formulation, the so-called "route planning problem" for sailing boats consists in minimizing the expected time to reach a given target for a vessel sailing in a partly stochastic wind field. A change of direction (especially when tacking) might be associated to a time loss, which is in fact a crucial point in short-course races. This transition cost makes it natural to formulate the problem in term of stochastic hybrid control. In this talk, we will discuss a detailed hybrid model to formulate the optimal route planning in the case of both fleet races and match races, provide a convergent numerical approximation and present an efficient solver of "fast sweeping" type.
We will also show numerical examples in perfect agreement with the heuristically known features of the optimal strategy.
This is a joint work with Simone Cacace and Adriano Festa.

Orateur: Roberto Ferretti (Rome tre)

18 Approximating the Stationary Hamilton-Jacobi-Bellman Equation by Hierarchical Tensor Products

Abstract: We treat infinite horizon optimal control problems by solving the associated stationary Hamilton-Jacobi-Bellman (HJB) equation numerically, for computing the value function and an optimal feedback area law. The dynamical systems under consideration are spatial discretizations of nonlinear parabolic partial differential equations (PDE), which means that the HJB is suffering from the curse of dimensionality.

Orateur: Mathias Oster (TU Berlin)

15:25 Coffee break

19 Eulerian Fast-Marching methods for seismic traveltime computation

The fast marching method (Sethian 1996), is a finite difference scheme for the (standard isotropic) eikonal PDE, written in Eulerian coordinates and benefiting from the appealing property of causality : it can be numerically solved in a single pass over the domain, using an adequate ordering of the nodes determined at run time. Non-isotropic eikonal equations however arise in a variety of contexts, such as motion planning, geometry processing, or traveltime tomography, and their discretization often involves more complex and costly multi-pass schemes, of semi-Lagrangian or Lagrangian type. In this talk, I will present single-pass Eulerian finite difference schemes for some non-isotropic eikonal equations, of Riemannian class and of a Finslerian class characterising seismic traveltimes.

Orateur: Jean-Marie Mirebeau (Paris-Sud University)