20220313


 
[begin transmission]

"She knows what a shitty person I am and she still smiles at me."

[end transmission]

20220306



 [begin transmission 6/? ]

Right. What has been covered so far?
Optimal control problem (OCP) statements, check. Cost functions, check. Coupled first-order ODE dynamics, check.
There are other parts of an OCP to cover (initial conditions, endpoints, constraints) but those are easy to explain.
Let's get back more into the theory of optimal control. Now that we have our OCP, what the heck do we do w/ it?

This will be the last theory-heavy post, I promise! I'm planning on providing a concrete example in the next one.


From Russia with Love: Pontryagin's Principle

Recall that we have our OCP stated in its canonical form, given as follows:

\begin{equation} \textit{State:} \quad \textbf{x}:= [x_1, x_2, ... x_n] \quad \textbf{x} \in \mathbb{R}^n \tag{1}\end{equation}
\begin{equation} \textit{Control:} \quad \textbf{u}:= [u_1, u_2, ... u_m] \quad \textbf{u} \in \mathbb{R}^m \tag{2}\end{equation}
\begin{equation} \textit{Minimize:} \quad J[x(\cdot), u(\cdot), t_f] = E[x(t_f), t_f] + \int_{t_0}^{t_f} F[x(t), u(t), t] dt \tag{3}\end{equation}
\begin{equation} \textit{Subject to:} \quad \dot x = f(x(t), u(t), t) \tag{4}\end{equation}
\begin{equation} \  \qquad x(t_0) = x^0 \tag{5}\end{equation}
\begin{equation} \quad t_0 = t^0 \tag{6}\end{equation}
\begin{equation} \quad \qquad e(x_f, t_f) = 0 \tag{7}\end{equation}
\begin{equation} \quad \qquad \qquad \qquad \qquad \qquad h(x(t), u(t), t) = h(x(t), u(t), t) \tag{8}\end{equation}

Remember what this gibberish reads in plain English? Given a set of state and control variables that evolve according to a specified set of dynamics, find the control variable trajectories that minimize/maximize the objective function such that all of the declared conditions are met and none of the constraints are violated. Where do we go from here? We apply Pontryagin's Principle in order to determine the necessary conditions that a set of control variable trajectories must fulfill in order to achieve optimality. Pontryagin's Principle does NOT solve the OCP for us!

"Er, alright...what are those conditions? And conditions in reference to what, exactly?"
Great questions to ask, really. I ask you to suspend all doubts and follow me as I pull mathematical abstractions out of thin air. It'll make sense in the end, I hope. Like, seriously, if you can keep up w/ all of this, please let me know so that I can put you to work. There's great potential within you.

The process of applying Pontryagin's Principle is best remembered by the mnemonic HAMVET. Often times it is not the mnemonic itself that makes it memorable, but the stupid story that accompanies it. I will never forget how amused and self-pleased my professor was when he told the class that if we ever forget Pontryagin's Principle, to recall the tragic Prince of Denmark, Hamlet. As if engineers know how or even have the time to read classic literature...Anyway, the mnemonic:

-Form the Hamiltonian.
-Derive the Adjoint Equations.
-Maximize the Hamiltonian.
-Determine the Hamiltonian Value Condition.
-Determine the Hamiltonian Evolution Equation.
-Determine the Transversality Condition.

Just as if we were engineering a cake, I'll walk you through each step of this recipe.


Form the Hamiltonian

What is the Hamiltonian? For those of you w/ expertise in Newtonian physics, it might sound familiar and even look familiar, but it's just a tiny bit different. In short, the Hamiltonian is a mathematical construct used to relate the dynamics to the cost function. In order to do so, we need to introduce the concept of costates. You can think of costates as the evil twin of our states (as in the states of our system, such as x-position, y-position, x-velocity, y-velocity, temperature, voltage, etc.). The states of our system occupy a space (space in a mathematical, geometrical/topological sense) that is said to be the primal space, whereas the costates occupy the dual space. These costates are absolutely essential in forming the Hamiltonian. Thankfully, they're easy to formulate. Suppose we have the following state vector:

\begin{equation} \textbf{x}= [x, y, z, v_x, v_y, v_z] \tag{9}\end{equation}

Then our costates are simply:

\begin{equation} \mathbf{\lambda}= [\lambda_x, \lambda_y, \lambda_z, \lambda_{vx}, \lambda_{vy}, \lambda_{vz}] \tag{10}\end{equation}

Lambda is the conventional Greek letter of choice to denote costates; the subscript is my personal preference, as some like to simply number them. Anyway, the important thing to note here is that, for every state you have, you need a corresponding costate. Easy. Now that we have the costate vector down, please accept the following definition for the Hamiltonian:

\begin{equation} H(\mathbf{\lambda}, \mathbf{x}, \mathbf{u}, t) = F(\mathbf{x}, \mathbf{u}, t) + \mathbf{\lambda}^T f(\mathbf{x}, \mathbf{u}, t) \tag{11} \end{equation}

The Hamiltonian is a function of the costate vector, the state vector, the control vector, and time. In order to construct it, you just take the running cost (the F part of Equation 3) and add it to the product of the costate vector and your dynamical equations (Equation 4). The little 'T' next to the costate vector is a transpose; it's a vector operation that just means to flip its dimensions. It's only there so that the multiplication of the costate vector and the dynamical equations can be done. For those of you that are particularly math savvy out there, you'll recognize this as a Lagrangian expression--except that the multipliers are not constants, but rather functions of time. If you don't recognize this, don't worry; I'm just trying to make it clear that this is all simply an extension of calculus of variations.

Okay! Great. Now we have constructed our Hamiltonian on which everything else is contingent on. Let us continue.


Derive the Adjoint Equations

The adjoint equations simply describe how each of the costates behave over time. Nearing a truism at this point, these are represented as differential equations. They are obtained by taking the partial derivative of the negative of the Hamiltonian w/ respect to each state variable:

\begin{equation} \dot{\mathbf{\lambda}} = \frac{- \partial{H}}{\partial{\mathbf{x}}} \tag{12} \end{equation}


Maximize the Hamiltonian

Generally speaking, a necessary condition to find an extremal (maximum or minimum point) of a function is to check its derivative and see if it is equal to zero. The Hamiltonian is no different; though, instead of taking its time derivative, we look at its partial derivative w/ respect to our control input. Why? Remember, as bolded and underlined above, the entire point of an OCP is to find the control variable trajectories that minimize/maximize the cost function! Minimizing/maximizing the Hamiltonian is the way that we minimize/maximize the cost function by proxy. Here is the condition, mathematically formalized:

\begin{equation} \frac{\partial{H}}{\partial{\mathbf{u}}} = 0 \tag{13} \end{equation}


Determine the Hamiltonian Value Condition

Alright, at this point I must address endpoint constraints. In Post #20211121, I believe I referred to them as endpoint conditions; these terms are used interchangeably, apologies for the confusion. In any case, the gist of any endpoint constraint/condition is to tell you the final value a state of your system must achieve at the final time tf. So, let us suppose we have a state variable for y-velocity, denoted as vy. Suppose we want our y-velocity to be 200 at the final time. Seems like all we have to do is write out an equation that's something like vyf = 200. Close, but in the canonical form of the OCP, things must be formatted a bit strangely:

\begin{equation} v_{yf} - 200 = 0 \tag{14} \end{equation}

Simple algebraic manipulation reveals that this is an equivalent mathematical expression. This is not w/o purpose; it is required that they are presented in this strange form, so that we can use them in constructing yet another Lagrangian expression: the endpoint Lagrangian:

\begin{equation} \bar{E}(\mathbf{\nu}, \mathbf{x_f}, t_f) = E(\mathbf{x_f}, t_f) + \mathbf{\nu}^T e(\mathbf{x_f}, t_f) \tag{15} \end{equation}

Looks very similar to the Hamiltonian, doesn't it? Only, instead of the running cost, dynamical equations, and costates, we use our endpoint cost (it's E, remember?), endpoint constraints given by the problem, and some dummy variable (here designated as nu). Don't panic about the dummy variable; it's not important. It is only used as a place-holder to tell us that we're agnostic about the endpoint of a particular state variable. Anyway, the endpoint Lagrangian is used to formulate some other optimality conditions that are part of Pontryagin's Principle. One of those being the Hamiltonian Value Condition.

The Hamiltonian Value Condition does nothing more than denote the final value that the Hamiltonian will achieve if subjected to a candidate optimal control solution (in other words, it is another endpoint constraint, only applied to the Hamiltonian rather than a state variable). Its mathematical definition is as follows:

\begin{equation} H[@t_f] = \frac{-\partial{\bar{E}}}{\partial{t_f}} \tag{16} \end{equation}


Determine the Hamiltonian Evolution Condition

Okay...this particular condition may seem a bit tautological, but hear me out. The Hamiltonian Evolution Condition is defined as:

\begin{equation} \frac{d\cal{H}}{dt} = \frac{\partial{H}}{\partial{t}} \tag{17} \end{equation}

The H you see here is our friend the Hamiltonian, the one that we formed. It's important to note that H is linear; according to the definition in Equation X, it is simply the dot product of our dynamical equations and our costate vector. The fancy, curly H is the minimized/maximized (optimized) Hamiltonian; it is the Hamiltonian achieved if one were to take the found, optimal control solution and plug it into H. If one were to do that, they'd quickly come to see that our Hamiltonian becomes non-linear. All that this condition is saying is that the Hamiltonian that we constructed should evolve across time (behave) just like the optimized Hamiltonian.


Determine the Transversality Conditions

Remember the endpoint Lagrangian we defined in Determining the Hamiltonian Value Condition? We invoke it once again in order to derive the Transversality Conditions. What these conditions reveal to us is the final value our costates must assume if our system is subjected to an optimal control. The conditions are defined as follows:

\begin{equation} \mathbf{\lambda}(t_f) = \frac{\partial{\bar{E}}}{\partial{\mathbf{x_f}}} \tag{18} \end{equation}

Once again, since we invoke the Endpoint Lagrangian (barred E from Equation 15), we involve that dummy variable nu. Do not fret over the inclusion of our dummy variable. They are simply a place holder to denote that we are agnostic about a particular endpoint condition--in this instance, an endpoint of one or more of our costates.

...now, are Karush-Kuhn-Tucker conditions worth addressing here? These are certainly part of Pontryagin's Principle, but they might be a bit too nitty-gritty for our current elaboration. I think we can safely gloss over them.


To Be Continued...

Now that we have successfully applied Pontryagin's Principle to obtain the necessary conditions for optimality, what do we do now? What are we left w/? Paradoxically, the application of Pontryagin's Principle takes our original 'simple' OCP and transforms it into what's known as a DAE BVP. That is, a Differential-Algebraic Equation Boundary Value Problem. These types of problems are notorious for turning what should be ostensibly straight forward problems and making them mathematically complicated.

"...what the f*ck? What was the whole point of this exercise then?". I know dear reader, I know. I share in your frustration. It's all testament to just how dizzyingly complex the natural world is. Often times phenomena that appear straight forward on the first take are, in reality, intricate little dances when you get down to the details of the matter. Fortunately, we're not left high and dry on our mission; there are several well-known methods within the realms of mathematical optimization that allow us to solve DAN BVPs--the most commonly used are what's known as shooting methods and collocation methods. These methods are not something you can enlist w/ mere pen-and-paper. These are methods that demand some serious, heavy-duty number crunching and thus can only be implemented in silico. Now, if you fully understand the mathematics behind these methods, there's absolutely nothing to stop you from coding up your own algorithms to solve these problems; however, it isn't quite necessary to do that. Tons of scientific computing languages and accompanying software packages have powerful optimizers--some of my favorites are NLopt, Acados, and GPOPS, w/ the latter two being specialized to handle OCPs. Each have their strengths and weaknesses when it comes to solving optimization problems, as they each enlist different mathematics to solve them.

Will we go into depth when it comes to these mathematics. God no. There is simply too much to cover there and we risk straying way too far off-topic. Plus, I will freely admit that when it comes to the mathematics behind these solvers, I'm approaching the limit of my knowledge--it's such a expansive, sprawling field and I am currently wandering deeply into myself (if anyone wants to talk about pseudospectral optimal control techniques w/ me, please message me!).

[end transmission 6/? ]