Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

We begin with the Hamilton-Jacobi (HJ) initial value problem

$$\displaystyle{ \left \{\begin{array}{@{}l@{\quad }l@{}} \frac{\partial \varphi } {\partial t}(x,t) + H(\nabla _{x}\varphi (x,t))\; =\; 0\quad &\mbox{ in }\mathbb{R}^{n} \times (0,+\infty ) \\ \varphi (x,0)\; =\; J(x) \quad &\forall x \in \mathbb{R}^{n}.\end{array} \right. }$$
(12.1)

We assume \(J: \mathbb{R}^{n} \rightarrow \mathbb{R}\) is convex and one coercive, i.e., \(\lim _{\|x\|_{2}\rightarrow +\infty }\frac{J(x)} {\|x\|_{2}} = +\infty\), \(H: \mathbb{R}^{n} \rightarrow \mathbb{R}\) is convex and positively one homogeneous (we sometimes relax all these assumptions).

A good example of this is

$$\displaystyle{H(v) =\| v\|_{2}.}$$

Here \(\|v\|_{p} = \left (\varSigma _{i=1}^{n}\vert v_{i}\vert ^{p}\right )^{\frac{1} {p} }\) for p ≥ 1 and 〈x, v〉 = Σ i = 1 n x i v i .

Let us consider a convex Lipschitz function J having the property that, for Ω a convex compact set of \(\mathbb{R}^{n}\)

$$\displaystyle{\left \{\begin{array}{@{}l@{\quad }l@{}} J(x) <0\quad &\mbox{ for any }x\ \in \ \mbox{ int }\varOmega \\ J(x) = 0\quad &\mbox{ for any }x\ \in \ (\varOmega \setminus \mbox{ int }\varOmega ) \\ J(x)> 0\quad &\mbox{ for any }x\ \in \ (\mathbb{R}^{n}\setminus \varOmega ).\end{array} \right.}$$

We call this level set initial data. Then the set of points for which φ(x, t) = 0, t > 0 are exactly those at a distance t, from the boundary of Ω. In fact given \(\bar{x}\ \notin \ \varOmega\), then the closest point x opt from \(\bar{x}\) to (Ω ∖ int Ω) is exactly

$$\displaystyle{ x_{opt}\; =\;\bar{ x} - t \frac{\nabla \varphi (\bar{x},t)} {\|\nabla \varphi (\bar{x},t)\|_{2}}. }$$
(12.2)

To solve (12.1) we use the Hopf formula [5]

$$\displaystyle\begin{array}{rcl} \varphi (x,t) = (J^{{\ast}} + tH)^{{\ast}}(x) = -\min _{ v\in R^{n}}\{J^{{\ast}}(v) + tH(v) -\langle x,v\rangle \},& & {}\\ \end{array}$$

where the Fenchel-Legendre transform \(f^{{\ast}}: \mathbb{R}^{n} \rightarrow R \cup (+\infty )\) of the convex function f is defined by

$$\displaystyle{f^{{\ast}}(v) =\sup _{ x\,\in \,R^{n}}\{\langle v,x\rangle - f(x)\}.}$$

Moreover, for free we get that the minimizer satisfies

$$\displaystyle{ \arg \min _{v\in \mathbb{R}^{n}}\{J^{{\ast}}(v) + tH(v) -\langle x,v\rangle \} = \nabla _{ x}\varphi (x,t). }$$
(12.3)

whenever φ(⋅ , t) is differentiable at x. Let us note here that our algorithm computes φ(x, t) but also ∇ x φ(x, t).

Also, we can use the Hopf-Lax formula [5, 6] to solve (12.1).

$$\displaystyle{ \varphi (x,t) =\min _{z\ \in \ \mathbb{R}^{n}}\left \{J(z) + tH^{{\ast}}\left (\frac{x - z} {t} \right )\right \} }$$
(12.4)

for convex H.

From (12.4) it is easy to show that if we have k different initial value problems i = 1, … k

$$\displaystyle{ \left \{\begin{array}{@{}l@{\quad }l@{}} \frac{\partial \varphi _{i}} {\partial t}(x,t) + H(\nabla _{x}\varphi _{i}(x,t))\; =\; 0,\quad &\mbox{ in }\mathbb{R}^{n} \times (0,+\infty ) \\ \varphi _{i}(x,0)\; =\; J_{i}(x) \quad &\forall x \in \mathbb{R}^{n}\end{array} \right. }$$

with the usual hypotheses, then (12.4) implies, for any \(x\ \in \ \mathbb{R}^{n},\ t> 0\)

$$\displaystyle{\varphi _{i}(x,t) =\min _{z\ \in \ R^{n}}\left \{J_{i}(z) + tH^{{\ast}}\left (\frac{x - z} {t} \right )\right \}.}$$

So

$$\displaystyle{\min _{i=1,k}\varphi _{i}(x,t) =\min _{z\ \in \ R^{n}}\left \{\min _{i=1,\ldots,k}\left \{J_{i}(z) + tH^{{\ast}}\left (\frac{x - z} {t} \right )\right \}\right \}}$$

solves the initial value problem

$$\displaystyle{ \left \{\begin{array}{@{}l@{\quad }l@{}} \frac{\partial \varphi } {\partial t}(x,t) + H(\nabla _{x}\varphi (x,t))\; =\; 0,\quad &\mbox{ in }\mathbb{R}^{n} \times (0,+\infty ) \\ \varphi (x,0)\; =\;\min _{i=1,\ldots,k}J_{i}(x) \quad &\forall x \in \mathbb{R}^{n}. \end{array} \right. }$$
(12.5)

This means that if Ω = ∪ i = 1, …, k Ω i , where each Ω i is compact and convex and may overlap, then we can easily compute the set of all points at distance t from Ω which is exactly the solution to (12.5) where each J i is a level set function for Ω i . Moreover, at every point \(\bar{x}\) outside of \(\bar{\varOmega }\) for which there is one i such that \(\varphi _{i}(\bar{x},t) <\varphi _{i'}(\bar{x},t)\) for any i ≠ i′, then the closest point x opt to \(\bar{x}\) and Ω is again

$$\displaystyle{x_{opt} =\bar{ x} - t \frac{\nabla _{x}\varphi _{i}(\bar{x},t)} {\vert \nabla _{x}\varphi _{i}(\bar{x},t)\vert }.}$$

If there are several i for which \(\varphi _{i}(\bar{x},t)\) is the minimum among all k of them, then ∇ x φ will be “multivalued”, i.e., it will have jumps, but any of the x opt defined above will be a closest point on Ω to \(\bar{x}\).

2 Split Bregman

We solve the optimization problem (12.3) by using the split Bregman algorithm [4, 3, 9] as follows

$$\displaystyle\begin{array}{rcl} v^{k+1}& =& \arg \min _{ v\in \mathbb{R}^{n}}\{J^{{\ast}}(v) -\langle x,v\rangle + \frac{\lambda } {2}\|d^{k} - v - b^{k}\|_{ 2}^{2}\},{}\end{array}$$
(12.6)
$$\displaystyle\begin{array}{rcl} d^{k+1}& =& \arg \min _{ d\in \mathbb{R}^{n}}\left \{tH(d) + \frac{\lambda } {2}\|d - v^{k+1} - b^{k}\|_{ 2}^{2}\right \}{}\end{array}$$
(12.7)
$$\displaystyle\begin{array}{rcl} b^{k+1}& =& b^{k} + v^{k+1} - d^{k+1}.{}\end{array}$$
(12.8)

Here the sequences \((v^{k})_{k\in \mathbb{N}},(d^{k})_{k\in \mathbb{N}}\) both converge to ∇ x φ(x, t). Let us emphasize again that our numerical algorithm not only computes the solution φ(x, t) but also computes ∇ x φ(x, t) when φ(⋅ , t) is differentiable.

Both (12.6) and (12.7), up to change of variables, can be reformulated as finding the unique minimizer of

$$\displaystyle{\arg \min _{w}\left \{\alpha f(w) + \frac{1} {2}\|w - z\|_{2}^{2}\right \}}$$

which is the proximal map of f. Equation (12.6) can be solved if either J ∗ or J have easily computable proximal maps, which often occurs, especially if one of them is smooth.

Equation (12.7) can be easily solved if H(d) = ∥ d ∥ 2 via the shrink2 operator defined by

$$\displaystyle{shrink_{2}(z,\alpha ) = \left \{\begin{array}{@{}l@{\quad }l@{}} \frac{z} {\|z\|_{2}} \max (\|z\|_{2}-\alpha,0)\quad & if \ z\neq 0 \\ 0\qquad \qquad \quad & if \ z = 0 \end{array} \right.}$$

and we have

$$\displaystyle{\arg \min _{w}\left \{\alpha \|w\|_{2} + \frac{1} {2}\|w - z\|_{2}^{2}\right \}\; =\; shrink_{ 2}(z,\alpha )}$$

If H(d) = ∥ d ∥ 1 we use shrink1 operator defined as follows for any i = 1, …, n

$$\displaystyle{\left (shrink_{1}(z,\alpha )\right )_{i} = \left \{\begin{array}{@{}l@{\quad }l@{}} z_{i}-\alpha \quad &if\ z_{i}>\alpha \\ 0 \quad &if\ \vert z_{i}\vert \leq \alpha \\ z_{i}+\alpha \quad &if\ z_{i} <-\alpha \end{array} \right.}$$

and we have

$$\displaystyle{\arg \min _{w}\left \{\alpha \|w\|_{1} + \frac{1} {2}\|w - z\|_{2}^{2}\right \}\; =\; shrink_{ 1}(z,\alpha ).}$$

To solve (12.7) for more general H(d) convex one homogeneous or to find the proximal map for f of that type we use the fact that H ∗ is the characteristic function of a closed convex set \(C \subset \mathbb{R}^{n}\)

$$\displaystyle{H^{{\ast}} = I_{ c}.}$$

By using the Moreau identity [7] we realize that the proximal map of H can be obtained by projecting onto C. To do this projection, we merely solve the eikonal equation with level set initial data for C via split Bregman as above in (12.6), (12.7), (12.8) with H(d) = ∥ d ∥ 2. This is easy using the shrink2 operator. We then use (12.2) to obtain the projection and repeat the entire iteration.

3 Numerical Experiments

Numerical experiments on an Intel Laptop Core i5-5300U running at 2.3 GHz are now presented. We consider diagonal matrices D defined by \(D_{ii} = 1 + \frac{1+i} {n}\) for i = 1, …, n. We also consider matrices A defined by A ii  = 2 for i = 1, …, n and A ij  = 1 for i, j = 1, …, n. Table 12.1 presents the average time (in seconds) to evaluate the solution over 1,000,000 samples (x, t) uniformly drawn in [−10, 10]n × [0, 10]. The convergence is remarkably rapid: 10−6 to 10−8 seconds on a standard laptop, per function evaluation. Figure 12.1 depicts 2-dimensional slices at different times for the (H-J) equation with a weighted ℓ 1 Hamiltonian H = ∥ D ⋅ ∥ 1, initial data \(J = \frac{1} {2}\| \cdot \|_{2}^{2}\) and n = 8.

Fig. 12.1
figure 1

Evaluation of the solution ϕ((x 1, x 2, 0, 0, 0, 0, 0, 0)†, t) of the HJ-PDE with initial data \(J = \frac{1} {2}\| \cdot \|_{2}^{2}\) and Hamiltonian H = ∥ D ⋅ ∥ 1 for (x 1, x 2) ∈ [−20, 20]2 for different times t. Plots for t = 0, 3, 5, 8 and respectively depicted in (a), (b), (c), and (d). The level lines multiple of 10 are superimposed on the plots.

Full size image
Table 12.1 Time results in seconds for the average time per call for evaluating the solution of the HJ-PDE with the initial data \(J = \frac{1} {2}\| \cdot \|_{2}^{2}\), several Hamiltonians and various dimensions n.
Full size table

4 Summary and Future Work

We have derived a very fast and totally parallelizable method to solve a large class of high dimensional, state independent H-J initial value problems. We do this suing the Hopf formula and convex optimization via splitting, which overcomes the “curse of dimensionality”. This is also done without the use of grids or numerical approximations, yielding not only the solution, but also its gradient.

We also, as a step in this procedure, very rapidly compute the projections from a point in \(\mathbb{R}^{n}\), n large, to a fairly arbitrary compact set.

In future work, we expect to extend this set of ideas to nonconvex Hamiltonians, including some that arise in differential games, to new linear programming algorithms, to fast methods for redistancing in level set methods and, hopefully, to a wide class of state dependent Hamiltonians.