# Linear Hamilton Jacobi Bellman Equations in high dimensions

@article{Horowitz2014LinearHJ, title={Linear Hamilton Jacobi Bellman Equations in high dimensions}, author={Matanya B. Horowitz and Anil Damle and Joel W. Burdick}, journal={53rd IEEE Conference on Decision and Control}, year={2014}, pages={5880-5887} }

The Hamilton Jacobi Bellman Equation (HJB) provides the globally optimal solution to large classes of control problems. Unfortunately, this generality comes at a price, the calculation of such solutions is typically intractible for systems with more than moderate state space size due to the curse of dimensionality. This work combines recent results in the structure of the HJB, and its reduction to a linear Partial Differential Equation (PDE), with methods based on low rank tensor… Expand

#### 55 Citations

Efficient Methods for Stochastic Optimal Control

- Mathematics
- 2014

The Hamilton Jacobi Bellman (HJB) equation is central to stochastic optimal control (SOC) theory, yielding the optimal solution to general problems specified by known dynamics and a specified cost… Expand

A Tensor Decomposition Approach for High-Dimensional Hamilton-Jacobi-Bellman Equations

- Computer Science, Mathematics
- ArXiv
- 2019

The proposed method combines a tensor train approximation for the value function together with a Newton-like iterative method for the solution of the resulting nonlinear system, solving Hamilton-Jacobi equations with more than 100 dimensions at modest cost. Expand

Sequential alternating least squares for solving high dimensional linear Hamilton-Jacobi-Bellman equation

- Mathematics, Computer Science
- 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
- 2016

This work resolves the ill-conditioning issue by computing the solution sequentially and introducing boundary condition rescaling, which reduces the condition number of matrices in the ALS-based algorithm. Expand

Tensor Decompositions for High-dimensional Hamilton-Jacobi-Bellman Equations

- Mathematics
- 2019

A tensor decomposition approach for the solution of high-dimensional, fully nonlinear Hamilton-Jacobi-Bellman equations arising in optimal feedback control of nonlinear dynamics is presented. The… Expand

Algorithm for overcoming the curse of dimensionality for certain non-convex Hamilton–Jacobi equations, projections and differential games

- Mathematics
- 2018

Abstract : In this paper, we develop a method for solving a large class of non-convex Hamilton-Jacobi partial differential equations (HJ PDE). The method yields decoupled subproblems, which can be… Expand

Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations

- Mathematics, Computer Science
- J. Comput. Phys.
- 2019

Algorithms to overcome the curse of dimensionality in possibly non-convex state-dependent Hamilton-Jacobi equations (HJ PDEs) arising from optimal control and differential game problems, and elsewhere are developed. Expand

Polynomial Approximation of High-Dimensional Hamilton-Jacobi-Bellman Equations and Applications to Feedback Control of Semilinear Parabolic PDEs

- Mathematics, Computer Science
- SIAM J. Sci. Comput.
- 2018

A procedure for the numerical approximation of high-dimensional Hamilton--Jacobi--Bellman (HJB) equations associated to optimal feedback control problems for semilinear parabolic equations is… Expand

Approximating optimal feedback controllers of finite horizon control problems using hierarchical tensor formats

- Computer Science, Mathematics
- ArXiv
- 2021

A linear error propagation with respect to the time discretization is proved and numerical evidence is given by controlling a diffusion equation with unstable reaction term and an Allen-Kahn equation. Expand

Semiclassical Approximation in Stochastic Optimal Control: I. Portfolio Construction Problem

- Mathematics, Economics
- 2014

This is the first in a series of papers in which we study an efficient approximation scheme for solving the Hamilton-Jacobi-Bellman equation for multi-dimensional problems in stochastic control… Expand

Hopf-type representation formulas and efficient algorithms for certain high-dimensional optimal control problems

- Mathematics
- 2021

Solving high-dimensional optimal control problems and their corresponding Hamilton-Jacobi partial differential equations is an important but challenging problem. In particular, handling optimal… Expand

#### References

SHOWING 1-10 OF 53 REFERENCES

A Curse-of-Dimensionality-Free Numerical Method for Solution of Certain HJB PDEs

- Mathematics, Computer Science
- SIAM J. Control. Optim.
- 2007

This work considers HJB PDEs in which the Hamiltonian takes the form of a (pointwise) maximum of linear/quadratic forms, and obtains a numerical method not subject to the curse of dimensionality. Expand

Semidefinite relaxations for stochastic optimal control policies

- Mathematics, Computer Science
- 2014 American Control Conference
- 2014

This work proposes a new method obtaining approximate solutions to these linear stochastic optimal control (SOC) problems, and a candidate polynomial with variable coefficients is proposed as the solution to the SOC problem. Expand

Numerical Solutions to the Bellman Equation of Optimal Control

- Mathematics, Computer Science
- J. Optim. Theory Appl.
- 2014

A numerical algorithm to compute high-order approximate solutions to Bellman’s dynamic programming equation that arises in the optimal stabilization of discrete-time nonlinear control systems using a patchy technique to build local Taylor polynomial approximations defined on small domains. Expand

Moving least-squares approximations for linearly-solvable stochastic optimal control problems

- Mathematics
- 2011

Nonlinear stochastic optimal control problems are fundamental in control theory. A general class of such problems can be reduced to computing the principal eigenfunction of a linear operator. Here,… Expand

The Geometry of the Solution Set of Nonlinear Optimal Control Problems

- Mathematics
- 2006

In an optimal control problem one seeks a time-varying input to a dynamical systems in order to stabilize a given target trajectory, such that a particular cost function is minimized. That is, for… Expand

Numerical solution of high dimensional stationary Fokker-Planck equations via tensor decomposition and Chebyshev spectral differentiation

- Computer Science, Mathematics
- Comput. Math. Appl.
- 2014

A tensor decomposition approach is combined with Chebyshev spectral differentiation to drastically reduce the number of degrees of freedom required to maintain accuracy as dimensionality increases. Expand

Overapproximating Reachable Sets by Hamilton-Jacobi Projections

- Mathematics, Computer Science
- J. Sci. Comput.
- 2003

This paper devise and implement a method that projects the true reachable set of a high dimensional system into a collection of lower dimensional subspaces where computation is less expensive. Expand

Nonlinear Optimal Control via Occupation Measures and LMI-Relaxations

- Mathematics, Computer Science
- SIAM J. Control. Optim.
- 2008

This work provides a simple hierarchy of LMI- (linear matrix inequality)-relaxations whose optimal values form a nondecreasing sequence of lower bounds on the optimal value of the OCP under some convexity assumptions. Expand

The Convex Geometry of Linear Inverse Problems

- Mathematics, Computer Science
- Found. Comput. Math.
- 2012

This paper provides a general framework to convert notions of simplicity into convex penalty functions, resulting in convex optimization solutions to linear, underdetermined inverse problems. Expand

Linearly-solvable Markov decision problems

- Computer Science, Mathematics
- NIPS
- 2006

A class of MPDs which greatly simplify Reinforcement Learning, which have discrete state spaces and continuous control spaces and enable efficient approximations to traditional MDPs. Expand