Optimal control

Linear quadratic control

A special case of the general nonlinear optimal control problem given in the previous section is the linear quadratic (LQ) optimal control problem. The LQ problem is stated as follows. Minimize the quadratic continuous-time cost functional $${\displaystyle J=\frac{1}{2}{\mathbf{x}}^{\mathsf{T}}(t_f){\mathbf{S}}_f\mathbf{x}(t_f)+\frac{1}{2}{\int }_{t_0}^{t_f}[{\mathbf{x}}^{\mathsf{T}}(t)\mathbf{Q}(t)\mathbf{x}(t)+{\mathbf{u}}^{\mathsf{T}}(t)\mathbf{R}(t)\mathbf{u}(t)]\mathrm{d}t}$$

Subject to the linear first-order dynamic constraints $${\displaystyle \dot{\mathbf{x}}(t)=\mathbf{A}(t)\mathbf{x}(t)+\mathbf{B}(t)\mathbf{u}(t),}$$ and the initial condition $${\displaystyle \mathbf{x}(t_0)={\mathbf{x}}_0}$$

A particular form of the LQ problem that arises in many control system problems is that of the linear quadratic regulator (LQR) where all of the matrices (i.e., ${\displaystyle \mathbf{A}}$, ${\displaystyle \mathbf{B}}$, ${\displaystyle \mathbf{Q}}$, and ${\displaystyle \mathbf{R}}$) are constant, the initial time is arbitrarily set to zero, and the terminal time is taken in the limit ${\displaystyle t_f\to \mathrm{\infty }}$ (this last assumption is what is known as infinite horizon). The LQR problem is stated as follows. Minimize the infinite horizon quadratic continuous-time cost functional $${\displaystyle J=\frac{1}{2}{\int }_0^{\mathrm{\infty }}[{\mathbf{x}}^{\mathsf{T}}(t)\mathbf{Q}\mathbf{x}(t)+{\mathbf{u}}^{\mathsf{T}}(t)\mathbf{R}\mathbf{u}(t)]\mathrm{d}t}$$

Subject to the linear time-invariant first-order dynamic constraints $${\displaystyle \dot{\mathbf{x}}(t)=\mathbf{A}\mathbf{x}(t)+\mathbf{B}\mathbf{u}(t),}$$ and the initial condition $${\displaystyle \mathbf{x}(t_0)={\mathbf{x}}_0}$$

In the finite-horizon case the matrices are restricted in that ${\displaystyle \mathbf{Q}}$ and ${\displaystyle \mathbf{R}}$ are positive semi-definite and positive definite, respectively. In the infinite-horizon case, however, the matrices ${\displaystyle \mathbf{Q}}$ and ${\displaystyle \mathbf{R}}$ are not only positive-semidefinite and positive-definite, respectively, but are also constant. These additional restrictions on ${\displaystyle \mathbf{Q}}$ and ${\displaystyle \mathbf{R}}$ in the infinite-horizon case are enforced to ensure that the cost functional remains positive. Furthermore, in order to ensure that the cost function is bounded, the additional restriction is imposed that the pair ${\displaystyle (\mathbf{A},\mathbf{B})}$ is controllable. Note that the LQ or LQR cost functional can be thought of physically as attempting to minimize the control energy (measured as a quadratic form).

The infinite horizon problem (i.e., LQR) may seem overly restrictive and essentially useless because it assumes that the operator is driving the system to zero-state and hence driving the output of the system to zero. This is indeed correct. However the problem of driving the output to a desired nonzero level can be solved after the zero output one is. In fact, it can be proved that this secondary LQR problem can be solved in a very straightforward manner. It has been shown in classical optimal control theory that the LQ (or LQR) optimal control has the feedback form $${\displaystyle \mathbf{u}(t)=-\mathbf{K}(t)\mathbf{x}(t)}$$ where ${\displaystyle \mathbf{K}(t)}$ is a properly dimensioned matrix, given as $${\displaystyle \mathbf{K}(t)={\mathbf{R}}^{-1}{\mathbf{B}}^{\mathsf{T}}\mathbf{S}(t),}$$ and ${\displaystyle \mathbf{S}(t)}$ is the solution of the differential Riccati equation. The differential Riccati equation is given as $${\displaystyle \dot{\mathbf{S}}(t)=-\mathbf{S}(t)\mathbf{A}-{\mathbf{A}}^{\mathsf{T}}\mathbf{S}(t)+\mathbf{S}(t)\mathbf{B}{\mathbf{R}}^{-1}{\mathbf{B}}^{\mathsf{T}}\mathbf{S}(t)-\mathbf{Q}}$$

For the finite horizon LQ problem, the Riccati equation is integrated backward in time using the terminal boundary condition $${\displaystyle \mathbf{S}(t_f)={\mathbf{S}}_f}$$

For the infinite horizon LQR problem, the differential Riccati equation is replaced with the algebraic Riccati equation (ARE) given as $${\displaystyle \mathbf{0}=-\mathbf{S}\mathbf{A}-{\mathbf{A}}^{\mathsf{T}}\mathbf{S}+\mathbf{S}\mathbf{B}{\mathbf{R}}^{-1}{\mathbf{B}}^{\mathsf{T}}\mathbf{S}-\mathbf{Q}}$$

Understanding that the ARE arises from infinite horizon problem, the matrices ${\displaystyle \mathbf{A}}$, ${\displaystyle \mathbf{B}}$, ${\displaystyle \mathbf{Q}}$, and ${\displaystyle \mathbf{R}}$ are all constant. It is noted that there are in general multiple solutions to the algebraic Riccati equation and the positive definite (or positive semi-definite) solution is the one that is used to compute the feedback gain. The LQ (LQR) problem was elegantly solved by Rudolf E. Kálmán.

Numerical methods for optimal control

Optimal control problems are generally nonlinear and therefore, generally do not have analytic solutions (e.g., like the linear-quadratic optimal control problem). As a result, it is necessary to employ numerical methods to solve optimal control problems. In the early years of optimal control (c. 1950s to 1980s) the favored approach for solving optimal control problems was that of indirect methods. In an indirect method, the calculus of variations is employed to obtain the first-order optimality conditions. These conditions result in a two-point (or, in the case of a complex problem, a multi-point) boundary-value problem. This boundary-value problem actually has a special structure because it arises from taking the derivative of a Hamiltonian. Thus, the resulting dynamical system is a Hamiltonian system of the form $${\displaystyle \begin{array}{cc}\dot{\mathbf{\text{x}}}& =\frac{\mathrm{\partial }H}{\mathrm{\partial }\mathit{\lambda }}\\ \dot{\mathit{\lambda }}& =-\frac{\mathrm{\partial }H}{\mathrm{\partial }\mathbf{\text{x}}}\end{array}}$$ where $${\displaystyle H=F+{\mathit{\lambda }}^{\mathsf{T}}\mathbf{\text{f}}-{\mathit{\mu }}^{\mathsf{T}}\mathbf{\text{h}}}$$ is the augmented Hamiltonian and in an indirect method, the boundary-value problem is solved (using the appropriate boundary or transversality conditions). The beauty of using an indirect method is that the state and adjoint (i.e., ${\displaystyle \mathit{\lambda }}$) are solved for and the resulting solution is readily verified to be an extremal trajectory. The disadvantage of indirect methods is that the boundary-value problem is often extremely difficult to solve (particularly for problems that span large time intervals or problems with interior point constraints). A well-known software program that implements indirect methods is BNDSCO.

The approach that has risen to prominence in numerical optimal control since the 1980s is that of so-called direct methods. In a direct method, the state or the control, or both, are approximated using an appropriate function approximation (e.g., polynomial approximation or piecewise constant parameterization). Simultaneously, the cost functional is approximated as a cost function. Then, the coefficients of the function approximations are treated as optimization variables and the problem is "transcribed" to a nonlinear optimization problem of the form:

Minimize $${\displaystyle F(\mathbf{z})}$$ subject to the algebraic constraints $${\displaystyle \begin{array}{cc}\mathbf{g}(\mathbf{z})& =\mathbf{0}\\ \mathbf{h}(\mathbf{z})& \le \mathbf{0}\end{array}}$$

Depending upon the type of direct method employed, the size of the nonlinear optimization problem can be quite small (e.g., as in a direct shooting or quasilinearization method), moderate (e.g. pseudospectral optimal control) or may be quite large (e.g., a direct collocation method). In the latter case (i.e., a collocation method), the nonlinear optimization problem may be literally thousands to tens of thousands of variables and constraints. Given the size of many NLPs arising from a direct method, it may appear somewhat counter-intuitive that solving the nonlinear optimization problem is easier than solving the boundary-value problem. It is, however, the fact that the NLP is easier to solve than the boundary-value problem. The reason for the relative ease of computation, particularly of a direct collocation method, is that the NLP is sparse and many well-known software programs exist (e.g., SNOPT) to solve large sparse NLPs. As a result, the range of problems that can be solved via direct methods (particularly direct collocation methods which are very popular these days) is significantly larger than the range of problems that can be solved via indirect methods. In fact, direct methods have become so popular these days that many people have written elaborate software programs that employ these methods. In particular, many such programs include DIRCOL, SOCS, OTIS, GESOP/ASTOS, DITAN. and PyGMO/PyKEP. In recent years, due to the advent of the MATLAB programming language, optimal control software in MATLAB has become more common. Examples of academically developed MATLAB software tools implementing direct methods include RIOTS, DIDO, DIRECT, FALCON.m, and GPOPS, while an example of an industry developed MATLAB tool is PROPT. These software tools have increased significantly the opportunity for people to explore complex optimal control problems both for academic research and industrial problems. Finally, it is noted that general-purpose MATLAB optimization environments such as TOMLAB have made coding complex optimal control problems significantly easier than was previously possible in languages such as C and FORTRAN.

Discrete-time optimal control

The examples thus far have shown continuous time systems and control solutions. In fact, as optimal control solutions are now often implemented digitally, contemporary control theory is now primarily concerned with discrete time systems and solutions. The Theory of Consistent Approximations provides conditions under which solutions to a series of increasingly accurate discretized optimal control problem converge to the solution of the original, continuous-time problem. Not all discretization methods have this property, even seemingly obvious ones. For instance, using a variable step-size routine to integrate the problem's dynamic equations may generate a gradient which does not converge to zero (or point in the right direction) as the solution is approached. The direct method RIOTS is based on the Theory of Consistent Approximation.

Examples

A common solution strategy in many optimal control problems is to solve for the costate (sometimes called the shadow price) ${\displaystyle \lambda (t)}$. The costate summarizes in one number the marginal value of expanding or contracting the state variable next turn. The marginal value is not only the gains accruing to it next turn but associated with the duration of the program. It is nice when ${\displaystyle \lambda (t)}$ can be solved analytically, but usually, the most one can do is describe it sufficiently well that the intuition can grasp the character of the solution and an equation solver can solve numerically for the values.

Having obtained ${\displaystyle \lambda (t)}$, the turn-t optimal value for the control can usually be solved as a differential equation conditional on knowledge of ${\displaystyle \lambda (t)}$. Again it is infrequent, especially in continuous-time problems, that one obtains the value of the control or the state explicitly. Usually, the strategy is to solve for thresholds and regions that characterize the optimal control and use a numerical solver to isolate the actual choice values in time.

Finite time

Consider the problem of a mine owner who must decide at what rate to extract ore from their mine. They own rights to the ore from date ${\displaystyle 0}$ to date ${\displaystyle T}$. At date ${\displaystyle 0}$ there is ${\displaystyle x_0}$ ore in the ground, and the time-dependent amount of ore ${\displaystyle x(t)}$ left in the ground declines at the rate of ${\displaystyle u(t)}$ that the mine owner extracts it. The mine owner extracts ore at cost ${\displaystyle u(t{)}^2/x(t)}$ (the cost of extraction increasing with the square of the extraction speed and the inverse of the amount of ore left) and sells ore at a constant price ${\displaystyle p}$. Any ore left in the ground at time ${\displaystyle T}$ cannot be sold and has no value (there is no "scrap value"). The owner chooses the rate of extraction varying with time ${\displaystyle u(t)}$ to maximize profits over the period of ownership with no time discounting.

1. Discrete-time version

   The manager maximizes profit ${\displaystyle \mathrm{\Pi }}$: $${\displaystyle \mathrm{\Pi }=\sum _{t=0}^{T-1}\left[p{u}_t-\frac{u_t^2}{x_t}\right]}$$ subject to the law of motion for the state variable ${\displaystyle x_t}$ $${\displaystyle x_{t+1}-x_t=-u_t}$$

   Form the Hamiltonian and differentiate: $${\displaystyle \begin{array}{cc}H& =p{u}_t-\frac{u_t^2}{x_t}-{\lambda }_{t+1}{u}_t\\ \frac{\mathrm{\partial }H}{\mathrm{\partial }{u}_t}& =p-{\lambda }_{t+1}-2\frac{u_t}{x_t}=0\\ {\lambda }_{t+1}-{\lambda }_t& =-\frac{\mathrm{\partial }H}{\mathrm{\partial }{x}_t}=-{\left(\frac{u_t}{x_t}\right)}^2\end{array}}$$

   As the mine owner does not value the ore remaining at time ${\displaystyle T}$, $${\displaystyle {\lambda }_T=0}$$

   Using the above equations, it is easy to solve for the ${\displaystyle x_t}$ and ${\displaystyle {\lambda }_t}$ series $${\displaystyle \begin{array}{cc}{\lambda }_t& ={\lambda }_{t+1}+\frac{{\left(p-{\lambda }_{t+1}\right)}^2}{4}\\ x_{t+1}& =x_t\frac{2-p+{\lambda }_{t+1}}{2}\end{array}}$$

   and using the initial and turn-T conditions, the ${\displaystyle x_t}$ series can be solved explicitly, giving ${\displaystyle u_t}$.
2. Continuous-time version

   The manager maximizes profit ${\displaystyle \mathrm{\Pi }}$: $${\displaystyle \mathrm{\Pi }={\int }_0^T\left[pu(t)-\frac{u(t{)}^2}{x(t)}\right]dt}$$ where the state variable ${\displaystyle x(t)}$ evolves as follows: $${\displaystyle \dot{x}(t)=-u(t)}$$

   Form the Hamiltonian and differentiate: $${\displaystyle \begin{array}{cc}H& =pu(t)-\frac{u(t{)}^2}{x(t)}-\lambda (t)u(t)\\ \frac{\mathrm{\partial }H}{\mathrm{\partial }u}& =p-\lambda (t)-2\frac{u(t)}{x(t)}=0\\ \dot{\lambda }(t)& =-\frac{\mathrm{\partial }H}{\mathrm{\partial }x}=-{\left(\frac{u(t)}{x(t)}\right)}^2\end{array}}$$

   As the mine owner does not value the ore remaining at time ${\displaystyle T}$, $${\displaystyle \lambda (T)=0}$$

   Using the above equations, it is easy to solve for the differential equations governing ${\displaystyle u(t)}$ and ${\displaystyle \lambda (t)}$ $${\displaystyle \begin{array}{cc}\dot{\lambda }(t)& =-\frac{(p-\lambda (t){)}^2}{4}\\ u(t)& =x(t)\frac{p-\lambda (t)}{2}\end{array}}$$ and using the initial and turn-T conditions, the functions can be solved to yield

   $${\displaystyle x(t)=\frac{{\left(4-pt+pT\right)}^2}{{\left(4+pT\right)}^2}{x}_0}$$