Travelling-tube method

From Encyclopedia of Mathematics
Jump to: navigation, search

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


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


(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).


[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:
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