View source for Travelling-tube method

{{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

$$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|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|Local variations, method of]]), in which the number of nodes in each cross-section is minimal (and equal to two).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  N.N. Moiseev,   "Elements of the theory of optimal systems" , Moscow  (1975)  (In Russian)</TD></TR></table>

'