Namespaces
Variants
Actions

Difference between revisions of "Travelling-tube method"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
A direct method for the numerical solution of problems of [[Optimal control|optimal control]] with constraints on the phase coordinates and control functions. The original problem of optimal control by discretization (with respect to time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t0940401.png" /> and phase vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t0940402.png" />) can be reduced to the minimization of a function of the type
+
{{TEX|done}}
 +
A direct method for the numerical solution of problems of [[Optimal control|optimal control]] with constraints on the phase coordinates and control functions. The original problem of optimal control by discretization (with respect to time $t$ and phase vector $x$) can be reduced to the minimization of 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/t/t094/t094040/t0940403.png" /></td> </tr></table>
+
$$I(x_0,\dots,x_N)=\sum_{i=0}^{N-1}\phi_i(x_i,x_{i+1}),$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t0940404.png" /> is the value of the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t0940405.png" /> at the nodal points of hyperplanes given in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t0940406.png" />-space by the equations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t0940407.png" />. The discretization with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t0940408.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t0940409.png" /> is effected by given steps <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t09404010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t09404011.png" />. To each set of vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t09404012.png" /> there corresponds a polygonal line passing through the nodes, which is an approximate representation of the trajectory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t09404013.png" /> of the original problem of optimal control. The length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t09404014.png" /> of this line is the sum of the (generalized) lengths <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t09404015.png" /> of the individual pieces. The polygonal line having shortest length is found with the aid of the recurrence relation
+
where $x_i$ is the value of the vector $x$ at the nodal points of hyperplanes given in the $(t,x)$-space by the equations $t=t_i$. The discretization with respect to $t$ and $x$ is effected by given steps $\Delta t$ and $\Delta x$. To each set of vectors $\{x_0,\dots,x_N\}$ there corresponds a polygonal line passing through the nodes, which is an approximate representation of the trajectory $x(t)$ of the original problem of optimal control. The length $I(x_0,\dots,x_N)$ of this line is the sum of the (generalized) lengths $\phi_i(x_i,x_{i+1})$ of the individual pieces. The polygonal line having shortest length is found with the aid of the recurrence relation
  
<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/t/t094/t094040/t09404016.png" /></td> </tr></table>
+
$$l_s(i+1)=\min_k(l_k(i)+l_{ks}(i))$$
  
 
(cf. [[Variational calculus, numerical methods of|Variational calculus, numerical methods of]]).
 
(cf. [[Variational calculus, numerical methods of|Variational calculus, numerical methods of]]).
  
The search for a global minimum on any graph thus obtained requires a large operation memory and long computing times (especially in connection with the diminution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t09404017.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t09404018.png" /> to obtain a solution of desired accuracy).
+
The search for a global minimum on any graph thus obtained requires a large operation memory and long computing times (especially in connection with the diminution of $\Delta x$ and $\Delta t$ to obtain a solution of desired accuracy).
  
 
The required amounts of memory and the number of operations can be considerably reduced if the attempt to find a global minimum is abandoned. The algorithm used works by successive approximations; the optimal trajectory is not sought on the entire graph, but on a subgraph given by a  "tube"  containing the initial polygonal line; this is the initial approximation. Each cross-section of the tube contains a given amount of nodes. The polygonal line which is found is taken as the successive approximation, after which the computations are repeated on a new subgraph.
 
The required amounts of memory and the number of operations can be considerably reduced if the attempt to find a global minimum is abandoned. The algorithm used works by successive approximations; the optimal trajectory is not sought on the entire graph, but on a subgraph given by a  "tube"  containing the initial polygonal line; this is the initial approximation. Each cross-section of the tube contains a given amount of nodes. The polygonal line which is found is taken as the successive approximation, after which the computations are repeated on a new subgraph.
  
Estimates show that in the travelling-tube method the number of operations increases linearly with the number of grid nodes with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t09404019.png" /> (with decreasing step-size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094040/t09404020.png" />), while in the method of global selection the increase is quadratic.
+
Estimates show that in the travelling-tube method the number of operations increases linearly with the number of grid nodes with respect to $x$ (with decreasing step-size $\Delta x$), while in the method of global selection the increase is quadratic.
  
 
A special case of the travelling-tube method is the method of local variations (cf. [[Local variations, method of|Local variations, method of]]), in which the number of nodes in each cross-section is minimal (and equal to two).
 
A special case of the travelling-tube method is the method of local variations (cf. [[Local variations, method of|Local variations, method of]]), in which the number of nodes in each cross-section is minimal (and equal to two).

Latest revision as of 10:39, 31 August 2014

A direct method for the numerical solution of problems of optimal control with constraints on the phase coordinates and control functions. The original problem of optimal control by discretization (with respect to time $t$ and phase vector $x$) can be reduced to the minimization of a function of the type

$$I(x_0,\dots,x_N)=\sum_{i=0}^{N-1}\phi_i(x_i,x_{i+1}),$$

where $x_i$ is the value of the vector $x$ at the nodal points of hyperplanes given in the $(t,x)$-space by the equations $t=t_i$. The discretization with respect to $t$ and $x$ is effected by given steps $\Delta t$ and $\Delta x$. To each set of vectors $\{x_0,\dots,x_N\}$ there corresponds a polygonal line passing through the nodes, which is an approximate representation of the trajectory $x(t)$ of the original problem of optimal control. The length $I(x_0,\dots,x_N)$ of this line is the sum of the (generalized) lengths $\phi_i(x_i,x_{i+1})$ of the individual pieces. The polygonal line having shortest length is found with the aid of the recurrence relation

$$l_s(i+1)=\min_k(l_k(i)+l_{ks}(i))$$

(cf. Variational calculus, numerical methods of).

The search for a global minimum on any graph thus obtained requires a large operation memory and long computing times (especially in connection with the diminution of $\Delta x$ and $\Delta t$ to obtain a solution of desired accuracy).

The required amounts of memory and the number of operations can be considerably reduced if the attempt to find a global minimum is abandoned. The algorithm used works by successive approximations; the optimal trajectory is not sought on the entire graph, but on a subgraph given by a "tube" containing the initial polygonal line; this is the initial approximation. Each cross-section of the tube contains a given amount of nodes. The polygonal line which is found is taken as the successive approximation, after which the computations are repeated on a new subgraph.

Estimates show that in the travelling-tube method the number of operations increases linearly with the number of grid nodes with respect to $x$ (with decreasing step-size $\Delta x$), while in the method of global selection the increase is quadratic.

A special case of the travelling-tube method is the method of local variations (cf. Local variations, method of), in which the number of nodes in each cross-section is minimal (and equal to two).

References

[1] N.N. Moiseev, "Elements of the theory of optimal systems" , Moscow (1975) (In Russian)

'

How to Cite This Entry:
Travelling-tube method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Travelling-tube_method&oldid=16219
This article was adapted from an original article by I.B. VapnyarskiiI.A. Vatel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article