Numerical Methods¶
The indirect methods are based on the classic theory of calculus of variations and on the famous Pontryagin’s Maximum (Minimum) Principle (PMP). Starting from the necessary first order optimality conditions they obtain a two-point (in general a multi-point) boundary value problem.
It is derived from the first variation of the Lagrangian function associated to the optimal control problem. An equivalent derivation is possible taking derivatives of the Hamiltonian function.
The boundary conditions of this BV problem are given by the initial/final condition given by the problem itself, other are yielded from the transversal condition of the adjoint variables. Of course, by the intrinsic nature of the optimal control problems, a closed form analytical solution is seldom obtained, but the indirect methods can produce it. In presence of path constraint or inequalities it is difficult to apply the PMP to solve for an explicit formula for the control, this leads to state dependent switches. The claimed disadvantage of the indirect method is that the resulting BV problems are difficult to solve. This is not completely true, because today there are various techniques to solve systems of differential equations. It is also mandatory to analyse the computed solution, because it is only extremal but not necessary a minimum. This can be accomplished inspecting the problem (convexity, second variation, etc). The advantages are given by the underlying philosophy of first optimize, then discretize: the boundary value problem has dimension \(2\times n_x\) where \(n_x\) is the number of state variables, therefore even large scale systems are feasible.
A different approach to OCPs is given by the direct methods which follow the philosophy of first discretize, then optimize and are somehow the opposite of the indirect methods. Here the state and the control variables are approximated by polynomial interpolation, the target functional itself is approximated by a cost function. Hence the problem is discretized on a mesh, and the optimization variables become the unknowns of a general nonlinear programming problem. There are three main algorithms employed in the application of a direct method, the first is the shooting method (single and multiple) which results in small NLP problems; the second is the pseudospectral method (medium sized problem); the third is the collocation method, which is the most accurate at the price of a very large NLP. The main advantage of the direct methods is that NLPs are widely studied and a plethora of state of art solution algorithms are available. Moreover it is easier to treat inequality constraints because they have their natural equivalent form in the associated NLP problem. The principal disadvantage is that direct methods produce only suboptimal or approximate solutions. Nowadays they are very popular because they are easy to understand and apply (no calculus of variations needed), they are also robust.
The third family of numerical methods to solve an optimal control problem is given by algorithms that make use of the Hamilton-Jacobi-Bellman equation. The idea behind this algorithms is the Principle of Optimality, which states that any subarc of an optimal trajectory is also optimal. A grid \(a=\zeta_0<\ldots<\zeta_N=b\) is introduced over the time interval \([a,b]\), and by the principle of optimality, on each subinterval \([\zeta_k,\zeta_{k+1}]\) the restriction of the functional on that interval is optimized. The resulting partial differential equation is solved recursively backwards starting at the end of the time interval. Advantages of this method are that it searches the whole state space giving a global optimum, can have optimal feedback controls precomputed, admits some analytical solutions (for linear systems with quadratic cost), the so called viscosity solutions exist and are feasible for a quite general class of nonlinear problems. The main disadvantage of Dynamic Programming is that the resulting partial differential equation is in a high dimensional space and is in general non tractable. This is what Bellman called the curse of dimensionality.