%\setcounter{chapter}{4}
\chapter{Dynamic Programming}

The objective of this chapter is to introduce the reader to the method of dynamic programming invented by Richard E. Bellman (1920-1984) in 1957. Dynamic programming can be used to synthesize optimal controllers for nonlinear, time-varying 
dynamic systems. We first present dynamic programming for discrete-time systems and then discuss the continuous version of dynamic programming.

\section{Discrete-Time Systems}
Dynamic programming is based on the Principle of Optimality (PO), that was formulated by Bellman as follows:

{\em An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision}.


In other words, an optimal trajectory has the property that at an intermediate point, no matter how it was reached, the rest of the trajectory must coincide with an optimal trajectory as computed from this intermediate point as the initial point. We prove the PO by contradiction. Suppose that we are given an optimal trajectory starting from an initial state $\b x_0=\b x(t_0)$ at time $t_0$ and terminating at the final state $\b x(t_f)$ at time $t_f$. Let $\b x(t)$ be an intermediate state on the optimal trajectory. Denote by $J^{*}(t,\b x(t))$ the optimal cost of traveling from $\b x(t)$ to the final state $\b x(t_f)$. Thus, $J^{*}(t_0,\b x(t_0))$ is the optimal cost of traveling from $\b x_0=\b x(t_0)$ to $\b x(t_f)$. It then follows that the portion of the optimal trajectory from $\b x(t)$ to $\b x(t_f)$ is also optimal. For if some other path, indicated by 
dashed curve in Figure~\ref{fig_po}, connecting $\b x(t)$  and $\b x(t_f)$ resulted in a smaller cost than the solid path, then this would provide a less expensive route from $\b x_0$ to $\b x(t_f)$, thus contradicting the optimality of the original trajectory.
\begin{figure}
\vspace{4in}
\hskip.2in\special{bmp:c:/mybook/fig_po.bmp x=5.33in y=4in}
\caption{Illustration of the Principle of Optimality.}
\label{fig_po}
\end{figure}

We note that the PO was already known to Johann Bernoulli who stated it in 1706 as follows ``... all curves, which should give a maximum, preserve also in all their sections the 
laws of the same maximum''. Here, the reader should interpret maximum as optimum. It seems that the PO first arose when Johann Bernoulli published the famous Brachistochrone challenge problem in June of 1696. Brachistochrone is Greek for shortest time. We discuss this problem in more detail in the chapter on calculus of variations. We now illustrate the PO on the following example of a sequential decision making 
process. We define a decision as the choice of alternative paths leaving a given node.
\begin{example} \rm
\label{ex_route}
We use dynamic programming to find the minimum cost path that starts at the node {\bf a} and ends at any one of the nodes {\bf k}, {\bf l}, {\bf m} in the routing network depicted in Figure~\ref{fig_route}.
\begin{figure}
\vspace{4in}
\hskip.2in\special{bmp:c:/mybook/route.bmp x=5.33in y=4in}
\caption{A routing network.}
\label{fig_route}
\end{figure} 
The travel costs are shown beside each path segment. The line segments can only be traversed from left to right. Applying the PO to this routing problem, we perform first a backward pass. Let $J^{*}_q$ be the minimum cost from a generic node {\bf d} to any one of the three possible final nodes. Then, we have
\[
J^{*}_g=16,\quad J^{*}_h=8,\quad J^{*}_i=7,\quad J^{*}_j=6.
\]
The next stage, yields
\[
J^{*}_d = \min\{3+J^{*}_g,11+J^{*}_h\}= \min\{19,19\}=19.
\]
Thus, in this case, we have two optimal paths from the node {\bf d}. We can take either {\bf dgk} or {\bf dhk} paths. We then compute optimal paths from nodes {\bf e} and {\bf f}. We have
\[
J^{*}_e = \min\{6+J^{*}_h,10+J^{*}_i\}= \min\{6+8,10+7\}=14,
\]
and
\[
J^{*}_f = \min\{4+J^{*}_i,12+J^{*}_j\}= \min\{4+7,12+6\}=11.
\]
Thus, the optimal path emanating from node {\bf e} is {\bf ehk}, and from node {\bf f} is {\bf fil}. The next stage yields
\[
J^{*}_b = \min\{9+J^{*}_d,2+J^{*}_e\}= \min\{9+19,12+6\}=16,
\]
and
\[
J^{*}_c = \min\{5+J^{*}_e,14+J^{*}_f\}= \min\{5+14,14+11\}=19.
\]
Therefore, the optimal path starting from {\bf b} is {\bf behk}, and starting from {\bf c} the optimal path is 
{\bf ceil}. Finally, the initial, and hence final, stage yields
\[
J^{*}_a = \min\{4+J^{*}_b,7+J^{*}_c\}= \min\{4+16,7+19\}=20.
\]
Hence, the optimal route from {\bf a} to any one of the three possible termination nodes {\bf k}, {\bf l}, or {\bf m} is {\bf abehk}. The minimum total cost on this path is $20$.
\end{example}
\markex
We now consider a class of discrete-time dynamic systems modeled by the difference equation
\[
\b x(k+1)=\b f\left(k,\b x(k),\b u(k)\right),
\]
with a given initial condition $\b x(k_0)=\b x_0$, and the associated performance index
\[
J=J_0=\Phi(N,\b x(N))+\sum_{k=0}^{N-1}F(k,\b x(k),\b u(k)).
\]
Let $J^{*}_k(\b x(k))$ denote the minimum cost of transferring the system from $\b x(k)$ to the terminal point $\b x(N)$. Since $\b x(N)$ is the terminal point, therefore $J^{*}_N(\b x(N))=\Phi(N,\b x(N))$. From the PO we obtain the cost of transfer from $\b x(N-1)$ to the terminal point. We have
\begin{eqnarray*}
J^{*}_{N-1}(\b x(N-1)) &=& \min_{\b u(N-1)}\left\{F(N-1,\b x(N-1),\b u(N-1))+J^{*}_N(\b x(N))\right\}\\
&=& \min_{\b u(N-1)}\left\{F(N-1,\b x(N-1),\b u(N-1))+\Phi(\b x(N))\right\}.
\end{eqnarray*}
When applying dynamic programming to solving optimal control problem for discrete-time dynamic systems, we usually perform two stage-by-stage passes through the time stages. We begin with a {\em backward pass\/}. For this, we use the equation $\b x(k+1)=\b f(k,\b x(k),\b u(k))$ to eliminate $\b x(N)$. Next, we carry out the minimization to find $\b u^{*}(N-1)$. We then repeat the process. A typical step of the backward pass is described as
\begin{eqnarray*}
J^{*}_k(\b x(k)) &=& \min_{\b u(k)}\left\{F(k,\b x(k),\b u(k))+J^{*}_{k+1}(\b x(k+1))\right\}\\
&=&\min_{\b u(k)}\left\{F(k,\b x(k),\b u(k))+J^{*}_{k+1}\left(\b f(k,\b x(k),\b u(k))\right)\right\}.
\end{eqnarray*}
The backward pass is completed when the initial time $k_0$ is reached. Now, since $\b x_0=\b x(k_0)$ is known, we find $\b u_0=\b u(k_0)$ in terms of this state. We can then proceed with the {\em forward pass\/}. We use $\b x_0,\b u_0$, and the difference equation $\b x(k+1)=f(k,\b x(k),\b u(k))$ to compute $\b x(k_0+1)$. The state $\b x(k_0+1)$ is then used to compute $\b u(k_0+1)$  from $\b x(k_0+2)=f(k_0+1,\b x(k_0+1),\b u(k_0+1))$, etc.
\begin{example} \rm
Consider a scalar discrete-time dynamic system modeled by
\[
x(k+1)=2x(k)-3u(k),\quad x(0)=4,
\]
and the performance index
\[
J=J_0=(x(2)-10)^2+\frac{1}{2}\sum_{k=0}^{1}\left(x^2(k)+u^2(k)\right).
\]
Note that the final state, in this example, is free. We use dynamic programming to find optimal $u(0)$ and $u(1)$. There are no constraints on $u(k)$. We begin with the backward pass. We have
\[
J^{*}(x(2))=(x(2)-10)^2.
\]
Then
\begin{eqnarray*}
J^{*}(x(1)) &=& \min_{u(1)}\left\{\frac{1}{2}\left(x^2(1)+u^2(1)\right)+J^{*}(x(2))\right\}\\
&=& \min_{u(1)}\left\{\frac{1}{2}\left(x^2(1)+u^2(1)\right)+\left(2x(1)-3u(1)-10\right)^2\right\}.
\end{eqnarray*}
Since there are no constraints on $u(1)$, we find optimal $u(1)$ as a function of $x(1)$ by applying the first-order necessary condition for unconstrained optimization to get
\[
\frac{\partial}{\partial u(1)}\left\{\frac{1}{2}\left(x^2(1)+u^2(1)\right)+\left(2x(1)-3u(1)-10\right)^2\right\}=0.
\]
Hence
\[
u(1)=\frac{1}{19}\left(12x(1)-60\right).
\]
Thus
\[
J^{*}(x(1)=\frac{1}{2}\left(x^2(1)+\left(\frac{12x(1)-60}{19}\right)^2\right)+\left(2x(1)-3\frac{12x(1)-60}{19}-10\right)^2.
\]
Next we compute $u(0)$. We have
\[
J^{*}(x(0))=\min_{u(0)}\left\{\frac{1}{2}\left(x^2(0)+u^2(0)\right)+J^{*}(x(1))\right\}.
\]
Taking into account that
\[
x(1)=2x(0)-3u(0),\quad x(0)=4,
\]
and the fact that there are no constraints on $u(0)$, we again use the first-order necessary condition for unconstrained optimization to find optimal $u(0)$. We compute
\[
\frac{\partial}{\partial u(0)}\left\{\frac{1}{2}\left(x^2(0)+u^2(0)\right)+J^{*}(x(1))\right\}=0
\]
to get
\begin{eqnarray*}
&{}&\frac{\partial}{\partial u(0)}\left\{8+\frac{1}{2}u^2(0)+\frac{1}{2}\left(\frac{12(8-3u(0))-60}{19}\right)^2\right\}\\
&{}&\quad  +\frac{\partial}{\partial u(0)}\left\{2(8-3u(0))-3\frac{12(8-3u(0))-60}{19}-10\right\}^2=0.
\end{eqnarray*}
Performing some manipulations yields
\[
13.7895u(0)=27.7895.
\]
Hence
\[
u(0)=2.0153.
\] 
This completes the backward pass. We are now ready for the forward pass. We use the system difference equation, $x(0)$, and $u(0)$ to compute $x(1)$. We get
\[
x(1)=1.9541.
\]
Using the above, we find
\[
u(1)= \frac{12x(1)-60}{19}= -1.9237.
\]
Therefore,
\[
x(2) = 2x(1)-3u(1)=9.6794.
\]
This completes the forward pass.
\end{example}
\markex
\section{Discrete Linear Quadratic Regulator Problem}
We now apply the PO to find the optimal control of a linear state-feedback form for the discrete linear quadratic regulator problem. This problem is stated as follows. Given a 
discrete linear plant model of the form:
\[
\b x(k+1)=\b A\b x(k)+\b B\b u(k),\quad 0\le k\le N-1,
\]
with a specified initial condition $\b x(0)=\b x_0$. Calculate the optimal control sequence
\[
\left\{\b u^{*}(0),\b u^{*}(1),\ldots,\b u^{*}(N-1)\right\}
\]
that minimizes the quadratic performance index
\[
J=J_0=\frac{1}{2}\b x^T(N)\b H_N\b x(N)+\frac{1}{2}\sum_{k=0}^{N-1}\left\{\b x^T(k)\b Q\b x(k)+\b u^T(k)\b R\b u(k)\right\},
\]
where $\b H_N=\b H^T_N \ge 0$, $\b Q=\b Q^T\ge 0$, and $\b R=\b R^T>0$. We assume that the components of the control vector are unconstrained. To solve this problem we use the PO. To begin, we note that
\[
J^{*}(\b x(N))=\frac{1}{2}\b x^T(N)\b H_N\b x(N).
\]
The above is the penalty for being in a state $\b x(N)$ at a time $N$.

We now decrement $k$ to $N-1$ to get
\[
J_{N-1}(\b x(N-1))=\frac{1}{2}\b x^T(N)\b H_N\b x(N)+\frac{1}{2}\b x^T(N-1)\b Q\b x(N-1)+\frac{1}{2}\b u^T(N-1)\b R\b u(N-1).
\]
We use the state equation to eliminate $\b x(N)$ from $J_{N-1}$ to obtain
\begin{eqnarray*}
J_{N-1} &=& \frac{1}{2}\left(\b A\b x(N-1)+\b B\b u(N-1)\right)^T\b H_N\left(\b A\b x(N-1)+\b B\b u(N-1)\right)\\
&{}&\quad +\frac{1}{2}\b x^T(N-1)\b Q\b x(N-1)+\frac{1}{2}\b u^T(N-1)\b R\b u(N-1).
\end{eqnarray*}
Since there are no constraints on control, we can apply the first-order necessary condition to find $\b u^{*}(N-1)$ as a function of $\b x(N-1)$. We get
\begin{eqnarray*}
\frac{\partial}{\partial \b u(N-1)}J_{N-1} &=& \left(\b A\b x(N-1)+\b B\b u(N-1)\right)^T\b H_N\b B+\b u^T(N-1)\b R\\
&=& \b 0.
\end{eqnarray*}
Solving for the optimal control, we obtain
\[
\b u^{*}(N-1)=-\left(\b B^T\b H_N\b B+\b R\right)^{-1}\b B^T\b H_N\b A\b x_{N-1}.
\]
Let
\[
\b K_{N-1}=\left(\b B^T\b H_N\b B+\b R\right)^{-1}\b B^T\b H_N\b A,
\]
then
\[
\b u^{*}(N-1)=-\b K_{N-1}\b x(N-1).
\]
Computing the optimal cost of transferring the system from $N-1$ to $N$, yields
\begin{eqnarray*}
J^{*}_{N-1} &=&\frac{1}{2}\b x^T(N-1)(\b A-\b B\b K_{N-1})^T\b H_N(\b A-\b B\b K_{N-1})\b x(N-1)\\
&{}&\quad +\frac{1}{2}\b x^T(N-1)\left(\b K^T_{N-1}\b R\b K_{N-1}\b + \b Q\right)\b x(N-1).
\end{eqnarray*}
Let
\[
\b H_{N-1}=(\b A-\b B\b K_{N-1})^T\b H_N(\b A-\b B\b K_{N-1})+\b K^T_{N-1}\b R\b K_{N-1}+\b Q,
\]
then
\[
J^{*}_{N-1}=\frac{1}{2}\b x^T(N-1)\b H_{N-1}\b x(N-1).
\]
We now decrement $k$ to $N-2$ to obtain
\[
J_{N-1}=\frac{1}{2}\b x^T(N-1)\b H_{N-1}\b x(N-1)+\frac{1}{2}\b x^T(N-1)\b Q\b x(N-2)+\frac{1}{2}\b u^T(N-2)\b R\b u(N-2).
\]
Note that $J_{N-2}$ has the same form as $J_{N-1}$. Thus, we obtain analogous optimal feedback gain with $N$ replaced by  $N-1$. Continuing in this fashion, we get the following results for each $k=N-1,N-2,\ldots,0$:
\begin{eqnarray*}
\b K_k &=& \left(\b B^T\b H_{k+1}\b B+\b R\right)^{-1}\b B^T\b H_{k+1}\b A,\\
\b u^{*}(k) &=& -\b K_k\b x(k),\\
\b H_{k}&=&(\b A-\b B\b K_{k})^T\b H_{k+1}(\b A-\b B\b K_{k})+\b K^T_{k}\b R\b K_{k}+\b Q,
\end{eqnarray*}
and
\[
J^{*}_k=\frac{1}{2}\b x^T(k)\b H_k\b x(k).
\]
The above control scheme can be implemented by computing the sequence of gain matrices $\{\b K_k\}$ off-line and stored. Then, we can implement the controller $\b u^{*}(k) = -\b K_k\b x(k)$. Note that the time-varying nature of the feedback controller may make an implementation of the control strategy quite complicated, especially for large $n$ and $N$. However, as we go to the limit as $N\to \infty$, we can simplify the solution to the problem. Specifically, let us 
consider a (reachable) system model
\[
\b x(k+1)=\b A\b x(k)+\b B\b u(k),\quad k \ge 0,\quad \b x(0)=\b x_0,
\]
and the performance index
\[
J=\frac{1}{2}\sum_{k=0}^{\infty}\left\{\b x^T(k)\b Q\b x(k)+\b u^T(k)\b R\b u(k)\right\}
\]		 
obtained from the previously considered performance index by letting $N\to \infty$ and setting $\b H_N=\b 0$. Then, the optimal controller takes the form
\[
\b u^{*}(k) = -\b K_{\infty}\b x(k),\quad k\ge0,
\]
where
\[
\b K_{\infty} = \left(\b B^T\b H_{\infty}\b B+\b R\right)^{-1}\b B^T\b H_{\infty}\b A
\]
and $\b H_{\infty}$ is defined as the limit obtained by continuing the recursion 
\[
\b H_{k}=(\b A-\b B\b K_{k})^T\b H_{k+1}(\b A-\b B\b K_{k})+\b K^T_{k}\b R\b K_{k}+\b Q
\]
back to $k=-\infty$, that is,
\[
\lim_{k\to -\infty}\b H_k=\b H_{\infty}.
\]
Alternatively, letting $k\to -\infty$ in the above recursion relation for $\b H_k$, we obtain
\[
\b H_{\infty}=(\b A-\b B\b K_{\infty})^T\b H_{\infty}(\b A-\b B\b K_{\infty})+\b K^T_{\infty}\b R\b K_{\infty}+\b Q,
\]
where $\b K_{\infty} = \left(\b B^T\b H_{\infty}\b B+\b R\right)^{-1}\b B^T\b H_{\infty}\b A$. Combining the above equations yields
\begin{eqnarray*}
\b H_{\infty} &=& \left(\b A-\b B(\b B^T\b H_{\infty}\b B+\b R)^{-1}\b B^T\b H_{\infty}\b A\right)^T\b H_{\infty}\\
&{}& \quad\times\left(\b A-\b B(\b B^T\b H_{\infty}\b B+\b R)^{-1}\b B^T\b H_{\infty}\b A\right)\\
&{}& +\left((\b B^T\b H_{\infty}\b B+\b R)^{-1}\b B^T\b H_{\infty}\b A\right)\b R\left((\b B^T\b H_{\infty}\b B+\b R)^{-1}\b B^T\b H_{\infty}\b A\right)+\b Q.
\end{eqnarray*}
Thus, we can compute $\b H_{\infty}$ by solving the above algebraic equation.

We next discuss a continuous form of dynamic programming. We begin our discussion by analyzing the minimum time regulator problem. Then, we focus our attention on a more general optimal control problem.

\section{Continuous Minimum Time Regulator Problem}
In this section we consider a control system modeled by
\[
\dot{\b x}=\b f(t,\b x,\b u)
\]
with a given initial state $\b x(t_0)=\b x_0$. We restrict the components $u_i$, $i=1,2,\ldots,m$  of the control vector $\b u$ to satisfy the amplitude constraints
\[
\alpha_i\le u_i\le \beta_i
\]
where $\alpha_i$, $\beta_i$ are fixed real numbers. A piecewise continuous control vector $\b u$ satisfying the above constraints is called admissible. We denote the set of admissible controllers by $U$. Our goal is to determine an admissible control law $\b u^*$ that steers system's trajectory from a given initial state $\b x(t_0)=\b x_0$ to a specified final state $\b x_f$ in the shortest 
possible time. This is equivalent to minimizing the performance index
\begin{eqnarray*}
J(\b u)&=&\int_{t_0}^{t_f}dt\\
&=& t_f-t_0.
\end{eqnarray*}
We call such a controller {\em time optimal}. Without loss of generality we can assume $t_0=0$ and $\b x_f=\b 0$. We assume that for any $\b x\ne \b x_f$ there exists admissible time optimal control transferring the system from $\b x$ to $\b x_f$ in minimum time. We denote by
\[
J^{*}(t,\b x)=J^{*}(t,\b x(t))
\]
the time of the optimal transfer from $\b x(t)$ to the specified $\b x_f$. Observe that
\[
J^{*}(t,\b x) = J^{*}(t,x_1,x_2\ldots,x_n):\mb{\Bb R}^{n+1}\to \mb{\Bb R},
\]
that is, $J^{*}(t,\b x)$ is a real valued function of $n+1$ variables. We assume that the function $J^{*}(t,\b x)$ is continuous and has continuous partial derivatives everywhere except at the point $\b x_f$.

Now, let $\b x_0\ne \b x_f$ be an arbitrary initial state in $\mb{\Bb R}^n$. Assume that we applied some admissible $\b u_0\in U$ on the time interval $[t_0,t]$. As a result of this control action, the system is transferred from $\b x(t_0)$ to $\b x(t)$. The time spent on the motion from $\b x(t_0)$ to $\b x(t)$ is $t-t_0$. We then apply an admissible optimal control that transfers the system in the minimum time $J^{*}(t,\b x(t))$ from $\b x(t)$ to $\b x_f$. The above considerations are illustrated in Figure~\ref{fig_transfer}.
\begin{figure}
\vspace{4in}
\hskip.2in\special{bmp:c:/mybook/transfer.bmp x=5.33in y=4in}
\caption{Transferring a dynamic system from an initial state to the final state in an optimal manner.}
\label{fig_transfer}
\end{figure}
Denoting the optimal time of transferring the system from $\b x(t_0)$ to $\b x_f$ by $J^{*}(t_0,\b x(t_0))$, we obtain
\[
(t-t_0)+J^{*}(t,\b x(t))\ge J^{*}(t_0,\b x(t_0).
\]
Rearranging the terms of the above equation and dividing by  $(t-t_0)$, yields
\[
1+\frac{J^{*}(t,\b x(t))- J^{*}(t_0,\b x(t_0)}{t-t_0}\ge 0.
\]
Letting $t\to t_0$, and taking into account that $\dot{x}_i=f_i(t,\b x,\b u)$, $i=1,2,\ldots,n$, we obtain
\begin{eqnarray*}
1+\frac{\partial J^{*}(t,\b x)}{\partial t}+\sum_{i=1}^{n}\frac{\partial J^{*}(t,\b x)}{\partial x_i}\dot{x}_i &=& 1+\frac{\partial J^{*}(t,\b x)}{\partial t}+\sum_{i=1}^{n}\frac{\partial J^{*}(t,\b x)}{\partial x_i}f_i\\
&=& 1+\frac{\partial J^{*}}{\partial t}+\frac{\partial J^{*}}{\partial \b x}\b f\\
&\ge& 0.
\end{eqnarray*}
We conclude that for any $\b x_0 \ne \b x_f$ and for any $\b u\in U$, we have
\[
1+\frac{\partial J^{*}}{\partial t}+\frac{\partial J^{*}}{\partial \b x}\b f \ge 0.
\]
Let us now define the Hamiltonian function
\[
H(t,\b x,\b u,\b p)=F(t,\b x, \b u)+\b p^T\b f(t,\b x,\b u),
\]
where
\[
\b p=\left[\begin{array}{cccc}
\frac{\partial J^*}{\partial x_1}&\frac{\partial J^*}{\partial x_2}&\ldots&\frac{\partial J^*}{\partial x_n}
\end{array}\right]^T.
\]
For the time optimal control problem under consideration we have $F(t,\b x,\b u)=1$. Thus, we can say that for any $\b x_0\ne \b x_f$ and for any $\b u\in U$, we have
\[
\frac{\partial J^*(t,\b x)}{\partial t}+H(t,\b x,\b u) \ge 0.
\]
We now show that
\[
\frac{\partial J^*(t,\b x)}{\partial t}+H(t,\b x,\b u) = 0
\]
for any optimal transfer, that is,
\[
\frac{\partial J^*(t,\b x)}{\partial t}+\min_{\b u\in U}H(t,\b x,\b u) = 0 \quad \mb{for any} \quad \b x\ne \b x_f.
\]
In the following we use the PO. Suppose that $\b u(t)\in U$ is an optimal controller that transfers the system from the initial state $\b x(t_0) \ne \b x_f$ to the given final state $\b x_f$ at time $t_f$. Thus, we have $J^{*}(t_0,\b x(t_0))=t_f-t_0$. The transfer from $\b x(t)$ to $\b x_f$ requires $(t_f-t_0)$ time units. See Figure~\ref{fig_hjb} for an illustration of the arguments.
\begin{figure}
\vspace{4in}
\hskip.2in\special{bmp:c:/mybook/hjb.bmp x=5.33in y=4in}
\caption{Illustration of the derivation of the Hamilton-Jacobi-Bellman equation.}
\label{fig_hjb}
\end{figure}
Hence,
\[
t_f-t=J^{*}(t_0,\b x(t_0))-(t-t_0),
\]
and it is not possible to go from $\b x(t)$ to $\b x_f$ in a time less than $J^{*}(t_0,\b x(t_0))-(t-t_0)$. For if such a more rapid motion were to exist, indicated by the dashed curve in Figure~\ref{fig_hjb}, then moving from $\b x_0$ to $\b x(t)$ during the time $t-t_0$, and then from $\b x(t)$ to $\b x_f$ during a time less than $J^{*}(t_0,\b x(t_0))-(t-t_0)$, we would accomplish the transfer from $\b x_0$ to $\b x_f$ during a time less than $J^{*}(t_0,\b x(t_0))$ which is impossible. Therefore, we can write
\begin{eqnarray*}
t_f-t &=& J^{*}(t,\b x(t))\\
&=& J^{*}(t_0,\b x(t_0))-(t-t_0).
\end{eqnarray*}
Rearranging terms, dividing by $t-t_0$, and letting $t\to t_0$, yields
\[
\frac{\partial J^*(t,\b x)}{\partial t}+\min_{\b u\in U}H(t,\b x,\b u) = 0 \quad \mb{for any} \quad \b x\ne \b x_f.
\]
We summarize our considerations in the following theorem.
\begin{thm}
Let $\dot{\b x}=\b f(t,\b x,\b u)$ be a control system model, $U$ a set of admissible controllers, and $\b x_f$ a prescribed final state. Suppose that
\begin{itemize}
\item [(i)] for any $\b x\ne \b x_f$ there exists an admissible optimal control transferring $\b x$ to $\b x_f$,
\item [(ii)]  the function $J^{*}(t,\b x(t))$, which is the time of optimal transfer of the system from $\b x$ to $\b x_f$, is continuously differentiable except at the point $\b x_f$,
\end{itemize} 
then
\begin{eqnarray*}
\frac{\partial J^*(t,\b x)}{\partial t}+H(t,\b x,\b u) &\ge& 0 \quad \mb{for any}\quad \b u\in U \quad \mb{and}\quad \b x\ne \b x_f,\\
\frac{\partial J^*(t,\b x)}{\partial t}+\min_{\b u\in U}H(t,\b x,\b u) &=& 0 \quad \mb{for any optimal transfer, where}\quad \b x\ne \b x_f.
\end{eqnarray*}
\end{thm}
The above theorem is a special case of the more general result known as the continuous form of the dynamic programming. 

We now use the PO to derive a continuous form of dynamic programming for a class of problems with a more general performance index.

\section{The Hamilton-Jacobi-Bellman Equation}

We consider a control process model of the form
\[
\dot{\b x}=\b f(t,\b x,\b u),\quad \b x(t_0)=\b x_0,
\]
and the performance index to minimize
\[
J(t,\b x(t_0),\b u)=\Phi(t_f,\b x(t_f))+\int_{t_0}^{t_f}F(\tau,\b x(\tau),\b u(\tau))d\tau.
\]
We define
\[
J(t,\b x(t),\b u(\tau))=\Phi(t_f,\b x(t_f))+\int_{t}^{t_f}F(\tau,\b x(\tau),\b u(\tau))d\tau
\]
with $t\le \tau\le t_f$, and write
\[
J^{*}(t,\b x(t))=\min_{\b u(\tau)}J(t,\b x(t),\b u(\tau)).
\]
We subdivide the interval $[t,t_f]$ as
\[
[t,t_f]=[t,t+\Delta t]\cup[t+\Delta t,t_f].
\]
Then, we can write
\[
J^{*}(t,\b x(t),\b u(\tau))=\min_{\b u(\tau)}\left\{\int_{t}^{t+\Delta t}Fd\tau+\int_{t+\Delta t}^{t_f}Fd\tau+\Phi(t_f,\b x(t_f))\right\}.
\]
However, the PO requires that the trajectory on the interval $[t,t+\Delta t]$ must be optimal. Hence, we have
\[
J^{*}(t,\b x(t))=\min_{\b u(\tau)}\left\{\int_{t}^{t+\Delta t}Fd\tau + J^{*}(t+\Delta t,\b x(t+\Delta t))\right\}.
\]
We next expand $J^{*}(t+\Delta t,\b x(t+\Delta t))$ in a Taylor series about the point $(t,\b x(t))$ to get
\[
J^{*}(t,\b x(t))=\min_{\b u(\tau)}\left\{\int_{t}^{t+\Delta t}Fd\tau + J^*+\frac{\partial J^*}{\partial t}\Delta t+\frac{\partial J^*}{\partial \b x}\left(\b x(t+\Delta t)-\b x(t)\right)+ \mb{H.O.T.}\right\},
\]
where H.O.T. stands for higher order terms. Since $J^*(t,\b x(t))$ is independent of $\b u$, we cancel the terms $J^*(t,\b x(t))$ out to obtain
\[
0=\min_{\b u(\tau)}\left\{\int_{t}^{t+\Delta t}Fd\tau + \frac{\partial J^*}{\partial t}\Delta t+\frac{\partial J^*}{\partial \b x}\left(\b x(t+\Delta t)-\b x(t)\right)+ \mb{H.O.T.}\right\}.
\]
Assuming that $\Delta t$ is small, we can write
\[
0=\min_{\b u(\tau)}\left\{F\Delta t+\frac{\partial J^*}{\partial t}\Delta t+\frac{\partial J^*}{\partial \b x}\b f\Delta t + \mb{H.O.T.}\right\}.
\]
Dividing the above equation by $\Delta t$ and letting $\Delta t \to 0$ yields
\[
0=\frac{\partial J^*}{\partial t}+\min_{\b u(\tau)}\left\{F+\frac{\partial J^*}{\partial \b x}\b f\right\}.
\]
Taking into account the definition of the Hamiltonian function, we write the above partial differential equation as
\[
0=\frac{\partial J^*}{\partial t}+\min_{\b u(\tau)}H
\]
subject to the boundary condition
\[
J^*(t_f,\b x(t_f))=\Phi(t_f,\b x(t_f)).
\]
The above partial differential equation for the optimal cost $J^*(t,\b x(t))$  is called the {\em Hamilton-Jacobi-Bellman\/} (HJB) equation. It provides the solution to the optimal control problem for general nonlinear dynamic systems. However, analytical solution to the HJB  equation is difficult to obtain in most cases. We now illustrate how the HJB equation can be used to construct optimal controllers with two examples.
\begin{example}\rm
We consider a general class of dynamic systems modeled by the scalar differential equation
\[
\dot{x}=ax+bu,\quad x(t_0)=x_0,
\]
with the associated cost index
\[
J(t_0)=\frac{1}{2}fx^2(t_f)+\frac{1}{2}\int_{t_0}^{t_f}\left(qx^2(t)+ru^2(t)\right)dt,
\]
where the initial time $t_0=0$, the final time $t_f<\infty$ is fixed, and the final state $x(t_f)$ is free. Our goal is construct the control $u^{*}$ that minimizes $J(0,x_0)$.

We first form the Hamiltonian function for the problem. It has the form
\[
H\left(t,x,u,\frac{\partial J^{*}}{\partial x}\right)=\frac{1}{2}qx^2+\frac{1}{2}ru^2+\frac{\partial J^{*}}{\partial x}(ax+bu).
\]
Since there are no constraints on the control $u$, we can determine the form of the optimal control by applying the first order necessary condition for static optimization. We compute
\[
\frac{\partial H}{\partial u} = ru+b\frac{\partial J^{*}}{\partial x}= 0.
\]
The optimal control, therefore, has the form
\[
u^{*}=-\frac{1}{r}b\frac{\partial J^{*}}{\partial x}.
\]
This control indeed minimizes the Hamiltonian function $H$ because
\[
\frac{\partial ^2 H}{\partial u^2}= r > 0,
\]
that is, the second order sufficient condition for static minimization is satisfied. We thus reduced the problem of constructing the optimal control to that of finding $\frac{\partial J^{*}}{\partial x}$. Substituting $u^{*}$ into the HJB equation yields
\begin{eqnarray*}
&{}&\frac{\partial J^{*}}{\partial t}+\frac{1}{2}qx^2+\frac{b^2}{2r}\left(\frac{\partial J^{*}}{\partial x} \right)^2+ax\frac{\partial J^{*}}{\partial x}-\frac{b^2}{r}\left( \frac{\partial J^{*}}{\partial x}\right)^2\\
&{}&\quad = \frac{\partial J^{*}}{\partial t}+\frac{1}{2}qx^2-\frac{b^2}{2r} \left(\frac{\partial J^{*}}{\partial x} \right)^2+ax \frac{\partial J^{*}}{\partial x}\\
&{}&\quad = 0.
\end{eqnarray*}
Let us now assume that $J^{*}$ is a quadratic function of the state for all $t\le t_f$, that is,
\[
J^{*}=\frac{1}{2}p(t)x^2,
\]
where $p(t)$ is a scalar function of time to be determined. Partial derivatives of $J^{*}$ are
\begin{eqnarray*}
\frac{\partial J^{*}}{\partial t}&=& \frac{1}{2}\dot{p}(t)x^2,\\
\frac{\partial J^{*}}{\partial x}&=&p(t)x.
\end{eqnarray*}
Substituting the above into the HJB equation and performing some manipulations gives
\[
\left(\frac{1}{2}\dot{p}(t)+\frac{1}{2}q+ap(t)-\frac{b^2p^2(t)}{2r}\right)x^2=0.
\]
For the above to hold for all $x=x(t)$ it is enough that
\[
\frac{1}{2}\dot{p}(t)+\frac{1}{2}q+ap(t)-\frac{b^2p^2(t)}{2r}=0,
\]
or equivalently
\[
\dot{p}(t)+q+2ap(t)-\frac{b^2p^2(t)}{r}=0
\]
subject to the boundary condition $p(t_f)=f$ that we obtain by comparing $J^{*}=\frac{1}{2}p(t)x^2$ and $J(t_f)=\frac{1}{2}fx^2(t_f)$. To solve the above equation we assume that
\[
p(t)=\rho\frac{\dot{w}(t)}{w(t)},
\]
where the parameter $\rho$ is be determined. Note that
\[
\dot{p}(t)=\rho \frac{\ddot{w}(t)w(t)-\dot{w}^2(t)}{w^2(t)}.
\]
Using the above, we obtain
\begin{eqnarray*}
&{}&\dot{p}+q+2ap-\frac{b^2p^2}{r}\\
&{}& \quad =\rho \frac{\ddot{w}w-\dot{w}^2}{w^2}+q\frac{w^2}{w^2}+2a\rho\frac{\dot{w}}{w}-\frac{b^2\rho ^2\dot{w}^2/r}{w^2}\\
&{}&\quad =\frac{\rho \ddot{w}w-\rho \dot{w}^2+qw^2+2a\rho \dot{w}w-b^2\rho ^2\dot{w}^2/r }{w^2}\\
&{}&\quad =0.
\end{eqnarray*}
We now choose $\rho$ so that the terms nonlinear in $\dot{w}$ cancel out. For this it is enough that
\[
-\rho \dot{w}^2-b^2\rho ^2\dot{w}^2/r=0.
\]
Hence, if we set
\[
\rho=-\frac{r}{b^2},
\]
then we the equation to be solved takes the form
\[
\frac{\left(-\frac{r}{b^2}\ddot{w}-\frac{2ar}{b^2}\dot{w}+qw \right)w}{w^2}=0.
\]
The above will be satisfied if
\[
-\frac{r}{b^2}\ddot{w}-\frac{2ar}{b^2}\dot{w}+qw=0,
\]
or equivalently
\[
\ddot{w}+2a\dot{w}-\frac{qb^2}{r}w=0
\]
which is just a second order linear differential equation. Its characteristic equation has two real roots:
\[
s_{1,2}=-a\pm \sqrt{a^2+\frac{qb^2}{r}}.
\]
Hence
\[
w(t)=C_1e^{s_1t}+C_2e^{s_2t},
\]
and
\[
p(t)=\rho\frac{\dot{w}(t)}{w(t)}= \rho \frac{s_1C_1e^{s_1t}+s_2C_2e^{s_2t}}{C_1e^{s_1t}+C_2e^{s_2t}}.
\]
Using the bounadary value $p(t_f)=f$, we express $C_1$ in terms of $C_2$ to obtain
\[
C_1=\frac{\rho s_2 C_2 e^{s_1 t_f}-fC_2e^{s_2 t_f}}{fe^{s_1 t_f}-\rho s_1e^{s_1t_f}}.
\]
We substitute the above expression for $C_1$ into $p(t)$ and cancel out $C_2$. Then, we use the obtained result to construct the optimal controller
\[
u^{*} = -\frac{1}{r}b\frac{\partial J^{*}}{\partial x}= -\frac{1}{r}bp(t)x.
\]
\end{example}
\markex
In the above example, the final time $t_f$ was fixed and $t_f<\infty$. In the following example, we consider the linear quadratic regulator design for $t_f=\infty$ using the HJB equation.
\begin{example}\rm
For the following model of a dynamic system:
\[
\left[\begin{array}{c}
\dot{x}_1\\
\dot{x}_2
\end{array}\right]=\left[\begin{array}{cc}
0 & 1\\
0 & -1
\end{array}\right]\left[\begin{array}{c}
x_1\\
x_2
\end{array}\right]+\left[\begin{array}{c}
0\\
1
\end{array}\right]u,
\]
and the performance index
\[
J=\frac{1}{2}\int_0^{\infty}\left(x^2_1+x^2_2+u^2\right)dt,
\]
use the HJB equation to find the optimal state-feedback 
controller. We first form the Hamiltonian function
\[
H=\frac{1}{2}\left(x^2_1+x^2_2+u^2\right)+\frac{\partial J^*}{\partial x_1}x_2+\frac{\partial J^*}{\partial x_2}(-x_2+u).
\]
We assume that $J^*$ has the form
\[
J^*=\frac{1}{2}\left(\alpha x^2_1+2\beta x_1 x_2 + \gamma x^2_2\right).
\]
Hence
\[
\frac{\partial J^*}{\partial t}=0,
\]
and the HJB equation takes the form
\[
\min_uH=0,
\]
with the boundary condition
\begin{eqnarray*}
J^*(\b x(t_f)) &=& J^*(\b x(\infty))\\
&=& 0.
\end{eqnarray*}
Since there are no constraints on $u$, we apply the first-order necessary condition for unconstrained optimization to find $u$ minimizing $H$. We compute
\begin{eqnarray*}
\frac{\partial H}{\partial u} &=& 0\\
&=& u^*+\frac{\partial J^*}{\partial x_2}.
\end{eqnarray*}
Hence
\[
u^*=-\frac{\partial J^*}{\partial x_2}.
\]
We substitute $u^*$ into the HJB equation to get
\[
\frac{1}{2}\left(x^2_1+x^2_2+\left( \frac{\partial J^*}{\partial x_2}\right)^2\right)+\frac{\partial J^*}{\partial x_1}x_2-\frac{\partial J^*}{\partial x_2}x_2-\left( \frac{\partial J^*}{\partial x_2}\right)^2=0.
\]
Taking into account that
\begin{eqnarray*}
\frac{\partial J^*}{\partial x_1} &=& \alpha x_1 + \beta x_2,\\
\frac{\partial J^*}{\partial x_2} &=& \beta x_1 + \gamma x_2,
\end{eqnarray*}
and substituting the above into the HJB equation yields
\[
\frac{1}{2}\left(x^2_1+x^2_2+(\beta x_1+\gamma x_2)^2 \right) + (\alpha x_1 + \beta x_2)x_2 - (\beta x_1 + \gamma x_2)x_2-(\beta x_1 + \gamma x_2)^2=0.
\]
We rearrange the above equation to obtain
\[
\frac{1}{2}x^2_1(1-\beta ^2)+x_1x_2(\alpha -\beta -\beta \gamma)+\frac{1}{2}x^2_2(1-2\gamma -\gamma^2 + 2\beta )=0.
\]
For this equation to hold we have to have
\begin{eqnarray*}
1-\beta ^2 &=& 0,\\
\alpha -\beta -\beta \gamma &=& 0,\\
1-2\gamma -\gamma^2 + 2\beta &=& 0.
\end{eqnarray*}
There are three solutions to the above system of equations:
\begin{enumerate}
\item $\alpha=2$, $\beta = \gamma =1$;
\item $\alpha =-2$, $\beta =1$, $\gamma=-3$;
\item $\alpha =0$, $\beta = \gamma = -1$.
\end{enumerate}
Thus, we have three candidate solutions to the problem:
\begin{eqnarray*}
u^{1} &=& -x_1-x_2,\\
u^{2} &=& -x_1+3x_2,\\
u^{3} &=& x_1+x_2.
\end{eqnarray*}
However, only $u^1$ stabilizes the plant. Hence, the optimal control law for the problem is
\[
u^*=-x_1-x_2.
\]
Note, that only for this controller the boundary condition, $J^*(\b x(t_f)) = J^*(\b x(\infty))= 0$, is satisfied.
\end{example}
\markex
\section{Exercises}
\begin{exercise}\rm
Show
\end{exercise}