©2021 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works.

This work has been submitted to the IEEE for possible publication. Copyright
may be transferred without notice, after which this version may no longer be
accessible.

# Lax Formulae for Efficiently Solving Two Classes of State-Constrained
Optimal Control Problems

Donggun Lee  Student Member, IEEE  and Claire J. Tomlin  Fellow, IEEE This
research is supported by ONR under the BRC program in multibody control
systems, by DARPA under the Assured Autonomy program, and by NSF grant
#1837244.Donggun Lee is with the Department of Mechanical Engineering,
University of California, Berkeley, USA<EMAIL_ADDRESS>J.
Tomlin is with the Department of Electrical Engineering and Computer Sciences,
University of California, Berkeley, USA<EMAIL_ADDRESS>
###### Abstract

This paper presents Lax formulae for solving the following optimal control
problems: minimize the maximum (or the minimum) cost over a time horizon,
while satisfying a state constraint. We present a viscosity theory, and by
applying the theory to the Hamilton-Jacobi (HJ) equations, these Lax formulae
are derived. A numerical algorithm for the Lax formulae is presented: under
certain conditions, this algorithm’s computational complexity is polynomial in
the dimension of the state. For each class of optimal control problem, an
example demonstrates the use and performance of the Lax formulae.

##  1 Introduction

This paper presents Lax formulae for two classes of optimal control problems,
in which an optimal control signal is specified to minimize the maximum (or
the minimum) cost over a time horizon subject to a state constraint. In the
two classes of problems, terminal time maximizes (or minimizes) cost, and both
a control signal and the terminal time must be determined. The two classes of
problems can be solved by the Hamilton-Jacobi (HJ) equations in [1] and [2].
The HJ equations are, in general, computed by grid-based methods (such as
level-set methods and fast marching method [3]), which require spatial
discretization, and computational complexity is exponential in the dimension
of the system’s state. It is intractable to compute the solution to the HJ
equations using the grid-based methods for high dimensional systems.

Lax and Hopf theory specify an optimization problem that solves HJ equations
under particular conditions [4, 5, 6, 7]. The optimization problem from Lax
and Hopf theory is computed by gradient-based methods based on temporal
discretization, which allows the computational complexity to be polynomial in
the dimension of the state. Lax formulae assume that the Hamiltonian is convex
in the costate, on the other hand, Hopf formulae assume that the terminal cost
is convex in the state. Lax and Hopf formulae have been investigated for
optimal control problems or zero-sum games, where the cost is the integration
of the stage cost and the terminal cost, and the terminal time is a fixed
constant. On the other hand, in the two classes of problems in this paper, the
terminal time is not fixed but need to be specified.

The initial version of the Lax formula and Hopf formula were presented in [8,
9, 5] for particular state-unconstrained problems: in these, the Hamiltonian
only depends on the costate, implying the dynamics of the system and the stage
cost only depend on the control input. Bardi and Evans [5] first proved these
initial version of the Lax and Hopf formulae in a sense of viscosity theory of
partial differential equations (PDEs). The Hopf formula has been generalized
to the time-dependent Hamiltonian [10] and linear dynamic systems [11]. Later,
Chow et al. [6] generalized Lax and Hopf formulae under the assumption that
the stage cost is convex, and the dynamics is affine in the state and the
control. Also, the authors’ previous paper [7] presents a Lax formula dealing
with state constraints for fixed-horizon optimal control problems.

In these prior works, there have been two approaches for deriving the Lax and
Hopf formulae. First, Bardi and Evans [5] followed two steps: in step 1, an
equivalent optimal control problem was found by analyzing the corresponding HJ
equation, in which a control signal has to be specified, and in step 2, the
step-1 Lax or Hopf formulae is simplified to optimization problems (the step-2
formulae) for which the dimension of the decision variable is the same as that
of the state. For the class of problems Bardi and Evans solved, it turns out
that the step-1 Lax and Hopf formulae are convex in the control, even if the
given optimal control problem is non-convex in the control, leading to fewer
variables to be determined for the step-2 formulae in comparison to the step-1
formulae. On the other hand, Chow et al. [6] utilized the strong duality
technique to directly find approximate step-2 Lax and Hopf formulae, which
shows the connection between HJ PDEs and Pontryagin minimum (or maximum)
principle.

This paper proposes a step-1 Lax formula for state-constrained optimal control
problems for the two classes of problems. We leave the proposal of a step-2
Lax formula for future work. The organization of this paper is as follows.
Section 2 defines the two classes of problems. Section 3 presents the HJ
equations corresponding to the both classes of problems. Section 4 proposes a
viscosity theory, which is utilized to propose and prove the Lax formulae for
the two classes of problems. Section 5 presents convexity conditions for the
proposed Lax formula under which most gradient-based methods guarantee
optimality with polynomial complexity. Section 6 presents a numerical
algorithm to compute a solution to the given two classes of problems by
utilizing the proposed Lax formulae. Section 7 presents two examples to
demonstrate the utility and performance of the proposed Lax formulae for each
class of problems. Section 8 concludes this paper.

##  2 State-Constrained Optimal Control Problem and the Hamilton-Jacobi
Equation

In this paper, we consider the state trajectory ($\mathrm{x}$) solving the
following ordinary differential equation (ODE):

$\displaystyle\dot{\mathrm{x}}(s)=f(s,\mathrm{x}(s),\alpha(s)),s\in[t,T],\text{
and }\mathrm{x}(t)=x,$ (1)

where $(t,x)$ are the initial time and state,
$\mathrm{x}\mathrel{\mathop{\mathchar
58\relax}}[t,T]\times\mathbb{R}^{n}\times A\rightarrow\mathbb{R}^{n}$ is the
state trajectory, $A(t)\subset\mathbb{R}^{m}$ is the control constraint,
$\alpha\in\mathcal{A}(t)$ is the control signal, and we denote the set of
measurable control signals

$\displaystyle\mathcal{A}(t)\coloneqq\\{\alpha\mathrel{\mathop{\mathchar
58\relax}}[t,T]\rightarrow A~{}|~{}\|\alpha\|_{L^{\infty}(t,T)}<\infty\\}.$
(2)

We assume that $A$ is a compact subset in $\mathbb{R}^{m}$.

With this dynamical system, we solve two optimal control problems.

###### Problem 1

For given initial time and state $(t,x)$, solve

$\displaystyle\begin{split}&\vartheta_{1}(t,x)\coloneqq\inf_{\alpha\in\mathcal{A}}\max_{\tau\in[t,T]}\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s))ds\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+g(\tau,\mathrm{x}(\tau)),\end{split}$
(3) $\displaystyle\text{subject to }\quad c(s,\mathrm{x}(s))\leq 0,\quad
s\in[t,T],$ (4)

where $\mathrm{x}$ solves (1).

###### Problem 2

For given initial time and state $(t,x)$, solve

$\displaystyle\begin{split}&\vartheta_{2}(t,x)\coloneqq\inf_{\alpha\in\mathcal{A}}\min_{\tau\in[t,T]}\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s))ds\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+g(\tau,\mathrm{x}(\tau)),\end{split}$
(5) $\displaystyle\text{subject to }\quad c(s,\mathrm{x}(s))\leq 0,\quad
s\in[t,\tau].$ (6)

where $\mathrm{x}$ solves (1).

For both problems, $L\mathrel{\mathop{\mathchar
58\relax}}[t,T]\times\mathbb{R}^{n}\times A\rightarrow\mathbb{R}$ is the stage
cost, $g\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ is the terminal
cost, $f\mathrel{\mathop{\mathchar 58\relax}}[t,T]\times\mathbb{R}^{n}\times
A\rightarrow\mathbb{R}^{n}$ is the system dynamics, and
$c\mathrel{\mathop{\mathchar
58\relax}}[t,T]\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ is the state
constraint.

In Problem 1, we are concerned with finding a control signal that minimizes
the maximum cost over the time horizon under the constraint. On the other
hand, in Problem 2, we determine a control signal that minimizes the minimum
cost over the time horizon under the constraint. The HJ equations for Problems
1 and 2 were presented in [1] and [2], respectively, and we review these in
Section 3.

In this paper, we assume the following.

######  Assumption 1 (Lipschitz continuity and compactness)

  1. 1.

The control set $A$ is compact and convex;

  2. 2.

$f\mathrel{\mathop{\mathchar 58\relax}}[0,T]\times\mathbb{R}^{n}\times
A\rightarrow\mathbb{R}^{n}$ ($f=f(t,x,a)$) is Lipschitz continuous in $(t,x)$
for each $a\in A$;

  3. 3.

the stage cost $L\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}$
($L=L(t,x,a)$) is Lipschitz continuous in $(t,x)$ for each $a\in A$;

  4. 4.

for all $(t,x)\in[0,T]\times\mathbb{R}^{n}$, $\\{f(t,x,a)~{}|~{}a\in A\\}$ and
$\\{L(t,x,a)~{}|~{}a\in A\\}$ are compact and convex;

  5. 5.

the terminal cost $g\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ ($g=g(t,x)$) is
Lipschitz continuous in $(t,x)$;

  6. 6.

the state constraint $c\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ ($c=c(t,x)$) is
Lipschitz continuous in $(t,x)$;

  7. 7.

the stage cost ($L$) and the terminal cost ($g$) are bounded below.

Assumption 1 guarantees the existence of the unique solution to the HJ
equations, presented in Section 3.

##  3 Hamilton-Jacobi Equations for Optimal Control Problems

This section addresses the HJ equations for Problems 1 and 2 from the previous
studies [1, 2]. For each Problem, two HJ equations are presented: one for
time-varying stage cost, terminal cost, dynamics, and state constraint, the
other for the time-invariant case: stage cost, terminal cost, dynamics, and
state constraint are time-invariant.

###  3.1 Hamilton-Jacobi equation for Problem 1

Instead of solving $\vartheta_{1}$ in (3) subject to (4), we derive an HJ
equation for a different value function $V_{1}\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$

$\displaystyle\begin{split}V_{1}&(t,x,z)\coloneqq\inf_{\alpha\in\mathcal{A}(t)}\max\Big{\\{}\max_{s\in[t,T]}c(s,\mathrm{x}(s)),\\\
&\max_{\tau\in[t,T]}\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s))ds+g(\tau,\mathrm{x}(\tau))-z\Big{\\}},\end{split}$
(7)

where $\mathrm{x}$ solves (1) and $z$ is an auxiliary variable in
$\mathbb{R}$. The reason to solve (7) instead of (3) subject to (4) is that
$\vartheta_{1}$ is not continuous in $(t,x)$-space since $\vartheta_{1}$ is
infinity if there is no control signal to satisfy the state constraint. Thus,
viscosity theory cannot be applied. Note that the viscosity theory deals with
a concept of weak solutions to nonlinear-first-order PDEs, and viscosity
solutions are continuous and bounded.

On the other hand, $V_{1}$ is continuous in $(t,x,z)$-space, and $V_{1}$
encodes information of $\vartheta_{1}$ as stated in Lemma 1.

######  Lemma 1 (Equivalence of two value functions [1])

Suppose Assumption 1 holds. For all $(t,x)\in[0,T]\times\mathbb{R}^{n}$,

$\displaystyle\vartheta_{1}(t,x)=\min z\text{ subject to }V_{1}(t,x,z)\leq 0,$
(8)

where $\vartheta_{1}$ and $V_{1}$ are defined in (3) subject to (4), and in
(7), respectively.

Theorem 1 presents a corresponding HJ equation for $V_{1}$.

######  Theorem 1 (HJ equation for Problem 1 [1])

Suppose Assumption 1 holds. $V_{1}$ in (7) is the unique viscosity solution to
the HJ equation:

$\displaystyle\begin{split}\max\big{\\{}c(t,x)-&V_{1}(t,x,z),g(t,x)-z-V_{1}(t,x,z),\\\
&V_{1,t}-\bar{H}(t,x,z,D_{x}V_{1},D_{z}V_{1})\big{\\}}=0\end{split}$ (9)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where
$\bar{H}\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}\times\mathbb{R}\rightarrow\mathbb{R}$

$\displaystyle\bar{H}(t,x,z,p,q)\coloneqq\max_{a\in A}-p\cdot
f(t,x,a)+qL(t,x,a),$ (10)

and

$\displaystyle V_{1}(T,x,z)=\max\\{c(T,x),g(T,x)-z\\}$ (11)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$. Denote
$V_{1,t}=\frac{\partial V_{1}}{\partial t}$, $D_{x}V_{1}=\frac{\partial
V_{1}}{\partial x}$, and $D_{z}V_{1}=\frac{\partial V_{1}}{\partial z}$.

For the time-invaraint case, $V_{1}$ is also the unique viscosity solution to
the HJ equation:

$\displaystyle\begin{split}\max\big{\\{}c(x)-&V_{1}(t,x,z),\\\
&V_{1,t}-\bar{H}_{1}^{\textnormal{TI}}(x,z,D_{x}V_{1},D_{z}V_{1})\big{\\}}=0\end{split}$
(12)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where

$\displaystyle\bar{H}^{\textnormal{TI}}_{1}(x,z,p,q)\coloneqq\min\big{\\{}0,\bar{H}(x,z,p,q)\big{\\}}$
(13)

for
$(x,z,p,q)\in\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}\times\mathbb{R}$,
$\bar{H}$ is defined in (10) and the time dependency is omitted for the time-
invariant case, and

$\displaystyle V_{1}(T,x,z)=\max\\{c(x),g(x)-z\\}$ (14)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$.

This theorem states that, for the time-invariant case, the HJ equation (9) is
equivalent to (12).

###  3.2 Hamilton-Jacobi equation for Problem 2

The HJ analysis for Problem 2 is similar to that for Problem 1. With an
auxiliary variable $z\in\mathbb{R}$, we define a new value function $V_{2}$
that combines the cost (5) and the constraint (6) of $\vartheta_{2}$: for
$(t,x,z)\in[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$,

$\displaystyle\begin{split}V_{2}(t,x,z)\coloneqq\inf_{\alpha\in\mathcal{A}(t)}\min_{\tau\in[t,T]}\max\Big{\\{}\max_{s\in[t,\tau]}c(s,\mathrm{x}(s)),\\\
\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s))ds+g(\tau,\mathrm{x}(\tau))-z\Big{\\}},\end{split}$
(15)

where $\mathrm{x}$ solves (1). Note that $V_{1}$ in (7) and $V_{2}$ in (15)
are different: $V_{1}$ contains the maximum operation over $\tau$, and $V_{2}$
has the minimum operation over $\tau$.

$\vartheta_{2}$ and $V_{2}$ satisfy the following lemma.

######  Lemma 2 (Equivalence of two value functions [2])

Suppose Assumption 1 holds. For all $(t,x)\in[0,T]\times\mathbb{R}^{n}$,

$\displaystyle\vartheta_{2}(t,x)=\min z\text{ subject to }V_{2}(t,x,z)\leq 0,$
(16)

where $\vartheta_{2}$ and $V_{2}$ are defined in (5) subject to (6), and in
(15).

Theorem 2 presents an HJ equation for $V_{2}$.

######  Theorem 2 (HJ equation for Problem 2 [2])

Suppose Assumption 1 holds. $V_{2}$ in (15) is the unique viscosity solution
to the HJ equation:

$\displaystyle\max\Big{\\{}c(t,x)-$ $\displaystyle
V_{2}(t,x,z),\min\big{\\{}g(t,x)-z-V_{2}(t,x,z),$ $\displaystyle
V_{2,t}-\bar{H}(t,x,z,D_{x}V_{2},D_{z}V_{2})\big{\\}}\Big{\\}}=0$ (17)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where $\bar{H}$ is defined in
(10), and

$\displaystyle V_{2}(T,x,z)=\max\\{c(T,x),g(T,x)-z\\}$ (18)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$.

For the time-invariant case, $V_{2}$ is also the unique viscosity solution to
HJ equation:

$\displaystyle\begin{split}\max\big{\\{}c(x)-&V_{2}(t,x,z),\\\
&V_{2,t}-\bar{H}_{2}^{\textnormal{TI}}(x,z,D_{x}V_{2},D_{z}V_{2})\big{\\}}=0\end{split}$
(19)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where

$\displaystyle\bar{H}_{2}^{\textnormal{TI}}(x,z,p,q)=\max\big{\\{}0,\bar{H}(x,z,p,q)\big{\\}}$
(20)

for
$(x,z,p,q)\in\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}\times\mathbb{R}$,
$\bar{H}$ is defined in (10), and

$\displaystyle V_{2}(T,x,z)=\max\\{c(x),g(x)-z\\}$ (21)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$.

The Hamiltonian $\bar{H}_{2}^{\textnormal{TI}}$ for the time-invariant Problem
2 in (19) is $\max\\{0,\bar{H}\\}$, which is convex in the costate space
$(p,q)$ for each $(x,z)$. On the other hand, the Hamiltonian
$\bar{H}_{1}^{\textnormal{TI}}$ for the time-invariant Problem 1 in (12) is
$\min\\{0,\bar{H}\\}$, which is not convex in the costate space $(p,q)$.

###  3.3 Computational complexity of grid-based method

For Problems 1 and 2, the HJ equations in Theorems 1 and 2 can be numerically
solved by grid-based methods, such as the level-set methods [3] and fast
marching method [12]. These methods require spatial and temporal
discretization, which leads to computational complexity exponential in the
dimension of the state. Thus, it is intractable to utilize these grid-based
methods for systems of state dimension beyond six.

##  4 Lax formula for the state-constrained optimal control problem

In this section, we propose Lax formulae for Problems 1 and 2. In Section 4.1,
we first propose viscosity theory, which will be utilized to derive Lax
formulae for these problems in the following subsections: Section 4.2 is for
Problem 1; Section 4.3 is for Problem 2; and Section 4.4 is for the time-
invariant Problem 2. There is no Lax formula for the time-invariant Problem 1
since the corresponding Hamiltonian (13) is non-convex in the costate. This
issue will be discussed more in Section 4.4.

###  4.1 Sufficient condition under which two different PDEs have the same
solution

This section proposes a general technique in viscosity theory to investigate
the equivalence of two first-order PDEs.

Suppose $t\in[0,T]\subset\mathbb{R}$, $x\in\mathbb{R}^{n_{x}}$,
$z\in\mathbb{R}^{n_{z}}$. Consider two first-order differential functions: for
$i=1,2$, $F_{i}(t,x,z,u,r,p,q)\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{z}}\times\mathbb{R}\times\mathbb{R}\times\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{z}}\rightarrow\mathbb{R}$,
and suppose $X_{i}(t,x,z)\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{z}}\rightarrow\mathbb{R}$
is the unique viscosity solution to

$\displaystyle\begin{split}0=F_{i}(t,x,z&,X_{i}(t,x,z),X_{i,t}(t,x,z),\\\
&D_{x}X_{i}(t,x,z),D_{z}X_{i}(t,x,z))\end{split}$ (22)

in $(t,x,z)\in(0,T)\times\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{z}}$, and the
terminal values for $X_{1}$ and $X_{2}$ are the same:

$\displaystyle
X_{1}(T,x,z)=X_{2}(T,x,z)\quad\forall(x,z)\in\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{z}}.$
(23)

We present conditions under which $X_{1}$ and $X_{2}$ are the same even though
$F_{1}$ and $F_{2}$ are different.

Consider superdifferentials and subdifferentials of $X_{i}$ ($i=1,2$) with
respect to $z$: for each
$(t,x,z)\in[0,T]\times\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{z}}$, $q\in
D_{z}^{+}X_{i}(t,x,z)$ ($i=1,2$) is a superdifferential with respect to $z$,
if

$\displaystyle
D_{z}^{+}X_{i}(t,x,z)\coloneqq\big{\\{}q~{}|~{}\limsup_{\bar{z}\rightarrow 0}$
$\displaystyle\big{(}X_{i}(t,x,z+\bar{z})-X_{i}(t,x,z)$
$\displaystyle-q\cdot\bar{z}\big{)}/\lVert\bar{z}\rVert\leq 0\\},$ (24)

and $q\in D_{z}^{-}X_{i}(t,x,z)$ ($i=1,2$) is a subdifferential with respect
to $z$, if

$\displaystyle
D_{z}^{-}X_{i}(t,x,z)\coloneqq\big{\\{}q~{}|~{}\liminf_{\bar{z}\rightarrow 0}$
$\displaystyle\big{(}X_{i}(t,x,z+\bar{z})-X_{i}(t,x,z)$
$\displaystyle-q\cdot\bar{z}\big{)}/\lVert\bar{z}\rVert\geq 0\\}.$ (25)

Theorem 3 generalizes the condition for the equivalence of the two value
functions ($X_{1}$ and $X_{2}$) even in the case where $F_{1}$ is different
from $F_{2}$ for some $(t,x,z,u,r,p,q)$.

###### Theorem 3

Suppose each of the two first-order differential equations in (22) with the
terminal value (23) for $i=1,2$ has the unique solution ($X_{i}$). If, for all
$(t,x,z,u,r,p)\in[0,T]\times\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{z}}\times\mathbb{R}\times\mathbb{R}\times\mathbb{R}^{n_{x}}$

$\displaystyle\begin{split}F_{1}(t,x,z,u,r&,p,q)=F_{2}(t,x,z,u,r,p,q)\\\
&\forall q\in D_{z}^{+}X_{1}(t,x,z)\cup D_{z}^{-}X_{1}(t,x,z),\end{split}$
(26)

then $X_{1}\equiv X_{2}$.

Proof. See Appendix .1.

###  4.2 Lax formula for Problem 1

In this subsection, we utilize the theory in Section 4.1 to derive and prove a
Lax formula for Problem 1, the solution to the HJ equation in Theorem 1.

We first investigate the superdifferentials and subdifferentials of $V_{i}$
($i=1,2$) with respect to $z$.

######  Lemma 3 (Convexity of the value function in $z$)

For each $(t,x)\in[0,T]\times\mathbb{R}^{n}$, $V_{1}(t,x,\cdot)$ in (7) and
$V_{2}(t,x,\cdot)$ in (15) are convex in $z\in\mathbb{R}$: for all
$z_{1},z_{2}\in\mathbb{R}$ and $\theta\in[0,1]$,

$\displaystyle
V_{i}(t,x,\theta_{1}z_{1}+\theta_{2}z_{2})\leq\theta_{1}V_{i}(t,x,z_{1})+\theta_{2}V_{i}(t,x,z_{2})$
(27)

for $i=1,2$.

Proof. See Appendix .2.

###### Lemma 4

For all $(t,x,z)\in[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$ and $i=1,2$,

$\displaystyle D_{z}^{-}V_{i}(t,x,z)\subset[-1,0],$ (28)

and if $D_{z}^{+}V_{i}(t,x,z)$ is not the empty set, there exists a unique
$q\in\mathbb{R}$ such that

$\displaystyle D_{z}^{+}V_{i}(t,x,z)=\\{D_{z}V_{i}(t,x,z)\\}\subset[-1,0].$
(29)

Note that $V_{1}$ and $V_{2}$ are defined in (7) and (15), respectively.

Proof. See Appendix .3.

Define, for initial time and state $(t,x)\in[0,T]\times\mathbb{R}^{n}$,

$\displaystyle\begin{split}&\varphi_{1}(t,x)\coloneqq\inf_{\beta}\max_{\tau\in[t,T]}\int_{t}^{\tau}H^{*}(s,\mathrm{x}(s),\beta(s))ds\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+g(\tau,\mathrm{x}(\tau)),\end{split}$
(30) $\displaystyle\text{subject to
}\begin{cases}\dot{\mathrm{x}}(s)=-\beta(s),&s\in[t,T],\\\ \mathrm{x}(t)=x,\\\
c(s,\mathrm{x}(s))\leq 0,&s\in[t,T],\end{cases}$ (31)

where $H\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$

$\displaystyle H(s,x,p)\coloneqq\bar{H}(s,x,z,p,-1),$ (32)

and $H^{*}\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$

$\displaystyle H^{*}(s,x,b)\coloneqq\max_{p\in\mathbb{R}^{n}}p\cdot
b-H(s,x,p).$ (33)

$H^{*}$ is the Legendre-Fenchel transformation (the convex conjugate) of $H$
with respect to $p\in\mathbb{R}^{n}$, and the state constraint,
$c(s,\mathrm{x}(s))\leq 0$, is satisfied in $[t,T]$ but not $[t,\tau]$.
Combining (30) and (31), define a value function,
$W_{1}\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\times\mathbb{R}\rightarrow\mathbb{R}$:

$\displaystyle\begin{split}W_{1}&(t,x,z)=\inf_{\beta}\max\Big{\\{}\max_{s\in[t,T]}c(s,\mathrm{x}(s)),\\\
&\max_{\tau\in[t,T]}\int_{t}^{\tau}H^{*}(s,\mathrm{x}(s),\beta(s))ds+g(\tau,\mathrm{x}(\tau))-z\Big{\\}}.\end{split}$
(34)

By Theorem 1, $W_{1}$ is the unique viscosity solution to

$\displaystyle\begin{split}\max\big{\\{}c(t,x)&-W_{1}(t,x,z),g(t,x)-z-W_{1}(t,x,z),\\\
&W_{1,t}-\bar{H}_{W}(t,x,z,D_{x}W_{1},D_{z}W_{1})\big{\\}}=0\end{split}$ (35)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where
$\bar{H}_{W}\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}\times\mathbb{R}\rightarrow\mathbb{R}$

$\displaystyle\bar{H}_{W}(t,x,z,p,q)\coloneqq\max_{b}p\cdot b+qH^{*}(t,x,b),$
(36)

$H^{*}$ is defined in (33), and

$\displaystyle W_{1}(T,x,z)=\max\\{c(T,x),g(T,x)-z\\}$ (37)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$.

In the rest of this subsection, we build a mathematical background to utilize
Theorem 3 in order to prove that $\vartheta_{1}$ ((3) subject to (4)) and
$\varphi_{1}$ ((30) subject to (31)) are the same.

For $s\in[t,T]$, the control $\beta(s)$ is constrained in the domain of
$H^{*}(s,\mathrm{x}(s),\cdot)$,

$\displaystyle\text{Dom}(H^{*}(s,\mathrm{x}(s),\cdot))=\\{b~{}|~{}H^{*}(s,\mathrm{x}(s),b)<\infty\\}.$
(38)

which is specified in Lemma 5.

######  Lemma 5 (Domain of $H^{*}$ [7])

For all $(t,x)\in[0,T]\times\mathbb{R}^{n}$,

$\displaystyle\text{Dom}(H^{*}(t,x,\cdot))=\text{co}(B(t,x)),$ (39)

where $H^{*}$ is defined in (33), for $(t,x)\in[0,T]\times\mathbb{R}^{n}$,

$\displaystyle B(t,x)\coloneqq\\{-f(t,x,a)~{}|~{}a\in A\\},$ (40)

and $\text{co}(B(t,x))$ is the convex hull of the set $B(t,x)$.

Although the control constraint for $\beta(s)$ is omitted in (31), $\beta(s)$
is constrained in $\text{co}(B(s,\mathrm{x}(s)))$ (the domain of
$H^{*}(t,x,\cdot)$). By combining Lemma 5 and the definitions of Hamiltonians
($\bar{H}$ in (10) and $\bar{H}_{W}$ in (36)), we derive the following lemma.

###### Lemma 6

For
$(t,x,z,p,q)\in[0,T]\times\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}\times\mathbb{R}$,

$\displaystyle\bar{H}(t,x,z,p,q)=\bar{H}_{W}(t,x,z,p,q)\quad\text{ if }q\leq
0,$ (41)

where $\bar{H}$ and $\bar{H}_{W}$ are defined in (10) and (36), respectively.

Proof. See Appendix .4.

For $q>0$, (41) does not generally hold. Therefore, the two HJ equations in
(9) and (35) are different in general. However, as proved in Lemma 4, the
subdifferentials and superdifferentials of $V_{1}(t,x,z)$ with respect to $z$
are less than or equal to 0 for all $(t,x,z)$. Thus, by combining Theorem 3,
Lemma 4 for $i=1$, and Lemma 6, we prove $V_{1}\equiv W_{1}$ as in Theorem 4.
This implies that $\vartheta_{1}$ ((3) subject to (4)) and $\varphi_{1}$ ((30)
subject to (31)) are the same by Lemma 1. This paper calls $\varphi_{1}$ the
Lax formula for Problem 1.

###### Theorem 4

(Lax formula for Problem 1) For all $(t,x)\in[0,T]\times\mathbb{R}^{n}$,
$W_{1}$ (34) is the unique viscosity solution to the HJ equation (9) and (11)
in Theorem 1, i.e.

$\displaystyle V_{1}\equiv W_{1}.$ (42)

Also,

$\displaystyle\vartheta_{1}(t,x)=\varphi_{1}(t,x),$ (43)

where $\vartheta_{1}$ is (3) subject to (4), and $\varphi_{1}$ is (30) subject
to (31).

###### Remark 1

This paper calls $\varphi_{1}$ in (30) subject to (31) the Lax formula for
Problem 1, which provides the optimal value $\vartheta_{1}$ of Problem 1.

###  4.3 Lax formula for Problem 2

This subsection presents a Lax formula for Problem 2. We use an analogous
derivation presented in Section 4.2.

Define, for initial time and state $(t,x)\in[0,T]\times\mathbb{R}^{n}$,

$\displaystyle\begin{split}&\varphi_{2}(t,x)\coloneqq\inf_{\beta}\min_{\tau\in[t,T]}\int_{t}^{\tau}H^{*}(s,\mathrm{x}(s),\beta(s))ds\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+g(\tau,\mathrm{x}(\tau)),\end{split}$
(44) $\displaystyle\text{subject to
}\begin{cases}\dot{\mathrm{x}}(s)=-\beta(s),&s\in[t,T],\\\ \mathrm{x}(t)=x,\\\
c(s,\mathrm{x}(s))\leq 0,&s\in[t,\tau],\end{cases}$ (45)

where $H^{*}$ is defined in (33), and $\beta(s)$ is constrained in the domain
of $H^{*}(s,\mathrm{x}(s),\cdot)$. We call $\varphi_{2}$ the Lax formula for
Problem 2.

Following the same argument for the proof of Theorem 4, Theorem 5 is derived.

###### Theorem 5

(Lax formula for Problem 2) For all $(t,x)\in[0,T]\times\mathbb{R}^{n}$,

$\displaystyle\vartheta_{2}(t,x)=\varphi_{2}(t,x),$ (46)

where $\vartheta_{2}$ is (5) subject to (6), and $\varphi_{2}$ is (44) subject
to (45).

###### Remark 2

This paper calls $\varphi_{2}$ in (44) subject to (45) the Lax formula for
Problem 2, which provides the optimal value $\vartheta_{2}$ of Problem 2.

###  4.4 Lax formula for the time-invariant Problem 2

For the time-invariant case, there is no time dependency on the stage and
terminal costs, dynamics, and state constraint. Theorems 1 and 2 present HJ
equations for Problem 1 and 2 for the time-invariant case, respectively. On
the derivation of Lax formulae, the Hamiltonian has to be convex in the
costate, unless Lemma 6 does not hold. The Hamiltonian for the time-invariant
Problem 1, $\bar{H}_{1}^{\textnormal{TI}}$ in (13), is generally non-convex,
thus there is no corresponding Lax formula. On the other hand, the Hamiltonian
for the time-invariant Problem 2, $\bar{H}_{2}^{\textnormal{TI}}$ in (20), is
convex, thus the corresponding Lax formula can be derived.

Define, for the initial time and state $(t,x)\in[0,T]\times\mathbb{R}^{n}$,

$\displaystyle\varphi_{2}^{\textnormal{TI}}(t,x)$
$\displaystyle\coloneqq\inf_{\beta}\int_{t}^{T}H_{2}^{\textnormal{TI*}}(\mathrm{x}(s),\beta(s))ds+g(\mathrm{x}(T)),$
(47) $\displaystyle\text{subject to
}\begin{cases}\dot{\mathrm{x}}(s)=-\beta(s),&s\in[t,T],\\\ \mathrm{x}(t)=x,\\\
c(\mathrm{x}(s))\leq 0,&s\in[t,T],\end{cases}$ (48)

where $H_{2}^{\textnormal{TI}}\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$

$\displaystyle
H_{2}^{\textnormal{TI}}(x,p)\coloneqq\bar{H}_{2}^{\textnormal{TI}}(x,z,p,-1),$
(49)

where $\bar{H}_{2}^{\textnormal{TI}}$ is defined in (20), and
$H_{2}^{\textnormal{TI}*}\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$

$\displaystyle H_{2}^{\textnormal{TI*}}(x,b)\coloneqq\max_{p}p\cdot
b-H_{2}^{\textnormal{TI}}(x,p).$ (50)

Note that

$\displaystyle H_{2}^{\textnormal{TI}}(x,p)=\max\\{0,H(x,p)\\},$ (51)

where $H$ is defined in (32), and $\bar{H}_{2}^{\textnormal{TI}}$ in (49) has
no $z$-dependency, thus $H_{2}^{\textnormal{TI}}$ does not depend on $z$.

In comparison to the Lax formula for Problem 2, the Lax formula for the time-
invariant Problem 2 only contains the minimum operation over the control
signal $\beta$, on the other hand, the Lax formula for Problem 2 contains the
two minimum operations over the control signal $\beta$ and the terminal time
$\tau$.

The new control signal $\beta$ is constrained to the domain of the stage cost
$H_{2}^{\textnormal{TI}*}$, presented in Lemma 7.

######  Lemma 7 (Domain of $H_{2}^{\textnormal{TI}*}$)

For all $x\in\mathbb{R}^{n}$,

$\displaystyle\text{Dom}(H_{2}^{\textnormal{TI}*}(x,\cdot))=\text{co}(\\{0\\}\cup
B(x)),$ (52)

where $H_{2}^{\textnormal{TI}*}$ is defined in (50),

$\displaystyle B(x)\coloneqq\\{-f(x,a)~{}|~{}a\in A\\},$ (53)

which does not have the time dependency in comparison to $B(t,x)$ in (40), and
co refers to the convex hull operation.

Proof. See Appendix .5.

We will prove that $\varphi_{2}^{\textnormal{TI}}$ are the same as
$\vartheta_{2}$ for the time-invariant case by the viscosity theory in Section
4.1. Corresponding to $\varphi_{2}^{\textnormal{TI}}$, define a value function
$W_{2}^{\textnormal{TI}}\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\times\mathbb{R}\rightarrow\mathbb{R}$:

$\displaystyle\begin{split}W_{2}^{\textnormal{TI}}(t&,x,z)=\inf_{\beta}\Big{\\{}\max_{s\in[t,T]}c(\mathrm{x}(s)),\\\
&\int_{t}^{T}H_{2}^{\textnormal{TI}*}(s,\mathrm{x}(s),\beta(s))ds+g(\mathrm{x}(T))-z\Big{\\}}.\end{split}$
(54)

Theorem 3.1 in [13] states the relationship between $W_{2}^{\textnormal{TI}}$
and $\varphi_{2}^{\textnormal{TI}}$ as below.

$\displaystyle\varphi_{2}^{\textnormal{TI}}=\min z\text{ subject to
}W_{2}^{\textnormal{TI}}\leq 0$ (55)

Also, Proposition 3.4 in [13] shows that $W_{2}^{\textnormal{TI}}$ is the
unique viscosity solution to

$\displaystyle\begin{split}\max\Big{\\{}&c(x)-W_{2}^{\textnormal{TI}},\\\
&W_{2,t}^{\textnormal{TI}}-\bar{H}_{W}^{\textnormal{TI}}(x,z,D_{x}W_{2}^{\textnormal{TI}},D_{z}W_{2}^{\textnormal{TI}})\Big{\\}}=0\end{split}$
(56)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where
$\bar{H}_{W}^{\textnormal{TI}}\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}\times\mathbb{R}\rightarrow\mathbb{R}$

$\displaystyle\bar{H}_{W}^{\textnormal{TI}}(x,z,p,q)\coloneqq\max_{b}p\cdot
b+qH_{2}^{\textnormal{TI}*}(x,b),$ (57)

where $H_{2}^{\textnormal{TI}*}$ is defined in (50).

Lemma 8 states that the Hamiltonian for $W_{2}^{\textnormal{TI}}$
($\bar{H}_{W}^{\textnormal{TI}}$) in (57) is equivalent to the Hamiltonian for
the time-invariant $V_{2}$ ($\bar{H}_{2}^{\textnormal{TI}}$) in (20).

###### Lemma 8

For
$(x,z,p,q)\in\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}\times\mathbb{R}$,

$\displaystyle\bar{H}_{2}^{\textnormal{TI}}(x,z,p,q)=\bar{H}_{W}^{\textnormal{TI}}(x,z,p,q)\quad\text{if
}q\leq 0,$ (58)

where $\bar{H}_{2}^{\textnormal{TI}}$ and $\bar{H}_{W}^{\textnormal{TI}}$ are
defined in (20) and (57), respectively.

Proof. See Appendix .6.

Consider the two HJ equations (19) and (56). By combining Lemma 4 for $i=2$,
Lemma 8, and Theorem 3, we prove that $V_{2}$ in (15) and
$W_{2}^{\textnormal{TI}}$ in (54) are the same viscosity solution to the HJ
equation (56), as presented in Theorem 6. Also, three value functions
($\varphi_{2}^{\textnormal{TI}}$ in (47) subject to (48), $\vartheta_{2}$ in
(5) subject to (6), and $\varphi_{2}$ in (44) subject to (45)) are the same by
(55), Lemma 2 for $i=2$, and Theorem 5.

###### Theorem 6

(Lax formula for Problem 2 (time-invariant version)) Consider Problem 2 for
the time-invariant case: $\vartheta_{2}$ in (5) subject to (6). For all
$(t,x)\in[0,T]\times\mathbb{R}^{n}$, $W_{2}^{\textnormal{TI}}$ in (54) is the
unique viscosity solution to the HJ equation in (19) and (21), i.e.,

$\displaystyle V_{2}(t,x,z)=W_{2}(t,x,z)=W_{2}^{\textnormal{TI}}(t,x,z).$ (59)

In addition,

$\displaystyle\vartheta_{2}(t,x)=\varphi_{2}(t,x)=\varphi_{2}^{\textnormal{TI}}(t,x),$
(60)

where $\vartheta_{2}$ is (5) subject to (6), $\varphi_{2}$ is (44) subject to
(45), and $\varphi_{2}^{\textnormal{TI}}$ is (47) subject to (48).

This paper calls $\varphi_{2}^{\textnormal{TI}}$ in (47) subject to (48) the
Lax formula for the time-invariant Problem 2.

##  5 Convexity analysis

From this section, we set the initial time $t$ to 0 in Problems 1 and 2.
Without spatial discretization, we temporally discretize problems and utilize
gradient-based methods, which provide the optimal cost and a optimal control
signal if the discretized problem is convex. Thus, in this section, we present
convexity analysis for the Problems 1 and 2 ($\vartheta_{1}$, $\vartheta_{2}$)
and the corresponding Lax formulae ($\varphi_{1}$, $\varphi_{2}$,
$\varphi_{2}^{\textnormal{TI}}$). For the temporal discretization, the first-
order forward Euler method is chosen. Note that the convexity analysis in this
section is invariant even if other temporal discretization methods are
utilized, such as backward Euler method, Crank Nicolson method, and a family
of Runge-Kutta methods.

###  5.1 Convexity analysis for Problem 1 and the corresponding Lax formula

This subsection presents a convexity analysis for the temporally discretized
Problem 1$(\vartheta_{1}$ in (3) subject to (4)) and corresponding Lax formula
($\varphi_{1}$ in (30) subject to (31)).

The temporally discretized problem can be found using a temporal
discretization $\\{t_{0}=0,...,t_{K}=T\\}$.

$\displaystyle\begin{split}&\quad\vartheta_{1}(0,x)\simeq\min_{\mathrm{x}[\cdot],\alpha[\cdot]}\max_{k^{\prime}\in\\{0,...,K\\}}\sum_{k=0}^{k^{\prime}}L(t_{k},\mathrm{x}[k],\alpha[k])\Delta_{k}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+g(t_{k^{\prime}},\mathrm{x}[k^{\prime}]),\end{split}$
(61) $\displaystyle\text{subject to
}\begin{cases}\mathrm{x}[k+1]-\mathrm{x}[k]=\Delta_{k}f(t_{k},\mathrm{x}[k],\alpha[k]),\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\phantom{{}^{\prime\prime}}k\in\\{0,...,K-1\\},\\\
\alpha[k]\in
A,\quad\quad\quad\quad\quad\quad\phantom{{}^{\prime}}k\in\\{0,...,K-1\\},\\\
\mathrm{x}[0]=x,\\\ c(t_{k},\mathrm{x}[k])\leq 0,\quad\quad\quad\quad
k\in\\{0,...,K\\},\end{cases}$ (62)

where $\Delta_{k}\coloneqq t_{k+1}-t_{k}$. In this paper, we use $\mathrm{x}$
to denote both a state trajectory and sequence. Note that $\mathrm{x}(s)$ is a
state at time $s$, and $\mathrm{x}[k]$ is a $k$-th state. This notation rule
is also applied for $\alpha$.

The following lemma provides convexity conditions for the temporal discretized
Problem 1 ((61)) subject to (62)) in
$(\mathrm{x}[\cdot],\alpha[\cdot])$-space.

###### Condition 1

(Convexity conditions for the temporally discretized Problem 1
($\vartheta_{1}$))

  1. 1.

$L(t,x,a)$ is convex in $(x,a)$ for all $t\in[0,T]$,

  2. 2.

$g(t,x)$ is convex in $x$ for all $t\in[0,T]$,

  3. 3.

$c(t,x)$ is convex in $x$ for all $t\in[0,T]$,

  4. 4.

$f(t,x,a)$ is affine in $(x,a)$ for all $t\in[0,T]$,

  5. 5.

$A$ is convex.

###### Lemma 9

Suppose Condition 1 holds. For a fixed initial state $x\in\mathbb{R}^{n}$, the
temporally discretized Problem 1 ($\vartheta_{1}$ in (61) subject to (62)) is
convex in $(\mathrm{x}[\cdot],\alpha[\cdot])$.

Proof. See Appendix .7.

In this convexity analysis, we consider only $(\mathrm{x},\alpha)$ (or
$(\mathrm{x}[\cdot],\alpha[\cdot])$) as variables to be determined, but not
$\tau$ (or $k^{\prime}$). The reason of choosing these decision variables is
to avoid solving a minimax problem and to utilize the fact that the pointwise
maximum of a family of convex functions is convex.

The temporally discretized Lax formula for Problem 1 is

$\displaystyle\begin{split}&\varphi_{1}(0,x)\simeq\min_{\mathrm{x}[\cdot],\beta[\cdot]}\max_{k^{\prime}\in\\{0,...,K\\}}\sum_{k=0}^{k^{\prime}}H^{*}(t_{k},\mathrm{x}[k],\beta[k])\Delta_{k}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+g(t_{k^{\prime}},\mathrm{x}[k^{\prime}]),\end{split}$
(63) $\displaystyle\text{subject to
}\begin{cases}\mathrm{x}[k+1]-\mathrm{x}[k]=-\Delta_{k}\beta[k],\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\phantom{{}^{\prime\prime}}k\in\\{0,...,K-1\\},\\\
\beta[k]\in\text{co}(B(t_{k},\mathrm{x}[k])),\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\phantom{{}^{\prime\prime}}k\in\\{0,...,K-1\\},\\\
\mathrm{x}[0]=x,\\\ c(t_{k},\mathrm{x}[k])\leq 0,\quad\quad\quad\quad
k\in\\{0,...,K\\}.\\\ \end{cases}$ (64)

Lemma 9 implies that if $H^{*}(s,x,b)$ and
$\\{(x,b)~{}|~{}b\in\text{co}(B(s,x))\\}$ are convex in $(x,b)$ for each $s$,
the temporally discretized Lax formula ((63) subject to (64)) is convex. In
one of the authors’ paper [7], sufficient conditions for convex $H^{*}(s,x,b)$
and $\\{(x,b)~{}|~{}b\in\text{co}(B(s,x))\\}$ are presented: 1)
$L(s,x,a)=L^{x}(s,x)+L^{a}(s,a)$, and $L^{x}$ is convex in $x$ for all
$s\in[0,T]$, 2) $f(s,x,a)=M(s)x+L^{a}(s,a)$ for some matrix
$M(s)\in\mathbb{R}^{n}\times\mathbb{R}^{n}$. Corollary 1 summarizes the
convexity conditions for the temporally discretized Lax formula for Problem 1.

###### Condition 2

(Convexity condition for the temporally discretized $\varphi_{1}$)

  1. 1.

$L(s,x,a)=L^{x}(s,x)+L^{a}(s,a)$ for some $L^{x}$ and $L^{a}$, and $L^{x}$ is
convex in $x$ for all $s\in[0,T]$,

  2. 2.

$g(s,x)$ is convex in $x$ for all $s\in[0,T]$,

  3. 3.

$c(s,x)$ is convex in $x$ for all $s\in[0,T]$,

  4. 4.

$f(s,x,a)=M(s)x+f^{a}(s,a)$ for some $M$ and $f^{a}$ for all $s\in[0,T]$.

###### Corollary 1

Suppose Condition 2 holds. the Lax formula for Problem 1 ($\varphi_{1}$) in
(30) subject to (31) is convex in $(\mathrm{x},\beta)$. Also, the temporally
discretized Lax formula for Problem 1 ((63) subject to (64)) is convex in
$(\mathrm{x}[\cdot],\beta[\cdot])$.

###  5.2 Convexity analysis for Problem 2 and the corresponding Lax formula

This section presents convexity analysis for the temporal discretization of
Problem 2$(\vartheta_{2}$ in (5) subject to (6)), Lax formula for Problem 2
($\varphi_{2}$ in (44) subject to (45)), and Lax formula for the time-
invariant Problem 2 ($\varphi_{2}^{\textnormal{TI}}$ in (47) subject to (48)).

The temporally discretized Problem 2 on $\\{t_{0}=0,...,t_{K}=T\\}$ is

$\displaystyle\quad\vartheta_{2}(0,x)\simeq\min_{\mathrm{x}[\cdot],\alpha[\cdot],k^{\prime}\in\\{0,...,K\\}}\sum_{k=0}^{k^{\prime}}L(t_{k},\mathrm{x}[k],\alpha[k])\Delta_{k}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+g(t_{k^{\prime}},\mathrm{x}[k^{\prime}]),$
(65) $\displaystyle\text{subject to
}\begin{cases}\mathrm{x}[k+1]-\mathrm{x}[k]=\Delta_{k}f(t_{k},\mathrm{x}[k],\alpha[k]),\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\phantom{{}^{\prime\prime}}k\in\\{0,...,K-1\\},\\\
\alpha[k]\in
A,\quad\quad\quad\quad\quad\quad\phantom{{}^{\prime}}k\in\\{0,...,K-1\\},\\\
\mathrm{x}[0]=x,\\\ c(t_{k},\mathrm{x}[k])\leq 0,\quad\quad\quad\quad
k\in\\{0,...,k^{\prime}\\}.\\\ \end{cases}$ (66)

In Section 5.1, we analyze the convexity conditions for the temporally
discretized Problem 1 in $(\mathrm{x}[\cdot],\alpha[\cdot])$-space, on the
other hand, in this section, the convexity conditions for Problem 2 is
analyzed in $(\mathrm{x}[\cdot],\alpha[\cdot],k^{\prime})$-space. This is
because Problem 2 is minimization problem over
$(\mathrm{x}[\cdot],\alpha[\cdot],k^{\prime})$-space. The result of the
convexity analysis is summarized in the fourth column of Table 1.

Using the same temporal discretization $\\{t_{0}=0,...,t_{K}=T\\}$, the Lax
formula for Problem 2 ((44) subject to (45)) is discretized to

$\displaystyle\begin{split}&\varphi_{2}(0,x)\simeq\min_{\mathrm{x}[\cdot],\beta[\cdot],k^{\prime}\in\\{0,...,K\\}}\sum_{k=0}^{k^{\prime}}H^{*}(s,\mathrm{x}[k],\beta[k])\Delta_{k}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+g(t_{k^{\prime}},\mathrm{x}[k^{\prime}]),\end{split}$
(67) $\displaystyle\text{subject to
}\begin{cases}\mathrm{x}[k+1]-\mathrm{x}[k]=-\Delta_{k}\beta[k],\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\phantom{{}^{\prime\prime\prime}}k\in\\{0,...,K-1\\},\\\
\beta[k]\in\text{co}(B(t_{k},\mathrm{x}[k])),\quad k\in\\{0,...,K-1\\},\\\
\mathrm{x}[0]=x,\\\ c(t_{k},\mathrm{x}[k])\leq
0,\quad\quad\quad\quad\quad\phantom{{}^{\prime\prime}}k\in\\{0,...,k^{\prime}\\}.\\\
\end{cases}$ (68)

Note that, [7] presents that $L=0$ implies $H^{*}=0$, and the control
constraint ($\text{co}(B(t_{k},\mathrm{x}[k]))$) is convex if
$f(s,x,a)=M(s)x+f^{a}(s,a)$ for some $M$ and $f^{a}$ for all $s\in[0,T]$. The
result of the convexity analysis is summarized at the fifth column of Table 1.

###  5.3 Convexity analysis for the time-invariant Problem 2 and the
corresponding Lax formula

As summarized in Table 1, the temporally discretized Lax formula for Problem 2
($\varphi_{2}$ in (67) subject to (68)) is non-convex for non-zero costs.
Thus, gradient-based methods do not, in general, provide a global optimal
solution for Problem 2. Nevertheless, the Lax formula for the time-invariant
Problem 2 provides a convex problem under a particular set of conditions,
which will be presented in this subsection.

Consider a temporal discretization $\\{t_{0}=0,...,T_{K}=T\\}$, and the
temporal discretized Lax formula $\varphi_{2}^{\textnormal{TI}}$ in (47)
subject to (48):

$\displaystyle\varphi_{2}^{\textnormal{TI}}(0,x)\simeq\min_{\mathrm{x}[\cdot],\beta[\cdot]}\sum_{k=0}^{K}H_{2}^{\textnormal{TI}*}(\mathrm{x}[k],\beta[k])\Delta_{k}+g(\mathrm{x}(K)),$
(69) $\displaystyle\text{subject to
}\begin{cases}\mathrm{x}[k+1]-\mathrm{x}[k]=-\Delta_{k}\beta[k],\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\phantom{{}^{\prime\prime\prime}}k\in\\{0,...,K-1\\},\\\
\beta[k]\in\text{co}(\\{0\\}\cup B(\mathrm{x}[k])),\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\phantom{{}^{\prime\prime\prime}}k\in\\{0,...,K-1\\},\\\
\mathrm{x}[0]=x,\\\ c(\mathrm{x}[k])\leq
0,\quad\quad\quad\quad\quad\phantom{{}^{\prime\prime\prime}}k\in\\{0,...,K\\}.\\\
\end{cases}$ (70)

Note that $H_{2}^{\textnormal{TI}*}$ is defined in (50).

This problem is convex if the costs ($H_{2}^{\textnormal{TI*}}$ and $g$) in
(69) and the constraints in (70) are convex in
$(\mathrm{x}[\cdot],\beta[\cdot])$. The last column of Table 1 shows the
convexity result for the Lax formula in the time-invariant case.

###  5.4 Comparison of convexity conditions for Problem 1, 2, and the
corresponding Lax formulae

Table 1 shows the summary of convexity conditions for Problems 1 and 2,
analyzed in Section 5.1, 5.2, and 5.3.

In contrast to Problem 1, the temporally discretized Lax formula for Problem 2
is generally non-convex unless the cost is zero. This non-convexity is caused
by the temporal discretization that converts $\min_{\tau\in[0,T]}$ in (5) to
$\min_{k^{\prime}\in\\{0,...,K\\}}$ in (65). However, this non-convexity issue
is resolved in the temporally discretized Lax formula for the time-invariant
case under the specified conditions in Table 1.

###### Remark 3

  1. 1.

Suppose the stage cost $L$ and dynamics $f$ are decomposed into state and
control dependent parts:

$\displaystyle L(s,x,a)=L^{x}(s,x)+L^{a}(s,a),$ (71) $\displaystyle
f(s,x,a)=M(s)x+f^{a}(s,a).$ (72)

$L^{a}$ and $f^{a}$ need to be convex and affine in the control, respectively,
for convex temporally discretized Problem 1 ($\vartheta_{1}$ in (61) subject
to (62)), but not for convex temporally discretized Lax formula $\varphi_{1}$
((63) subject to (64)).

  2. 2.

The temporally discretized Problem 2 and Lax formula for Problem 2 are non-
convex unless the cost is zero.

  3. 3.

Despite of the above remark, the temporally discretized Lax formula for the
time-invariant Problem 2 ($\varphi_{2}^{\textnormal{TI}}$ in (69) subject to
(70)) is convex if the stage cost and dynamics only depend on the control, and
the terminal cost and state constraint are convex in the state.

Table 1: Convexity Conditions for the Temporally Discretized Problems 1, 2, and the Corresponding Lax Formulae | Problem 1 |  | Lax formula
---
for Problem 1
Problem 2 |  | Lax formula
---
for Problem 2
| Lax formula
---
for time-invariant
Problem 2
problem |  $\vartheta_{1}$ (3) s.t. (4) |  $\varphi_{1}$ (30) s.t. (31) |  $\vartheta_{2}$ (5) s.t. (6) |  $\varphi_{2}$ (44) s.t. (45) |  $\varphi_{2}^{\textnormal{TI}}$ (47) s.t. (48)
| temporally
---
discretized
problem
(61) s.t. (62) | (63) s.t. (64) | (65) s.t. (66) | (67) s.t. (68) | (69) s.t. (70)
| stage cost
---
$L=L^{x}(s,x)$
”’$+L^{a}(s,a)$
|  $L^{x}(s,\cdot)$ is
---
””””’convex in $x$
$L^{a}(s,\cdot)$ is
””””’convex in $a$
$L^{x}(s,\cdot)$ is convex in $x$ | $L=0$ | $L=0$ |  | $L^{x}=0$
---
($L=L^{a}$)
| terminal cost
---
$g(s,x)$
convex in $x$ | convex in $x$ | $g=0$ | $g=0$ |  | $g=g(x)$
---
is convex in $x$
| dynamics
---
$f(s,x,a)$
| $f=M(s)x$
---
”””’$+N(s)a+C(s)$
| $f=M(s)x$
---
””””’$+f^{a}(s,a)$
| $f=M(s)x$
---
”””’$+N(s)a+C(s)$
| $f=M(s)x$
---
””””’$+f^{a}(s,a)$
$f=f^{a}(a)$
| state constraint
---
$c(s,x)$
convex in $x$ | convex in $x$ | $c=c(s)$ | $c=c(s)$ | convex in $x$
For $s\in[0,T]$, $M$ (or $M(s)$) is a matrix in
$\mathbb{R}^{n}\times\mathbb{R}^{n}$, $N$ (or $N(s)$) is a matrix in
$\mathbb{R}^{n}\times\mathbb{R}^{m}$, $C(s)$ is a vector in $\mathbb{R}^{n}$,
and $f^{a}(a)$ (or $f^{a}(s,a)$) is a nonlinear function in $a$, where $n$ and
$m$ are the dimension of the state and the control.

##  6 Numerical Algorithm Using the Lax formula

###  6.1 Numerical algorithm for Problem 1

Remark 1 describes one of benefits of convexity of the Lax formula for Problem
1. For problems where Problem 1 is non-convex but the corresponding Lax
formula is convex, we 1) solve the Lax formula for Problem 1 ($\varphi_{1}$ in
(30) subject to (31)) by temporal discretization and gradient-based methods to
get a global optimal solution $(\mathrm{x}_{*},\beta_{*})$ and 2) find the
corresponding optimal state trajectory and control signal
($\mathrm{x}_{*},\alpha_{*}$) to Problem 1 ($\vartheta_{1}$ in (3) subject to
(4)).

In this section, we utilize a numerical method presented in [7] for a
different class of problems, which also works for our problems.

Suppose an optimal solution $\mathrm{x}_{*},\beta_{*}$ to the Lax formula for
Problem 1 ($\varphi_{1}$) is given, in which the initial time $t$ is 0.
Consider a temporal discretization $\\{t_{0}=0,...,t_{K}=T\\}$ to numerically
find approximate optimal stage trajectory $\mathrm{x}^{\epsilon}$ and control
signal $\alpha^{\epsilon}$ for Problem 1 ($\vartheta_{1}$).

[7] showed that $H^{*}$ (the stage cost of the Lax formula for Problem 1) is
linearly decomposed by a finite number of stage costs. This was derived from
one of properties of the Legendre-Fenchel transformation: for
$(s,x,b)\in[0,T]\times\mathbb{R}^{n}\times B(s,x)$,

$\displaystyle H^{*}(s,x,b)=((L^{b})^{*})^{*}(s,x,b),$ (73)

where $L^{b}(s,x,b)\coloneqq\min_{a\in A}L(s,x,a)$ subject to $f(s,x,a)=-b$,
which is the corresponding stage cost for Problem 1 by converting the dynamics
from $f(s,x,a)$ to $-b$. This implies that, for all $k=0,...,K-1$, there exist
$a_{i}^{k}\in A$ and $\gamma_{i}^{k}\in[0,1]$ ($\sum_{i}\gamma_{i}^{k}=1$)
such that

$\displaystyle\begin{split}\begin{bmatrix}H^{*}(t_{k},\mathrm{x}_{*}(t_{k}),\beta_{*}(t_{k}))\\\
-\beta_{*}(t_{k})\end{bmatrix}=\sum_{i}\gamma_{i}^{k}\begin{bmatrix}L(t_{k},\mathrm{x}_{*}(t_{k}),a_{i}^{k})\\\
f(t_{k},\mathrm{x}_{*}(t_{k}),a_{i}^{k})\end{bmatrix}.\end{split}$ (74)

The detailed explanation for (74) can be found in [7]. This implies that
applying $\beta_{*}(t_{k})$ for the time interval $[t_{k},t_{k+1})$ in the Lax
formula for Problem 1 ($\varphi_{1}$) can be approximated by applying a series
of $a_{i}^{k}$ for $\gamma_{i}^{k}$-fraction of $[t_{k},t_{k+1})$, which
provides an approximate state trajectory and cost:

$\displaystyle\alpha^{\epsilon}_{*}(s)=a_{i}^{k},s\in[t_{k,i},t_{k,i+1}),$
(75)

where $t_{k,i}\coloneqq t_{k}+\sum_{j=1}^{i-1}\gamma_{j}^{k}\Delta_{k}$,
$\Delta_{k}\coloneqq t_{k+1}-t_{k}$. Then, $\mathrm{x}^{\epsilon}$ solving (1)
for $s=0,\alpha=\alpha_{*}^{\epsilon}$ is an approximate optimal state
trajectory for Problem 1.

Theorem 7 guarantees the quality of this approximation: as the size of the
temporal discretization converges to 0, the approximation error of the state
trajectory and the cost also converges to 0.

###### Theorem 7

(Guarantee of the quality of the approximation) Suppose Assumption 1 holds.
For initial time $t=0$ and state $x\in\mathbb{R}^{n}$, assume that Problem 1
has a feasible solution. Denote an optimal control signal $\beta_{*}$ and an
optimal state trajectory $\mathrm{x}_{*}$ to the Lax formula for Problem 1
($\varphi_{1}$ in (30) subject to (31)).

A control signal $\alpha_{*}^{\epsilon}$ in (75) on a temporal discretization
$\\{t_{0}=0,...,t_{K}=T\\}$ and the corresponding state trajectory
$\mathrm{x}_{*}^{\epsilon}$ solving (1) for $t=0,\alpha=\alpha_{*}^{\epsilon}$
satisfy the following statement: let $\delta=\max_{k}\Delta_{k}$, then

$\displaystyle\lim_{\delta\rightarrow
0}\|\mathrm{x}_{*}-\mathrm{x}_{*}^{\epsilon}\|_{L^{\infty}(0,T;\mathbb{R}^{n})}=0,$
(76) $\displaystyle\lim_{\delta\rightarrow
0}\|c(\cdot,\mathrm{x}_{*}^{\epsilon}(\cdot))-c(\cdot,\mathrm{x}_{*}(\cdot))\|_{L^{\infty}(0,T)}=0,$
(77) $\displaystyle\begin{split}&\lim_{\delta\rightarrow
0}\max_{\tau\in[0,T]}\int_{0}^{\tau}L(s,\mathrm{x}_{*}^{\epsilon}(s),\alpha_{*}^{\epsilon}(s))ds+g(\tau,\mathrm{x}_{*}^{\epsilon}(\tau))\\\
&\quad\quad\quad\quad=\vartheta_{1}(0,x),\end{split}$ (78)

where $\vartheta_{1}$ is defined in (3) subject to (4).

Proof. See Appendix .8.

Algorithm 1 summarizes how to numerically solve Problem 1 ($\vartheta_{1}$)
using the Lax formula $\varphi_{1}$ with the temporal discretization
$\\{t_{0}=0,...,t_{K}=T\\}$.

Algorithm 1 Computing optimal state trajectory ($\mathrm{x}_{*}^{\epsilon}$)
and control signal ($\alpha_{*}^{\epsilon}$) for Problem 1 using the Lax
formula

1:Input: initial time $t=0$, initial state $x$.

2:Output: optimal state trajectory ($\mathrm{x}$), control signal ($\alpha$),
and terminal time ($\tau$).

3:Generate a temporal discretization: $\\{t_{0}=t,...,t_{K}=T\\}$.

4:Solve $\varphi_{1}$ in (63) subject to (64) for
$\mathrm{x}_{*}[\cdot],\beta_{*}[\cdot]$.

5:Solve $(a_{i}^{k},\gamma_{i}^{k})$ in (74).

6:Additionally discretize each temporal interval $[t_{k},t_{k+1})$ into
multiple sub intervals: $[t_{k,i},t_{k,i+1})$, and design
$\alpha_{*}^{\epsilon}$ as in (75).

7:Compute $\mathrm{x}_{*}^{\epsilon}$ by solving the ODE (1) for
$\alpha_{*}^{\epsilon}$ and the initial state $x$.

8:Compute $\tau_{*}=t_{k^{\prime}}$, where $k^{\prime}$ maximizes (61).

With the analogous derivation, one can prove that the approximate optimal
control design in (75) also works for Problem 2 and the corresponding Lax
formula. Nevertheless, these two problems are generally non-convex, thus,
gradient-based methods do not provide a globally optimal solution
$(\mathrm{x}_{*},\beta_{*})$ for the temporally discretized Lax formula for
Problem 2. The following subsection presents a numerical method for the time-
invariant Problem 2, in which the corresponding Lax formula is convex under
the conditions in the last column of Table 1.

###  6.2 Numerical algorithm for the time-invariant Problem 2

We present a numerical method for the time-invariant Problem 2 based on one of
the authors’ prior work [14], which provides a numerical method for the reach-
avoid problem, which is a particular example of Problem 2 where the stage cost
is zero $L=0$. We generalize the method [14] for non-zero stage cost even
though the convexity condition for the time-invariant Problem 2 in Table 1
requires zero stage cost.

Suppose an optimal solution $\mathrm{x}_{*},\beta_{*}$ to the Lax formula for
the time-invariant Problem 2 is given for the zero initial time, $t=0$, and
consider the temporal discretization $\\{t_{0}=0,...,t_{K}=T\\}$.

In [1], the time-invariant Problem 2 is converted to a fixed-horizon optimal
control problem, in which the stage cost is $L(x,a)a_{d}$ and $a_{d}\in[0,1]$
is a freezing control. In the fixed-horizon optimal control problem, the
dynamics $f(x,a)a_{d}$ is converted to $-b$, and the stage cost $L$ is also
converted to $L^{b,\textnormal{TI}}(x,b)\coloneqq\min_{a\in
A,a_{d}\in[0,1]}L(x,a)a_{d}$ subject to $f(x,a)a_{d}=b$. Similar to (73), we
have, for $(x,b)\in\mathbb{R}^{n}\times B(x)$,

$\displaystyle
H_{2}^{\textnormal{TI}*}(x,b)=(L^{b,\textnormal{TI}})^{**}(x,b).$ (79)

This implies that the epigraph of $H_{2}^{\textnormal{TI}*}(x,\cdot)$ (33) is
the convex hull of the epigraph of $L^{b,\textnormal{TI}}(x,\cdot)$, and the
domain of $H_{2}^{\textnormal{TI}*}(x,\cdot)$ is the convex hull of the union
of the zero vector and $B(x)$ in (40). Thus, for all $k=0,...,K-1$, there
exist $a_{i}^{k}\in A$ and $\gamma_{i}^{k}\in[0,1]$
($\sum_{i}\gamma_{i}^{k}\leq 1$) such that

$\displaystyle\begin{split}\begin{bmatrix}H_{2}^{\textnormal{TI}*}(\mathrm{x}_{*}(t_{k}),\beta_{*}(t_{k}))\\\
-\beta_{*}(t_{k})\end{bmatrix}=\sum_{i}\gamma_{i}^{k}\begin{bmatrix}L(\mathrm{x}_{*}(t_{k}),a_{i}^{k})\\\
f(\mathrm{x}_{*}(t_{k}),a_{i}^{k})\end{bmatrix}.\end{split}$ (80)

We approximate the state trajectory and control signal
$\mathrm{x}_{*}^{\epsilon},\beta_{*}^{\epsilon}$ in two steps. In step 1, we
first define approximate $\mathrm{x}_{*}^{1},\beta_{*}^{1}$:

$\displaystyle\beta_{*}^{1}(s)=\begin{cases}-f(x_{*}(t_{k}),a_{i}^{k}),&s\in[t_{k,i},t_{k,i+1}),\\\
0,&s\in[t_{k}+\sum_{i}\gamma_{i}^{k}\Delta_{k},t_{k+1}),\end{cases}$ (81)

where $t_{k,i}\coloneqq t_{k}+\sum_{j=1}^{i-1}\gamma_{j}^{k}\Delta_{k}$, and
$\mathrm{x}_{*}^{1}$ solves

$\displaystyle\dot{\mathrm{x}}_{*}^{1}(s)=-\beta_{*}^{1}(s),\quad
s\in[0,T],\quad\mathrm{x}_{*}^{1}(0)=x.$ (82)

In step 2, the psuedo time operation is introduced.

$\displaystyle\sigma_{\beta_{*}^{1}}(s)\coloneqq\int_{0}^{s}\mathds{1}\\{\beta_{*}^{1}(\tau)\neq
0\\}d\tau,$ (83)

where $\mathds{1}$ outputs 1 if the input condition is true, or 0 if not. The
corresponding inverse operation is defined: for $s\in[0,T]$,

$\displaystyle\sigma^{-1}_{\beta_{*}^{1}}(s)\coloneqq\min\tau\text{ subject to
}\sigma_{\beta_{*}^{1}}(\tau)=s.$ (84)

Using this operation, define state trajectory and control signal:

$\displaystyle\alpha_{*}^{\epsilon}(s)=\begin{cases}a_{i}^{k},&s\in[\sigma_{\beta_{*}^{1}}(t_{i}^{k}),\sigma_{\beta_{*}^{1}}(t_{i+1}^{k})),\\\
\text{any control},&s\in[\sigma_{\beta_{*}^{1}}(T),T],\end{cases}$ (85)

and $\mathrm{x}_{*}^{\epsilon}$ solves (1) for $\alpha_{*}^{\epsilon}$ with
the initial state $x$. Theorem 8 shows
$(\mathrm{x}_{*}^{\epsilon},\alpha_{*}^{\epsilon})$ are approximate optimal
state trajectory and control signal to the time-invariant Problem 2.

###### Theorem 8

(Guarantee of the quality of the approximation for the time-invariant Problem
2) Suppose Assumption 1 holds, and assume that Problem 2 for the time-
invariant case has a feasible solution. For initial time $t=0$ and state
$x\in\mathbb{R}^{n}$, denote an optimal control signal $\beta_{*}$ and an
optimal state trajectory $\mathrm{x}_{*}$ to the Lax formula for the time-
invariant Problem 2 ($\varphi_{2}^{\textnormal{TI}}$ in (47) subject to (48)).

A control signal $\alpha_{*}^{\epsilon}$ in (85) on a temporal discretization
$\\{t_{0}=0,...,t_{K}=T\\}$ and the corresponding state trajectory
$\mathrm{x}_{*}^{\epsilon}$ solving (1) for $t=0,\alpha=\alpha_{*}^{\epsilon}$
satisfy the following statement: let $\delta=\max_{k}\Delta_{k}$, then

$\displaystyle\lim_{\delta\rightarrow
0}\lVert\mathrm{x}_{*}(\cdot)-\mathrm{x}_{*}^{\epsilon}(\sigma(\cdot;\beta_{*}^{1}))\rVert_{L^{\infty}(0,T;\mathbb{R}^{n})}=0,$
(86) $\displaystyle\lim_{\delta\rightarrow 0}\lVert
c(\cdot,\mathrm{x}_{*}(\cdot))-c(\cdot,\mathrm{x}_{*}^{\epsilon}(\sigma(\cdot;\beta_{*}^{1})))\rVert_{L^{\infty}(0,T)}=0,$
(87) $\displaystyle\begin{split}&\lim_{\delta\rightarrow
0}\int_{0}^{\sigma(T;\beta_{*}^{1})}L(\mathrm{x}_{*}^{\epsilon}(s),\alpha_{*}^{\epsilon}(s))ds+g\left(\mathrm{x}_{*}^{\epsilon}(\sigma(T;\beta_{*}^{1}))\right)\\\
&\quad\quad\quad\quad=\vartheta_{2}(0,x),\end{split}$ (88)

where $\vartheta_{2}$, $\sigma$, and $\beta_{*}^{1}$ are defined in (5)
subject to (6), (83), and (81).

Proof. See Appendix .9.

Algorithm 2 summarizes how to numerically solve the time-invariant Problem 2
($\vartheta_{2}$) using the Lax formula $\varphi_{2}^{\textnormal{TI}}$ with
the temporal discretization $\\{t_{0}=0,...,t_{K}=T\\}$.

Algorithm 2 Computing optimal state trajectory ($\mathrm{x}_{*}^{\epsilon}$)
and control signal ($\alpha_{*}^{\epsilon}$) for the time-invariant Problem 2
using the Lax formula

1:Input: initial time $t=0$, initial state $x$.

2:Output: optimal state trajectory ($\mathrm{x}$), control signal ($\alpha$),
and terminal time ($\tau$).

3:Generate a temporal discretization: $\\{t_{0}=t,...,t_{K}=T\\}$.

4:Solve $\varphi_{2}^{\textnormal{TI}}$ in (69) subject to (70) for
$\mathrm{x}_{*}[\cdot],\beta_{*}[\cdot]$ .

5:Solve $(a_{i}^{k},\gamma_{i}^{k})$ in (80).

6:Additionally discretize each temporal interval $[t_{k},t_{k+1})$ into
multiple sub intervals: $[t_{k,i},t_{k,i+1})$, and design $\beta*^{1}$ as in
(81).

7:Design $\alpha_{*}^{\epsilon}$ (85)

8:Compute $\mathrm{x}_{*}^{\epsilon}$ by solving the ODE (1) for
$\alpha_{*}^{\epsilon}$ and the initial state $x$.

9:Compute $\tau_{*}=t_{k^{\prime}}$, where $k^{\prime}$ minimizes (65).

##  7 Numerical Examples

This section provides two numerical examples to demonstrate the Lax formulae
for Problems 1 and 2.

###  7.1 Problem 1: Robust formation control

We control a multi-robot inspection system. Each robot moves in two-
dimensional space and is equipped with a sensor system. The robots need to
maintain a certain formation during the sensing time, so that each sensor
image and the gathered image map are of good quality. In the presence of
disturbance, the formation might not be maintained, and we would like to
robustly control the multi-robot system so that the formation violation is
minimized. Suppose the required sensing time is 2 s, and each robot is a four
dimensional system, which follows

$\displaystyle\begin{split}&\dot{\mathrm{x}}_{1}^{r}(s)=\mathrm{x}_{2}^{r}(s),\quad\dot{\mathrm{x}}_{2}^{r}(s)=\alpha_{1}^{r}(s)\cos\alpha_{2}^{r}(s)+d(s),\\\
&\dot{\mathrm{x}}_{3}^{r}(s)=\mathrm{x}_{4}^{r}(s),\quad\dot{\mathrm{x}}_{4}^{r}(s)=\alpha_{1}^{r}(s)\sin\alpha_{2}^{r}(s),\end{split}$
(89)

where
$\mathrm{x}^{r}(s)=(\mathrm{x}^{r}_{1}(s),\mathrm{x}^{r}_{2}(s),\mathrm{x}^{r}_{3}(s),\mathrm{x}^{r}_{4}(s))\in\mathbb{R}^{4}$
for all $s\in[0,2]$,
$\mathrm{x}=(\mathrm{x}^{1},...,\mathrm{x}^{R})\in\mathbb{R}^{4R}$, $R=10$ is
the number of the robots, $r=1,...,R$, and $d$ is the horizontal disturbance:
$d(s)=0.5(1+\cos\pi s)$. $\mathrm{x}_{1}$ and $\mathrm{x}_{2}$
($\mathrm{x}_{3}$ and $\mathrm{x}_{4}$) are horizontal (vertical) position and
velocity, $\alpha_{1}^{r}$ is the magnitude of acceleration, and
$\alpha_{2}^{r}$ is the angle of the acceleration of robot $r$.

Consider the following problem:

$\displaystyle\begin{split}&\quad\quad\inf_{\alpha}\max_{\tau\in[0,2]}\lVert(\mathrm{x}^{1}_{1}(\tau),\mathrm{x}^{1}_{3}(\tau))-x_{g}^{1}\rVert_{2}\\\
&\quad\quad+\sum_{r=2}^{R}\lVert(\mathrm{x}^{r}_{1}(\tau),\mathrm{x}^{i}_{3}(\tau))-(\mathrm{x}^{r}_{1}(\tau),\mathrm{x}^{1}_{3}(\tau))-o^{r}\rVert_{2}\end{split}$
(90) $\displaystyle\text{subject to}\begin{cases}\eqref{eq:exaple1_dyn},\text{
}\alpha^{r}(s)\in[-1,1]\times[-\frac{\pi}{6},\frac{\pi}{6}],\text{
}s\in[0,2],&\\\ \mathrm{x}(0)=x,\\\ \mathrm{x}_{1}^{r}(s)\leq
5.2,\mathrm{x}_{2}^{r}(s)\geq 0,\quad r=1,...,R,s\in[0,2].\end{cases}$ (91)

The stage cost $L$ is zero, $x_{g}^{1}$ is $(1,1)$,
$o^{r}=(0.4rR/(R-1),0)(\in\mathbb{R}^{2})$ is the offset for the formation of
robot $i$ with respect to robot $1$, and the initial state of the robots is
the positions whose corresponding cost is zero with randomly chosen velocities
between -0.5 and 0.5:
$(\mathrm{x}^{1}_{1}(0),\mathrm{x}^{1}_{3}(0))=x_{g}^{1}$ and
$(\mathrm{x}^{r}_{1}(\tau),\mathrm{x}^{r}_{3}(\tau))=(\mathrm{x}^{1}_{1}(\tau),\mathrm{x}^{1}_{3}(\tau))+o^{r}$.

For the given problem, the Hamiltonian $H$ in (32) becomes

$\displaystyle H(s,x,p)=\bar{H}(s,x,z,p,-1)$ $\displaystyle=$
$\displaystyle\max_{\begin{subarray}{c}a^{r}\in[-1,1]\times[-\frac{\pi}{6},\frac{\pi}{6}],\\\
r=1\dots
R\end{subarray}}-\sum_{r}\begin{tabular}[]{l}$\big{(}p^{r}_{1}x^{r}_{2}+p^{r}_{2}(a_{1}^{r}\cos
a_{2}^{r}+d(s))$\\\ $+p^{r}_{3}x_{4}^{r}+p^{r}_{4}a_{1}^{r}\sin
a_{2}^{r}\big{)}$\end{tabular}$ (94) $\displaystyle=$
$\displaystyle\sum_{r}\begin{tabular}[]{l}$-p_{1}^{r}x_{2}^{r}-p_{2}^{r}d(s)-p_{3}^{r}x_{4}^{r}$\\\
$+\max\\{\|(p_{2}^{r},p_{4}^{r})\|_{2},|p_{2}^{r}|\frac{\sqrt{3}}{2}+|p_{4}^{r}|\frac{1}{2}\\}$.\end{tabular}$
(97)

$H$ is convex in $p$, and any supporting hyperplane for $H$ can be written as
$b\cdot p=0$ for some normal vector $b$. Since the supporting hyperplane
$b\cdot p=0$ passes through the origin for any $b$,

$\displaystyle H^{*}(s,x,b)=0$ (98)

for $b\in\text{Dom}(H^{*}(s,x,\cdot))=\text{co}(B(s,x))$. See Lemma 5 for the
above property for the domain of $H^{*}$. In general, if the stage cost $L$ is
zero, $H^{*}$ becomes zero, which has been investigated in [7].

By the Lax formula for Problem 1 in Theorem 1, (90) subject to (91) is
equivalent to

$\displaystyle\begin{split}&\quad\quad\inf_{\beta}\max_{\tau\in[0,2]}\lVert(\mathrm{x}^{1}_{1}(\tau),\mathrm{x}^{1}_{3}(\tau))-x_{g}^{1}\rVert_{2}\\\
&\quad\quad+\sum_{i=2}^{r}\lVert(\mathrm{x}^{r}_{1}(\tau),\mathrm{x}^{r}_{3}(\tau))-(\mathrm{x}^{1}_{1}(\tau),\mathrm{x}^{1}_{3}(\tau))-o^{r}\rVert_{2}\end{split}$
(99) $\displaystyle\text{subject
to}\begin{cases}\mathrm{x}^{r}(s)=-\beta^{r}(s),\\\
\beta^{r}_{1}(s)=-\mathrm{x}^{r}_{2}(s),\beta^{r}_{3}(s)=-\mathrm{x}^{r}_{4}(s),\\\
\lVert(\beta^{r}_{2}(s)+d(s),\beta^{r}_{4}(s))\rVert_{2}\leq
1,|\beta^{r}_{4}(s)|\leq\frac{1}{2},&\\\ \mathrm{x}(0)=x,\\\
\mathrm{x}_{1}^{r}(s)\leq 5.2,\mathrm{x}_{2}^{r}(s)\geq 0,\quad
r=1,...,R,s\in[0,2],\end{cases}$ (100)

where $\beta(s)=(\beta^{1},...,\beta^{R})(s)$ and
$\beta^{r}(s)=(\beta_{1}^{r},\beta_{2}^{r},\beta_{3}^{r},\beta_{4}^{r})(s)$.
Note that $B(s,x)=B^{1}(s,x^{1})\times\dots\times B^{R}(s,x^{R})$,

$\displaystyle
B^{r}(s,x^{r})=\left\\{(-x_{2}^{r},b_{2},-x_{4}^{r},b_{4})\bigg{|}\begin{tabular}[]{l}$\lVert(b_{2}+d(s),b_{4})\rVert_{2}\leq
1,$\\\ $|b_{4}|\leq\sqrt{3}|b_{2}+d(s)|$\end{tabular}\right\\},$ (103)

and $\text{co}(B(s,x))$ can be found in (100).

The given problem (90) subject to (91) is non-convex, but the Lax formula (99)
subject to (100) is convex since Condition 2 is satisfied, which allows the
proposed Lax formula to provide an optimal solution.

For numerical computation of the Lax formula, we discretize the temporal space
to $\\{t_{0}=0\dots t_{K}=2\\}$ with $\Delta_{k}=0.1$ (21 time steps). The
computation time to solve the Lax formula ((99) subject to (100)) is 103.7 s,
in which the optimal control signal $\beta_{*}$ and state trajectory
$\mathrm{x}_{*}$ are computed. This system is 40 dimension with 10 robots, for
which it is intractable to utilize grid-based methods (such as the level-set
method [3]) to solve the HJ equations (9).

We follow Algorithm 1 to compute an optimal control signal
($\alpha_{*}^{\epsilon}$ in (75)) for the given problem. Applying line 5 to 7
in Algorithm 1 for each robot also works. In other words, we first find
$a_{i}^{k,r}$ and $\gamma_{i}^{k,r}$ for robot $r=1,...,R$ as in (74). For
$\beta_{*}^{r}(t_{k})=(\beta_{*,1}^{r},\beta_{*,2}^{r},\beta_{*,3}^{r},\beta_{*,4}^{r})(t_{k})\in
B^{r}(t_{k},\mathrm{x}_{*}^{r}(t_{k}))$,

$\displaystyle
a_{1}^{k,r}=\small\begin{pmatrix}\text{sign}\left(-\beta_{*,2}^{r}(t_{k})-d(t_{k})\right)\left\|\begin{pmatrix}\beta_{*,2}^{r}(t_{k})+d(t_{k})\\\
\beta_{*,4}^{r}(t_{k})\end{pmatrix}\right\|_{2}\\\
\arctan\left(\beta_{*,4}^{r}(t_{k})/\left(\beta_{*,2}^{r}(t_{k})+d(t_{k})\right)\right)\end{pmatrix},$
(104)

$\gamma_{1}^{k,r}=1$, and for $\beta_{*}^{r}(t_{k})$ in
$\text{co}(B^{r}(t_{k},\mathrm{x}_{*}^{r}(t_{k})))$ but not in
$B^{r}(t_{k},\mathrm{x}_{*}^{r}(t_{k}))$,

$\displaystyle
a_{1}^{k,r}=\left(-2\beta_{*,4}^{r}(t_{k}),\pi/6\right),a_{2}^{k,r}=-a_{1}^{k,r},$
(105)
$\displaystyle\gamma_{1}^{k,r}=\frac{|-\beta_{*}(t_{k},2)-d(t_{k})-\sqrt{3}\beta_{*,4}(t_{k})|}{|2\sqrt{3}\beta_{*,4}(t_{k})|},$
(106)
$\displaystyle\gamma_{2}^{k,r}=\frac{|\beta_{*,2}(t_{k})+d(t_{k})-\sqrt{3}\beta_{*,4}(t_{k})|}{|2\sqrt{3}\beta_{*,4}(t_{k})|}.$
(107)

Based on the computed $a_{1}^{k,r}$ and $\gamma_{i}^{k,r}$ for robot $r$, each
approximate optimal control signal $\alpha_{*}^{r,\epsilon}$ is designed as in
(75), and the corresponding state trajectory $\mathrm{x}_{*}^{\epsilon}$ can
be also computed by solving the ODE (1) for $\alpha_{*}^{\epsilon}$, where
$\alpha_{*}^{\epsilon}=(\alpha_{*}^{1,\epsilon},...,\alpha_{*}^{R,\epsilon})$.

---
Figure 1:  (a) The red lines are the optimal state trajectories of the 10
robots that robustly minimize the worst formation violation in the given time
horizon. The blue triangles are the initial position of the robots, and the
black circles are the position of the robots at which the cost
$g(\mathrm{x}_{*}(\tau))$ is maximized. (b) Under the optimal control, the
worst cost is attained at 1 s.

Figure 1 (a) shows an optimal position of the robots, and Figure 1 (b) shows
the cost over the time. The cost is maximized at 1 s, at which the positions
of the robots are marked as the black circles in Figure 1 (a). The blue
triangles are the initial positions of the robots. Even under the disturbance,
all robots avoid the obstacles.

###  7.2 Lax formula for the time-invariant Problem 2

In this example, we also deal with a multi-robot system with each robot moving
in two-dimensional space, and the goal is to find an optimal control signal
and time that achieve the best formation of the robot system over the given
time horizon. Suppose the given time-horizon is 2 s, and each robot is a two
dimensional system:

$\displaystyle\dot{\mathrm{x}}_{1}^{r}(s)=\alpha_{1}^{r}(s)+2,\quad\dot{\mathrm{x}}_{2}^{r}(s)=\alpha_{2}^{r}(s),$
(108)

where $\mathrm{x}=(\mathrm{x}^{1},...,\mathrm{x}^{R})$, $R=10$ is the number
of the robots,
$\mathrm{x}^{r}(s)=(\mathrm{x}_{1}^{r}(s),\mathrm{x}_{2}^{r}(s))\in\mathbb{R}^{2}$
for all $s\in[0,2]$, $r=1,..,R$,
$\alpha^{r}(s)=(\alpha_{1}^{r},\alpha_{2}^{r})(s)\in\mathbb{R}^{2}$, and
$\|\alpha^{r}(s)\|_{\infty}\leq 1$.

Consider the following problem:

$\displaystyle\inf_{\alpha}\min_{\tau\in[0,2]}\lVert\mathrm{x}^{1}(\tau)-x_{g}^{1}\rVert_{2}+\sum_{r=2}^{R}\lVert\mathrm{x}^{r}(\tau)-\mathrm{x}^{1}(\tau)-o^{r}\rVert_{2}$
(109) $\displaystyle\text{subject
to}\begin{cases}\eqref{eq:ex2_dyn},\lVert\alpha^{r}(s)\rVert_{\infty}\leq
1,s\in[0,2],\\\ \mathrm{x}(0)=x,\\\ \mathrm{x}_{1}^{r}(s)\leq
5,\mathrm{x}_{2}^{r}(s)\geq 0,r=1\dots R,s\in[0,\tau],\end{cases}$ (110)

where $x_{g}^{1}=(1,1)$, $o^{r}=(0.4rR/(R-1),0)\in\mathbb{R}^{2}$ is the
offset for the formation of robot $r$ with respect to robot $1$, the initial
state of the first robot is randomly sampled near the goal state $x_{g}^{1}$,
and for the other robots, the initial states are randomly sampled near
$x_{g}^{1}+o^{r}$.

For this problem, the Hamiltonian in (10) is

$\displaystyle\bar{H}(x,z,p,q)$
$\displaystyle=\max_{\begin{subarray}{c}\|a^{r}\|_{\infty}\leq 1,\\\ r=1\dots
R\end{subarray}}-\sum_{r}\left(p^{r}_{1}(a^{r}_{1}+2)+p^{r}_{2}a^{r}_{2}\right)$
$\displaystyle=-2\sum_{i}p_{1}^{r}+\|p\|_{1},$ (111)

where $p=(p^{1},...,p^{R})\in\mathbb{R}^{2R}$, and
$p^{r}=(p_{1}^{r},p_{2}^{r})\in\mathbb{R}^{2}$. By (32) and (51),

$\displaystyle
H_{2}^{\textnormal{TI}}(x,p)=\max\\{0,-2\sum_{r}p_{1}^{r}+\|p\|_{1}\\}.$ (112)

Since $H_{2}^{\textnormal{TI}}$ is a pointwise maximum of two convex functions
in $p$, $H_{2}^{\textnormal{TI}}$ is convex in $p$. Also, for all
$b\in\mathbb{R}^{2R}$, the supporting hyperplane of $H_{2}^{\textnormal{TI}}$
in $p$-space with respect to the normal vector $b$ crosses the origin. Thus,

$\displaystyle H_{2}^{\textnormal{TI}*}(x,b)=0$ (113)

for
$b=(b^{1},...,b^{R})=(b^{1}_{1},b^{1}_{2},...,b^{R}_{1},b^{R}_{2})\in\text{Dom}(H_{2}^{\textnormal{TI}*}(x,\cdot))=\text{co}(\\{0\\}\cup
B(x))$, where $B(x)=\\{[-3,-1]\times[-1,1]\\}^{R}$ and

co $\displaystyle(\\{0\\}\cup B(x))=\big{\\{}b~{}|~{}\forall
r_{1},r_{2}\in\\{1,...,R\\},$ $\displaystyle-3\leq
b^{r_{1}}_{1},|b_{2}^{r_{1}}|\leq 1,b^{r_{1}}_{1}-3b^{r_{2}}_{1}\geq
0,b^{r_{1}}_{1}-\frac{1}{3}b^{r_{2}}_{1}\leq 0,$ $\displaystyle
b^{r_{1}}_{2}-b^{r_{2}}_{1}\geq 0,b^{r_{1}}_{2}+b^{r_{2}}_{1}\leq 0\big{\\}}.$
(114)

By the Lax formula for the time-invariant Problem 2 in Theorem 6 and (113),
the given problem is equivalent to

$\displaystyle\quad\quad\inf_{\beta}\lVert\mathrm{x}^{1}(2)-x_{g}^{1}\rVert_{2}+\sum_{r=2}^{R}\lVert\mathrm{x}^{r}(2)-\mathrm{x}^{1}(2)-o^{r}\rVert_{2}$
(115) $\displaystyle\text{subject to
}\begin{cases}\dot{\mathrm{x}}^{r}(s)=-\beta^{r}(s),\\\
\beta(s)\in\text{co}\left(\\{0\\}\cup B(\mathrm{x}_{*}(s))\right)\text{ in
\eqref{eq:ex2_CtrlSet}},\\\ \mathrm{x}(0)=x\\\ \mathrm{x}_{1}^{r}(s)\leq
5,\mathrm{x}_{2}^{r}(s)\geq 0,r=1\dots R,s\in[0,2].\end{cases}$ (116)

The temporally discretized Lax formula for the time-invariant Problem 2 ((115)
subject to (116)) is convex although the temporally discretized given problem
((90) subject to (91)) is non-convex. Thus, the Lax formula ((115) subject to
(116)) provides an optimal solution by utilizing gradient-based methods. This
formula is numerically solved by the interior-point method, in which numerical
optimal control signal $\beta_{*}$ and state trajectory $\mathrm{x}_{*}$ are
specified. The computational time is 82.6 s. Since the dimension of the system
is 20, it is intractable to utilize any grid-based method to solve the HJ
equation (19).

Using $\beta_{*}$ and $\mathrm{x}_{*}$, we follow the steps in Algorithm 2.
Denote $\beta_{*}(t_{k})=(\beta_{*}^{1},...,\beta_{*}^{R})(t_{k})$ and
$\beta_{*}^{r}=(\beta_{*,1}^{r},\beta_{*,2}^{r})$. First, we find $a_{i}^{k}$
and $\gamma_{i}^{k}$ as in (81). For $\beta_{*}(t_{k})\in
B(\mathrm{x}_{*}(t_{k}))=\\{[-3,-1]\times[-1,1]\\}^{R}$, $a_{1}^{k}$ is
$(a_{1}^{k,1},...,a_{1}^{k,r})\in\mathbb{R}^{2R}$, where

$\displaystyle
a_{1}^{k,r}=(-\beta_{*,1}^{1}(t_{k})-2,-\beta_{*,2}^{1}(t_{k})),\text{ and
}\gamma_{1}^{k}=1.$ (117)

For $\beta_{*}(t_{k})$ in $\text{co}(\\{0\\}\cup B(\mathrm{x}_{*}(t_{k}))\\}$
but not in $B(\mathrm{x}_{*}(t_{k}))$, $a_{1}^{k}$ is
$(a_{1}^{k,1},...,a_{1}^{k,r})\in\mathbb{R}^{2R}$,

$\displaystyle
a_{1}^{k,r}=(-\beta_{*,1}^{r}(t_{k})/\gamma_{1}^{k}-2,-\beta_{*,2}^{r}(t_{k})/\gamma_{1}^{k}),$
(118)
$\displaystyle\gamma_{1}^{k}=-\max_{r=1,...,R}\beta_{*,1}^{r}\in[0,1]\subset\mathbb{R}.$
(119)

Using the above $a_{i}^{k,r}$ and $\gamma_{i}^{k,r}$, an approximate optimal
control signal $\alpha_{*}^{\epsilon}$ is designed as in (85), and the
corresponding state control trajectory $\mathrm{x}_{*}^{\epsilon}$ is computed
by solving the dynamics ODE (1).

---
Figure 2:  (a) The red lines are the optimal state trajectories of the 10
robots. The blue triangles and the black circles are the position of the
robots at the initial time and the optimal time, respectively. Since the
horizontal disturbance is big, some of robots on the right side cannot avoid
the collision. (b) The cost over $\tau$ ($g(\mathrm{x}_{*}(\tau))$) is
minimized at $\tau=0.32$ (s). For $\tau>0.32$, the cost
$g(\mathrm{x}_{*}(\tau))$ becomes the infinity since the state constraint is
violated.

Figure 2 (a) shows the optimal state (position) trajectories of the robot
system from the initial time to the minimum time ($\tau=0.32$ s) that
minimizes the given cost. Since the horizontal disturbance is more dominant
than the robots’ control, there exist some time ($\tau=0.32$ s) when one of
the robots violates the state constraint in the given horizon. As shown in
Figure 2 (b), the cost is minimized at $\tau=0.32$ (s) after which the state
constraint is violated.

###  7.3 Discussion

Benefits of grid-based methods, such as the level set methods [3] and fast
marching method [12], are that the global optimality is guaranteed, and a
closed-loop control is provided. In other words, the optimal control is
provided for any state-time pair. However, due to computational complexity,
grid-based methods are typically implemented offline to precompute the value
function, and then used online with feedback. Offline computation of grid-
based methods is intractable for systems with continuous state dimension
higher than six or seven.

The first and second examples in this paper are systems with forty and twenty
state dimensions, whose dimensions are too high for grid-based methods. Using
the proposed method, the computation time for each example is 103.7 and 82.6
s, respectively. In comparison to grid-based methods, this efficient
computation is achieved since our method is gradient-based. Although gradient-
based methods provide local optimal solutions for non-convex problems, the
proposed method guarantees the global optimality under the specified
conditions in Table 1. Even though our methods provides an optimal control
signal, unfortunately as with other gradient-based method, this is an open-
loop control.

To have a closed-loop control, our method could cooperate with closed-loop
control frameworks, such as model predictive control (MPC). Closed-loop
control is achieved by solving optimal control problems in real-time, and the
real-time computation is allowed by the receding horizon setting. Our method
can cooperate with a number of MPC methods [15] to have a closed-loop control
and real-time computation.

##  8 Conclusion and Future Work

This paper presents three Lax formulae for 1) Problem 1, 2) Problem 2, and 3)
the time-invariant Problem 2, and the Lax formulae are efficiently computed by
gradient-based methods. The derivation of the Lax formulae is based on
proposed viscosity theory that provides a sufficient condition under which two
different HJ equations have the same solution. Furthermore, this paper
provides a set of convexity conditions under which the Lax formulae provide an
optimal solution by the gradient-based methods: for Problem 1, the convexity
in the state is required but not in the control; Problem 2 is generally non-
convex; for the time-invariant Problem 2, the dynamics and the stage cost only
depend on the control, and the terminal cost and the state constraint are
convex in the state. This paper also presents a numerical algorithm for the
Lax formulae. For each class of problems, an example demonstrates how to
utilize the Lax formulae and the numerical algorithm, and show the performance
as well.

###  .1 Proof of Theorem 3

(i) The terminal values of $X_{1}$ and $X_{2}$ are the same.

(ii) $X_{1}$ is a subsolution to the PDE $0=F_{2}$.

Since $X_{1}$ is a subsolution to the PDE
$0=F_{1}(t,x,z,X_{1},X_{1,t},D_{x}X_{1},D_{z}X_{1})$, for any $U\in
C^{1}((0,T)\times\mathbb{R}^{n}\times\mathbb{R})$ such that $X_{1}-U$ has a
local maximum at
$(t_{0},x_{0},z_{0})\in(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$ and
$(X_{1}-U)(t_{0},x_{0},z_{0})=0$,

$\displaystyle\begin{split}F_{1}(t_{0},x_{0},z_{0},U_{0},U_{t0},D_{x}U_{0},D_{z}U_{0})\geq
0,\end{split}$ (120)

where $U_{0}=U(t_{0},x_{0},z_{0})$, $U_{t0}=U_{t}(t_{0},x_{0},z_{0})$,
$D_{x}U_{0}=D_{x}U(t_{0},x_{0},z_{0})$, and
$D_{z}U_{0}=D_{z}U(t_{0},x_{0},z_{0})$. Since $X_{1}-U$ has a local maximum at
$(t_{0},x_{0},z_{0})$, $D_{z}U_{0}$ is in the superdifferential of $X_{1}$
with respect to $z$: $D_{z}U_{0}\in D_{z}^{+}X_{1}(t_{0},x_{0},z_{0})$. By
(26),

$\displaystyle F_{2}(t_{0},x_{0},z_{0},U_{0},U_{t0},D_{x}U_{0},D_{z}U_{0})\geq
0.$ (121)

(iii) $X_{1}$ is a supersolution to the PDE $0=F_{2}$.

Since $X_{1}$ is a supersolution to the PDE $0=F_{1}$, for any $U\in
C^{1}((0,T)\times\mathbb{R}^{n}\times\mathbb{R})$ such that $X_{1}-U$ has a
local minimum at
$(t_{0},x_{0},z_{0})\in[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$ and
$(X_{1}-U)(t_{0},x_{0},z_{0})=0$,

$\displaystyle\begin{split}F_{1}(t_{0},x_{0},z_{0},U_{0},U_{t0},D_{x}U_{0},D_{z}U_{0})\leq
0,\end{split}$ (122)

Since $X_{1}-U$ has a local minimum at $(t_{0},x_{0},z_{0})$, $D_{z}U_{0}$ is
in the subdifferential of $X_{1}$ with respect to $z$
($D_{z}^{-}X_{1}(t_{0},x_{0},z_{0})$). By (26),

$\displaystyle F_{2}(t_{0},x_{0},z_{0},U_{0},U_{t0},D_{x}U_{0},D_{z}U_{0})\leq
0.$ (123)

∎

###  .2 Proof of Lemma 3

(i) For all $y_{1},y_{2},y_{3},y_{4}\in\mathbb{R}$,

$\displaystyle\max\\{y_{1}+y_{2},y_{3}+y_{4}\\}\leq\max\\{y_{1},y_{3}\\}+\max\\{y_{2},y_{4}\\}.$
(124)

(ii) Proof of (27) for $V_{1}$.

Let

$\displaystyle\text{Const}(\alpha,\tau)\coloneqq\max_{s\in[t,T]}c(s,\mathrm{x}(s)),$
(125)
$\displaystyle\text{Cost}(\alpha,\tau)\coloneqq\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s))ds+g(\tau,\mathrm{x}(\tau)).$
(126) $\displaystyle V_{1}(t,x,\theta_{1}z_{1}+\theta_{2}z_{2})$
$\displaystyle=$
$\displaystyle\min_{\alpha\in\mathcal{A}}\max_{\tau\in[t,T]}\max\big{\\{}\theta_{1}\text{Const}(\alpha,\tau)+\theta_{2}\text{Const}(\alpha,\tau),$
$\displaystyle\quad\quad\quad\quad\quad{\color[rgb]{1,1,1}i}\theta_{1}\big{[}\text{Cost}(\alpha,\tau)-z_{1}\big{]}+\theta_{2}\big{[}\text{Cost}(\alpha,\tau)-z_{2}\big{]}\big{\\}}$
$\displaystyle\leq$
$\displaystyle\min_{\alpha\in\mathcal{A}}\max_{\tau\in[t,T]}\theta_{1}\max\big{\\{}\text{Const}(\alpha,\tau),\text{Cost}(\alpha,\tau)-z_{1}\big{\\}}$
$\displaystyle\quad\quad\quad\quad+\theta_{2}\max\big{\\{}\text{Const}(\alpha,\tau),\text{Cost}(\alpha,\tau)-z_{2}\big{\\}}.$
(127)

The first equality is according to the distributive property of the maximum
operations, and the second inequality is by (124). For $\alpha\in\mathcal{A}$,
we use $\tau_{*}(\alpha)$ to denote a maximizer of the last term in (127). By
the triangular inequality, we simplify (127) to

$\displaystyle V_{1}(t,x,\theta_{1}z_{1}+\theta_{2}z_{2})$ $\displaystyle\leq$
$\displaystyle\min_{\alpha\in\mathcal{A}}\theta_{1}\max\big{\\{}\text{Const}(\alpha,\tau),\text{Cost}(\alpha,\tau_{*}(\alpha))-z_{1}\big{\\}}$
$\displaystyle+$
$\displaystyle\min_{\alpha\in\mathcal{A}}\theta_{2}\max\big{\\{}\text{Const}(\alpha,\tau),\text{Cost}(\alpha,\tau_{*}(\alpha))-z_{2}\big{\\}}$
$\displaystyle\leq$
$\displaystyle\theta_{1}V_{1}(t,x,z_{1})+\theta_{2}V_{1}(t,x,z_{2}).$ (128)

The last inequality holds by the definition of $V_{1}$ in (7).

(iii) Similar to (127),

$\displaystyle V_{2}(t,x,\theta_{1}z_{1}+\theta_{2}z_{2})$ $\displaystyle\leq$
$\displaystyle\min_{\alpha\in\mathcal{A}}\min_{\tau\in[t,T]}\theta_{1}\max\big{\\{}\text{Const}(\alpha,\tau),\text{Cost}(\alpha,\tau)-z_{1}\big{\\}}$
$\displaystyle\quad\quad\quad+\theta_{2}\max\big{\\{}\text{Const}(\alpha,\tau),\text{Cost}(\alpha,\tau)-z_{2}\big{\\}}.$
(129)

Since the the last term in (129) is greater than or equal to
$\theta_{1}V_{2}(t,x,z_{1})+\theta_{2}V_{2}(t,x,z_{2})$ by the triangular
inequality, we conclude the proof. ∎

###  .3 Proof of Lemma 4

(i) The proof of (28).

For $\bar{z}\geq 0$, $V_{1}(t,x,z+\bar{z})\leq V_{1}(t,x,z)$, and by the
distributive property of the maximum operations,

$\displaystyle V_{1}(t,x,z+\bar{z})$
$\displaystyle=\inf_{\alpha\in\mathcal{A}}\max_{\tau\in[t,T]}\max\Big{\\{}\max_{s\in[t,T]}c(s,\mathrm{x}(s))+\bar{z},$
$\displaystyle\int_{t}^{\tau}L(s,\mathrm{x}(s),u(s))ds+g(\tau,\mathrm{x}(\tau))-z\Big{\\}}-\bar{z}$
$\displaystyle\geq V_{1}(t,x,z)-\bar{z}.$

Thus, for $\bar{z}\geq 0$,

$\displaystyle V_{1}(t,x,z)-\bar{z}\leq V_{1}(t,x,z+\bar{z})\leq
V_{1}(t,x,z),$ (130)

and, by the same derivation, for $\bar{z}\leq 0$,

$\displaystyle V_{1}(t,x,z)\leq V_{1}(t,x,z+\bar{z})\leq
V_{1}(t,x,z)-\bar{z}.$ (131)

Suppose there exists $q>0$ in $D_{z}^{-}V_{1}(t,x,z)$. Then, there exists
$\epsilon>0$ such that $V_{1}(t,x,z+\bar{z})\geq V_{1}(t,x,z)+q\bar{z}$ for
all $\bar{z}\in[-\epsilon,\epsilon]$. However, for $\bar{z}\in(0,\epsilon)$,

$\displaystyle V_{1}(t,x,z+\bar{z})>V_{1}(t,x,z).$ (132)

This contradicts (130).

Suppose there exists $q<-1$ in $D_{z}^{-}V_{1}(t,x,z)$. Then, there exists
$\epsilon>0$ such that $V_{1}(t,x,z+\bar{z})\geq V_{1}(t,x,z)+q\bar{z}$ for
all $\bar{z}\in[-\epsilon,\epsilon]$. However, for $\bar{z}\in(-\epsilon,0)$,

$\displaystyle V_{1}(t,x,z+\bar{z})>V_{1}(t,x,z)-\bar{z}.$ (133)

This contradicts (131). Thus, $q\in[-1,0]$.

With the analogous derivation for $V_{2}$, we conclude that
$D_{z}^{-}V_{2}(t,x,z)\subset[-1,0]$.

(ii) The proof of (29).

The convexity of $V_{i}(t,x,z)$ ($i=1,2$) stated in Lemma 3 implies that
$D_{z}^{+}V_{i}(t,x,z)$ contains a single superdifferential $q$ if
$V_{i}(t,x,z)$ is locally affine in $z$, otherwise, $D_{z}^{+}V_{i}(t,x,z)$ is
the empty set. If $V_{i}(t,x,z)$ is locally affine in $z$, it is also
differentiable in $z$. As $\bar{z}$ converges to 0 in (130), we have
$D_{z}V_{i}(t,x,z)\in[-1,0]$. Thus, if the superdifferential $q$ exists, $q$
and $D_{z}V_{i}(t,x,z)$ are the same, and $q\in[-1,0]$. ∎

###  .4 Proof of Lemma 6

(i) Case 1: $q=0$.

$\displaystyle\begin{split}\bar{H}(t,x,z,p,0)&=\max_{a\in A}-p\cdot
f(t,x,a)=\max_{b\in B(t,x)}p\cdot b\end{split}$ (134)

by the definition of $B(t,x)$ in (40). Since $B(t,x)\subset\text{co}(B(t,x))$,

$\displaystyle\begin{split}\bar{H}&(t,x,z,p,0)\leq\bar{H}_{W}(t,x,z,p,0).\end{split}$
(135)

On the other hand, let $b_{*}\in\arg\max_{b\in\text{co}(B(t,x))}p\cdot b$.
Since $B(t,x)$ is compact, there exists a finite number of $b_{i}\in B(t,x)$
and $\theta_{i}\in[0,1]$ such that $b_{*}=\sum_{i}\theta_{i}b_{i}$ and
$\sum_{i}\theta_{i}=1$. Then,

$\displaystyle\bar{H}_{W}(t,x,z,p,0)$ $\displaystyle=\sum_{i}\theta_{i}p\cdot
b_{i}\leq\max_{i}\\{p\cdot b_{i}\\}$ $\displaystyle\leq\max_{b\in
B(t,x)}p\cdot b=\bar{H}(t,x,z,p,0).$ (136)

The last inequality holds since all $b_{i}$s are in $B(t,x)$. By (135) and
(136), we have

$\displaystyle\bar{H}$ $\displaystyle(t,x,z,p,0)=\bar{H}_{W}(t,x,z,p,0).$
(137)

(ii) Case 2: $q<0$.

$\displaystyle\begin{split}\bar{H}(t,x,z,p,q)&=\max_{a\in A}-p\cdot
f(t,x,a)+qL(t,x,a)\\\ &=-qH\bigg{(}t,x,-\frac{p}{q}\bigg{)}.\end{split}$ (138)

Since $H$ is convex in $p$ for each $(t,x)$ and lower semi-continuous in $p$,
$H^{**}\equiv H$. Thus, we have

$\displaystyle\bar{H}_{W}(t$
$\displaystyle,x,z,p,q)=-q\max_{b\in\text{co}(B(t,x))}-\frac{p}{q}\cdot
b-H^{*}(t,x,b)$
$\displaystyle=-qH^{**}\bigg{(}t,x,-\frac{p}{q}\bigg{)}=-qH\bigg{(}t,x,-\frac{p}{q}\bigg{)}.$
(139)

By (138) and (139), we conclude

$\displaystyle\bar{H}$ $\displaystyle(t,x,z,p,q)=\bar{H}_{W}(t,x,z,p,q).$
(140)

for all $q<0$. ∎

###  .5 Proof of Lemma 7

This proof generalizes the proof of Lemma 1 [14], which is for the zero stage
cost problem.

(i) For $b\in B(x)$, $b=-f(x,\bar{a})$ for some $\bar{a}\in A$. Then,

$\displaystyle H_{2}^{\textnormal{TI}*}(x,b)$ $\displaystyle=\max_{p}-p\cdot
f(x,\bar{a})-H_{2}^{\textnormal{TI}}(x,p)$ $\displaystyle\leq\max_{p}-p\cdot
f(x,\bar{a})+\min_{a\in A}p\cdot f(x,a)+L(x,a)$ $\displaystyle<\infty.$ (141)

The last inequality holds since $\min_{a\in A}p\cdot f(x,a)+L(x,a)\leq p\cdot
f(x,\bar{a})+L(x,\bar{a})$ and $L$ is finite for a fixed $x$.

(ii) If $b=0$,

$\displaystyle
H_{2}^{\textnormal{TI}*}(x,b)=\max_{p}-H_{2}^{\textnormal{TI}}(x,p)\leq
0<\infty.$ (142)

(iii) $b\in\text{co}(\\{0\\}\cup B(x))$

There exists a finite set of $\theta_{i}\in[0,1]$ ($\sum_{i}\theta_{i}\leq
1$), $a_{i}\in A$ such that $b=-\sum_{i}\theta_{i}f(x,a_{i}).$ Since
$H_{2}^{\textnormal{TI}*}$ is convex in $b$,

$\displaystyle
H_{2}^{\textnormal{TI}*}(x,b)\leq\sum_{i}\theta_{i}H_{2}^{\textnormal{TI}*}(x,b_{i})+(1-\sum_{i}\theta_{i})H_{2}^{\textnormal{TI}*}(x,0)<\infty$

by (141) and (142).

(iv) $b\notin\text{co}(\\{0\\}\cup B(x))$

For the two convex sets $\\{b\\}$ and $\text{co}(\\{0\\}\cup B(x))$, by the
separating hyperplane theorem [16], there exists a hyperplane
($P\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}^{n}\rightarrow\mathbb{R}$):
$P(b^{\prime})\mathrel{\mathop{\mathchar 58\relax}}=p^{\prime}\cdot
b^{\prime}+c$ such that $P(b)>0$ but $P(b^{\prime})<0$ for all
$b^{\prime}\in\text{co}(\\{0\\}\cup B(x))$. By picking $p=dp^{\prime}$,

$\displaystyle
H_{2}^{\textnormal{TI}*}(x,b)\geq\max_{d}\min\big{\\{}dp^{\prime}\cdot
b,\min_{a\in A}dp^{\prime}\cdot(b+f(x,a))+L(x,a)\big{\\}}.$

Since $p^{\prime}\cdot b>0$ and $p^{\prime}\cdot(b+f(x,a))>0$ for all $a\in
A$, the maximum of the right term in the above equation is attained at
$d=\infty$, thus, $H_{2}^{\textnormal{TI}*}(x,b)=\infty$. $\blacksquare$

###  .6 Proof of Lemma 8

(i) Case 1: $q=0$.

$\displaystyle\bar{H}^{\textnormal{TI}}_{2}(x,z,p,0)=\max\\{0,\max_{b\in
B(x)}p\cdot b\\},$ (143)

where $B(x)$ is defined in (53). Since $B(x)\subset\text{co}(\\{0\\}\cup
B(x))$,

$\displaystyle\bar{H}^{\textnormal{TI}}_{2}(x,z,p,0)\leq\bar{H}^{\textnormal{TI}}_{W}(x,z,p,0).$
(144)

On the other hand, let $b_{*}\in\arg\max_{b\in\text{co}(\\{0\\}\cup
B(x))}p\cdot b$, then, there exists a finite number of $b_{i}\in B(x)$ and
$\theta_{i}\in[0,1]$ such that $b_{*}=\sum_{i}\theta_{i}b_{i}$ and
$\sum_{i}\theta_{i}<1$. Thus, we have

$\displaystyle\bar{H}_{W}^{\textnormal{TI}}(x,z,p,0)$
$\displaystyle=\sum_{i}\theta_{i}p\cdot b_{i}\leq\max\\{0,\max_{i}p\cdot
b_{i}\\}$ $\displaystyle\leq\bar{H}^{\textnormal{TI}}_{2}(x,z,p,0).$ (145)

Combining (144) and (145), we have

$\displaystyle\bar{H}_{W}^{\textnormal{TI}}(x,z,p,0)=\bar{H}^{\textnormal{TI}}_{2}(x,z,p,0).$
(146)

(ii) Case 2: $q<0$.

$\displaystyle\bar{H}_{2}^{\textnormal{TI}}(x,z,p,q)=-q\max\bigg{\\{}0,H\bigg{(}x,-\frac{p}{q}\bigg{)}\bigg{\\}}$
(147)

and, since $H_{2}^{\textnormal{TI}**}\equiv H_{2}^{\textnormal{TI}}$ by the
convexity of $H_{2}^{\textnormal{TI}}$ in $p$,

$\displaystyle\bar{H}_{W}^{\textnormal{TI}}(x,z,p,q)=-qH_{2}^{\textnormal{TI}}\bigg{(}x,-\frac{p}{q}\bigg{)}.$
(148)

By combining (147), (148), and (51), we conclude the proof. ∎

###  .7 Proof of Lemma 9

Proof.
(i) For each $k^{\prime}\in\\{0,...,K\\}$,

$\displaystyle\sum_{k=0}^{k^{\prime}}L(t_{k},\mathrm{x}[k],\alpha[k])+g(t_{k^{\prime}},\mathrm{x}[k^{\prime}])$
(149)

is convex in $([\mathrm{x}[\cdot],\alpha[\cdot])$. Since a pointwise maximum
of a family of convex functions is convex, the cost (61) is convex in
$([\mathrm{x}[\cdot],\alpha[\cdot])$.

(ii) The dynamical constraint, the control constraint, the initial state
constraint, the state constraints are all convex in
$([\mathrm{x}[\cdot],\alpha[\cdot])$. ∎

###  .8 Proof of Theorem 7

Proof. Let

$\displaystyle
J_{1}(\tau)=\int_{0}^{\tau}H^{*}(s,\mathrm{x}_{*}(s),\beta_{*}(s))ds+g(\tau,\mathrm{x}_{*}(\tau)),$
(150) $\displaystyle
J_{2}(\tau)=\int_{0}^{\tau}L(s,\mathrm{x}_{*}^{\epsilon}(s),\alpha_{*}^{\epsilon}(s))ds+g(\tau,\mathrm{x}_{*}^{\epsilon}(\tau)).$
(151)

Theorem 3 in [7] states that for any $\epsilon>0$, there exists $\delta>0$
such that, for any discretization $\\{t_{0}=0,...,t_{K}=T\\}$ where
$\max_{k}|\Delta t_{k}|<\delta$:

$\displaystyle\|\mathrm{x}_{*}-\mathrm{x}_{*}^{\epsilon}\|_{L^{\infty}(0,T;\mathbb{R}^{n})}<\epsilon,$
(152) $\displaystyle\|J_{1}(\tau)-J_{2}(\tau)\|_{L^{\infty}(0,T)}<\epsilon.$
(153)

(i) (152) and Assumption 1 imply (76) and (77).

(ii) Let

$\displaystyle\tau_{*}^{1}\in\arg\max_{\tau\in[0,T]}J_{1}(\tau),\quad\tau_{*}^{2}\in\arg\max_{\tau\in[0,T]}J_{2}(\tau).$
(154)

Then, we have

$\displaystyle V_{1}(0,x)\geq
J_{1}(\tau_{*}^{2})~{}~{}\text{and}~{}~{}\max_{\tau\in[0,T]}J_{2}(\tau)\geq
J_{2}(\tau_{*}^{1}).$ (155)

Since, for all $\epsilon>0$, there exists $\delta>0$ such that (153) for both
$\tau_{*}^{1}$ and $\tau_{*}^{2}$,

$\displaystyle
J_{1}(\tau_{*}^{2})>\max_{\tau\in[0,T]}J_{2}(\tau)-\epsilon,\quad
J_{2}(\tau_{*}^{1})>V_{1}(0,x)-\epsilon.$ (156)

Combining with (155) and (156), we conclude

$\displaystyle|V_{1}(0,x)-\max_{\tau\in[0,T]}J_{2}(\tau)|<\epsilon.$ (157)

This concludes the proof of (78). ∎

###  .9 Proof of Theorem 8

Proof. Let

$\displaystyle
J_{1}(\tau)=\int_{0}^{\tau}H_{2}^{\textnormal{TI}*}(\mathrm{x}_{*}(s),\beta_{*}(s))ds+g(\mathrm{x}_{*}(\tau)),$
(158) $\displaystyle
J_{2}(\tau)=\int_{0}^{\tau}L(\mathrm{x}_{*}^{\epsilon}(s),\alpha_{*}^{\epsilon}(s))ds+g(\mathrm{x}_{*}^{\epsilon}(\tau)).$
(159)

By applying Theorem 3 in [7], Theorem 3 in [14] is generalized: for any
$\epsilon>0$, there exists $\delta>0$ such that, for any discretization
$\\{t_{0}=0,...,t_{K}=T\\}$ where $\max_{k}|\Delta t_{k}|<\delta$:

$\displaystyle\|\mathrm{x}_{*}(\cdot)-\mathrm{x}_{*}^{\epsilon}(\sigma(\cdot;\beta_{*}^{1}))\|_{L^{\infty}(0,T;\mathbb{R}^{n})}<\epsilon,$
(160)
$\displaystyle\|J_{1}(\tau)-J_{2}(\sigma(\tau;\beta_{*}^{1}))\|_{L^{\infty}(0,T)}<\epsilon.$
(161)

(160) and Assumption 1 imply (86) and (87). Also, (161) implies (88). ∎

## References

  * [1] D. Lee and C. J. Tomlin, “Hamilton-Jacobi equations for two classes of state-constrained zero-sum games,” _arXiv preprint arXiv:2106.15006_ , 2021\.
  * [2] D. Lee, A. Keimer, A. M. Bayen, and C. J. Tomlin, “Hamilton-Jacobi formulation for state-constrained optimal control and zero-sum game problems,” in _2020 59th IEEE Conference on Decision and Control (CDC)_. IEEE, 2020, pp. 1078–1085.
  * [3] S. Osher and R. Fedkiw, _Level Set Methods and Dynamic Implicit Surfaces_. Springer-Verlag, 2003, vol. 153\.
  * [4] E. Hopf, “Generalized solutions of non-linear equations of first order,” _Journal of Mathematics and Mechanics_ , vol. 14, no. 6, pp. 951–973, 1965\.
  * [5] M. Bardi and L. C. Evans, “On Hopf’s formulas for solutions of Hamilton-Jacobi equations,” _Nonlinear Analysis: Theory, Methods & Applications_, vol. 8, no. 11, pp. 1373–1381, 1984.
  * [6] Y. T. Chow, J. Darbon, S. Osher, and W. Yin, “Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations,” _Journal of Computational Physics_ , vol. 387, pp. 376–409, 2019.
  * [7] D. Lee and C. J. Tomlin, “A computationally efficient Hamilton-Jacobi-based formula for state-constrained optimal control problems,” _arXiv preprint arXiv:2106.13440_ , 2021.
  * [8] P. D. Lax, “Hyperbolic systems of conservation laws ii,” _Communications on pure and applied mathematics_ , vol. 10, no. 4, pp. 537–566, 1957.
  * [9] L. C. Evans, _Partial differential equations_. American Mathematical Society, 2010.
  * [10] P.-L. Lions and J.-C. Rochet, “Hopf formula and multitime Hamilton-Jacobi equations,” _Proceedings of the American Mathematical Society_ , vol. 96, no. 1, pp. 79–84, 1986.
  * [11] J. Darbon and S. Osher, “Algorithms for overcoming the curse of dimensionality for certain Hamilton–Jacobi equations arising in control theory and elsewhere,” _Research in the Mathematical Sciences_ , vol. 3, no. 1, p. 19, 2016.
  * [12] J. A. Sethian, “A fast marching level set method for monotonically advancing fronts,” _Proceedings of the National Academy of Sciences_ , vol. 93, no. 4, pp. 1591–1595, 1996.
  * [13] A. Altarovici, O. Bokanowski, and H. Zidani, “A general Hamilton-Jacobi framework for non-linear state-constrained control problems,” _ESAIM: Control, Optimisation and Calculus of Variations_ , vol. 19, no. 2, pp. 337–357, 2013.
  * [14] D. Lee and C. J. Tomlin, “A Hopf-Lax formula in Hamilton-Jacobi analysis of reach-avoid problems,” _IEEE Control Systems Letters_ , vol. 5, no. 3, pp. 1055–1060, 2020.
  * [15] J. Guanetti, Y. Kim, and F. Borrelli, “Control of connected and automated vehicles: State of the art and future challenges,” _Annual reviews in control_ , vol. 45, pp. 18–40, 2018.
  * [16] S. Boyd and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.

[]Donggun Lee is a Ph.D. student in Mechanical Engineering at UC Berkeley. He
received B.S. and M.S. degrees in Mechanical Engineering from Korea Advanced
Institute of Science and Technology (KAIST), Daejeon, Korea, in 2009 and 2011,
respectively. Donggun works in the area of control theory and robotics. []Dr.
Claire Tomlin is the Charles A. Desoer Professor of Engineering in EECS at
Berkeley. She was an Assistant, Associate, and Full Professor in Aeronautics
and Astronautics at Stanford from 1998 to 2007, and in 2005 joined Berkeley.
Claire works in the area of control theory and hybrid systems, with
applications to air traffic management, UAV systems, energy, robotics, and
systems biology. She is a MacArthur Foundation Fellow (2006), an IEEE Fellow
(2010), in 2017 she was awarded the IEEE Transportation Technologies Award,
and in 2019 was elected to the National Academy of Engineering and the
American Academy of Arts and Sciences.