Namespaces
Variants
Actions

Difference between revisions of "Local variations, method of"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fix tex)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
<!--
 +
l0602501.png
 +
$#A+1 = 60 n = 0
 +
$#C+1 = 60 : ~/encyclopedia/old_files/data/L060/L.0600250 Local variations, method of
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A [[Direct method|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 [[#References|[1]]]–[[#References|[3]]]).
 
A [[Direct method|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 [[#References|[1]]]–[[#References|[3]]]).
  
In the method of local variations the original problem of optimal control, given as a [[Lagrange problem|Lagrange problem]], is made discrete with respect to the argument <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l0602501.png" /> and the phase vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l0602502.png" />. The original problem is thus replaced by the problem of minimizing the additive functional
+
In the method of local variations the original problem of optimal control, given as a [[Lagrange problem|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
  
<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/l/l060/l060250/l0602503.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
= \sum _ { k=0 } ^ { N-1 }  F ^ { 0 } ( x _ {k} , x _ {k+1} , u _ {k} , t _ {k} , t _ {k+1} )
 +
$$
  
 
under the constraints
 
under the 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/l/l060/l060250/l0602504.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
$$ \tag{2 }
 +
x _ {k+1} - x _ {k}  = \tau F ( x _ {k} , x _ {k+1} , u _ {k} , t _ {k} , t _ {k+1} ) ,
 +
$$
  
<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/l/l060/l060250/l0602505.png" /></td> </tr></table>
+
$$
 +
= 0 \dots N- 1 ,
 +
$$
  
<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/l/l060/l060250/l0602506.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{3 }
 +
( x _ {k} , u _ {k} )  \in  G _ {k} ,\  k = 0 \dots N ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l0602507.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l0602508.png" /> are the vectors of the phase coordinates and controls at the node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l0602509.png" /> (having dimensions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025011.png" />, respectively), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025012.png" /> are given domains in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025013.png" />-dimensional space (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025015.png" /> describe the boundary conditions), and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025016.png" /> is the step of the partition of the original interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025017.png" /> for the independent variable. An essential condition for the method of local variations is that the dimensions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025019.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025021.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025022.png" /> that takes the system from the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025023.png" /> to a neighbouring point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025024.png" />. If the dimensions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025026.png" /> are equal, and under certain additional constraints, the control <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025027.png" /> is defined on every interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025028.png" /> by the solution of the system of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025029.png" /> equations (2), obtained as a result of a finite-difference approximation of the system of differential equations of the original variational problem.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025030.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025031.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025032.png" /> passes, realized as a result of successive local variation of each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025033.png" />-th component of the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025034.png" />. On each part from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025035.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025037.png" /> for fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025039.png" /> each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025040.png" />-th component of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025041.png" /> in turn is varied with step <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025042.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025043.png" />-st component of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025044.png" />, otherwise the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025045.png" />-th component is varied with step <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025046.png" />. This local variation is carried out successively for all the nodes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025047.png" />. As a result, at the instant of ending the iteration one obtains a new polygonal curve <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025048.png" /> on which the functional (1) takes a value not greater than on the initial approximation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025049.png" />. Successive iterations are carried out similarly. If necessary one decreases the steps <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025050.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025051.png" />. The approximate solution of the original variational problem is determined by interpolation with respect to the values of the control found at each step.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025052.png" /> the solution obtained by the method of local variations for given values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025053.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025054.png" /> satisfies the finite-difference approximation of the [[Euler equation|Euler equation]] up to terms of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025055.png" /> (see [[#References|[3]]]).
+
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|Euler equation]] up to terms of order $  \max ( h , h / \tau , h / \tau  ^ {2} ) $(
 +
see [[#References|[3]]]).
  
If the variation of the original polygonal curve <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025056.png" /> is not restricted to successive variation of its nodes, and is carried out on a more complete graph corresponding to the chosen steps <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025057.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025058.png" /> and including <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025059.png" />, one talks of the [[Travelling-tube method|travelling-tube method]].
+
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|travelling-tube method]].
  
For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l060/l060250/l06025060.png" />, performing an elementary operation presents certain difficulties. In this case instead of the method of local variations one can use the [[Travelling-wave method|travelling-wave method]], which is close to it.
+
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|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 [[#References|[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 [[#References|[2]]]).
 
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 [[#References|[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 [[#References|[2]]]).

Latest revision as of 17:24, 31 December 2020


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
How to Cite This Entry:
Local variations, method of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Local_variations,_method_of&oldid=12292
This article was adapted from an original article by I.B. Vapnyarskii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article