### Zheng Qu (University of Edinburgh)

#### Max-plus numerical methods for Hamilton-Jacobi equations: attenuation of the curse of dimensionality

*Wednesday 5 March 2014 at 15.30, JCMB 6206*

##### Abstract

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.

### Seminars by year

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*