View source for Extremal problems, numerical methods

Methods of computational mathematics that are applied to find the extrema (maxima or minima) of functions and functionals.

The numerical solution of extremal problems considered in infinite-dimensional function spaces (for example, problems of optimal control by means of processes described by ordinary or partial differential equations) can be obtained by using appropriate generalizations of many methods of mathematical programming developed for problems of minimization or maximization of functions of finitely many variables. In this context it is very important to make the correct choice of a suitable function space in which a concrete problem should be considered. Such a space is usually chosen by taking into account physical considerations, properties of admissible controls, properties of the solutions of the corresponding initial-boundary value problems for a fixed control, etc.

For example, the problem of optimal control consisting of the minimization of the functional

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e0372001.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

under the conditions

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e0372002.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e0372003.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>

is usually considered in the function space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e0372004.png" />. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e0372005.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e0372006.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e0372007.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e0372008.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e0372009.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720010.png" /> are given functions, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720012.png" /> known moments in time, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720014.png" /> is a given initial point, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720015.png" /> is a given set in the Euclidean space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720016.png" /> for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720017.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720018.png" /> is the Hilbert space of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720019.png" />-dimensional vector functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720021.png" />, where each function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720022.png" /> is, together with its square, Lebesgue integrable over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720023.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720024.png" />; the inner product of two functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720026.png" /> in this space is defined by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720027.png" /></td> </tr></table>

and the norm by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720028.png" /></td> </tr></table>

For a specific degree of smoothness of the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720030.png" /> the increment of the functional (1) can be represented in the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720031.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720032.png" /></td> </tr></table>

where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720033.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720034.png" /></td> </tr></table>

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720035.png" /> is the solution of the problem (2) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720036.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720037.png" /> is the solution of the adjoint problem

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720038.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720039.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>

Formula (4) implies that the functional (1) is differentiable in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720040.png" /> and that its gradient is the vector function

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720041.png" /></td> <td valign="top" style="width:5%;text-align:right;">(8)</td></tr></table>

Hence, (1)–(3) can be solved by applying various methods that use the gradient of the functional. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720042.png" /> one may apply the gradient method

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720043.png" /></td> </tr></table>

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720044.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720045.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720046.png" /> are given functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720047.png" />, then it is possible to apply the method of gradient projection:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720048.png" /></td> </tr></table>

where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720049.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720050.png" /></td> </tr></table>

The parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720051.png" /> can be chosen from the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720052.png" />. The methods of the conditional gradient, dual gradients, etc. (see [[#References|[4]]]–[[#References|[6]]] and [[#References|[11]]]) can be adapted for the problem (1)–(3) analogously. If this problem is considered under the additional restrictions

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720053.png" /></td> <td valign="top" style="width:5%;text-align:right;">(9)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720054.png" /> is a given set in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720055.png" />, then these restrictions can be taken into account by using the method of penalty functions (cf. [[Penalty functions, method of|Penalty functions, method of]]). For example, if

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720056.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720057.png" /></td> </tr></table>

then as a penalty function one may take

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720058.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720059.png" /></td> </tr></table>

and (1)–(3), (9) is replaced by the problem of minimizing the functional <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720060.png" /> under the conditions (2) and (3), where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720061.png" /> is the penalty coefficient and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720062.png" />.

Other methods for solving (1)–(3), (9) are based on Pontryagin's maximum principle and on dynamic programming (see [[Pontryagin maximum principle|Pontryagin maximum principle]]; [[Dynamic programming|Dynamic programming]] and [[Variational calculus, numerical methods of|Variational calculus, numerical methods of]]).

The problem of minimizing a quadratic functional subject to a system of linear ordinary differential equations or linear partial differential equations can be solved by applying the method of moments (see [[#References|[3]]] and [[#References|[8]]]). This method is described below when applied to the problem of minimizing the functional

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720063.png" /></td> <td valign="top" style="width:5%;text-align:right;">(10)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720064.png" /> is the solution of the problem

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720065.png" /></td> <td valign="top" style="width:5%;text-align:right;">(11)</td></tr></table>

and the controls <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720066.png" /> are such that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720067.png" /></td> <td valign="top" style="width:5%;text-align:right;">(12)</td></tr></table>

here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720068.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720069.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720070.png" /> are given matrices of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720071.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720072.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720073.png" />, respectively, with piecewise-continuous entries on the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720074.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720075.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720076.png" /> are given points, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720077.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720078.png" /> is the inner product in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720079.png" />. From the rule of [[Lagrange multipliers|Lagrange multipliers]] it follows that the control <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720080.png" /> is optimal in the problem (10)–(12) if and only if there is a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720081.png" /> (the Lagrange multiplier for the constraint (12)) such that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720082.png" /></td> <td valign="top" style="width:5%;text-align:right;">(13)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720083.png" /></td> <td valign="top" style="width:5%;text-align:right;">(14)</td></tr></table>

here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720084.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720085.png" />. Formulas (5)–(8) imply that the gradient <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720086.png" /> of the functional (10) in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720087.png" /> has the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720088.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720089.png" /> is the solution of the problem

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720090.png" /></td> <td valign="top" style="width:5%;text-align:right;">(15)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720091.png" /></td> <td valign="top" style="width:5%;text-align:right;">(16)</td></tr></table>

here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720092.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720093.png" /> are the transposed matrices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720094.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720095.png" />, respectively. Then condition (13) becomes

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720096.png" /></td> <td valign="top" style="width:5%;text-align:right;">(17)</td></tr></table>

Condition (16) is equivalent to

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720097.png" /></td> <td valign="top" style="width:5%;text-align:right;">(18)</td></tr></table>

for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720098.png" />, where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e03720099.png" /></td> </tr></table>

and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200100.png" /> is the solution of the system (15) satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200101.png" /> (a unit vector). Hence, the optimal control <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200102.png" /> in the problem (10)–(12) is determined by solving the system (14), (15), (17), (18) relative to the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200103.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200104.png" /> and the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200105.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200106.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200107.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200108.png" /> and (18) reduces to the problem of moments (see [[Moment problem|Moment problem]]): To find a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200109.png" />, knowing

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200110.png" /></td> </tr></table>

with respect to the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200111.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200112.png" />.

System (14), (15), (17), (18) is a generalized moment problem for (10)–(12) with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200113.png" /> (see [[#References|[3]]] and [[#References|[8]]]).

Any solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200114.png" /> of (15) is uniquely representable in the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200115.png" /></td> <td valign="top" style="width:5%;text-align:right;">(19)</td></tr></table>

System (15), (17), (18) has a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200116.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200117.png" /> for any fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200118.png" />, and among all its solutions there is a unique one such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200119.png" /> has the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200120.png" /></td> <td valign="top" style="width:5%;text-align:right;">(20)</td></tr></table>

To find <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200121.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200122.png" /> one substitutes (19) and (20) in (17) and (18) and obtains a system of linear algebraic equations with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200123.png" />, from which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200124.png" /> are determined uniquely and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200125.png" /> non-uniquely if the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200126.png" /> is linearly dependent. In the practical solution of the problem (10)–(12) it is advisable to set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200127.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200128.png" /> from the beginning and to use (18) to determine <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200129.png" /> of the form (20). Next, it must be checked that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200130.png" />. If this inequality holds, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200131.png" /> is the optimal control of (10)–(12) with minimal norm among all optimal controls; the set of all optimal controls in this case consists of controls of the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200132.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200133.png" /> belongs to the orthogonal complement in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200134.png" /> of the linear span of the system of functions

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200135.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200136.png" /></td> </tr></table>

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200137.png" />, then for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200138.png" /> the solutions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200139.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200140.png" /> of the form (19) and (20), respectively, are found from (17) and (18), and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200141.png" /> is found from the equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200142.png" /></td> <td valign="top" style="width:5%;text-align:right;">(21)</td></tr></table>

The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200143.png" /> of the variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200144.png" /> is continuous and strictly decreasing for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200145.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200146.png" />; therefore, the desired <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200147.png" /> is determined uniquely from (21). The control <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200148.png" /> is optimal for the problem (10)–(12); for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200149.png" /> this problem has no other optimal controls.

The method of moments is also applicable for the solution of the high-speed problem for the system (11) and other linear systems (see [[#References|[3]]] and [[#References|[8]]]).

The above methods are also widely used for the numerical solution of problems of optimal control by means of processes described by partial differential equations.

The numerical realizations of many methods for solving problems of optimal control are based on the use of some technique for the approximate solution of the intervening initial-boundary value problems (see [[Boundary value problem, numerical methods for partial differential equations|Boundary value problem, numerical methods for partial differential equations]]) and of approximate computations of integrals (see [[Integration, numerical|Integration, numerical]]). As a result, the original problem of optimal control is replaced by a family of approximate problems depending on some parameters (for example, on the steps of the difference grid). About questions regarding the construction of approximate problems and the investigation of their convergence, see [[#References|[5]]].

Large classes of extremal problems are ill posed (see [[Ill-posed problems|Ill-posed problems]]) and their solution requires the use of a [[Regularization method|regularization method]] (see [[#References|[5]]] and [[#References|[3]]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.M. Alekseev,   V.M. Tikhomirov,   S.V. Fomin,   "Optimal control" , Consultants Bureau  (1987)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  I.V. Beiko,   B.N. Bublik,   P.N. Zin'ko,   "Methods and algorithms for the solution of optimization problems" , Kiev  (1983)  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.G. Butkovskii,   "Methods of control by means of systems with distributed parameters" , Moscow  (1975)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  F.P. Vasil'ev,   "Numerical method for solving extremal problems" , Moscow  (1980)  (In Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  F.P. Vasil'ev,   "Methods for solving extremal problems" , Moscow  (1981)  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  Yu.G. Evtushenko,   "Numerical optimization techniques" , Optim. Software  (1985)  (Translated from Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  A.I. Egorov,   "Optimal control by means of thermal and diffusion processes" , Moscow  (1978)  (In Russian)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  N.N. Krasovskii,   "Theory of control by motion" , Moscow  (1968)  (In Russian)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  J.-L. Lions,   "Optimal control of systems governed by partial differential equations" , Springer  (1971)  (Translated from French)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  B.T. Polyak,   "Introduction to optimization" , Moscow  (1983)  (In Russian)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  J. Céa,   "Lectures on optimization: theory and algorithms" , Springer  (1978)</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  T.K. Sirazetdinov,   "Optimization of systems with distributed parameters"  (1977)  (In Russian)</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  A.N. Tikhonov,   V.I. [V.I. Arsenin] Arsenine,   "Solutions of ill-posed problems" , Winston  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  R.P. Fedorenko,   "Approximate solution of problems of optimal control" , Moscow  (1978)  (In Russian)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  I. Ekeland,   R. Téman,   "Analyse convexe et problèmes variationnels" , Dunod  (1974)</TD></TR></table>



====Comments====
Constraints of the kind <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200150.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e037/e037200/e037200151.png" /> are usually referred to as state constraints. Among the methods available for the numerical solution of [[Optimal control|optimal control]] problems, a distinction can be made between direct and indirect methods. With direct methods the optimal control problem is treated directly as a minimization problem, i.e. the method is started with an initial approximation of the solution, which is iteratively improved by minimizing the objective functional (cf. [[Objective function|Objective function]]) (augmented with a  "penalty"  term) along the direction of search. The direction of search is obtained via linearization of the problem. With indirect methods the optimality conditions, which must hold for a solution of the optimal control problem, are used to derive a multi-point boundary value problem. Solutions of the optimal control problem will also be solutions of this multi-point boundary value problem and hence the numerical solution of the multi-point boundary value problem yields a candidate for the solution of the optimal control problem.

Most direct methods are of the gradient type, i.e. they are function space analogues of the well-known [[Gradient method|gradient method]] for finite-dimensional non-linear programming problems [[#References|[a1]]]. These methods can be extended to Newton-like methods [[#References|[a1]]], [[#References|[a2]]] (cf. [[Newton method|Newton method]]). As indicated in the main article above, state constraints can be treated via a penalty-function approach. Numerical results, however, indicate that this approach yields an inefficient and inaccurate method for the solution of state-constrained optimal control problems [[#References|[a3]]]. Another way to treat state constraints is via a slack-variable transformation technique, using quadratic slack variables [[#References|[a4]]].

A well-known indirect method is the one based on the numerical solution of the multi-point boundary value problem using multiple shooting [[#References|[a3]]], [[#References|[a5]]] (cf. [[Shooting method|Shooting method]]). For optimal control problems with state constraints, the right-hand side of the differential equation of the multi-point boundary value problem will, in general, be discontinuous at junction points, i.e. points where an inequality constraint changes from active to inactive or vice versa. These discontinuities require special attention [[#References|[a1]]].

In general, the properties of direct and indirect methods are somewhat complementary. Direct methods tend to have a relatively large region of convergence and tend to be relatively inaccurate, whereas indirect methods generally have a relatively small region of convergence and tend to be relatively accurate.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A.E. Bryson,   Y.-C. Ho,   "Applied optimal control" , Hemisphere  (1975)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  E.R. Edge,   W.F. Powers,   "Function-space quasi-Newton algorithms for optimal control problems with bounded controls and singular arcs"  ''J. Optimization Theory and Appl.'' , '''20'''  (1976)  pp. 455–479</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  K.H. Well,   "Uebungen zu den optimale Steuerungen" , ''Syllabus of the course  "Optimierungsverfahren"  of the Carl Cranz Geselschaft'' , Oberpfaffenhofen, FRG  (1983)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D.H. Jacobson,   M.M. Lele,   "A transformation technique for optimal control problems with a state variable constraint"  ''IEEE Trans. Automatic Control'' , '''14''' :  5  (1969)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  H. Maurer,   "An optimal control problem with bounded state variables and control appearing linearly"  ''SIAM J. Control Optimization'' , '''15'''  (1977)  pp. 345–362</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  D.P. Bertsekas,   "Constrained optimization and Lagrange multiplier methods" , Acad. Press  (1982)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  P.L. Falb,   J.L. de Jong,   "Some successive approximation methods in control and oscillation theory" , Acad. Press  (1969)</TD></TR></table>