TY - GEN
T1 - Curse-of-complexity attenuation in the curse-of-dimensionality-free method for HJB PDEs
AU - McEneaney, William M.
AU - Deshpande, Ameet
AU - Gaubert, Stephane
PY - 2008/1/1
Y1 - 2008/1/1
N2 - Recently, a curse-of-dimensionality-free method was developed for solution of Hamilton-Jacobi-Bellman partial differential equations (HJB PDEs) for nonlinear control problems, using semiconvex duality and max-plus analysis. The curse-of-dimensionality-free method may be applied to HJB PDEs where the Hamiltonian is given as (or well-approximated by) a pointwise maximum of quadratic forms. Such HJB PDEs also arise in certain switched linear systems. The method constructs the correct solution of an HJB PDE from a maxplus linear combination of quadratics. The method completely avoids the curse-of- dimensionality, and is subject to cubic computational growth as a function of space dimension. However, it is subject to a curse-of-complexity. In particular, the number of quadratics in the approximation grows exponentially with the number of iterations. Efficacy of such a method depends on the pruning of quadratics to keep the complexity growth at a reasonable level. Here we apply a pruning algorithm based on semidefinite programming. Computational speeds are exceptional, with an example HJB PDE in six-dimensional Euclidean space solved to the indicated quality in approximately 30 minutes on a typical desktop machine.
AB - Recently, a curse-of-dimensionality-free method was developed for solution of Hamilton-Jacobi-Bellman partial differential equations (HJB PDEs) for nonlinear control problems, using semiconvex duality and max-plus analysis. The curse-of-dimensionality-free method may be applied to HJB PDEs where the Hamiltonian is given as (or well-approximated by) a pointwise maximum of quadratic forms. Such HJB PDEs also arise in certain switched linear systems. The method constructs the correct solution of an HJB PDE from a maxplus linear combination of quadratics. The method completely avoids the curse-of- dimensionality, and is subject to cubic computational growth as a function of space dimension. However, it is subject to a curse-of-complexity. In particular, the number of quadratics in the approximation grows exponentially with the number of iterations. Efficacy of such a method depends on the pruning of quadratics to keep the complexity growth at a reasonable level. Here we apply a pruning algorithm based on semidefinite programming. Computational speeds are exceptional, with an example HJB PDE in six-dimensional Euclidean space solved to the indicated quality in approximately 30 minutes on a typical desktop machine.
U2 - 10.1109/ACC.2008.4587234
DO - 10.1109/ACC.2008.4587234
M3 - Conference contribution
AN - SCOPUS:52449083909
SN - 9781424420797
T3 - Proceedings of the American Control Conference
SP - 4684
EP - 4690
BT - 2008 American Control Conference, ACC
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2008 American Control Conference, ACC 2008
Y2 - 11 June 2008 through 13 June 2008
ER -