Local variations, method of

A direct method for numerically solving problems of optimal control with constraints on the phase coordinates and control functions, based on variation in the state space (see [1]–[3]).

In the method of local variations the original problem of optimal control, given as a Lagrange problem, is made discrete with respect to the argument $ t $ and the phase vector $ x $. The original problem is thus replaced by the problem of minimizing the additive functional

$$ \tag{1 } I = \sum _ { k=0 } ^ { N-1 } F ^ { 0 } ( x _ {k} , x _ {k+1} , u _ {k} , t _ {k} , t _ {k+1} ) $$

under the constraints

$$ \tag{2 } x _ {k+1} - x _ {k} = \tau F ( x _ {k} , x _ {k+1} , u _ {k} , t _ {k} , t _ {k+1} ) , $$

$$ k = 0 \dots N- 1 , $$

$$ \tag{3 } ( x _ {k} , u _ {k} ) \in G _ {k} ,\ k = 0 \dots N , $$

where $ x _ {k} $ and $ u _ {k} $ are the vectors of the phase coordinates and controls at the node $ t _ {k} $( having dimensions $ n $ and $ m $, respectively), $ G _ {k} $ are given domains in the $ ( n+ m ) $-dimensional space ( $ G _ {0} $ and $ G _ {N} $ describe the boundary conditions), and $ \tau = ( T - t _ {0} ) / N $ is the step of the partition of the original interval $ [ t _ {0} , T ] $ for the independent variable. An essential condition for the method of local variations is that the dimensions $ n $ and $ m $ of $ x $ and $ u $ are equal, in which case the construction of an elementary operation turns out to be quite simple. An elementary operation is the determination of a control $ u _ {k} $ that takes the system from the point $ ( t _ {k} , x _ {k} ) $ to a neighbouring point $ ( t _ {k+1} , x _ {k+1} ) $. If the dimensions of $ x $ and $ u $ are equal, and under certain additional constraints, the control $ u _ {k} $ is defined on every interval $ ( t _ {k} , t _ {k+1} ) $ by the solution of the system of $ N $ equations (2), obtained as a result of a finite-difference approximation of the system of differential equations of the original variational problem.

Suppose that for the initial approximation there is specified a polygonal curve $ \Gamma _ {0} $: $ ( x _ {0} ^ {0} \dots x _ {N} ^ {0} ) $ for which (2) and (3) are satisfied. The algorithm of the method of local variations consists in successively improving the position of the nodes through which $ \Gamma _ {0} $ passes, realized as a result of successive local variation of each $ j $- th component of the vector $ x _ {k} $. On each part from $ t _ {k} $ to $ t _ {k+2} $, $ k = 0 , 1 \dots $ for fixed $ x _ {k} $ and $ x _ {k+2} $ each $ j $-th component of $ x _ {k} $ in turn is varied with step $ h _ {j} > 0 $. If as a result of this variation the value of the functional (1) decreases (with (2) and (3) satisfied), then a similar variation is carried out with the next $ ( j+ 1 ) $- st component of $ x _ {k} $, otherwise the $ j $-th component is varied with step $ ( - h _ {j} ) $. This local variation is carried out successively for all the nodes of $ \Gamma _ {0} $. As a result, at the instant of ending the iteration one obtains a new polygonal curve $ \Gamma _ {1} $ on which the functional (1) takes a value not greater than on the initial approximation $ \Gamma _ {0} $. Successive iterations are carried out similarly. If necessary one decreases the steps $ h _ {j} $ and $ \tau $. The approximate solution of the original variational problem is determined by interpolation with respect to the values of the control found at each step.

For $ m = n = 1 $ the solution obtained by the method of local variations for given values of $ \tau $ and $ h $ satisfies the finite-difference approximation of the Euler equation up to terms of order $ \max ( h , h / \tau , h / \tau ^ {2} ) $( see [3]).

If the variation of the original polygonal curve $ \Gamma _ {0} $ is not restricted to successive variation of its nodes, and is carried out on a more complete graph corresponding to the chosen steps $ \tau $ and $ h _ {j} $ and including $ \Gamma _ {0} $, one talks of the travelling-tube method.

For $ m < n $, performing an elementary operation presents certain difficulties. In this case instead of the method of local variations one can use the travelling-wave method, which is close to it.

The method of local variations can be directly generalized to variational problems with non-additive functionals, in which the constraints have the character of isoperimetric conditions (see [3]). The method of local variations can be extended to variational problems in which the unknown functions depend on several independent variables and the corresponding functionals are given in the form of integrals over domains of different dimensions (see [2]).

References

[1]	N.N. Moiseev, "Computational methods in the theory of optimal systems" , Moscow (1971) (In Russian)
[2]	I.A. Krylov, F.L. Chernous'ko, "Solution of problems of optimal control by the method of local variations" USSR Comp. Math. Math. Phys. , 6 : 2 (1966) pp. 12–31 Zh. Vychisl. Mat. i Mat. Fiz. , 6 (1966) pp. 203–217
[3]	N.V. Banichuk, V.M. Petrov, F.L. Chernous'ko, "The method of local variations for variational problems involving non-additive functionals" USSR Comp. Math. Math. Phys. , 9 : 3 (1969) pp. 66–76 Zh. Vychisl. Mat. i Mat. Fiz. , 9 (1969) pp. 548–557