View source for Variational calculus, numerical methods of

The branch of numerical mathematics in which one deals with the determination of extremal values of functionals.

Numerical methods of variational calculus are usually subdivided into two major classes: indirect and direct methods. Indirect methods are based on the use of necessary optimality conditions (cf. [[Variational calculus|Variational calculus]]; [[Euler equation|Euler equation]]; [[Weierstrass conditions (for a variational extremum)|Weierstrass conditions (for a variational extremum)]]; [[Transversality condition|Transversality condition]]; [[Pontryagin maximum principle|Pontryagin maximum principle]]), with the aid of which the original variational problem is reduced to a boundary value problem. Thus, the computational advantages and drawbacks of indirect methods are fully determined by the properties of the respective boundary value problem. In direct methods, the extremum of the functional is found directly. The optimization methods thus employed are a development of the idea of [[Mathematical programming|mathematical programming]].

The subdivision of the numerical methods of variational calculus into direct and indirect methods is largely arbitrary. In some algorithms both approaches are utilized. Moreover, some methods cannot be classified as belonging to either class. Thus, methods based on sufficient optimality conditions form a separate group.

The first numerical methods of the calculus of variations appeared in the work of L. Euler. However, their most rapid development took place in the mid-20th century as a result of the spread of computers and the possibility, afforded by these techniques, to solve complicated problems in technology. The development of numerical methods in variational calculus mostly concerned the theory of optimal control, which, from the aspect of practical applications, is the most important (cf. [[Optimal control, mathematical theory of|Optimal control, mathematical theory of]]).

==Indirect methods.==
With the advent of the Pontryagin maximum principle (1956), variational problems can very often be reduced to boundary value problems.

Consider the following problem in optimal control: Find a trajectory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v0962101.png" /> and a control <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v0962102.png" /> for which 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/v/v096/v096210/v0962103.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

assumes its minimal value, given the differential constraints

<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/v/v096/v096210/v0962104.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

the boundary 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/v/v096/v096210/v0962105.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</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/v/v096/v096210/v0962106.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>

and control 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/v/v096/v096210/v0962107.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v0962108.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v0962109.png" /> are the vectors of the coordinates of the phase and the controls, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621011.png" /> is a closed set in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621012.png" />-dimensional space, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621013.png" /> (the time) is an independent variable.

According to Pontryagin's maximum principle, the optimal control <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621014.png" /> must, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621015.png" />, produce the absolute maximum of the [[Hamilton function|Hamilton 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/v/v096/v096210/v09621016.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/v/v096/v096210/v09621017.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621018.png" /> is defined by the system of equations

<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/v/v096/v096210/v09621019.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>

The control <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621020.png" /> is found from condition (6) and is substituted in (2) and (7). As a result one obtains a closed boundary value problem for a system of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621021.png" /> differential equations (2) and (7) with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621022.png" /> boundary conditions (3) and (4).

The scheme of numerical solution which is most frequently employed for this boundary value problem involves the use of Newton's method of fractional steps [[#References|[3]]]. One introduces the discrepancy vector

<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/v/v096/v096210/v09621023.png" /></td> <td valign="top" style="width:5%;text-align:right;">(8)</td></tr></table>

where the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621024.png" /> is obtained by solving the Cauchy problem for the system (2), (7) with initial conditions (3) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621026.png" />. The discrepancies (8) are considered as functions of the unknowns <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621027.png" />, defined by the system of equations

<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/v/v096/v096210/v09621028.png" /></td> <td valign="top" style="width:5%;text-align:right;">(9)</td></tr></table>

The system (9) is solved by Newton's method (cf. [[Newton method|Newton method]]); the partial derivatives involved,

<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/v/v096/v096210/v09621029.png" /></td> </tr></table>

are numerically determined by the formula:

<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/v/v096/v096210/v09621030.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/v/v096/v096210/v09621031.png" /></td> </tr></table>

where the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621032.png" /> are obtained by solving Cauchy's problem for the system (2), (7), with initial conditions (3) and 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/v/v096/v096210/v09621033.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621034.png" /> is a small increment of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621035.png" />.

The partial derivatives may be determined by a more accurate, but more laborious, method [[#References|[4]]], involving the integration of a system of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621036.png" /> equations in variations for the system (2), (7).

The difficulties in Newton's method consist, in the first place, in the selection of a successful initial approximation for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621037.png" /> and, secondly, in the unstability of the Cauchy problem, which is very strongly manifested on large intervals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621038.png" />. There is no generally valid procedure to overcome the first difficulty. A number of methods (cf. [[Cauchy problem, numerical methods for ordinary differential equations|Cauchy problem, numerical methods for ordinary differential equations]]) are available to deal with the unstability of the Cauchy problem.

If the boundary conditions and the functional are given in a more general form than in (3), (4) and (1) (e.g. in the [[Bolza problem|Bolza problem]] with mobile ends, in a [[Variational problem|variational problem]] with free (mobile) ends), the [[Transversality condition|transversality condition]] is added to supplement the optimality conditions (6) and (7). After elimination of the arbitrary constants which appear in these conditions, a closed boundary value problem and a corresponding system of equations of the type (9) are obtained.

The solution of the system (9) may also be obtained by any other method used in solving non-linear systems.

Specific methods for solving boundary value problems of a special type have been developed. Thus, linear boundary value problems are solved by the method of transfer of the boundary conditions ([[Shooting method|shooting method]]). This method is also employed as a constituent element for the iterative solution of non-linear boundary value problems [[#References|[1]]].

Problems in variational calculus are very often solved with the aid of electronic computers, since in this way indirect methods can be effectively and relatively simply realized. However, such techniques are not applicable in all cases; for certain important classes of problems in variational calculus — e.g. problems involving phase restrictions — it is difficult to write down the necessary conditions and these result in boundary value problems with a complicated structure. Moreover, the boundary conditions need not ensure that the solution found in fact supplies an extremum of the functional. This must be verified by introducing sufficient optimality conditions. All this restricts the scope of application of indirect methods.

==Direct methods.==
The first direct method was proposed by Euler for the solution of the simplest problem in variational calculus. It is known as Euler's method of polygonal lines (or as Euler's finite-difference method). In this method 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/v/v096/v096210/v09621039.png" /></td> <td valign="top" style="width:5%;text-align:right;">(10)</td></tr></table>

is considered on continuous polygonal lines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621040.png" /> which satisfy given boundary 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/v/v096/v096210/v09621041.png" /></td> <td valign="top" style="width:5%;text-align:right;">(11)</td></tr></table>

and which consist of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621042.png" /> rectilinear segments with end points at given abscissas. Thus, the functional becomes a function of the ordinates of the vertices of the polygonal line, while the initial problem is reduced to the task of minimizing a function of several variables (cf. [[Euler method|Euler method]]).

Since the labour involved in such calculations is considerable, direct methods were neglected for a long time in traditional studies in variational calculus. They were taken up again early in the 20th century. New methods for the reduction to the problem of finding an extremum of a function of several variables were proposed. Of these, the most important one is the [[Ritz method|Ritz method]], according to which the solution of minimizing (10) subject to condition (11) is to be found in the class of functions 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/v/v096/v096210/v09621043.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621044.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621045.png" />, are elements of a complete infinite system of linearly independent functions which satisfy the boundary 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/v/v096/v096210/v09621046.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/v/v096/v096210/v09621047.png" /></td> </tr></table>

The problem is reduced to finding a minimum of the 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/v/v096/v096210/v09621048.png" /></td> </tr></table>

of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621049.png" /> variables. Ritz's method is sufficiently general. It is applied to the solution of variational problems in mathematical physics consisting of the minimization of a functional which depends on functions of several variables. A further generalization of the method to include this class of problems is the method, [[#References|[2]]], in which the coefficients are considered to be unknown functions of one of the independent variables (e.g. if the problem involves two independent variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621050.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621052.png" /> may be given as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621053.png" />). The initial functional becomes dependent on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621054.png" /> functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621055.png" />, which may be defined in terms of the necessary conditions, i.e., in the final count, by solving the boundary value problem for a system of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621056.png" /> Euler equations.

Practical requirements enhanced the interest in non-classical problems of optimal control. The presence in technical problems of complicated restrictions on the phase coordinates and the control functions, the discontinuity of the right-hand sides of differential equations, the possible existence of singular and sliding optimal conditions, etc. — all this stimulated the development of new direct methods. The most popular methods are those involving the idea of descent in the space of controls and of successive analysis of variants (of the type of [[Dynamic programming|dynamic programming]]).

Descent methods in the space of the controls are based on finding a sequence of controls <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621057.png" /> 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/v/v096/v096210/v09621058.png" /></td> <td valign="top" style="width:5%;text-align:right;">(12)</td></tr></table>

which corresponds to a monotone decreasing sequence of values of the functional. For instance, suppose it is required to find a minimum 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/v/v096/v096210/v09621059.png" /></td> <td valign="top" style="width:5%;text-align:right;">(13)</td></tr></table>

subject to the conditions (2), (3) and (5) (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621060.png" /> is a convex and simply-connected set). The increment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621061.png" /> is found as follows. The variational equations for (2) and the conjugate system (7), subject to 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/v/v096/v096210/v09621062.png" /></td> </tr></table>

at the right-hand end, are used to represent the linear part of the increment of the functional (13) as a result of the variation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621063.png" />, 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/v/v096/v096210/v09621064.png" /></td> </tr></table>

In order to decrease the value of the functional (13), the increment

<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/v/v096/v096210/v09621065.png" /></td> </tr></table>

where the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621066.png" /> is calculated on the control <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621067.png" /> and on the corresponding trajectory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621068.png" />, must be chosen for each iteration. The regularity of the linearization, and hence also the decrease in the value of the functional (13), is ensured by choosing a sufficiently small value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621069.png" />. The descent process (12) begins from some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621070.png" /> and is terminated when, as a result of the last iteration, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621071.png" /> becomes smaller than some given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621072.png" />. In the case of a free right-hand end described above, the resulting algorithm is most simple [[#References|[5]]], [[#References|[6]]], [[#References|[7]]]. Another method which does not involve linearization of the initial problem is very effective in solving problems with a free end [[#References|[8]]]. If the right-hand end is also subject to boundary conditions, all algorithms become much more complicated. To deal with boundary conditions, a gradient projection procedure is employed in [[#References|[5]]], while in [[#References|[6]]] failure to satisfy the boundary conditions is penalized by considering 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/v/v096/v096210/v09621073.png" /></td> <td valign="top" style="width:5%;text-align:right;">(14)</td></tr></table>

rather than (13). The method in which the increment of the control is determined by solving an auxiliary linear programming problem, resembles the gradient methods [[#References|[9]]].

A large group of direct methods for the numerical solution of optimal control problems is based on the idea of optimal analysis of variants [[#References|[10]]], [[#References|[11]]], [[#References|[12]]]. An important feature of this method is that it may be used to solve problems with phase restrictions of the kind

<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/v/v096/v096210/v09621074.png" /></td> <td valign="top" style="width:5%;text-align:right;">(15)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621075.png" /> is a closed set in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621076.png" />-dimensional space. Its principal disadvantage is the fact that its use rapidly becomes more difficult as the dimension of the space increases. In these methods the initial problem is reduced to a problem of non-linear programming of a special type. Two ways of effecting such a reduction are usually employed. The first method ultimately yields the problem of minimizing a function which depends only on the controls given at the points of a discrete grid on the axes [[#References|[13]]]. In the second method controls are discarded and the task is reduced to minimizing a function of the type

<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/v/v096/v096210/v09621077.png" /></td> <td valign="top" style="width:5%;text-align:right;">(16)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621078.png" /> is the value of the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621079.png" /> at the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621080.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621081.png" />, subject to the 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/v/v096/v096210/v09621082.png" /></td> <td valign="top" style="width:5%;text-align:right;">(17)</td></tr></table>

which follow from the restrictions (3), (4) and (15). The procedure employed for the minimization of (l6) subject to (17) may be geometrically interpreted as follows.

<img style="border:1px solid;" src="https://www.encyclopediaofmath.org/legacyimages/common_img/v096210a.gif" />

Figure: v096210a

Each family of vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621083.png" /> is put into correspondence with a polygon line, as shown in the figure, passing through <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621084.png" /> and lying in the hyperplanes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621085.png" /> defined by equations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621086.png" />. The length of the polygon line <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621087.png" /> is the sum of the lengths <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621088.png" /> of its individual links. The domain of admissible <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621089.png" />-values is defined by (17), and is separated from the forbidden domain by some polygonal line (the forbidden domain is shown shaded in the figure). The problem is to find the minimum length of a polygonal line located in the admissible domain and connecting the hyperplanes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621090.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621091.png" />. The algorithm by which this problem is solved is a multi-step process, during which a certain set of variants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621092.png" /> known not to contain the optimal polygonal line is marked off at each stage <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621093.png" />. The zero-th stage consists in defining the 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/v/v096/v096210/v09621094.png" /></td> </tr></table>

i.e. the length of the shortest link connecting each point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621095.png" /> with the hyperplane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621096.png" />. Since

<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/v/v096/v096210/v09621097.png" /></td> </tr></table>

the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621098.png" /> of polygonal lines not containing the segment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v09621099.png" /> may be discarded. In the first stage one constructs the shortest polygonal line

<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/v/v096/v096210/v096210100.png" /></td> </tr></table>

connecting each point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210101.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210102.png" />, and the set of polygonal lines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210103.png" /> not containing the straight line <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210104.png" /> is also discarded, etc. In the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210105.png" />-th stage one constructs the shortest polygonal line

<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/v/v096/v096210/v096210106.png" /></td> <td valign="top" style="width:5%;text-align:right;">(18)</td></tr></table>

connecting each point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210107.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210108.png" />, and the set of polygonal lines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210109.png" /> not containing the polygonal line <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210110.png" /> is discarded. The last stage yields the solution of the initial problem — the shortest polygonal line connecting the hypersurfaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210111.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210112.png" />:

<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/v/v096/v096210/v096210113.png" /></td> </tr></table>

Formula (18) is a recurrence relation which describes the multi-step process for finding the solution. It is the base of dynamic programming and of Bellman's optimality principle.

In accordance with (18), the minimum must be found on sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210114.png" /> with, generally speaking, the cardinality of the continuum. The numerical realization involves a finite-dimensional approximation of them. To do this one constructs — in addition to the grid with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210115.png" /> (e.g. with a constant step <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210116.png" />) — also a grid with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210117.png" /> with step <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210118.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210119.png" />). The problem is then reduced to finding the shortest path in a special graph, with the grid nodes as vertices. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210120.png" /> be the node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210121.png" /> lying in the hyperplane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210122.png" />; let

<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/v/v096/v096210/v096210123.png" /></td> </tr></table>

be the length of the segment connecting two nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210124.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210125.png" /> in neighbouring hyperplanes; and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210126.png" /> be the length of the shortest path connecting the node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210127.png" /> with the hyperplane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210128.png" />. The recurrence relation (18) will then assume 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/v/v096/v096210/v096210129.png" /></td> </tr></table>

where the minimum is taken over the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210130.png" /> of all nodes located in the admissible domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210131.png" /> of the hyperplane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210132.png" />. In the general case this minimum is found by inspecting all nodes. This method makes it possible to find a global extremum of the function (16), subject to (3), (4) and (15), with an accuracy determined by the steps <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210133.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210134.png" /> of the grids. In order that the method converge to the solution of the initial problem, certain relations between these steps (e.g. of the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096210/v096210135.png" />) must hold. The method requires the use of fast computers with large memories. For this reason, the first step in practical work is to find a solution on a coarse grid, after which a finer grid is used to obtain a more exact solution in a neighbourhood of the solution thus found. This is done with the aid of one of the methods for finding a local extremum (cf. [[Travelling-tube method|Travelling-tube method]]; [[Local variations, method of|Local variations, method of]]; [[Travelling-wave method|Travelling-wave method]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  N.N. Moiseev,   "Computational methods in the theory of optimal systems" , Moscow  (1971)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L.V. Kantorovich,   V.I. Krylov,   "Approximate methods of higher analysis" , Noordhoff  (1958)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  V.K. Isaev,   V.V. Sonin,   "Numerical aspects of the problem of optimum flight as a boundary value problem"  ''USSR Comput. Math. Math. Phys.'' , '''5''' :  2  (1965)  pp. 117–129  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''5''' :  2  (1965)  pp. 252–261</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  S. Dzhurovich,   D. Makintair,   ''Raketnaya Tekhn.'' :  9  (1962)  pp. 47–53</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  V. Denkhem,   V. Braison,   ''Raketnaya Tekhn. i Kosmonavtika'' :  1  (1964)  pp. 34–47</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  L.I. Shatrovskii,   "On a numerical method of solving problems of optimum control"  ''USSR Comput. Math. Math. Phys.'' , '''2''' :  3  (1962)  pp. 511–514  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''2''' :  3  (1962)  pp. 488–491</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  T.M. Eneev,   ''Kosmicheskie Issl.'' , '''4''' :  5  (1966)  pp. 651–659</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  I.A. Krylov,   F.L. Chernous'ko,   "On a method of successive approximations for the solution of problems of optimal control"  ''USSR Comput. Math. Math. Phys.'' , '''2''' :  6  (1962)  pp. 1371–1382  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''2''' :  6  (1962)  pp. 1132–1139</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  R.P. Fedorenko,   "Approximate solution of some optimal control problems"  ''USSR Comput. Math. Math. Phys.'' , '''4''' :  6  (1964)  pp. 89–116  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''4''' :  6  (1964)  pp. 1045–1064</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  R. Bellman,   "Dynamic programming" , Princeton Univ. Press  (1957)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  V.S. Mikhalevich,   "Sequential optimization algorithms and their application. Part I"  ''Cybernetics'' , '''1''' :  1  (1965)  pp. 44–56  ''Kibernetika (Kiev)'' , '''1''' :  1  (1965)  pp. 45–56</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  N.N. Moiseev,   "Numerical methods of optimal control theory using variations in the state space"  ''Cybernetics'' , '''2''' :  3  (1966)  pp. 1–24  ''Kibernetika (Kiev)'' , '''2''' :  3  (1966)  pp. 1–29</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  Yu.M. Ermol'ev,   V.P. Gulenko,   "The finite-difference method in optimal control problems"  ''Cybernetics'' , '''3''' :  3  (1967)  pp. 1–16  ''Kibernetika (Kiev)'' , '''3''' :  3  (1967)  pp. 1–20</TD></TR></table>



====Comments====
"Phase coordinates"  are usually called  "state variablestate variables"  in the Western literature.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A.E. Bryson,   Y.-C. Ho,   "Applied optimal control" , Hemisphere  (1975)</TD></TR></table>