Cool Things in Optimal Control and Physics

The Euler-Lagrange equation was developed in the 1750s by Euler and Lagrange in connection with their studies of the tautochrone problem. This is the problem of determining a curve on which a weighted particle will fall to a fixed point in a fixed amount of time, independent of the starting point. Lagrange solved this problem in 1755 and sent the solution to Euler. The two further developed Lagrange's method and applied it to mechanics, which led to the formulation of Lagrangian mechanics. Their correspondence ultimately led to the calculus of variations, a term coined by Euler himself in 1766.

In calculus of variations, the Euler-Lagrange equation, or Lagrange's equation, is a differential equation whose solutions are the functions for which a given functional is stationary. Because a differentiable functional is stationary at its local maxima and minima, the Euler-Lagrange equation is useful for solving optimization problems in which, given some functional, one seeks the function minimizing (or maximizing) it.

The Euler-Lagrange equation is an equation satisfied by a function \(q\) of a real argument t which is a stationary point of the functional:

\begin{equation} \label{eq:el-eqn-1} S(q) = \int_{a}^{b}L(t,q,\dot{q})dt \end{equation}

The Euler-Lagrange equation, then, is the ordinary differential equation

\begin{equation} \label{eq:el-eqn-2} \frac{\partial L}{\partial q}-\frac{d}{dt}\frac{\partial L}{\partial \dot{q}} = 0 \end{equation}

The solution of this Eq. \ref{eq:el-eqn-2} is the stationary solution of Eq. \ref{eq:el-eqn-1}.

For \(q\) to be a stationary solution of Eq. \ref{eq:el-eqn-1}:

\begin{equation} \label{eq:11} \frac{\delta S}{\delta q} = 0 \end{equation} \begin{eqnarray*} \label{eq:33} \delta S(q(t)) &=& \int_{t_0}^{t_f} \{ \frac{\partial L}{\partial q}\delta q + \frac{\partial{L}}{\partial{\dot{q}}}\delta{\dot{q}} \} dt \\ &=& \frac{\partial{L}}{\partial{\dot{q}}}\delta{q}(t)\Big|^{t_f}_{t_0} + \int_{t_0}^{t_f} \Big(\frac{\partial{L}}{\partial{q}} - \frac{d}{dt}\frac{\partial{L}}{\partial{\dot{q}}}\Big)\delta{q} dt \end{eqnarray*}

Major trick: \[ \frac{d}{dt} \{ \frac{\partial L}{\partial \dot{q}} \delta q \} = \frac{d}{dt} \{ \frac{\partial L}{\partial \dot{q}} \} \delta q + \frac{\partial L}{\partial \dot{q}} \delta \dot{q} \] Then we have: \[ \frac{\partial L}{\partial \dot{q}} \delta \dot{q} = \frac{d}{dt} \{ \frac{\partial L}{\partial \dot{q}} \delta q \} - \frac{d}{dt} \{ \frac{\partial L}{\partial \dot{q}} \} \delta q \]

The boundary conditions, \(\delta{q}(t_0) = 0\) and \(\delta{q}(t_f)=0\), causes the first term to vanish. Therefore, the stationary solution of Eq. \ref{eq:el-eqn-1} must satisfy: \[ \frac{\partial L}{\partial q}-\frac{d}{dt}\frac{\partial L}{\partial \dot{q}} = 0 \]

A Bellman equation, named after its discoverer, Richard Bellman, also known as a dynamic programming equation, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming. It writes the value of a decision problem at a certain point in time in terms of the payoff from some initial choices and the value of the remaining decision problem that results from those initial choices. This breaks a dynamic optimization problem into simpler subproblems, as Bellman's 'Principle of Optimality' prescribes. The Bellman equation was first applied to engineering control theory and to other topics in applied mathematics, and subsequently became an important tool in economic theory. Almost any problem which can be solved using optimal control theory can also be solved by analyzing the appropriate Bellman equation. However, the term 'Bellman equation' usually refers to the dynamic programming equation associated with discrete-time optimization problems. In continuous-time optimization problems, the analogous equation is a partial differential equation which is usually called the Hamilton-Jacobi-Bellman equation (HJB).

For the discrete-time optimal control problem: \[ J_k({x}_k) = \min_{{u}_k \in \cal{U}_k} \{ \phi(x_N) + \sum_{k=0}^{N-1} L_k({x}_k,{u}_k) \} \] s.t. \[ x_{k+1} = F(x_k, u_k, k) \]

Bellman equation says \(J_k(x_k)\), the optimal cost-to-go function, should satisfy:

\begin{equation} \label{eq:bellman} J_k(x_k) = \min_{{u}_k \in \cal{U}_k} \{ L_k(x_k, u_k) + J_{k+1}(x_{k+1}, u_{k+1}) \} \end{equation}

The Hamilton-Jacobi-Bellman (HJB) equation is a partial differential equation which is central to optimal control theory. The solution of the HJB equation is the value function, which gives the optimal cost-to-go for a given dynamical system with an associated cost function. The solution is open loop, but it also permits the solution of the closed loop problem. Classical variational problems, for example, the brachistochrone problem can be solved using this method. The HJB method can be generalized to stochastic systems as well.

The equation is a result of the theory of dynamic programming which was pioneered in the 1950s by Richard Bellman and coworkers. The corresponding discrete-time equation is usually referred to as the Bellman equation. In continuous time, the result can be seen as an extension of earlier work in classical physics on the Hamilton-Jacobi equation by William Rowan Hamilton and Carl Gustav Jacob Jacobi.

For the continuous time optimal control problem: \[ V(\mathbf{x}, t) = \min_{\mathbf{u}} \{ \phi(x(T)) + \int_t^T l(\mathbf{x}(t),\mathbf{u}(t), t) dt \} \] s.t. \[ \dot{x} = f(x,u,t) \]

The HJB equation is a partial differential equation. It says \(V(x, t)\), the value function, should satisfy:

\begin{equation} \label{eq:HJB} \color{red}{ -\frac{\partial V(\mathbf{x},t)}{\partial t} = \min_{\mathbf{u}}\{l(\mathbf{x},\mathbf{u}, t) + V_{\mathbf{x}}f(\mathbf{x},\mathbf{u}, t)\} } \end{equation}

with boundary condition: \[ \color{blue} V(x(T), T) = \phi(x(T), T) \]

Compare with the discrete time Bellman equation: \[ J_k(x_k) = \min_{{u}_k \in \mathcal{U}_k} \{ L_k(x_k, u_k) + J_{k+1}(x_{k+1}, u_{k+1}) \} \]

Note: \(V_t(x,t)\) in HJB equation is the gradient of \(V\) w.r.t time \(t\). It is different from \(\dot{V}\). The relation between these two are: \[ \dot{V}(x, t) = V_x \dot{x} + V_t \]

As we can see, if we can solve for \(V\) then we can find from it a close-form control policy \(u\) that achieves the minimum cost.

Intuitively, HJB can be derived as follows:

If \(V(x(t),t)\) is the optimal cost-to-go function (also called the 'value function'), then by Richard Bellman's principle of optimality, going from time \(t\) to \(t + dt\), we have

\begin{equation*} V(\mathbf{x}(t),t) = \min_{\mathbf{u}} \{l(\mathbf{x}(t),\mathbf{u}(t),t) dt + V(\mathbf{x}(t+ dt),t + dt)\} \end{equation*}

The Taylor expansion of the last term is:

\begin{equation*} V(\mathbf{x}(t+ dt),t+ dt) = V(\mathbf{x},t) + V_t dt + V_{\mathbf{x}}\dot{\mathbf{x}} dt + o( dt^2) \end{equation*}

where \(o( dt^2)\) denotes the terms in the Taylor expansion of higher order than one. Then if we cancel \(V(\mathbf{x}(t),t)\) on both sides, divide by \(dt\), and take the limit as \(dt\) approaches zero, then we obtain the HJB equation \ref{eq:HJB}.

Eq. \ref{eq:6} is often referred to as 'canonical equation'canonical equation'. As we can see there are boundary constraints on the initial state and the final co-state, therefore, we need to solve a two point BVP.

It shows that the optimal control \(\mathbf{u}^*\) is the value of \(\mathbf{u}\) that globally minimizes the Hamiltonian \(H(\mathbf{x},\mathbf{u},t,V_{\mathbf{x}})\), holding \(\mathbf{x}\), \(V_{\mathbf{x}}\), and \(t\) constant. It was formulated by the Russian mathematician Lev Semenovich Pontryagin and his students and known as Pontryagin's maximum principle.

One of the most effective way to solve HJB, which is a first-order nonlinear partial differential equation, is the method of characteristic. It amounts to find a field of extremals. We can use Euler-Lagrange Equations, which is ordinary differential equation (ODE), to solve a particular optimal path and its associate optimal function, thus get the field of extremals.

Recall the HJB equation \ref{eq:HJB}: \[ V_{t}(\mathbf{x},t) + \min_{\mathbf{u}}\{V_{\mathbf{x}}^Tf(\mathbf{x},\mathbf{u}) + l(\mathbf{x},\mathbf{u})\} = 0 \]

if the optimal control law is \(\pi(x,t)\), we can set \(u=\pi\) and drop 'min': \[ 0 = v_t(x,t) + l(x, \pi) + f(x, \pi)^T V_x(x,t) \] Now differentiate w.r.t \(x\) and suppress the dependences for clarity ¹: \[ 0 = V_{tx} + l_x + l_u u_x + (f_x^T + f_u^T u_x^T) V_x + V_{xx} f \]

Using the identify \[ \dot{V}_x = V_{tx} + V_{xx}f \] and regrouping yields: \[ 0 = \dot{V}_x + (l_x + f_x^T V_x) + u_x^T(l_u + f_u^T V_x) = \dot{V}_x + H_x + u_x^T H_u \]

When u is the optimal we have \(H_u = 0\), thus \[ - \dot{\lambda} = H_x(x,u,t) \] where \(\lambda := V_x\).

\[ \min \int_0^T l(x,u,t) dt \] s.t. \[ \dot{x} = f(x,u,t) \]

Let's convert the constrained optimization to unconstrained optimization using Method of Lagrange Multipliers method: \[ \min \int_0^T l(x,u,t) + \lambda^T (f(x,u,t) - \dot{x}) \] Let's define the Lagrange as: \[ L := l(x,u,t) + \lambda^T (f(x,u,t) - \dot{x}) \]

To extreme the functional, it should satisfies Euler-Lagrange Equation: \[ \frac{d}{dt} \nabla_{\dot{x}} L - \nabla_x L = 0 \] \[ \frac{d}{dt} \nabla_{\dot{\lambda}} L - \nabla_{\lambda} L = 0 \] \[ \frac{d}{dt} \nabla_{\dot{u}} L - \nabla_u L = 0 \]

Therefore we have: \[ \dot{\lambda} = - \nabla_x L \] \[ \dot{x} = f(x,u,t) \] \[ \nabla_u l + \lambda^T \nabla_u f(x,u,t) \]

Let's see how to find the same Hamiltonian by a general method: First, let's define a momentum: \[ p := \nabla_{\dot{x}} L = - \lambda \] then Hamiltonian is: \[ H := p\dot{x} - L = -l - \lambda^T f(x,u,t) \]

We have a different sign here, but if we choose \(\lambda\) as the momentum, we will have the same Hamiltonian.

• The maximum principle provides an efficient way to evaluate the gradient of the total cost w.r.t. the control, which can be used to find optima numerically: \[ \nabla_{u} J(t) = \nabla_{u} H(t) \]

Credit for the formulation of the principle of least action is commonly given to Pierre Louis Maupertuis, who wrote about it in 1744 and 1746, although the true priority is less clear, as discussed below.

Maupertuis felt that "Nature is thrifty in all its actions", and applied the principle broadly: The laws of movement and of rest deduced from this principle being precisely the same as those observed in nature, we can admire the application of it to all phenomena. The movement of animals, the vegetative growth of plants … are only its consequences; and the spectacle of the universe becomes so much the grander, so much more beautiful, the worthier of its Author, when one knows that a small number of laws, most wisely established, suffice for all movements.

Hamilton's principle is William Rowan Hamilton's formulation of the principle of stationary action. It states that the dynamics of a physical system is determined by a variational problem for a functional based on a single function, the Lagrangian, which contains all physical information concerning the system and the forces acting on it. The evolution \(q(t)\) of a system described by \(q(t) \in \mathbb{R}^N\) between \((t_1,q(t_1))\) and \((t_2,q(t_2))\) is an extremum of the action functional

\begin{equation} \label{eq:29} S(q):=\int_{t_1}^{t_2}L(t,q,\dot{q})dt \end{equation}

where \(L(t,q,\dot{q}):= K-V\) is the Lagrangian function for the system.

A good tutorial can be found at:

• http://www.eftaylor.com/software/ActionApplets/LeastAction.html

Lagrangian mechanics is a re-formulation of classical mechanics that combines conservation of momentum with conservation of energy. It was introduced by Italian mathematician Joseph-Louis Lagrange in 1788. In Lagrangian mechanics, the trajectory of a system of particles is derived by solving the Lagrange equations in one of two forms:

• the Lagrange equations of the first kind, which treat constraints explicitly as extra equations, often using Method of Lagrange Multipliers; and
• the Lagrange equations of the second kind, which incorporate the constraints directly by judicious choice of generalized coordinates.

The fundamental lemma of the calculus of variations shows that solving the Lagrange equations is equivalent to finding the path for which the Action functional is stationary, a quantity that is the integral of the Lagrangian over time.

Define the following scalar function (Action functional)

\begin{equation} \label{eq:lagrange} L=K(\dot{q})-V(q), \end{equation}

where \(K\) is kinetic energy and is a function of only \(\dot{q}\), \(V\) is the potential energy and is a function of only \(q\), \(q\) is called generalized coordinate. Lagrange equations are often written as

\begin{equation} \label{eq:lagrange-eqn} \frac{d}{dt}\frac{\partial L}{\partial \dot{q}} - \frac{\partial L}{\partial q} = 0. \end{equation}

Intuitive example:

\begin{equation} \label{eq:23} L = \frac{1}{2}mv^2-mgh \end{equation}

where \(v:=\dot{q}\) and \(h:=z\),the generalized coordinate is \(q:=(x,y,z)'\). The first term of \ref{eq:lagrange-eqn}

\begin{equation} \label{eq:24} \frac{d}{dt}\frac{\partial L}{\partial \dot{q}} = m\ddot{q}. \end{equation}

The second term is

\begin{equation} \label{eq:27} \frac{\partial L}{\partial q} = (0,0,mg)' \end{equation}

According to Newton's second law, \(m\ddot{q}-(0,0,mg) = 0\).

Hamiltonian mechanics is a reformulation of classical mechanics that was introduced in 1833 by Irish mathematician William Rowan Hamilton. It arose from Lagrangian mechanics, a previous reformulation of classical mechanics introduced by Joseph Louis Lagrange in 1788, but can be formulated without recourse to Lagrangian mechanics using symplectic spaces (see Mathematical formalism, below). The Hamiltonian method differs from the Lagrangian method in that instead of expressing second-order differential constraints on an n-dimensional coordinate space (where n is the number of degrees of freedom of the system), it expresses first-order constraints on a 2n-dimensional phase space.

In Hamiltonian mechanics, a classical physical system is described by a set of canonical coordinates \(r = (q, p)\), where each component of the coordinate \(q_i\), \(p_i\) is indexed to the frame of reference of the system. The time evolution of the system is uniquely defined by Hamilton's equations

\begin{eqnarray} \label{eq:hamilton-formula} \dot{p} &=& -\frac{\partial H}{\partial q} \\ \dot{q} &=& \frac{\partial H}{\partial p} \nonumber \end{eqnarray}

where \(p(t)\) is generalized momenta, \(q(t)\) is generalized coordinates, \(H\) is the Hamiltonian function, which often corresponds to the total energy of the system. For a closed system, it is the sum of the kinetic and potential energy in the system. . It is simply the total energy of the material point.

Intuitive Example:

\begin{equation} \label{eq:25} H=\frac{p^2}{2m}+V(q) \end{equation}

with the variable defined as:

• \(p = m\dot{q}\): the momentum of the material point
• \(q=(x,y,z)'\): the location of the material point
• \(V(q)\): the potential energy

Recall that \(F=\dot{p}=-\frac{\partial V}{\partial q}\), then Eq. \ref{eq:hamilton-formula} stands.

• Write out the Lagrangian \(L=T - V\). Express \(T\) and \(V\) as though you were going to use Lagrange's equation.
• Calculate the momenta by differentiating the Lagrangian with respect to velocity, as \(p=\frac{\partial{L}}{\partial{\dot{q}}}\)
• \(H=p\dot{q}-L\).

Kinetic energy: \[ E_k = \frac{1}{2} m \dot{x}^2 = p^2 / (2m)\] where \(p = \dot{x} m\) is the momentum.

Potential energy: \[ E_p = V(x) \]

the action functional: \[ \int (E_k - E_p) dt \] where \[ L = \frac{1}{2m} p^2 - V(x) \] define: \[ H := p\dot{x} - L = m \dot{x}^2 - L = \frac{1}{2m} p^2 + V(x) \] We have: \[ - \dot{p} = \nabla_{x} H = \nabla_x V \] (which is the Newton's second law) and \[ \dot{x} = \nabla_{p} H = p/m \]