An Adaptive Multi-Level Max-Plus Method for Deterministic Optimal Control Problems

MaRDI QIDQ6433759zbMATH OpenFDO

Authors Marianne Akian, Stéphane Gaubert, Shanqing Liu

Publication date 20 April 2023

Abstract: We introduce a new numerical method to approximate the solution of a finite horizon deterministic optimal control problem. We exploit two Hamilton-Jacobi-Bellman PDE, arising by considering the dynamics in forward and backward time. This allows us to compute a neighborhood of the set of optimal trajectories, in order to reduce the search space. The solutions of both PDE are successively approximated by max-plus linear combinations of appropriate basis functions, using a hierarchy of finer and finer grids. We show that the sequence of approximate value functions obtained in this way does converge to the viscosity solution of the HJB equation in a neighborhood of optimal trajectories. Then, under certain regularity assumptions, we show that the number of arithmetic operations needed to compute an approximate optimal solution of a $d$-dimensional problem, up to a precision $varepsilon$, is bounded by $O(C^d(1/varepsilon))$, for some constant $C>1$, whereas ordinary grid-based methods have a complexity in$O(1/varepsilo{n}^{ad}$) for some constant $a>0$.

This page was built for publication: An Adaptive Multi-Level Max-Plus Method for Deterministic Optimal Control Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433759)