%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%             This is a LaTeX file, containing the paper
%
%
%             FURTHER RESULTS ON THE BELLMAN EQUATION FOR
%               OPTIMAL CONTROL PROBLEMS WITH EXIT TIMES
%                    AND NONNEGATIVE LAGRANGIANS
%
%                 by M. Malisoff and H. J. Sussmann
%
%
%                Date of this version: August 20, 2001
%
%
%   WARNING:  This is a preliminary version which is not meant for
%   circulation and which should not be quoted without permission.
%
%
%                The paper is 12 printed pages long.
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass{article}
\usepackage{amsfonts,amssymb}
\topmargin -0.65in \textheight 9.0in \oddsidemargin 0.25in
\evensidemargin 0.25in \textwidth 6.25in
\parskip=5pt plus 1pt minus 1pt

\def\bf{\bfseries}
\def\it{\itshape}
\def\eq#1{(\ref{#1})}
\def\diag#1{\mbox{\rm diag}\{#1\}}
\def\tr{^{\rm T}}
%\def\Real{{\Bbb \rho}}
%\def\Compl {{\Bbb C}}
\def\Real{{I\!\!\rho}}
\def\Compl {{C\!\!\!\!I}}
\def\Integer{{I\!\!N}}
\def\spn{{\rm span}}
\newcommand{\supa}{\sup_{\scriptscriptstyle a\in A}}
\newcommand{\implies}{\Rightarrow}
\newcommand{\eps}{\varepsilon}
\newcommand{\norma}[1]{||\, #1 \, ||}
\newcommand{\Norm}{\Vert}
\newcommand{\norms}[1]{\Norm #1 \Norm_\frac{1}{1-s}}
 \newcommand{\normp}[1]{\Norm #1 \Norm_p}
 \newcommand{\normt}[1]{\Norm #1 \Norm_2}
\newcommand{\Br}{\Norm b \Norm_{2r}^{2r}}
\newcommand{\dist}{{\rm dist}}
\newcommand{\scr}{\scriptscriptstyle}
\newcommand{\ind}{1\kern-.4em 1}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}
\newtheorem{itlemma}{Lemma}[section] %number by section (set in \em by default)
%same numbering coter as itlemmas:
\newtheorem{itproposition}[itlemma]{Proposition}
\newtheorem{itcorollary}[itlemma]{Corollary}
\newtheorem{itremark}[itlemma]{Remark}
\newtheorem{itdefinition}[itlemma]{Definition}
\newtheorem{itexample}[itlemma]{Example}

\newenvironment{lemma}{\begin{itlemma}\rm}{\end{itlemma}} %no-italics
\newenvironment{remark}{\begin{itremark}\rm}{\end{itremark}} %no-italics
\newenvironment{corollary}{\begin{itcorollary}\rm}{\end{itcorollary}}
\newenvironment{proposition}{\begin{itproposition}\rm}{\end{itproposition}}
\newenvironment{definition}{\begin{itdefinition}\rm}{\end{itdefinition}}
\newenvironment{example}{\begin{itexample}\rm}{\end{itexample}}

\newcommand{\text}[1]{\hbox{\rm \ #1\ \/}}
%\newcommand{\be}[1]{\begin{equation}\label{#1}}
%\newcommand{\ee}{\end{equation}}

\newcommand{\bl}[1]{\begin{lemma}\label{#1}}
\newcommand{\br}[1]{\begin{remark}\label{#1}}
\newcommand{\bt}[1]{\begin{theorem}\label{#1}}
\newcommand{\bd}[1]{\begin{definition}\label{#1}}
\newcommand{\bp}[1]{\begin{proposition}\label{#1}}
\newcommand{\bc}[1]{\begin{corollary}\label{#1}}
\newcommand{\bfact}[1]{\begin{fact}\label{#1}}
\newcommand{\bex}[1]{\begin{example}\label{#1}}
\newcommand{\bem}[1]{\begin{example}\label{#1}}  %Yes, 2 different ones...
\newcommand{\ec}{\end{corollary}}
\newcommand{\eex}{\end{example}}
\newcommand{\eem}{\end{example}}
\newcommand{\el}{\end{lemma}}
\newcommand{\er}{\end{remark}}
\newcommand{\et}{\end{theorem}}
\newcommand{\ed}{\end{definition}}
\newcommand{\ep}{\end{proposition}}
\newcommand{\epr}{\end{proof}}
\newcommand{\bpr}{\begin{proof}}

\newcommand{\halmos}{\rule{1ex}{1.4ex}}
%\newcommand{\QED}{\hfill \halmos} %put \qed at right margin
%\newcommand{\mybox}{\hfill $\Box$} %put \qed at right margin (white square)
\newcommand{\mybox}{}
\newcommand{\beq}{\begin{eqnarray}}
\newcommand{\eeq}{\end{eqnarray}}
\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\st}{\, | \,}
\newcommand{\inter}{{\rm int}}
\newcommand{\co}{{\rm co}}
\newcommand{\col}{{\rm col}}
%alternative to \qed (see below)
\newenvironment{proof}{\noindent {\em Proof}.\ }{\hspace*{\fill}$\halmos$\medskip}
\newcommand{\twoif}[4]{
\left\{ \begin{array}{ll}#1&#2
\vspace{.4em}\\#3&#4\end{array}\right. }
\newcommand{\R}{{\mathbb R}}  %ams bold
\newcommand{\N}{{\mathbb N}}  %ams bold
\newcommand{\traja}{{\rm Traj}\, _\alpha\, }
\newcommand{\trajac}{{\rm Traj}\, _\alpha^{\scriptstyle co}\, }
\newcommand{\trajan}{{\rm Traj}\, _{\alpha_n}\, }
\newcommand{\trajb}{{\rm Traj}\, _\beta\, }
\newcommand{\T}{{\cal T}}
\newcommand{\smtimes}{ \!  \times \!  }
\newcommand{\smni}{{\scriptscriptstyle \ni}}
\newcommand{\mb}{\medbreak}
\newcommand{\pullin}{\vspace{-2mm}}
\newcommand{\xone}{x_{\scriptscriptstyle 1}}
\newcommand{\vfl}{v_{\scriptscriptstyle f, \ell, A}}
\newcommand{\ds}{\displaystyle}
\newcommand{\tpnt}{\tilde \phi_{n,2}}
%\newcommend{\tpnts}{\tilde \phi^2_{n,2}}
\newcommand{\mult}{\frac{\sqrt{\left\vert\tilde \phi_{n,2}(s)\right\vert}}{
\left(\tilde \phi^2_{n,2}(s)+1/n\right)^{1/4}}}
\newcommand{\tbf}{T_{\scriptscriptstyle B, f}}
\newcommand{\taf}{T_{\scriptscriptstyle A, f}}
\newcommand{\circc}{\text{\small $\circ$}}
\newcommand{\calk}{\kappa}
\newcommand{\crr}{{\cal R}}
\newcommand{\cg}{{\cal G}}
\newcommand{\calu}{{\cal U}}
\title{
Further Results on the Bellman Equation for Optimal Control
Problems with Exit Times and Nonnegative Lagrangians \footnote{Revised
August 20, 2001.  This is a preliminary version which is not meant for
circulation.}}
%\\{\small Version 2.2} }
%\thanks{\noindent Supported in part by
%DIMACS grant NSF-CCR91-19999 and NSF Grant DMS95-00798.
%This work was carried out between December 1998 and February 1999,
%while the author was a Research Assistant for H\'ector Sussmann.
%The author thanks Dr. Sussmann for his helpful comments
%on early drafts of this paper.  This paper appears in {\em Proc.
%38th IEEE Conf. Decision Control.}}}


\author{Michael Malisoff \footnote{This work was completed while
this author was a University and Louis Bevier Fellow in the
Department of Mathematics at Rutgers University. He was supported
by USAF Grant F49620-98-0242 and DIMACS
Grant NSF CCR91-19999.}\\ Department of Mathematics\\
Louisiana State University\\Baton Rouge, LA 70803 USA\\
$\mathtt{malisoff\, @\, math.lsu.edu}$
 \and H\'ector J. Sussmann
\footnote{This author was supported
  by NSF Grant DMS95-00798.}\\Department of
Mathematics\\Rutgers University\\New Brunswick, NJ 08903 USA\\
$\mathtt{sussmann\, @\, math.rutgers.edu}$}

%\pagestyle{myheadings} \markright{Bellman Equation for Exit Time
%Control Problems with Vanishing Lagrangians }
\date{}

\begin{document}
 \maketitle
%\normalsize
\begin{abstract}
In a recent series of papers, we proved theorems characterizing
the value function in exit time optimal control as the unique
viscosity solution of the corresponding Bellman equation that
satisfies appropriate side conditions.  The results applied to
problems with general nonnegative Lagrangians which satisfy a
positivity condition on the integrated costs or an asymptotics
condition on trajectories.  In this note, we prove a new theorem
which characterizes the exit time value function as the unique
bounded-from-below viscosity solution of the Bellman equation that
vanishes on the target.
The theorem applies to problems satisfying a strengthened asymptotics
condition, including problems whose  degenerate Lagrangians
vanish on open sets outside the target for some values of
the control.
We apply it to variants of the Fuller Problem from
control
engineering, and to other
examples that are not tractable by means of the known
results.

\vspace{.9em}

\noindent{\bf Key Words:\ } viscosity solutions, optimal control,
Fuller Problem, asymptotics of trajectories
\end{abstract}
\section{Introduction}
 This note is devoted to the study of
Hamilton-Jacobi-Bellman equations (HJBE's) for a large class of
unbounded optimal control problems for fully nonlinear systems
\begin{equation}
\label{problem} y'(t)\; =\; f(y(t),\alpha(t))\; \; \text{a.e.} t \ge
0,\; \; \; \; \alpha(t)\in U, \; \; \; \; y(0)\; =\; x
\end{equation}
with bounded control sets $U$ (but see $\S$\ref{unbdd} below for
generalizations to unbounded control sets). The optimal control
problems are of the form
\begin{equation}
\label{prob} \displaystyle {\rm Minimize\ \ }
\int_0^{t_x(\alpha)}\ell(y_x(t,\alpha), \alpha(t))\, dt\; \;
\text{over}\; \; \alpha\in{\cal U}(x),
\end{equation}
 where
${\cal U} := \{\text{$\! \! \! $ Measurable  Functions}
[0,+\infty)\to U\}$, $y_x(\cdot,\alpha)$ is the solution of
(\ref{problem}) for each $\alpha\in {\cal U}$, $\T\subseteq\R^N$
is a fixed closed set which we refer to as the target,
\[ t_x(\alpha)\; \; :=\; \; \inf\left\{t\ge 0:
y_x(t,\alpha)\in\T\right\}\; \in\; [0,+\infty]\; \; \; \; \forall
\alpha\in
{\cal U}, \forall x\in\R^N\] and ${\cal U}(x)$ is
the set
of
inputs $\beta\in\cal U$ for which $t_x(\beta)<\infty$.
We will refer to $\ell$ as the Lagrangian of (\ref{prob}), and we
call $t_x(\beta)$ an exit time.
Our
hypotheses allow linear quadratic (LQ) exit time problems,
including cases where the Lagrangian $\ell$  has the form $x'Rx+u'Qu$
with
$R$ positive semidefinite but not positive definite (cf.
$\S$\ref{unbdd}). We also
allow cases where the target $\T$ is unbounded.

The value function of (\ref{prob}) will be denoted by $v$, and
$\cal R$ denotes the set of points that can be brought to $\T$ in
finite time using the dynamics (\ref{problem}). Therefore,
$\crr:=\{x\in\R^N: {\cal U}(x)\ne\emptyset\}$, and
\begin{equation}
\label{vee}
\ds
v(x):= \ds \inf_{\scr \alpha\in {\cal U}(x)}
\left(\int_0^{t_x(\alpha)}\ell(y_x(t,\alpha), \alpha(t))\,
dt\right),
\end{equation}
so $v\equiv +\infty$ outside $\crr$.
The results below extend to problems with exit cost functions and
variable interest rates
from \cite{BARD} (cf. $\S$\ref{other}).
Notice that since $U$ is bounded, it need not be the case that
$\cal R$ is all of $\R^N$, even if the dynamics (\ref{problem})
has the form $\dot x=Ax+Bu$ and $(A,B)$ is a controllable pair
(cf. \cite{sontag}).
 The
Hamilton-Jacobi-Bellman equation (HJBE) of (\ref{prob}) is
\begin{equation}
\label{HJBE} \ds \sup_{\scr u\in U}\left\{-f(x,u)\cdot Dv(x)\; -\;
\ell(x,u)\right\}\;  \; =\; \;  0
\end{equation}
We will study solutions $w$ of (\ref{HJBE}) on open sets
$\Omega\setminus\T$ for which $w\equiv 0$ on $\T$ (cf. $\S$\ref{defs}
for the precise conditions we put on the solutions.)

We prove a new uniqueness theorem which characterizes $v$ as the
unique bounded-from-below solution of (\ref{HJBE}) on
${\cal R}\setminus\T$ that satisfies appropriate side conditions.
These side conditions reduce to the vanishing of the solution on
$\T$ if $\crr=\R^N$.
Since $v$
will not be differentiable in general (cf. \cite{BARD,M01}), we will
use the definition of solution from
viscosity solutions theory (cf.
\cite{BARD, FLEM} and $\S$\ref{defs} below).
Our new result applies to variants of the
Fuller Problem (cf. \cite{SUSS},  \cite{ZB}, and $\S$\ref{FP}
below) and
problems with possibly unbounded targets which satisfy a certain
asymptotics condition ($(A_4)$ below) used in \cite{S99a}
to prove uniqueness of nonnegative solutions of the HJBE.  This
asymptotic assumption is more stringent than the one used to prove
uniqueness of solutions in \cite{M01} (namely, (\ref{WA}) below), but
\cite{M01} also requires a condition on the integrated
costs (namely, (\ref{poss})) which is not needed below. In
particular, our new theorem applies to examples which were not
tractable using the known results (cf. $\S$\ref{appl}). (For
a detailed discussion of the uniqueness results of \cite{M99b,
MALI,M01}, see
Remark
\ref{compare}.)  The proof of our new theorem is based on
Zorn's Lemma and the representation theorem (cf. Lemma \ref{lemma0}),
and the hypotheses of our theorem can be
easily checked using a variant of Barb\v{a}lat's Lemma from adaptive
control (cf. Lemma \ref{lemma1}).

 Value function characterizations of this kind have
been studied and applied by many authors for a large number of
stochastic and deterministic optimal control problems in control
engineering  and for differential games. Also, uniqueness
characterizations form the bases for convergence proofs for many
recently developed numerical schemes for approximating value
functions.   One generally proves the convergence of such
schemes by showing that the value function $v_n$ of the
$n$-th discretization of the problem converges uniformly on
compact sets to a function $w$ which is a viscosity solution of
the HJBE as the mesh of the discretization tends to zero, and then one
invokes
the uniqueness characterization to show that the function $w$
being approximated is actually the value function.   Recent
accounts of work in these areas are in \cite{BARD, BFS99,
FLEM}; and
\cite{BS91, sorav} give general uniqueness
characterizations for the HJBE for problems whose
Lagrangians $\ell$ satisfy conditions of the form \footnote{\ We
set $B(S,\eps):=\{p\in\R^N: \; \inf\{||p-s||: s\in S\}<\eps\}$ for
all $S\subseteq \R^N$ and $\eps>0$.}
\begin{equation}
\label{pos}
\ds
\forall \eps>0, \; \; \exists C_\eps>0 \; \; \text{s.t.} \; \;
\ell(x,u)\; \ge
\; C_\eps\; \; \text{for \ \
all}\; \; x\notin B(\T,\eps)\; \; \text{and}\; \; u\in U.
\end{equation}
  Since
$\ell(\cdot, u)$ can vanish outside $\T$ for some choices of $u$,
these earlier results cannot be applied to (\ref{HJBE}) (cf. \cite{M99b}
for examples where (\ref{pos}) fails and the HJBE has several
bounded-from-below solutions vanishing on $\T$).
For
theorems characterizing  $v$ as the unique nonnegative viscosity
solution of the HJBE (\ref{HJBE}) on $\crr\setminus\T$ that
satisfies appropriate boundary conditions, see \cite{S99a}.   Our
work is part of a larger project which generalizes uniqueness
characterizations for HJBE's to versions that cover well-known
engineering problems with non-Lipschitz dynamics and general
nonnegative  Lagrangians. Earlier work in this area can be found
in \cite{BDL97} (which covers finite horizon LQ problems),
\cite{DAL} (which covers inifinite horizon LQ problems), and
\cite{MALI} (which gives a uniqueness characterization for the
HJBE for a class of exit time problems with non-Lipschitz dynamics,
including the Reflected
Brachystochrone Problem from \cite{Su-Japan}).

This note is organized as follows.  In $\S$\ref{defs}, we list
assumptions used in most of the sequel, and we state our main
lemmas. In $\S$\ref{main}, we state our main theorem, and we show
how the theorem improves what was known about solutions of the
HJBE.  This is followed in $\S$\ref{appl} by applications of the
theorem, including cases which are not tractable using the earlier
results. We prove our theorem in $\S$\ref{proof}, and
$\S$\ref{unbdd} shows how to extend the theorem to problems with
unbounded control sets.


\section{Definitions, Assumptions, and Main Lemmas}
\label{defs} For any set $S\subseteq \R^N$, let $C(S)$ denote the
set of all real-valued continuous functions on $S$, and, if $S$ is
also open, let $C^1(S)$ denote those functions in $C(S)$ with one
continuous derivative. Recall the following definition of
viscosity solutions:

\bd{definitionvis}

Assume $\cg\subseteq \R^N$ is open, $S\supseteq\cg$, and
$F:\R^N\times \R^N\to\R$ and $w: S\to\R$ are continuous. We call
$w$ a {\bf (viscosity) solution}  of $F(x,Dw(x))=0$ on $\cg$ if
the following two conditions are satisfied:
\begin{itemize}
\item[$(C_1)$]
If $\gamma\in C^1(\cg)$ and $x_o$ is a local minimum of
$w-\gamma$, then $F(x_o,\, D\, \gamma(x_o))\, \ge\,  0$.
\item[$(C_2)$]
If $\lambda\in C^1(\cg)$ and $x_1$ is a local maximum of
$w-\lambda$, then $F(x_1,\, D\, \lambda(x_1))\, \le\,  0$.
\end{itemize}\ed
This definition is equivalent to the definition of viscosity
solutions based on semidifferentials used in \cite{DAL} (cf.
\cite{BARD}).
All of what follows is based on the `test
function' viscosity solution definition given above, so we omit
the definition based on semidifferentials. We make the following
assumptions (but see $\S$\ref{unbdd} for the generalization to
unbounded control sets $U$):\bi
\item[$(A_0)$]
The control set $U$ is a nonempty compact metric space.
\item[$(A_1)$]
The dynamics $f:\; \R^N\, \times\,  U\; \to\; \R^N$ is continuous,
and there is a constant $L>0$ such that $||f(x,a)-f(y,a)||\le\;
L||x-y||$ for all $x,y\in\R^N$ and $a\in U$.
\item[$(A_2)$]
The target $\T\subseteq\R^N$ is closed and nonempty, and  $STC\T$ holds.
\item[$(A_3)$]
$\ell:\R^N\times U\to [0,\infty)$ is continuous.
\item[$(A_4)$]
If $\beta\in {\cal U}$ and $x\in \R^N$, and if $\int_0^\infty
\ell(y_x(s,\beta), \beta(s))\, ds<\infty$, then $\ds
\lim_{s\to\infty} y_x(s,\beta)\in\T$. \ei


The meaning of $(A_0)$-$(A_4)$ is as follows.
By standard arguments,
$(A_0)$-$(A_1)$ imply that for each
$\alpha\in {\cal U}$ and each $x\in\R^N$, there is a unique
trajectory $y$ for the dynamics (\ref{problem}) which starts at $x$
and which is defined on $[0,\infty)$. This trajectory will be
denoted by $y_x(\cdot, \alpha)$. Moreover, one can show (cf.
\cite{BARD}, Chapter 3)
 that if
$(A_1)$ holds, then for all $\alpha\in {\cal U}$,
$y_x(\cdot,\alpha)$ satisfies the condition
\begin{equation}
\label{sssss} ||y_x(t,\alpha)-x||\; \; \le \; \; M_x\, t\; \;
\text{for\ \ all}\; \; t\; \in\; [0,1/M_x],
\end{equation}
where \[M_x:=\sup\left\{||f(z,a)||:\, a\in U,\, ||z-x||\le
1\right\}\] if the supremum is nonzero and $M_x=1$ otherwise.
 By $STC{\cal T}$, we mean  $\cal
T\subset {\rm Interior}\, {\cal R}(\eps)$  for all $\eps>0$, where
\[{\cal
R}(\eps)\; \; :=\; \; \left\{x\in\R^N: \; \exists \; t\in[0,\eps)
\; \; \& \; \; \alpha\in {\cal U} \; \; \; {\rm s.t.}\; \; \;
y_x(t,\alpha)\in {\cal T}\right\}.\] The condition $STC{\cal T}$
holds under  suitable assumptions on the directions
of the vector field $f$ and its Lie brackets at $\partial{\cal T}$
(cf. \cite{susssymm}).  Notice that $\T$ can be unbounded,
that $\ell(\cdot, u)$ is allowed to vanish outside $\T$ for some
choices of $u\in U$, and that the positive integrated
costs condition (cf. (\ref{poss}) below) used in
\cite{M99b, MALI, M01} is no longer being assumed.  In particular,
$\ell(\cdot,
a)$ is allowed to vanish on open sets outside $\T$ for some values $a\in
U$ (cf. Example \ref{flat} below).
On the other hand,
condition $(A_4)$ is stronger than
the asymptotics condition (cf. (\ref{WA}) below)  used in \cite{M01}
(cf. Remark \ref{pert} for applications of \cite{M01} where (\ref{WA})
holds
but $(A_4)$
does
not hold).

We will give conditions guaranteeing that $v$
is the unique solution of
(\ref{HJBE}) on an open set $\Omega\setminus\T$
that satisfies the following type of boundary condition:
\bi\item[]\bi\item[]\bi\item[] \bi
\item[\ $BC(\Omega, \omega_o)$\ \ \ \ ]
$w: \; \Omega \, \to \,  \R$ \ \ is\ \  bounded\ \  below, \ \
$\omega_o\; \in\;  \R\cup\{+\infty\}$, \ \ $w(x)\, <\,
\omega_o$\vspace{.5em}\newline on\ \ $\Omega$, $w \; \equiv\;  0$\ \
on \ \ $\T,$ \ \ and\ \ $\ds \lim_{x\to x_o}w(x)\; =\; \omega_o$ \
\ for \ \ all\ \ $x_o\, \in\,
\partial\Omega$. \ei\ei\ei \ei\noindent
Notice that when $\crr=\R^N$, the limit condition in
$BC(\crr, \omega_o)$ is satisfied vacuously.  In particular,
there are no growth restrictions on functions $w$ which
satisfy $BC(\R^N, +\infty)$. Our uniqueness results
are based on the following well-known representation lemma from Chapter
3 of
\cite{BARD}:


\bl{lemma0}
Let $(A_0)$-$(A_3)$ hold,  let $B\subseteq \R^N$ be a bounded open
set, and let $u\in C(\bar B)$ be a viscosity solution of the HJBE
(\ref{HJBE}) on $B$. For each $q\in B$, each $\beta\in {\cal U}$,
and each \footnote{We set $\dist(q,P):=\inf\{||q-p||: p\in P\}$
for all $q\in \R^N$ and $P\subseteq \R^N$.}
$\delta\in(0,\dist(p,\partial B)/2)$, set
\[\ds \tau_q(\beta)\; = \; \inf\{\, t\ge 0 :\; y_q(t,\beta)\, \in\,
\partial B\}\; \; \text{and}\; \;
T_\delta(q)=\inf\{ t:
\text{dist}(y_q(t,\alpha),
\partial B)\le \delta, \alpha\in {\cal U} \}.\]
\noindent Then the inequalities

\begin{equation}
\label{first} u(q)\; \; \le\; \; \int_0^r \ell(y_q(s,\beta),
\beta(s))\, ds \; \; +\; \; u(y_q(r,\beta))
\end{equation}
\begin{equation}
\label{second} u(q)\; \; \ge\; \; \inf_{\alpha\in {\cal
U}}\left[\int_0^t \ell(y_q(s,\alpha), \alpha(s))\, ds \; \; +\; \;
u(y_q(t,\alpha))\right]
\end{equation}
hold for all $q\in B$, $\beta\in {\cal U}$, $r\in
[0,\tau_q(\beta))$, and $t\in [0, T_\delta(q))$. \el

We use the following definition:
\bd{homog}
A continuous function $\alpha:\R\to[0,\infty)$ is said
to be of {\bf class MK} provided that $\alpha(0)=0$ and
$\alpha$ is strictly increasing on $[0,\infty)$
and even.  \ed

\br{mrk} Notice that any function
$g$ of Sontag's Class ${\cal K}_\infty$ (cf. \cite{meagre}) gives
rise to a function $\alpha$ of class $MK$ defined by
$\alpha(x)=g(|x|)$. Also $\alpha(x)=|x|^q$ is of class $MK$
for all $q>0$.  In some of our applications, we will use the
Lagrangians $\ell(x,u)\equiv \alpha(x)$ for $\alpha$ of class
$MK$. Notice that functions of class $MK$ need not be bounded,
convex, or locally Lipschitz.\er

We use the following variant of Barb\v{a}lat's Lemma from adaptive
control (cf. \cite{meagre}): \bl{lemma1} Assume that
$\alpha$ is of class $MK$. Let
$\phi:[0,\infty)\to\R$ be a continuously differentiable function
for which $\phi'$ is Lipschitz continuous and $\int_0^\infty
\alpha(\phi(s))\, ds<\infty$. Then
$\ds\lim_{t\to\infty}\phi(t)=\lim_{t\to\infty}\phi'(t)=0$.\el \bpr
It suffices to
check that $\lim_{t\to\infty}\phi'(t)=0$, since then $\phi$ is
Lipschitz, and then the result follows by Barb\v{a}lat's Lemma (cf.
\cite{meagre}). We can
suppose that
 $\limsup_{t
\to\infty}\phi'(t)>\gamma\in(0,1)$.  (Otherwise, apply the
same argument to $-\phi$.) By passing to a subsequence, we can
choose $t_k\uparrow +\infty$ for which $t_{k+1}-t_k\ge 1$ and
$\phi'(t_k)>\gamma$ for all $k$. Choose a Lipschitz constant $C>1$
for $\phi'$, pick $0<\delta<\gamma/(2C)$, and set
$I_k=[t_k-\delta, t_k+\delta]$.  Then
\begin{equation}
\label{effect} \phi'(t)=\phi'(t)-\phi'(t_k)+\phi'(t_k)\ge
 -C\, \delta+\gamma\ge\gamma/2\end{equation} for all $t\in I_k$.
Set $ v_k=\inf\{|\phi(t)|: t\in I_k\}$ for all $k$, and choose
$s_k\in I_k$ so that $|\phi(s_k)|=v_k$.

If $\phi(s_k)> 0$, then  (\ref{effect}) gives $s_k=t_k-\delta$, so
we get $\phi(t)\ge
\gamma[t-(t_k-\delta)]/2$ for all $t\in I_k$, so
\begin{equation}
\label{summand} \int_{I_k}\alpha[\phi(s)] ds\; \ge\; 2/\gamma
\int_0^{\gamma\delta/4}\alpha(u)du\end{equation} by changing
variables. This last inequality remains true if $\phi(s_k)<0$ (in
which case $s_k=t_k+\delta$ and we have $-\phi(t)\ge
\gamma[t_k+\delta-t]/2$ on $I_k$, so (\ref{summand}) remains true since
$\alpha$ is even) or if $\phi(s_k)=0$
(in which
case
we argue as in the $\phi(s_k)>0$ case on $[s_k,t_k+\delta]$
and as in the $\phi(s_k)<0$ case on $[t_k-\delta,s_k]$, and then
we use the fact that
$[t_k+\delta-s_k]\vee[s_k-(t_k-\delta)]\ge \delta/2$). Since
$\delta<1/2$ and $t_{k+1}-t_k\ge 1$ for all $k$, the $I_k$'s are
disjoint, so we sum on $k$ in (\ref{summand}) to contradict
$\int_0^\infty\alpha[\phi(s)]ds<\infty$.
\epr

\section{Statement of Main Result and Remarks}
\label{main}
\subsection{Main Result} \label{thum} \noindent We will prove the
following theorem:
\bt{thm1} Assume conditions $(A_0)$-$(A_4)$ are
satisfied. If
$w\in C({\cal R})$ is a viscosity solution of
(\ref{HJBE}) on
${\cal R}\setminus\T$ which satisfies $BC(\crr,
\omega_o)$ for
some $\omega_o\in\R\cup\{+\infty\}$, then $w\equiv v$
on $\cal
R$.\et

Notice that if $v$ is continuous and known
to satisfy
$BC({\cal R}, \nu_o)$ for some
$\nu_o\in\R\cup\{+\infty\}$,
then this theorem becomes a uniqueness
characterization for
$v$. This
follows from the fact (cf. \cite{BARD}) that $v$ is
then a
viscosity solution of the HJBE (\ref{HJBE}) on
$\crr\setminus\T$.
 If we also have $\crr=\R^N$ (i.e., when all
points in $\R^N$ can
be brought to $\T$ by the dynamics $f$ with
controls in $U$), then
the limiting condition in $BC(\crr,\nu_o)$
holds vacuously, so we
get a characterization of $v$ as the unique
continuous
bounded-from-below solution of the HJBE that vanishes on
$\T$. For
a version of Theorem \ref{thm1} for unbounded control sets
$U$,
see Theorem \ref{thm2} below. The proof of Theorem \ref{thm1}
remains valid if $\crr$ is replaced by any open set
$\Omega\subseteq\R^N$ containing $\T$, so we also get uniqueness
characterizations for {\em local} solutions of the HJBE.  Also, the
theorem remains true if we add a bounded-from-below continuous final
cost function $g$ in (\ref{prob}) (cf. \cite{BARD}, Chapter 4), except
that the boundary condition that $w\equiv 0$ on $\T$ is replaced by the
condition that $w\equiv g$ on $\T$.

\subsection{Comparison of Theorem \ref{thm1} With Other Uniqueness
Characterizations} \label{compare} Let us now show how Theorem
\ref{thm1} applies to exit time problems which are not tractable
by means of \cite{BARD, M99b, MALI,M01}. The (undiscounted) exit
time results in \cite{BARD, BS91, sorav} assume (\ref{pos}), i.e.,
positive uniform lower bounds for $\ell$, and deduce that $v$ is
the only possible viscosity solution of
the HJBE (\ref{HJBE}) on
${\cal R}\setminus\T$ which is continuous
on $\cal R$ and which
satisfies $BC({\cal R}, \omega_o)$ for some
$\omega_o\in
\R\cup\{+\infty\}$. On the other hand, condition
(\ref{pos}) is
allowed to fail in applications such as variants of the well-known
Fuller Problem (cf. $\S$\ref{FP}). Therefore, our uniqueness
characterization
does not follow from the well-known results.

The papers \cite{Mdis, M99b, MALI} give conditions under which $v$
is
the
unique solution of the HJBE (\ref{hjf}) on $\crr\setminus\T$ in the
class of functions $w$
which vanish at $\T$, are continuous on
$\R^N$, and satisfy a
generalization of properness, where
properness
of $w$ is the condition that $\lim_{||x||\to\infty}w(x)=+\infty$. This
generalized condition can be
satisfied by functions with unbounded null
sets, so the results also apply to problems with unbounded targets.

  The main argument of \cite{M99b, MALI} is a
generalization of arguments for free boundary
problems from \cite{BARD}.  The results in
\cite{M99b, MALI, M01} {\em do not} require $(A_4)$, but they {\em do}
require
\begin{equation}\label{poss}
  \int_0^t\ell^r(y_x(s,\alpha),\alpha(s))\, ds>0\; \; \forall t>0,
  x\not\in\T, \text{and} \alpha\in {\cal U}^r,
\end{equation}
where ${\cal U}^r$ is the set of relaxed controls on $U$ and
$\ell^r(x,m):=\int_A\ell(x,a)dm(a)$ for all  $x\in\R^N$ and any
Radon probability measures $m$ on $A$. (See \cite{BARD} for the
definitions of relaxed controls and their trajectories.  We will
not use relaxed controls in our arguments below.) The novelty of
Theorem \ref{thm1}   is that it gives a uniqueness
characterization for $v$  within a class of
functions which includes functions  which violate both properness
and
the more general growth
conditions of \cite{M99b}, and that it applies to cases
where (\ref{poss}) is not satisfied (cf. $\S$\ref{FP}) as long as
$(A_4)$ holds, including cases where
$\ell(\cdot,a)$ can vanish on an open set outside $\T$.  Here is a class
of examples which is tractable by Theorem \ref{thm1} but not by the
earlier uniqueness characterizations:

\bex{flatt}
\label{flat}
Take $N=1$,
$\T=[1,+\infty)$, any nonempty compact $U\subseteq\R^M$,
any Lagrangian $\ell$
satisfying $(A_3)$, and any nonnegative dynamics $f$ satisfying $(A_1)$
which is identically
zero for $x\in[2, \infty)$ but uniformly bounded below by a
positive constant for $x\in(-\infty,3/2)$.
Then, $(A_0)$-$(A_4)$  hold, with $(A_4)$
holding vacuously because every trajectory asymptotically approaches
some point in $\T$.
However,
(\ref{poss}) will generally  not hold, since
$\ell$ can be identically zero for $x$ in an open set outside $\T$.
Therefore, this example
is
tractable by
Theorem \ref{thm1} but not by \cite{M99b, MALI, M01}.  This
example easily
generalizes to problems on $\R^N$.
\eex

\br{saaave}
\label{saave}
The paper \cite{M01} proves that if $\crr=\R^N$ with $v$
continuous, and if $(A_0)$-$(A_3)$,  (\ref{poss}), and
\begin{equation}
\label{WA}
\text{ If} \beta\in {\cal U} \text{and} x\in \R^N,
\text{and if} \int_0^\infty \ell(y_x(s,\beta), \beta(s))\, ds<\infty,
\text{then} y_x(s,\beta) \text{is bounded}. \end{equation} all  hold,
then
$v$ is
the
unique bounded-from-below solution of the HJBE on
$\R^N\setminus\T$ vanishing on $\T$.
Notice that (\ref{WA}) is a weaker asymptotics condition than $(A_4)$
for
bounded targets that could be satisfied by problems
violating $(A_4)$, e.g., the `Shifted FP' in Remark \ref{pert}
below, which is tractable by \cite{M01}. The arguments of \cite{M01}
are based on an iteration of
arguments from \cite{M99b} and readily generalize
to cases where $\crr\subsetneq\R^N$.
The condition $(A_4)$ is used in \cite{S99a}
and elsewhere to establish uniqueness of {\em nonnegative} solutions of
the HJBE.
\er\section{Applications}
\label{appl}
\subsection{The Fuller Problem and Its Perturbations}
\label{FP}
We will first show how to
apply the theorem to get a uniqueness characterization for
variants of the Fuller Problem (FP).  Let $\alpha$ be a function
of class $MK$.  Consider the
problem
\begin{equation}
\label{ssharp}
 \text{Infimize}\; \;
\int_0^{t_p(\beta)}\alpha(y_{1,p}(t,\beta)) dt \; \; \text{over\ \
all}\; \;  \beta\in{\cal U}(p)\end{equation} for each $p\in\R^2$,
where $t\mapsto y_p(t,u):=(y_{1,p}(t,u), y_{2,p}(t,u))$ is the
trajectory of
\[
\twoif{\dot x(t)\; =\; y(t),\; \; \dot y(t)\; =\; u(t)\; \in\;
U:=[-1,+1]}{}{(x(0), y(0))\; =\; p}{}
\]
and $t_p(u)$ is the first time this trajectory reaches the target
$\T:=\{\vec 0\}\subseteq\R^2$.  Let $v_\alpha$ denote the value
function of this problem.  Taking $\alpha(x)=x^2$, we get the
Fuller Problem (FP), whose value function will be denoted by
$v_{\scr FP}$.  One easily checks that for (\ref{ssharp}),
$\crr=\R^2$ (cf. \cite{sontag}). Using this fact and the convexity
of $x\mapsto x^2$, one easily checks that the value function
$v_{\scr FP}$ for the FP is strictly convex on $\R^2$ and
therefore continuous (cf. p.81 of \cite{R70}).   It follows from
Lemma \ref{lemma1} above that (\ref{ssharp}) satisfies
$(A_0)$-$(A_4)$,
so we conclude as follows: \bc{corfp} Let $\alpha$ be
a function of class $MK$.
If $w:\R^2\to\R$ is a continuous,
bounded-from-below solution of the HJBE
\begin{equation}
\label{hjf}\ds
 -\; \; y(Dw((x,y)'))_1\; \; +\; \; \vert (Dw((x,y)'))_2\vert\; \; -\;
 \;
\alpha(x)\; \; =\; \; 0
\end{equation}
on $\R^2\setminus\{\vec 0\}$
that vanishes at $\vec{0}$, then $w\equiv v_\alpha$.  In
particular, $v_{\scr FP}$ is the unique continuous
bounded-from-below solution of the  corresponding HJBE that
vanishes at $\vec 0$.\ec \br{cascade} Notice that this extends a
result in \cite{S99a} which characterizes the FP value function as
the unique viscosity solution of (\ref{hjf}) in the class of
nonnegative functions $w\in C(\R^2)$ which vanish at the origin.
More generally, we get a uniqueness result for the problems
\[\begin{array}{c}
\ds \text{Infimize} \; \; \int_0^{t_p(\alpha)} \sum_{j=1}^{n-1}
\gamma_j\left[x_j(t, \alpha)\right]\, dt \; \; \text{over}\; \;
\alpha\in{\cal
U}(p)\; \;
\text{subject \ \ to}\; \; x(0)=p\; \; \text{and}\\[.5em] %\] \bi\item[]\[
\begin{array}{ccccccccc}
\dot x_1(t, \alpha)&=&{}&{}&x_2(t,\alpha)&{}&{}&{}&{}\\ \dot
x_2(t, \alpha)&=&{}&{}&{} &x_3(t, \alpha)&{}&{}&{}\\ {}&\vdots
&{}&{}&{}&{}&{}&{}&{}\\ \dot x_{n-1}(t,
\alpha)&=&{}&{}&{}&{}&{}&x_n(t,\alpha)&{}\\ \dot x_n(t,
\alpha)&=&{}&{}&{}&{}&{}&{}&\alpha(t)\in U\end{array}
\end{array}\]%\ei
with the target $\{\vec 0\}\subset\R^n$ for any nonempty compact set
$U\subset\R$ and class $MK$ functions $\gamma_j$. This follows from a
repeated application of Lemma
\ref{lemma1} which we omit.  \er

\br{newk} The hypotheses of Corollary \ref{corfp} are minimal (cf.
\cite{M01}). Indeed,  using Soravia's Backward Dynamic Programming
Principle (cf. \cite{BARD, sorav}), one can easily show that
$(x,y)\mapsto \tilde v(x,y):=-v_{\scr FP}(-x,y)$ is also a viscosity
solution of
the
Fuller Problem HJBE on $\R^2\setminus\{\vec 0\}$ vanishing at the
origin.
The argument is based on the facts that $v_{\scr FP}$ is a {\em
bilateral} viscosity solution of the HJBE and that each $p\in\R^2$
is an optimal point (cf. \cite{BARD} for the definitions and
\cite{M01} for the details of the argument).
Notice that since $v_{\scr FP}$ is proper (cf. \cite{M99b}), $\tilde v$
is not bounded below.
It
follows that $v_{\scr FP}$ is the unique bounded-from-below
viscosity solution of the corresponding HJBE on
$\R^2\setminus\{\vec 0\}$ that vanishes at the origin and that the
hypotheses of the preceding Corollary \ref{corfp} are in fact
minimal, since the $\alpha(x)\equiv x^2$ case shows that the
bounded-from-below hypothesis in the corollary cannot be omitted.
\er \br{pert} As shown in \cite{M01}, if we perturb the FP data to
\begin{equation}
\label{datt} \T=\{(k,k)\}, \; \; U=[-1,+1], \; \;
f(x,y,a)=(y-k\Phi(x,y),a),  \; \; \ell(x,y,a)= x^2+k(1-|a|)^2
\end{equation}
where $k\ge 0$ and $\Phi:\R^2\to[0,1]$ is any $C^1$ function which
is $1$ near $(k,k)$ but identically $0$ in an open set containing the
$y$-axis, then Theorem \ref{thm1} given above no longer applies,
since $(A_4)$ would not hold for $k>0$.  In fact, \cite{M01} shows
that for all $k>0$, we can construct trajectories for the `Shifted
FP' exit time data (\ref{datt}) such that
\[
\int_0^\infty \ell(y_x(s,\beta),\beta(s))\, ds<\infty, \;
\text{but}\;  y_x(s,\beta) \to \vec 0\not\in \T \; \text{as}\;
s\to +\infty.
\]
However, one easily   shows (cf. \cite{M01}) that $(A_o)$-$(A_3)$ and
both (\ref{poss})
and (\ref{WA})
are all satisfied
for (\ref{datt}) for all choices of $k\ge 0$, and consequently
\cite{M01} shows that
that any continuous bounded-from-below solution $w:\R^2\to\R$ of
the corresponding HJBE that vanishes at $\vec 0$ must coincide
with $v$ (cf. Remark \ref{compare}).
The results of \cite{M01} generalize to solutions of the
HJBE in neighborhoods of $\T$.
 Therefore, while Theorem \ref{thm1} applies to
problems with `very degenerate' Lagrangians which violate
(\ref{poss}),
including cases
where the Lagrangian $\ell$ can vanish on open sets outside $\T$
(cf. Example \ref{flatt}), the results of \cite{M01} apply
under weaker asymptotics conditions for trajectories, and in
particular, to perturbations of  the FP which are not tractable
by Theorem \ref{thm1}.\er
\subsection{Other Applications}
\label{other}
As we saw in Example \ref{flatt}, condition $(A_4)$ holds automatically
when all trajectories asymptotically approach $\T$.  Notice that $(A_4)$
also holds automatically if $\int_0^\infty\ell (y_x(s,\beta),\beta(s))\,
ds=\infty$ for all $x\in\R^N$ and $\beta\in {\cal U}$.  In particular,
it applies to the shape-from-shading equation
\begin{equation}
\label{tone}
I(x)\left[1+||Du(x)||^2\right]^{1/2}-1=0,\; \; I(x)=||x||/(1+||x||)
\end{equation}
from image processing for cases where  $0\not\in\T$,
since (\ref{tone}) can also be written as
\begin{equation}
\label{ttwo}
\ds
\max_{||a||\le 1}\left\{
I(x)a\cdot
Du(x)-\left[1-I(x)\left(1-||a||^2\right)^{1/2}\right]\right\}=0,
\end{equation}
which is of the HJBE form (\ref{HJBE}).  Notice that (\ref{pos}) does
not in general hold for (\ref{ttwo}).
This example was studied in \cite{M01, S99a}.  In a similar way,
Theorem
\ref{thm1} also applies to the eikonal equations studied in \cite{M01}.

One can easily give a variant of Theorem \ref{thm1} for the variable
interest rate problem with exit costs studied in \cite{BARD,S99a}.
Recall that these
problems have the form
\begin{equation}
\label{vprob} \displaystyle \text{Minimize} \; \; \int_0^{t_x(\beta)}
\ell\left[y_x(s,\beta),\beta(s)\right]\, e^{-\delta(s,\beta,x)}
 ds\; +\; g\left[y_x(t_x(\beta),\beta)\right]\,
e^{-\delta(t_x(\beta),\beta,x)} \; \; \text{over} \; \; \beta\in {\cal
U}(x) \end{equation} where
\[\delta(t,\beta,x):=\int_0^th(y_x(r,\beta),\beta(r))\, dr\] for a
continuous nonnegative interest function $h$, and that the HJBE for
(\ref{vprob}) is \begin{equation} \label{vHJBE} \ds \sup_{u\in U}\;
\left\{\; -f(x,u)\cdot Dv(x)\; -\; \ell(x,u)\; +\; h(x,u)\cdot v(x)\;
\right\}\; \; =\; \; \; 0\; . \end{equation} The motivation for
introducing $h$ is that borrowing and lending rates are subject to
change in economic models.  The proof of Lemma \ref{lemma0} easily
generalizes to
variable interest rate problems (cf. \cite{BARD}).  The argument of
Theorem \ref{thm1} applies to (\ref{vHJBE}) but with $(A_4)$ replaced by
the
conditions
\bi \item[$(A^v_4)$] If $\beta\in {\cal
U}$ and $x\in \R^N$, and if \[\int_0^{ \infty} e^{-\delta(s,\beta,x)} \,
\ell(y_x(s,\beta),\beta(s))\, ds\; \; <\; \; \infty,\] then there exists
a point
$\bar p\in \T$ such that $\ds \lim_{s\to\infty} y_x(s,\beta)=\bar p$.
\item[$(A_h)$]
For each $q\in \crr$, there exists a constant $\bar h_q<\infty$ so that
\[\int_0^{t^\crr_q(\beta)}h(y_q(s,\beta),\beta(s))\, ds\; \; \le\; \;
\bar h_q\]
for all $\beta\in \calu$ satisfying $t^\crr_q(\beta)<\infty$, where
$t^{\cal R}_q(\beta)\; :=\; \inf\{t\ge
0:\, y_q(t,\beta)\in
\partial \crr\}$.\ei
Condition $(A_h)$ is easily used to generalize the boundary argument of
(\ref{asyy}) below if $\eps$ is chosen so that $w(\bar x)<e^{-\bar
h_{\bar x}}\omega_o-\eps$. The conclusion of this variant of the theorem
is that any continuous bounded-from-below solution $w$ of (\ref{vHJBE})
on ${\cal O}_v:=\{x\in \crr\setminus\T: w(x)< e^{-{\bar h}_x}\omega_o\}$
which
agrees with $g$ on $\T$ and satisfies $BC(\crr,\omega_o)$ coincides with
the value function $v$ on ${\cal
O}_v$.  The novelty is that we get a uniqueness
characterization for (\ref{vHJBE}) for cases where $h$ is allowed to
vanish (cf. \cite{S99a} for analogous results for (\ref{vHJBE}) for
cases where $h$ is uniformly bounded below by positive constants). We
remark that $(A_h)$ holds vacuously if $\crr=\R^N$, and that the
conclusion becomes $w\equiv v$ on $\crr$ just as before if $w$ satisfies
$BC(\crr,+\infty)$, since in that case, we have  ${\cal
O}_v=\crr\setminus\T$.
\section{Proof of Main Result}
\label{proof}

Let $w$ satisfy the hypotheses of Theorem \ref{thm1}, and let
$\bar x\in {\cal R}\setminus\T$ be given.  The fact that $v(\bar
x)\ge w(\bar x)$ is an easy consequence of (\ref{first})
of Lemma
\ref{lemma0} which is obtained by fixing an input $\alpha\in {\cal
U}$ that drives $\bar x$ to $\T$ in finite time, taking $B$ to be
an appropriate  open tube containing the trace of $y_{\bar x}(\cdot,
\alpha)$
on $[0, t_{\bar x}(\alpha)]$, and then infimizing over all
$\alpha$.
 Such a tube exists since  trajectories
that reach $\T$ in finite time remain in ${\cal R}$ on $[0,
t_{\bar x}(\alpha)]$ (because points which are outside $\crr$
cannot be brought to $\T$ in finite time using the dynamics
(\ref{problem})). We therefore only show that $w(\bar x)\ge v(\bar
x)$.\footnote{The proof that $v(\bar x)\ge w(\bar x)$ is slightly more
complicated if $\crr$  is replaced by a more general  open set
containing $\T$ (cf. $\S$\ref{thum}), since one must consider
trajectories
starting at $\bar x$ but exiting $\Omega$ before the first time they
reach $\T$.  The proof of this inequality for such cases is in
\cite{M99b}.  On the other hand, the proof of the reverse inequality
we are about to give remains valid if $\crr$ is replaced by any
open neighborhood $\Omega$ of $\T$, as long as $w$
satisfies $BC(\Omega,\omega_o)$.}

Choose $\eps>0$ such that
\begin{equation}
\label{choice} w(\bar x)\; \; <\; \; \omega_o\; -\; \eps.
\end{equation}
This is possible since $BC(\crr, \omega_o)$ is satisfied. (We
allow $\omega_o=+\infty$, in which case (\ref{choice}) holds for
all $\eps>0$.) The inequality $w(\bar x)\ge v(\bar x)$ will
evidently follow if we find an input $\bar\alpha\in {\cal U}$ that
drives $\bar x$ to $\T$ in finite time and which is such that
\begin{equation}
\label{goal}
w(\bar x)\; \; \ge\; \; \int_0^{t_{\bar x}(\bar
\alpha)} \ell(y_{\bar x}(s,\bar\alpha),{\bar \alpha}(s))\, ds\; \; -\;
\; \eps,
\end{equation}
since that would give $w(\bar x)\ge v(\bar x)-\eps$, by the
definition (\ref{vee}) of $v$, and then we
can let $\eps\downarrow 0$. We now prove the existence of such a
$\bar \alpha$ by using Zorn's Lemma. We remark for later reference
that it suffices to find $\bar\alpha\in {\cal U}$ and $t>0$ so that
$y_{\bar x}(t,\bar\alpha)\in\T$ and so that
$w(\bar x)\ge \int_0^t
\ell(y_{\bar x}(s,\bar\alpha),{\bar \alpha}(s))\,
ds-\eps$,
by the nonnegativity of $\ell$.
In what follows, we define
the functions $E_1, E_2, \ldots$ by
\[E_j(t)\; \; \equiv\; \; \frac{\eps}{4}\, \left[\,
e^{-(j-1)}-e^{-(t+j-1)}\, \right] \; \; \text{for\ \ each}\; \; t
>0.\]
Set
\[
{\cal Z}_1\; \; =\; \; \left\{
\begin{array}{c}
(t,\gamma):  \; \; \; 0\le t\le 1, \; \text{and} \gamma:\,
[0,t]\to \crr\; \text{is a trajectory}\\[.8em]\! \! \! \! {\rm
for}\; \; \dot x\, \, =\, \, f(x,\alpha )\; \text{for \ some}\;
\alpha\, \in\, {\cal U}\; \, \text{with}\,  \gamma(0)\, \,  =\, \,
\bar x\\[.8em] \! \! \! \! \text{so that} w(\bar x)\, \ge\,
\int_0^t \ell(\gamma(s), \alpha(s))\, ds+w(\gamma(t))- E_1(t)\, .
\end{array}
\right\}.
\]
Then ${\cal Z}_1$ is partially ordered by the relation
\begin{equation}
\label{rel} (t_1,\gamma_1)\; \; \sim\; \; (t_2, \gamma_2)\; \;
\text{iff}\; \; \left[\; \; t_1\le t_2\; \; \text{and}\; \;
\gamma_2\lceil[0,t_1]\equiv \gamma_1\; \; \right] \end{equation}
Moreover, one can use standard arguments to check that every
totally ordered subset of ${\cal Z}_1$ has an upper bound in
${\cal Z}_1$.

Indeed, let $\{(s_j, \mu_j)\}_j$ be a totally ordered subset of
${\cal Z}_1$, set $\bar s=\sup_j s_j$, and then define the
trajectory $\bar \mu:[0,\bar s)\to\crr$ by $\bar\mu(p)=\mu_j(p)$
for any $j$ so that $s_j>p$. (This is valid since the $s_j$'s
increase and $\mu_j$ extends $\mu_k$ for $k\le j$.  We assume $\bar
s>0$, since otherwise $(s_1,\mu_1)$ is the desired upper bound.)
Let
$\beta_j:(s_{j-1}, s_j]\to U$ be a control for the trajectory
$\mu_j\lceil (s_{j-1}, s_j]$, fix $\bar u\in U$, and define
$\beta^\dagger:(0,\infty)\to U$ by $\beta^\dagger(s):=\beta_j(s)$
on $(s_{j-1}, s_j]$ for $j\ge 1$ and $\beta^\dagger(s)=\bar u$ for
$s\ge \bar s$ (where we set $s_0=0$ and assume wlog that $s_j<\bar
s$ for all $j$). Then $\beta^\dagger$ is measurable and therefore
admits a corresponding trajectory $y_{\bar x}(\cdot,
\beta^\dagger)$ on $[0,\infty)$. Moreover, $y_{\bar x}(\cdot,
\beta^\dagger)$ coincides with $\bar \mu$ on $[0,\bar s)$. Setting
$\bar\mu(\bar s)=y_{\bar x}(\bar s, \beta^\dagger)$, it follows
that  $(\bar s, \bar \mu)$ is an upper bound for $\{(s_j,
\mu_j)\}_j$ in the relation (\ref{rel}). Also, the choice of
$\eps>0$ guarantees that $\bar \mu(\bar s)\in \crr$, which implies
that $(\bar s, \bar \mu)\in {\cal Z}_1$.

Indeed, if $\bar\mu(\bar s)\in \partial\crr$, and if we use $\alpha_j$
to denote
the control for $\mu_j$ for all $j$, then we would get $
\mu_j(s_j)\to \bar\mu(\bar s)\in\partial\crr$. It would then
follow from the assumption $BC(\crr, \omega_o)$ and the
nonnegativity  of $\ell$ that \begin{eqnarray}\label{asyy} w(\bar
x)&\ge &
\int_0^{s_j}\ell(\mu_j(s), \alpha_j(s))\, ds\; +\; w(\mu_j(s_j))-
E_1(s_j)\\&\ge& w(\mu_j(s_j))- E_1(s_j)\; \; \ge\; \;
w(\mu_j(s_j))-\eps\; \; \to\; \; \omega_o-\eps\nonumber, \end{eqnarray}
so
$w(\bar
x)\ge \omega_o-\eps$. This stands in contradiction to
(\ref{choice}), so we conclude that $\bar \mu(\bar s)\in \crr$.
Since $w$ is continuous at $\bar \mu(\bar s)\in \crr$, it follows
that $(\bar s, \bar \mu)\in {\cal Z}_1$ is an upper bound for
$\{(s_j, \mu_j)\}$.

It follows from Zorn's Lemma that ${\cal Z}_1$ contains a maximal
element which we will denote by $(\bar t, \bar \gamma)$. We will
assume wlog that $\bar \gamma(\bar t\, )\not\in \T$
(since otherwise, (\ref{goal}) is satisfied if we use the input
for $\bar \gamma$). We will now show that $\bar t=1$. Let $B$ be
an open set containing $\bar \gamma(\bar t\, )$ whose closure lies
in $\crr\setminus\T$.  Such as set exists since our hypothesis
$STC\T$ implies that $\crr$ is open (cf. \cite{BARD}) and
$\T$ is closed. Suppose that $\bar t<1$, set $q=\bar\gamma(\bar t)$, and
pick $\delta \in [0, \dist(q,
\partial B)/2)$. Set
\[
T_\delta(q)\; \; =\; \; \inf\left\{t:
\dist(y_{q}(t,\alpha),\partial B)\le \delta, \alpha\in
{\cal U}\right\}.
\]
Taking
$x=q$ in (\ref{sssss}), it follows that $T_\delta(q)>0$.

Indeed, for each $\tilde\delta>0$, we can use (\ref{sssss}) to
find a $\tilde t>0$ so that $y_{q}(t,\alpha)\in B(\{q\},
\tilde \delta)$ for all $\alpha\in \calu$ and all $t\in [0,\tilde
t\, ]$. Choosing $\tilde\delta=1/4\, \dist(q,\partial B)$, it
follows that
\begin{eqnarray}
\dist(y_{q}(t,\alpha), \partial B)&\ge & \dist(q,
\partial B)-||y_{q}(t,\alpha)-q||\nonumber
\\&\ge& \frac{1}{2}\dist(q, \partial B)\; \; \;
>\; \; \; \delta \nonumber
\end{eqnarray}
for all $t\in [0,\tilde t\, ]$ and $\alpha\in \calu$.  In
particular, $T_\delta(q)\ge \tilde t>0$.


By the conclusion (\ref{second}) of Lemma \ref{lemma0}, it follows
that there is a $t\in (0,1-\bar t\, )$ and a $\beta\in {\cal U}$
so that
\begin{equation}
\label{newone}
 w(\bar \gamma(\bar t\, ))\; \; \ge\; \; \int_0^t
\ell(y_{\bar\gamma(\bar t\, )}(s,\beta), \beta(s))\, ds\; +\;
w(y_{\bar\gamma(\bar t\, )}(t, \beta))\; -\; E_1(\bar t+t)\; +\;
E_1(\bar t\, ) \end{equation}
 and so that $y_{\bar \gamma(\bar
t)}(\cdot, \beta)$ remains in $B$ on $[0,t]$. Let $\tilde \alpha$
denote the control for $\bar\gamma$. Since $(\bar t, \bar
\gamma)\in {\cal Z}_1$, it follows that
\begin{equation}
\label{secondnewone}
 w(\bar \gamma(0))\; -\; w(\bar\gamma(\bar t\, ))\; \; \ge\; \;
\int_0^{\bar t}\ell(y_{\bar
x}(s,\tilde\alpha),\tilde\alpha(s))\, ds\; -\; E_1(\bar t\, ).
\end{equation}
Let $\beta^\sharp$ denote the concatenation of the restriction of
the input $\tilde \alpha$ to $[0, \bar t\, ]$ followed by the
input $\beta$. If we now add the inequalities (\ref{newone}) and
(\ref{secondnewone}), then we get
\begin{equation}
\label{thirdnewone}
 w(\bar\gamma(0))\; \; \ge\; \; \int_0^{\bar
t+t} \ell(y_{\bar x}(s, \beta^\sharp), \beta^\sharp(s))\, ds\; +\;
w(y_{\bar x}(\bar t+t,\beta^\sharp))\;
-\;
E_1(\bar t+t).
\end{equation}
Since $t$ was chosen so that $\bar t+t<1$ and $B\subseteq\crr$, we
conclude from (\ref{thirdnewone}) that $\left(\bar t+t, y_{\bar
x}(\cdot, \beta^\sharp)\right)\in {\cal Z}_1$.
Since $y_{\bar x}(\cdot,\beta^\sharp)$ is an extension of $\bar \gamma$,
this contradicts
the maximality of the pair $(\bar t, \bar \gamma)$. Therefore,
$\bar t=1$.

We will now extend $\bar \gamma:[0,1]\to\crr$ to get the desired
trajectory.  Set
\[
{\cal Z}_2\; \; =\; \; \left\{
\begin{array}{c}
(t,\gamma):  \; \; \; 0\, \le\,  t\, \le\,  1, \; \text{and}
\gamma:\; [0,t]\to \crr\; \text{is a trajectory}\\[.8em]\! \! \!
\! {\rm for}\; \; \dot x\,  \, =\, \,  f(x,\alpha )\; \text{for
some}\; \alpha\, \in\, {\cal U}\; \, \text{with}\,  \gamma(0)\, \,
=\, \, \bar \gamma(1)\\[.8em] \! \! \! \! \text{so that} w(\bar
\gamma(1))\, \ge\, \int_0^t \ell(\gamma(s), \alpha(s))\,
ds+w(\gamma(t))- E_2(t).
\end{array}
\right\},
\]
and partially order ${\cal Z}_2$ by the relation (\ref{rel}) as before.
By the preceding, we know that ${\cal Z}_2$ contains a
maximal element $(1,\tau_2)$.  Let $u_2:[0,1]\to U$ denote the
input for $\tau_2$.  We can assume that $\tau_2(1)\not\in\T$.
Indeed, if $s_2:=\inf\{t\ge 0: \tau_2(t)\in\T\}<\infty$, then
we can satisfy the requirement
(\ref{goal}) by setting
\[
\bar\alpha(t)= \twoif{\tilde\alpha(t),}{0\le t\le 1}
{u_2(t-1),}{1\le t\le 1+s_2},
\]
where $\tilde\alpha$ is the control for $\bar \gamma$ on $[0,1]$.
Let $c_2$ denote the concatenation of $\tilde\alpha\lceil[0,1]$
followed by $u_2\lceil[0,1]$, and let $\gamma_2$ denote the
corresponding concatenated trajectory for $c_2$ from $\bar x$ to
$\tau_2(1)$.  We can assume $\gamma_2(2)\not\in\T$, as argued
before.

Now reapply the procedure to $\gamma_2(2)$ to get a longer
trajectory that reaches $\T$ or runs for  three time units without
leaving $\crr$. The procedure is iterated, and it results in a
sequence of terminal points $\phi_n(n)$ for trajectories
$\phi_n(s)=y_{\bar x}(s,c_n)$
which begin at $\bar x$, are defined on $[0,n]$, and which we can
assume remain in
$\crr\setminus\T$.   It follows that for all $n\in\N$, we
would have
\begin{equation}
\label{trips} w(\bar x)\; \; \ge \; \; \int_0^n \ell(\phi_n(s,
c_n), c_n(s))\, ds\; +\; w(\phi_n(n))\; -\;
\frac{\eps}{2}(1-e^{-n}).
\end{equation}
Recall from assumption $(A_3)$ that $\ell$ is nonnegative. Setting
$\hat \alpha(s)=c_n(s)$ if  $n-1<s\le n$, letting $\hat
\phi$
denote the corresponding trajectory, and letting $b$ denote a
lower bound for $w$, a passage to the limit as $n\to\infty$ in
(\ref{trips}) gives
\[
\int_0^\infty \ell(\hat\phi(s),\hat\alpha(s))\, ds\; \; \le\; \;
w(\bar x)\; -\; b\; +\; \frac{\eps}{2}\; <\; \; \infty,
\]
since $\hat\phi\equiv \phi_n$ on $(0, n]$.   It follows
that $\lim_{s\to\infty}\hat\phi(s)$ exists and
lies in the target $\T$.

Set $p_n=\phi_n(n)$ for all $n$.
Since we were assuming that $U$ is compact, and since $\ell$ is
continuous, we conclude that
\begin{equation}
\label{numbiz}
\ds \sup_{n\in\N, 0\le s\le 1, \alpha\in \calu, u\in U}
\ell(y_{p_n}(s,\alpha), u)
\; =:
R\; \; <\; \; \infty
\end{equation}
Since condition $STC\T$ is satisfied, it follows that there is an
input $\tilde \beta$ and an $m\in \N$ so that
 \begin{equation}
 \label{maxx}
 \left\{\int_0^{t_{p_m}(\tilde\beta)}\ell(y_{p_m}
(s,\tilde \beta), \tilde\beta(s))\, ds\; \; \bigvee\; \;
\left\vert w(p_m)\right\vert\right\}\; \; <\; \; \eps/4.
\end{equation}
Indeed, the continuity of $w$ on $\cal R$ and the hypothesis that
$w\equiv 0$ on $\T\subseteq\crr$  guarantee that $w(\phi_n(n))\to
0$ as $n\to\infty$, and the $STC\T$ condition ensures that we can
drive $\phi_n(n)$ to $\T$ in time $<\eps/[4(R+1)]$ when $n$ is
large enough.
 Fixing $m\in\N$ for which there is a $\tilde \beta$ satisfying
 (\ref{maxx}),
 and letting $\bar \alpha$ denote the concatenation of
 the input $c_m\lceil[0,m]$ followed by the input  $\tilde
 \beta$,
we combine (\ref{trips}) and (\ref{maxx}) to get \beqn w(\bar
x)&\ge& \int_0^m\ell(\phi_m(s), c_m(s))\, ds\; \; +\; \;
w(p_m)\nonumber\\&+&\int_0^{t_{p_m}(\tilde\beta)}
\ell(y_{p_m}(s, \tilde\beta), \tilde\beta(s))\, ds\; \; -\;
\;  \frac{\eps}{2}(1-e^{-m})\; \; -\; \; \frac{\eps}{4}\nonumber\\
&\ge& \int_0^m\ell(\phi_m(s), c_m(s))\,
ds+\int_0^{t_{p_m}(\tilde\beta)} \ell(y_{\phi_m(m)}(s,
\tilde\beta), \tilde\beta(s))\,
ds-\frac{\eps}{2}(1-e^{-m})-\frac{\eps}{2}\nonumber\\ &\ge&
\int_0^{t_{\bar x}(\bar \alpha)} \ell(y_{\bar x}(s,\bar\alpha),
\bar\alpha(s))\, ds-\frac{\eps}{2}(2-e^{-m}).\eeqn Therefore,
$\bar\alpha$ satisfies the requirement (\ref{goal}). This proves
Theorem \ref{thm1}.


\section{Problems with Unbounded Control Sets}
\label{unbdd}
If we impose more regularity on $f$ and $\ell$, then we can extend
Theorem \ref{thm1} to
problems with unbounded control sets $U$ and unbounded
Lagrangians, including a large class of linear quadratic (LQ) problems
with $U=\R^M$.   Indeed, assume that $U\subseteq\R^M$ is closed
and nonempty but possibly unbounded, and that there are
positive constants $L$,
$L_\delta$, $C_\delta$ and $1\le q <p$ so that the following conditions
from \cite{S99a} hold:

\bi
\item[$(A_5)$]
$f:\R^N\times U\to\R^N$ is continuous, and the
estimates $||f(x,a)-f(z,a)||\le
L(1+||a||^q)||x-z||$ and $||f(x,a)||\le L(1+||x||+||a||^q)$ hold for all
$x,z\in\R^N$ and $a\in U$.
\item[$(A_6)$]
$\ell:\R^N\times U\to [0,\infty)$ is continuous, and the estimates
$|\ell(x,a)-\ell(z,a)|\le L_\delta[1+||a||^p]||x-z||$ and
$C_\delta||a||^p-L_\delta\le \ell(x,a)\le L_\delta(1+||a||^p)$ hold for
all
$x,z\in B_\delta(0)$ and
$a\in
U$ and for all $\delta>0$.
\item[$(A_7)$]
There is a compact set $C\subseteq U$ so that $f\lceil[ \R^N\times C]$
satisfies $STC\T$, where $\T\subseteq \R^N$ is closed and nonempty.
\ei
These assumptions imply that the
supremum in the definition of the HJBE is always finite. Moreover,
Lemma \ref{lemma0} on representation remains valid if the hypotheses
$(A_1)$-$(A_3)$
are replaced by $(A_5)$-$(A_7)$, and one can show that
\begin{equation}
\label{elab}
\ds w(x)=\inf_{\alpha\in \calu}\sup_{t\in[0,t_x(\alpha))}\left[\int_0^t
\ell(y_x(s,\alpha),\alpha(s))\, ds\; + \; w(y_x(t,\alpha))\right]\; \;
\forall x\in\crr\setminus\T
\end{equation}
for all viscosity solutions $w$ of the HJBE on $\crr\setminus\T$
 (cf. \cite{S99a}).  By replacing the constant $R$ in the proof of
Theorem \ref{thm1} with $\sup\{\ell(y_{p_n}(s,\alpha),u): n\in \N,0\le
s\le 1,\alpha\in {\cal C}, u\in C\}$ and using (\ref{elab}) to get
(\ref{newone}),
our proof of Theorem \ref{thm1} then gives the following:
\bt{thm2} Let $\emptyset\ne U\subseteq \R^M$ be closed.  Assume
$(A_4)$-$(A_7)$. Let $w:\crr\to \R$ be a continuous
bounded-from-below  viscosity solution of (\ref{HJBE}) on
$\crr\setminus\T$ that vanishes on $\T$ and satisfies
$BC(\crr,\omega_o)$ for some $\omega_o\in\R\cup\{+\infty\}$. Then
$w\equiv v$. \et

In the LQ case, where $f(x,a)=Px+Qa$ and
$\ell(x,a)=x'Rx+a'Sa$ for constant matrices $P$, $Q$, $R$, and $S$ with
$R\ge 0$ and $S > 0$, and where $U=\R^M$ and $\T=\{0\}$, one checks
that  $(A_5)$-$(A_7)$ hold with the choice
$C:=[-1,+1]^M\subseteq \R^M$
if
the
controllability matrix $[Q \; PQ \; P^{2}Q \; \ldots \; P^{N-1}Q]$ has
full rank
$N$ (cf.
\cite{BARD}).
Then Theorem \ref{thm2} applies if $(A_4)$ holds.



\begin{thebibliography}{10}


\bibitem{BARD}
Bardi, M., and I. Capuzzo-Dolcetta, {\em Optimal Control and
Viscosity
Solutions of Hamilton-Jacobi-Bellman Equations}, Birkh{\"a}user,
Boston,
1997.

\bibitem{BDL97}
Bardi, Martino, and Francesca Da Lio,  ``On the Bellman equation
for some unbounded control problems,'' {\em NoDEA Nonlinear
Differential Equations Appl.}, {\bf 4}(1997), pp. 276-285.

\bibitem{BFS99}
Bardi, M.,   T.E.S. Raghavan, and T. Parthasarathy, Eds.,
{\em Stochastic and Differential Games: Theory and Numerical Methods},
Birkh\"auser, Boston, 1999.

\bibitem{BS91}
Bardi, Martino, and Pierpaolo Soravia, ``Hamilton-Jacobi equations
with singular boundary conditions on a free boundary and
applications to differential games,'' {\em Trans. Amer. Math.
Soc.},  {\bf 325}(1991), pp. 205-229.
\bibitem{DAL}
Da Lio, F., ``On the Bellman equation for infinite horizon
problems with unbounded cost functional,'' {\em Appl. Math.
Optim.}, {\bf 41}(1999), pp. 171-197.

\bibitem{meagre}
Desch, W., H. Longemann, E.P. Ryan, and E.D. Sontag, ``Meagre
functions and asymptotic behavior of dynamical systems,'' {\em
Nonlinear Analysis}, to appear.




\bibitem{FLEM}
Fleming, W.H., and H.M. Soner, {\em Controlled Markov Processes and Viscosity
Solutions}, Springer, New York, 1993.
\bibitem{Mdis}
Malisoff, M., {\em Viscosity Solutions of the Bellman Equation for
Optimal
Control Problems with Exit Times}, Ph.D. Thesis, Rutgers University, New
Brunswick, NJ, January 2000.
\bibitem{M99b}
Malisoff, M., ``Viscosity solutions of the Bellman equation for
exit time optimal control problems with vanishing Lagrangians,''
{\em SIAM J. Control Optim.}, to appear.

\bibitem{MALI}
Malisoff, M., ``Viscosity solutions of the Bellman equation for
exit time optimal control problems with non-Lipschitz dynamics,''
{\em ESAIM: Control, Optimisation and Calculus of Variations},
{\bf 6}(2001), pp. 415-441.

\bibitem{M01}
Malisoff, M., ``Bounded-from-below solutions of the
Hamilton-Jacobi equation for optimal control problems with exit
times: Vanishing Lagrangians, eikonal equations, and
shape-from-shading,'' submitted.

\bibitem{R70}
Rockafeller, R.T., {\em Convex Analysis}, Princeton University
Press, Princeton, NJ, 1970.


\bibitem{SUSS}
Piccoli, B., and H. Sussmann, ``Regular synthesis and sufficient
conditions for optimality,'' {\em SIAM J. Control Optim.}, {\bf
39}(2000), pp. 359-410.

\bibitem{sontag}
Sontag, E.D., {\em Mathematical Control Theory, Deterministic Finite
Dimensional Systems, Second Edition}, Springer-Verlag, New York, 1998.

\bibitem{sorav}
Soravia, P., ``Pursuit evasion problems and viscosity solutions of
Isaacs equations,'' {\em SIAM J. Control Opt.}, {\bf 31}(1993),
pp. 604-623.

\bibitem{S99a}
Soravia, P., ``Optimality principles and representation formulas
for viscosity solutions of Hamilton-Jacobi equations II:
Equations of control problems with state constraints,'' {\em
Differential
Integral Equations}, {\bf 12}(1999), pp. 275--293
\bibitem{susssymm}
Sussmann, H.J., ``A general theorem on local controllability,''
{\em SIAM J. Control Optim.,} {\bf 25}(1987), pp. 158-194.

\bibitem{Su-Japan}
Sussmann, H.J., ``From the Brachystochrone problem to the maximum
principle,'' in {\em Proc. 35th IEEE CDC}, IEEE, New York, 1996,
pp. 1588-1594.



\bibitem{ZB}
Zelikin, M.I., and V.F. Borisov, {\em Theory of Chattering Control
with Applications to Astronautics, Robotics, Economics, and
Engineering},  Birkh{\"a}user, Boston, 1994.

\end{thebibliography}
\end{document}


