I've been told that HJB equations can be solved numerically. I know very little about the subject, could someone provide a couple of comments or a reference (ideally, one that is accessible for a layman) on:
- What are the main numerical methods used and, roughly, how do they work?
- What are the limitations of the methods? For example, does the complexity scale badly with dimension?
There are several approaches (I suppose you need to solve HJB for optimal control purposes)
A) Level sets methods which uses some theoretical information about system dynamics.
E.g. ellipsoidal approximations method. It is relatively simple to implement and has polynomial computational cost, but this method is applicable only for linear systems (see the Ellipsoidal toolbox for MATLAB on GitHub)
For nonlinear systems there is a comparison principle, but using of this method on practice faces with complications.
Dynamics and control of trajectory tube. Kurzhanski, Varaiya. Also several papers (on russian) about application of this principle to bilinear and other systems exist.
B) Level set methods by Mitchell. Applicable to nonlinear systems, feasable up to 5 dimensions problem (see the Level Set Methods Toolbox for MATLAB)
C) There is also one new method I know: viability sets approximation using support vectors. This method has surprisingly low computational complexity, but there is no open source implementation (as I know).
D) Max-plus methods (see the McEneaney's papers)
E) Finite-difference and semi-Lagrangian schemes (see the ROC-HJ software)
F) A bunch of methods which eliminate curse of dimensionality by decomposition/projection/approximation/etc of the original system. E.g. tensor decomposition, Schur decomposition, reachability set projection.