Dynamic programming is one of the main approaches to solve optimal control problems. It reduces the latter to Hamilton-Jacobi Partial Differential Equations (HJ PDE). Several techniques have been proposed in the literature to solve these PDE. We mention, for example, finite difference schemes, the so-called discrete dynamic programming method or semi-Lagrangian method, or the antidiffusive schemes. All these methods are grid-based, i.e., they require a discretization of the state space, and thus suffer from the so-called curse of dimensionality. The recently developed max-plus numerical methods for solving HJ PDE do not require a direct discretization of the state space, and therefore allow to solve some structured instances in which the state dimension is larger than 3. The presentation focuses on max-plus numerical solutions and convergence analysis for medium to high dimensional deterministic optimal control problems.
We first review the general principle of max-plus basis methods and present a negative result, showing that some form of curse dimensionality is unavoidable for these methods, but also for more classical approximate dynamic programming methods like stochastic dual dynamic programming, in which a convex value function is approximated by a supremum of affine functions. Then, we will present the curse of dimensionality free method originally introduced by McEneaney, and featured by its cubic growth complexity on the state dimension. This method applies to the class of infinite horizon switching optimal control problems with Hamiltonian given or approximated by the supremum of quadratic affine functions. However, the number of basis functions which are generated is a power of the number of switches, and this power grows quickly as the required precision increases. This is referred to as a curse of complexity, reducible by a pruning procedure. We present a refined pruning algorithm and an improved theoretical estimate of execution time with respect to the required accuracy. Finally we introduce a new max-plus based randomized algorithm, based on different principles, which provides a speedup between 10 and 100 (on instances of dimension from 4 to 15), compared to McEneaney's curse of dimensionality free method.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
