Editing Optimal control (section)

==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 ({{abbr|c.|circa}} 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 (control theory)|Hamiltonian]].  Thus, the resulting [[dynamical system]] is a [[Hamiltonian system]] of the form<ref name=":0" />
<math display="block">\begin{align}
\dot{\textbf{x}} & = \frac{\partial H}{\partial\boldsymbol{\lambda}} \\[1.2ex]
\dot{\boldsymbol{\lambda}} & = -\frac{\partial H}{\partial\textbf{x}}
\end{align}</math>
where
<math display="block">H= F +\boldsymbol{\lambda}^{\mathsf{T}}\textbf{f}- \boldsymbol{\mu}^{\mathsf{T}}\textbf{h}</math>
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., <math>\boldsymbol{\lambda}</math>) 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.<ref>Oberle, H. J. and Grimm, W., "BNDSCO-A Program for the Numerical Solution of Optimal Control Problems," Institute for Flight Systems Dynamics, DLR, Oberpfaffenhofen, 1989</ref>

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
<math display="block"> F(\mathbf{z})</math>
subject to the algebraic constraints
<math display="block"> \begin{align}
\mathbf{g}(\mathbf{z}) & = \mathbf{0} \\
\mathbf{h}(\mathbf{z}) & \leq \mathbf{0}
\end{align} </math>

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]]<ref name="ReviewPOC">{{cite journal |author-link=I. Michael Ross |first1=I. M. |last1=Ross |first2=M. |last2=Karpenko |title=A Review of Pseudospectral Optimal Control: From Theory to Flight |journal=Annual Reviews in Control |volume=36 |issue=2 |pages=182–197 |year=2012 |doi=10.1016/j.arcontrol.2012.09.002 |title-link=Pseudospectral optimal control }}</ref>) or may be quite large (e.g., a direct [[collocation method]]<ref>{{cite book |last=Betts |first=J. T. |title=Practical Methods for Optimal Control Using Nonlinear Programming |publisher=SIAM Press |location=Philadelphia, Pennsylvania |edition=2nd |year=2010 |isbn=978-0-89871-688-7 }}</ref>). 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]]<ref>Gill, P. E., Murray, W. M., and Saunders, M. A., ''User's Manual for SNOPT Version 7: Software for Large-Scale Nonlinear Programming'', University of California, San Diego Report, 24 April 2007</ref>) 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'',<ref>von Stryk, O., ''User's Guide for DIRCOL (version 2.1): A Direct Collocation Method for the Numerical Solution of Optimal Control Problems'', Fachgebiet Simulation und Systemoptimierung (SIM), Technische Universität Darmstadt (2000, Version of November 1999).</ref> SOCS,<ref>Betts, J.T. and Huffman, W. P., ''Sparse Optimal Control Software, SOCS'', Boeing Information and Support Services, Seattle, Washington, July 1997</ref> OTIS,<ref>{{cite journal |last1=Hargraves |first1=C. R. |last2=Paris |first2=S. W. |title=Direct Trajectory Optimization Using Nonlinear Programming and Collocation |journal=Journal of Guidance, Control, and Dynamics |volume=10 |issue=4 |year=1987 |pages=338–342 |doi=10.2514/3.20223 |bibcode=1987JGCD...10..338H }}</ref> GESOP/[[ASTOS]],<ref>Gath, P.F., Well, K.H., "Trajectory Optimization Using a Combination of Direct Multiple Shooting and Collocation", AIAA 2001–4047, AIAA Guidance, Navigation, and Control Conference, Montréal, Québec, Canada, 6–9 August 2001</ref> DITAN.<ref>Vasile M., Bernelli-Zazzera F., Fornasari N., Masarati P., "Design of Interplanetary and Lunar Missions Combining Low-Thrust and Gravity Assists", Final Report of the ESA/ESOC Study Contract No. 14126/00/D/CS, September 2002</ref> and PyGMO/PyKEP.<ref>Izzo, Dario. "PyGMO and PyKEP: open source tools for massively parallel optimization in astrodynamics (the case of interplanetary trajectory optimization)." Proceed. Fifth International Conf. Astrodynam. Tools and Techniques, ICATT. 2012.</ref> 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'',<ref>[http://www.schwartz-home.com/RIOTS/ RIOTS] {{Webarchive| url=https://web.archive.org/web/20110716014630/http://www.schwartz-home.com/RIOTS/ |date=16 July 2011 }}, based on {{cite thesis |type=Ph.D. |last=Schwartz |first=Adam |date=1996 |title=Theory and Implementation of Methods based on Runge–Kutta Integration for Solving Optimal Control Problems |publisher=University of California at Berkeley |oclc=35140322 }}</ref> ''[[DIDO (optimal control)|DIDO]]'',<ref>Ross, I. M., ''Enhancements to the DIDO Optimal Control Toolbox, arXiv 2020.'' https://arxiv.org/abs/2004.13112</ref> ''DIRECT'',<ref>Williams, P., ''User's Guide to DIRECT, Version 2.00,'' Melbourne, Australia, 2008</ref> FALCON.m,<ref>[http://www.falcon-m.com/ FALCON.m], described in Rieck, M., Bittner, M., Grüter, B., Diepolder, J., and Piprek, P., ''FALCON.m - User Guide'', Institute of Flight System Dynamics, Technical University of Munich, October 2019</ref> and ''GPOPS,''<ref>[http://gpops.sourceforge.net GPOPS] {{Webarchive|url=https://web.archive.org/web/20110724074641/http://gpops.sourceforge.net/ |date=24 July 2011 }}, described in Rao, A. V., Benson, D. A., Huntington, G. T., Francolin, C., Darby, C. L., and Patterson, M. A., ''User's Manual for GPOPS: A MATLAB Package for Dynamic Optimization Using the [[Gauss pseudospectral method|Gauss Pseudospectral Method]]'', University of Florida Report, August 2008.</ref> while an example of an industry developed MATLAB tool is ''[[PROPT]]''.<ref>Rutquist, P. and Edvall, M. M, ''PROPT – MATLAB Optimal Control Software," 1260 S.E. Bishop Blvd Ste E, Pullman, WA 99163, USA: Tomlab Optimization, Inc.</ref> These software tools have increased significantly the opportunity for people to explore complex optimal control problems both for academic research and industrial problems.<ref>I.M. Ross, [https://nps.edu/documents/103424443/116151573/Ross.pdf/2c85d1a1-ff5b-4f60-9700-2ee5e1f3f65f?t=1580766209000 Computational Optimal Control], 3rd Workshop in Computational Issues in Nonlinear Control, October 8th, 2019, Monterey, CA</ref> 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]].