A Multimethod Technique for Solving Optimal Control Problem

Abstract

A multimethod algorithm for solving optimal control problems is implemented in the form of parallel optimization processes with the choice of the best approximation. The multimethod algorithm based on a sequence of different methods is to provide fast convergence to an optimal solution. Such a technology allows one to take into account some particularities of the problem at all stages of its solving and improve the efficiency of optimal control search.

1 Introduction

The technology of finding the numerical solution to the applied optimal control problems is based on universal software which has a well-developed interface and a rich arsenal of optimization methods. Such software allows one to take into account specific features of the problem under consideration by making the use of diverse algorithms of improvement at different stages of iteration process. Application of several numerical methods for solving a single optimization problem was suggested in many publications oriented to the software development [1–3, 6, 7, 11].

Principal difficulty in applying the multimethod algorithm lies in the fact that at each stage of the problem-solving process one has information about efficiency of the method applied at the present moment. To determine the efficiency of any optimization method at some stage of searching for solution to the given problems it is necessary to perform one or several iterations. Therefore, to choose the method which is more appropriate for the given stage of problem solving, the operation of switching from one method to another is usually repeated.

Also, it is necessary to know about switching times. But this information can be easily obtained by tracking the current method measuring parameters characterizing its convergence.

Thus, the principal problem of the multimethod technology is the choice of method which allows one to continue effectively the optimization process from the moment when convergence of current method was impaired.

Modern operational systems provide a solution to the given problem by organizing parallel computational flows for simultaneous computation by several methods. In each flow, one can realize iterative process of one method from a collection of methods. Thus, a single problem can be solved by several methods. With the multiprocessor technology on hand, of course, it is convenient to use individual processor for accomplishing iteration of each method.

After finding the next approximation, each method is considered, for instance, evaluating an increment of the functional. More effective method is taken to continue the optimization. Next, the approximation obtained by this method is transferred to other methods as initial data to perform next iteration. Starting from this approximation, one or several iterations are again performed by all methods. Out of the obtained approximations again we take the one in which the functional has a smaller value.

Continue iterative process until the optimum criterion is met for the obtained approximation. After that we find an approximation solution to the problem under consideration. In this case the solution is found by the multimethod algorithm consisting of a sequence of steps of different methods attached to optimization process to accelerate its convergence. The advantage of the multimethod algorithm in comparison with each method separately lies in its greater adequacy in application to concrete problem. At each stage of searching for solution, the multimethod algorithm makes the use of optimization method which is more suitable in terms of specific features of a given problem (e.g., the ravines of function, specific character, and the structure of constraints).

In the graphic, the decrease in the functional I(u), in iterations of the multimethod algorithm, is shown by the broken line which consists of the graphics of separate methods. Figure 1 shows the multimethod algorithm operation in the case, when two methods M1 and M2 are used. The graphics given show the decrease in the functional in the iterations of the methods M1 and M2. The graphic of decrease in the functional in the iterations of the multimethod algorithm is the curve ABC. It is constructed by using two graphics corresponding to the methods M1 and M2. Namely, the region BC is obtained by parallel translation of the region EL. According to this figure, the zero value of functional is achieved in k ₁ iterations of the method M1, while the use of the methods M1 and M2 requires k ₂ iterations.

Fig. 1

Graphics of decrease of functional on the iterations of the methods M1, M2 and multimethod algorithm

The multimethod algorithm works, up to the $\bar{k}$th iteration, by the method M1 (the curve AB) and then by the method M2 (the curve BC). The reason is that beginning with the $\bar{k}$th iteration, the velocity of decrease in the functional during the use of the method M2 is higher. As a result, zero value of functional is achieved by the multimethod algorithm using k ^∗ iterations. This is considerably less than in the case where the methods M1 and M2 are used individually.

2 Parallel Computations in the First-Order Methods

By different criteria for choosing the closest optimization method and also organizing in different ways parallel computations on the method’s iterations, several different combinations of algorithms can be obtained to solve a single problem. Moreover, it is possible to construct the multimethod algorithms that do not contain repeated computations in the iterations of different optimization methods. For example, in the methods of gradient type [4, 13], laborious computations of the gradient, requiring an integration of the adjoint system, should be performed only once; then, the obtained gradient should be used in the iterative formulas of all methods. In this case, computational expenditures at one step of multi-flow algorithm are considerably reduced. Moreover, realization of the step by any of the methods is accomplished by using the same approximately obtained values. Then all optimization algorithms are applied as if to the one and the same approximate model. Thus, the criterion of new approximation is defined only by the optimization methods. Otherwise, because of computational errors, the same parameters used to estimate convergence of the methods may have different values which can lead to improper choice of the best method.

Let us consider an optimal control problem provided by the conditions in the form of equalities at the right trajectory end. The controlled process is described by the system

$$\dot{x} = f(x,u,t),\quad x({t}_{0}) = {x}_{0},\quad t \in T = [{t}_{0},{t}_{1}],\quad x(t) \in {\mathbb{R}}^{n},\quad u(t) \in {\mathbb{R}}^{r}$$

(1)

with terminal conditions

$${I}_{j}(u) = {\varphi }^{j}(x({t}_{ 1})) = 0,\quad j = \overline{1,m}$$

(2)

and with phase constraints

$${J}_{i}(u,t) = {g}^{i}(x,t) = 0,\quad i = \overline{1,s},\quad t \in T.$$

(3)

The control is constrained through

$$u(t) \in U,$$

(4)

where U is a bounded closed set in ${\mathbb{R}}^{r}$. Vector functions f(x, u, t) are assumed to be differentiable w.r.t. to x and u and continuous w.r.t. t; ${\varphi }^{j}(x)$, $j = \overline{1,m}$ are assumed to be continuously differentiable w.r.t. x functions.

It is required to find the control among controls fulfilled by (3), such that provides the validity of conditions (2), for controlled process (1) and, on the other hand, provides the minimum of the functional

$${I}_{0}(u) = {\varphi }^{0}(x({t}_{ 1})),$$

(5)

where ${\varphi }^{0}(x)$ is continuously differentiable function.

The gradients of functionals I _j (u), $j = \overline{0,m}$ in terms of the functions ${H}^{j}({\psi }_{j},x,u,t) = {\psi ^{\prime}}_{j}(t)f(x,u,t)$ and adjoint system

$$\dot{{\psi }}_{j} = -{f}_{x}(x,u,t)^{\prime}{\psi }_{j}(t),\quad {\psi }_{j}({t}_{1}) = -{\psi }_{x}^{j}(x({t}_{ 1}))$$

are given by the formula

$$\nabla {I}_{j}(u) = -{H}_{u}^{j}({\psi }_{ j},x,u,t),\quad j = \overline{1,m}.$$

(6)

For each t ∈ T one can calculate in much the same way the gradients J _j (u, t), $j = \overline{1,s}$:

$$\nabla {J}_{j}(u,t) = -{\overline{H}}_{u}^{j}({\Phi }_{ j},x,u,t,\tau ),\quad {t}_{0} \leq \tau \leq t \leq {t}_{1},$$

(7)

where ${\overline{H}}_{u}^{j}({\Phi }_{j},x,u,t,\tau ) = {\Phi ^{\prime}}_{j}(t,\tau )f(x,u,\tau )$, Φ _j (t, τ), $j = \overline{1,s}$ are the solutions of the conjugate system

$$\frac{\partial {\Phi }_{j}(t,\tau )} {\partial \tau } = -\frac{\partial f(x,u,\tau )} {\partial x} {\Phi }_{j}(t,\tau ),\quad \tau \in T,$$

with the boundary conditions ${\Phi }_{j}(t,t) = -\frac{\partial {g}^{j}(x(t))} {\partial x}$, $j = \overline{1,s}$.

2.1 Application of Gradient Methods

Gradient procedure of the minimization of the functional (4) without taking into account the constraints (2) and (3) is given through relation

$${u}^{k+1} = {u}^{k} - {\alpha }_{ k}\nabla {I}_{0}({u}^{k}),$$

where α _k are chosen, for example, from condition of fastest decrease of the functional I ₀(u). The solution of the problem with terminal conditions (2) without constraints (3) can be obtained by parallel application of the linearization and penalization methods given, for example, in [7]. When using penalization method, penalty functional which consists of the functions (2) and (4) is minimized with the help of gradient procedure. Making use of the multimethod technology, one can also simplify each iteration of the linearization method in such a way that its working time will be close to the one of the penalization method. Then the algorithm will be as follows:

• 1. For given u ^k(t), t ∈ T, system (1) is integrated; in the integration points, the phase coordinates of trajectory x ^k(t) are memorized.

• 2. m + 1 flows are organized, for parallel integration of adjoint system provided by different initial conditions ${\psi }_{j}({t}_{1}) = -{\psi }_{x}^{j}(x({t}_{1}))$, $j = \overline{0,m}$. In the process of integration, the solutions ψ _j (t) are used to construct a linear system of algebraic equations

  $$\sum\limits_{i=1}^{m}\left (\int\limits_{{t_0}}^{{t_1} }H_{u}^{j^{\prime}} H_{u}^{i}\,\mathrm{d}t\right ){\lambda }_{ i} = {I_j}({u^k}) -\int\limits_{{t_0}}^{{t_1}}H_{u}^{j^{\prime}} H_{u}^{0}\,\mathrm{d}t,\quad j = \overline{1,m}.$$

• 3. After solving this system, the values of variables λ _i , $i = \overline{1,m}$ are found.

• 4. A new approximation of the control

  $${u}^{k+1} = {u}^{k} + {\alpha }_{ k}\delta u,\qquad \delta u = {H}_{u}^{0} +\sum\limits_{i=1}^{m}{\lambda }_{ i}{H}_{u}^{i},$$

  is constructed, where the parameters α _k satisfy inequality

  $$\begin{array}{rcl} & & {I}_{0}({u}^{k} + {\alpha }_{ k}\delta u) + \beta {I}_{{j}_{0}}({u}^{k} + {\alpha }_{ k}\delta u) \leq {I}_{0}({u}^{k}) + \beta {I}_{{ j}_{0}}({u}^{k}) - \epsilon \int\limits_{{t}_{0}}^{{t}_{1} }\delta u^{\prime}\delta u\,\mathrm{d}t, \\ & & 0 < \epsilon < 1,\quad {j}_{0} ={ \arg \max }_{1\leq j\leq m}\left \vert {I}_{j}({u}^{k})\right \vert,\quad \beta =\sum\limits_{i=1}^{m}\left \vert {\lambda }_{ i}\right \vert.\end{array}$$

From this algorithm, as particular case (for m = 0), we obtain the ordinary gradient method.

2.2 The Methods for Solving Problem with Constraints on Control

Let us focus on the algorithms intended for solving the problems provided by constraints on control, but with free right end. Suppose that for some u ^k(t) ∈ U, t ∈ T, one finds any solution to the system (1) x ^k(t), t ∈ T. Setting in (5) j = 0, integrate adjoint system from t = t ₁ to t = t ₀ when u = u ^k(t), x = x ^k(t). Calculate on its solution ${\psi }^{k} = {\psi }^{0}(t)$ the control using the maximum principle:

$$\bar{{u}}^{k}(t) ={ \arg \max }_{ u\in U}H({\psi }^{k},{x}^{k},u,t),\quad t \in T,$$

and find the value of scalar function

$${w}_{k}(\bar{u}(t),t) = H({\psi }^{k},{x}^{k},\bar{u},t) - H({\psi }^{k},{x}^{k},{u}^{k},t),\quad t \in T.$$

Let t = τ _k the maximum point of this function being on T. Then, the necessary optimum condition of the control u ^k will be

$${w}_{k}(\bar{{u}}^{k}({\tau }_{ k}),{\tau }_{k}) = 0.$$

In the case when for given u ^k and obtained x ^k, ψ^k, $\bar{{u}}^{k}$, the maximum principle

$${w}_{k}(\bar{{u}}^{k}({\tau }_{ k}),{\tau }_{k}) > 0$$

does not hold; iteration of the method  [12] can be made to improve u ^k.

Denote the point set, where maximum principle is broken by

$${T}_{\epsilon } = \left \{t \in T :\; {w}_{k}(\bar{{u}}^{k}(t),t) \geq \epsilon {w}_{ k}(\bar{{u}}^{k}({\tau }_{ k}),{\tau }_{k})\right \},\quad \epsilon \in [0,1].$$

Observe that at $\epsilon = 0$, we have ${T}_{\epsilon }^{k} = T$, while at $\epsilon = 1$, the set ${T}_{\epsilon }^{k}$ consists of the maximum points of the function w _k (u(t), t).

By varying $\epsilon$, we can find such value for which the control

$${ u}_{\epsilon }^{k} = \left \{\begin{array}{cc} \bar{{u}}^{k}(t),& t \in {T}_{ \epsilon }, \\ {u}^{k}(t),&t \in T\,\setminus \,{T}_{\epsilon }\\ \end{array} \right.$$

(8)

provides the least value of the objective functional I ₀(u), i.e.,

$${\epsilon }_{k} =\arg \min_{\epsilon \in [0,1]}{I}_{0}({u}_{\epsilon }^{k}).$$

When searching for ${\epsilon }_{k}$, several flows can be used for simultaneous integration of system (1) with controls (8), corresponding to different values of $\epsilon \in [0,1]$. In addition, at t = t ₁, we have different phase space points ${x}_{\epsilon }^{k}({t}_{1})$ and pertinent values ${I}_{0}({u}_{\epsilon }^{k}) = \varphi ({x}_{\epsilon }^{k}({t}_{1}))$. After the smallest value of the functional ${I}_{0}({u}_{\epsilon }^{k})$ is chosen, we verify the inequality ${I}_{0}({u}_{\epsilon }^{k}) < {I}_{0}({u}^{k})$, and if it holds, we assume ${u}^{k+1} = {u}_{\epsilon }^{k}$. Otherwise, the subdivision of $\epsilon$ can be continued, and the values of functional for the following values can be found.

By virtue of structure of the controls generated by the iteration formula (8), the relaxation of an algorithm can be impaired even before the control satisfying the maximum principle is obtained. Therefore, to continue optimization process, it is necessary to apply another algorithm, in iteration of which the controls are constructed not only with boundary points but also with interior ones w.r.t. the set U as well. For example, the convergence can be restored by constructing a convex combination of two controls

$${u}^{k+1}(t) = {u}^{k}(t) + \alpha \left [\bar{{u}}^{k}(t) - {u}^{k}(t)\right ],\quad \alpha \in [0,1].$$

(9)

The calculations by the formulas (8) and (9) can be made simultaneously by choosing from the obtained approximations such u ^k + 1 to which the smallest value of the functional corresponds. In the case, where the functional values are compared within several iterations, the values of increase in the functional, obtained in the neighboring iterations of each method, should be used as a criterion to compare the efficiency of the methods (8) and (9).

In practice, it is established that the application of the variations of two types, namely, “horizontal” (8) and “vertical” (9), allows us to avoid the effect of “control sticking to the boundaries” which is inherent in the algorithms based on the maximum principle [5, 12].

In the case in the iteration equation (9), the control $\bar{{u}}^{k}(t)$ is derived from the linearized maximum principle

$$\bar{{u}}^{k}(t) =\arg \max_{ u\in U}{H}_{u}({\psi }^{k},{x}^{k},u,t)^{\prime}u(t),\quad t \in T;$$

(10)

we obtain the iterations of the conditional gradient method. It is evident that for the systems which are linear in control, the control function (10) coincides with that deduced from the maximum principle. Another algorithm of control improvement can be obtained by substituting, in the iteration formula (8), the interval ${T}_{\epsilon }$ for the following one:

$${T}_{\epsilon }^{k} = \left [{\tau }_{ k} - \epsilon ({\tau }_{k} - {t}_{0}^{k}),\,{\tau }_{ k} + \epsilon ({t}_{1}^{k} - {\tau }_{ k})\right ],\quad \epsilon \in [0,1],$$

(11)

where t ₀ ^k, t ₁ ^k are the nearest left and right discontinuity points of the function $w(\bar{{u}}^{k}(t),t)$.

In the process of finding the value of parameter ${\epsilon }_{k}$ providing convergence of the algorithm, we can apply the above procedure along with parallel computations. This way of constructing the interval provides blowing down of its ends towards the point τ _k , in the case, if the function $w(\bar{{u}}^{k}(t),t)$ is constant within some neighborhood of the point τ _k , thus maintaining the convergence of the algorithm [12].

2.3 Linearization Method for Solving Problems with Phase Constraints

Let u _k (t) be a current approximation of the control, and let x _k (t) be the phase trajectory, corresponding to u _k (t), t ∈ T. Using the gradients (6) and (7) we linearize the conditions (2) and (3) in the neighborhood of u _k :

$${I}_{i}^{L}({u}^{k},u) = {I}_{ i}({u}^{k}) +\int\limits_{{T}_{0}}^{{T}_{1} }\nabla {I}_{i}({u}^{k},t)^{\prime}\left(u(t) - {u}^{k}(t)\right)\mathrm{d}t = 0,\quad i = \overline{1,m},$$

(12)

$${J}_{j}^{L}({u}^{k},u,\tau ) = {J}_{ j}({u}^{k},\tau ) +\int\limits_{{t}_{0}}^{\tau }\nabla {J}_{ j}({u}^{k},t)^{\prime}\left(u(t) - {u}^{k}(t)\right)\mathrm{d}t = 0,$$

(13)

$$j = \overline{1,s},\quad \tau \in T.$$

Construct a modified Lagrange function for the problem (1)–(5) in the form:

$$\begin{array}{rcl} L(u,{u}^{k},{\lambda^k},{\mu^k})& =& {I}_{ 0}(u) - {\lambda^k}^{\prime}\left(I(u) - {I^L}({u^k},u)\right) \\ & & -\,\int\limits_{{t}_{0}}^{{t}_{1} }{\mu }^{k}(t)^{\prime}\left(J(u,t) - {J}^{L}({u}^{k},u,t)\right)\mathrm{d}t \\ & & +\,\frac{\rho } {2}\left(I(u) - {I}^{L}({u}^{k},u)\right)^{\prime}\left(I(u) - {I}^{L}({u}^{k},u)\right) \\ & & +\,\frac{\rho } {2}\int\limits _{{t}_{0}}^{{t}_{1} }\left(J(u,t) - {J}^{L}({u}^{k},u,t)\right)^{\prime}\left(J(u,t) - {J}^{L}({u}^{k},u,t)\right)\text{d}t, \\ & & \end{array}$$

(14)

where I, I ^L — m-vectors; J, J ^L — s-vectors; λ^k, μ^k are m- and s-dimensional Lagrange factors; ρ ≥ 0 is a penalty coefficient.

In the $k + 1 - st$ iteration of the considered method we solve the minimization problem of functional (14) on the solutions of the system (1) with the linear constraints (12), (13), and (4). By solving the problem, we determine new values of the Lagrange factors λ _i ^k + 1, $i = \overline{1,m}$, μ _i ^k + 1(t), $i = \overline{1,s}$, t ∈ T.

After determining u ^k + 1, λ^k + 1, and μ^k + 1, we again linearize constraints (2), and (3) in the neighborhood of u ^k + 1, construct the functional $L(u,{u}^{k+1},{\lambda }^{k+1},{\mu }^{k+1},\rho )$, and repeat the iteration.

Thus, the algorithm for solving the formulated problem consists of the following main operations:

• 1. Linearizing the constraints and solving the auxiliary problem (1), (4), and (12)–(14). Calculating the Jacobian of the linear system (13) is computationally very expensive.

• 2. Verifying the optimal conditions for the solution obtained on the kth iteration.

When solving the problems with linear constraints the application of this algorithm is greatly simplified because it is not necessary to calculate the constrained Jacobian.

2.4 The Block Scheme of Multimethod Algorithm Operation

Summarizing the above said we see that by applying various iteration procedures and making use of different rules to construct the sets of varying controls, we obtain the collection of algorithm, each working effectively enough only in a certain situation. Thus, in the process of finding the optimal control, it is necessary to include several algorithms.

By organizing parallel computations to realize some collection of algorithms and applying the selection procedure to take the best approximation after simultaneous iterations by all methods, we are able to find effectively optimal control by the multimethod algorithm.

Figure 2 demonstrates how the multimethod algorithm works in the case when three methods are used. The block of selection of the best approximation finds ${u}_{{i}_{0}}$ from a largest value of increment of the functional obtained in the (k + 1)-th iteration

$${u}_{{i}_{0}} =\arg \max_{i\in (1,\,2,\,3)}\left(I({u}^{k}) - I({u}_{ i}^{k+1})\right).$$

Fig. 2

The scheme of realization of (k + 1)-th iteration by multimethod algorithm using three methods M1, M2, and M3

This approximation is passed to all methods ${u}_{i}^{k+1} = {u}_{{i}_{0}}$, i = 1, 2, 3, to perform the next iteration.

It should be noted that another multimethod algorithm can be generated from the collection of methods for solving another problem. The algorithm can be more adequate because of taking into account the specific features of this problem.

3 Implementation of Multimethod Algorithm

3.1 Solving the Adjoint Problem

The most labor-consuming operation performed at each step of all first-order algorithms is numerical integration of original and adjoint system of differential equations provided by some control. The solving of adjoint system in the iterations is used to find either the value of Hamiltonian or both to perform the calculation of gradients of functionals. Thus, the numerical integration of this system is accomplished at each step of any of the first-order methods. Since the multimethod technology enables the steps to be made simultaneously by all methods, the solution of adjoint system, which is obtained by single integration, is used in all iteration formulas simultaneously.

3.2 Computation of the Method Step

Realization of each step of the first-order method needs to find the value of method’s step α or $\epsilon$, for which new obtained approximation provides the smallest value of objective functional. The search for such a value of α requires multiple integration of initial system (1). By constructing control u ^α by given iteration formula at different values of α, and integrating initial system, at u = u ^α, we obtain various trajectories x ^α(t), t ∈ T and find pertinent values of the functional I(u ^α). By applying the one-dimensional search method it is possible by several such recalculations to find the approximate value of α = α _k such that the minimum of I(u ^α) w.r.t. parameter α is provided. If, in the process, the inequality $I({u}^{{\alpha }_{k}}) < I({u}^{k})$ holds, the control ${u}^{{\alpha }_{k}}$ is taken as new approximation u ^k + 1. Otherwise, iteration process, using this method, comes to an end.

To recover the method convergence it is necessary to correct calculations, namely, diminish the integration step, increase the accuracy of one-dimensional search, and so on. The multimethod algorithm can be used to continue the process of control improvement by switching to another method, while the condition for termination of its work is impossibility to guarantee relaxation by none of the methods entering in the given collection.

Another scheme of search can also be used to find the value of α _k while using the multimethod algorithm. Its essence consists in the fact that in the process of subdivision of α, for example, by cutting in two, with each its value, it accomplishes test step by all methods. Since, in many algorithms, for finding α _k , it accomplishes subsequent subdivision in two until the inequality $I({u}^{{\alpha }_{k}}) < I({u}^{k})$ holds, then, for any fixed α, the validity of this inequality is checked simultaneously for all methods. In addition, with given value of α, in correspondence with iteration formula of each method, it is constructed the control u ^α integrated the system (1). Its solution is used to calculate the functional I(u ^α). If, in the process, for some value of parameter α, for some of the methods, the required inequality holds, then ${u}^{{\alpha }_{k}}$, obtained by this method, should be taken as a new approximation to be passed to all methods for continuation of iteration process.

3.3 Choice of Optimization Methods

For parameters to be used to estimate the efficiency of iteration process, one can take, for instance, the velocity of reduction of the residuals in optimization conditions, the value of increment of the objective functional, or the extent of violation of some important, for example, in the physical sense, constraints. The accuracy of calculations of these parameters provides the proper choice of the method and opportune transition to another optimization method.

3.4 The Methods of Approximation of Control

The principal error in modeling the control problem arising in the process of numerical solving is due to discrete approximation of controlled dynamic system and tabular representation of control function.

The methods of numerical integration allow for discretization of the system with given accuracy but provided that control functions are continuous and their values can be determined for arbitrary t ∈ T. However, in practice, piecewise constant approximation of control functions is often applied, and its values are defined only in given sites of the temporal network. These values are changed in iteration process, depending on optimization method to decrease minimized functional or to reduce the residuals for given terminal conditions. The values of control functions between the points, which are necessary, for example, to apply the numerical methods of Runge–Kutta type, as usual are taken to be equal either the value in the nearest left point or both are defined by linear interpolation by the values in left and right points. In this process, the error of numerical integration can be considerably extended. Then, on the obtained numerical solution of the system, the values of parameters, which are used to choose the method, could be incorrect.

To diminish the errors of calculation of trajectory, one can condense the temporal network in order to increase the number of desired values of control which implies to solve optimization problem of a big size. In the case if required control is smooth enough, then, with some number of points and with the help of interpolation formulas, the admissible accuracy of its approximation can be provided. However, in general case, if control functions are discontinuous, for example, of relay type, this approach may turn out to be inefficient, since, in this case, the condensation of network affects the approximation accuracy only in the neighborhood of the switching points. Therefore, in the process of solving the bang–bang optimal control problems, it is necessary to use the procedure of switching times correction to provide the approximation for control functions with prescribed accuracy. In the absence of this procedure, the control is found in the form of the array of numbers defined on temporal network. Such a control may differ in significantly from the optimal one both by the value of objective functional and by the accuracy of optimal conditions fulfillment.

3.5 The Estimation of Accuracy of a Chosen Method

The application of multimethod algorithm is correct only if all methods use the same approximation of the control and provide the same accuracy of integration of the systems. In this case, all optimization methods are used to solve the same finite dimensional problem obtained by discretization, while the values of parameters used to choose the method give a more correct estimate of the algorithm efficiency, providing thus a correct choice of the method to continue iteration process. As a result, the approximate solution is obtained in a lesser number of iterations, in comparison to individual use of each method from a given collection. This is because at each stage of solving the considered problem, a more effective algorithm is applied to be more adequate in this situation.

4 The Numerical Experiments

Let us present the results of the numerical experiments to demonstrate application of the multimethod technology. Two examples are considered: a test problem of the Rosenbrock function minimization and the problem of optimal control of the rocket flight.

4.1 Example 1

It is required to find the minimum of Rosenbrock function $f({x}_{1},{x}_{2}) = 100{({x}_{2} - {x}_{1}^{2})}^{2} + {(1 - {x}_{1})}^{2}$ with constraint ${({x}_{1} - 2)}^{2} + {({x}_{2} - 2)}^{2} \leq 1$ and initial approximation x ⁰ = (2, 1).

It is known that the absolute minimum of this function is achieved at the point (1, 1). It is equal to 0. In the problem under consideration, the point (1, 1) is not feasible. Therefore the zero value of objective functional is not attained.

This problem was solved numerically by the method of conditional gradient, by the method of gradient projection, and also by the multimethod algorithm which contains these two methods. The smallest value of the function equal to 0.0358, for prescribed accuracy $\epsilon = 1{0}^{-4}$, was attained using 240, 341, and 170 iterations, respectively. Minimum point is x ^∗ = (1. 189, 1. 415).

4.2 Example 2

In this case, controlled process is described by the system

$$\begin{array}{l} \dot{{x}}_{1} = -cp{x}_{1}^{2}[1.174 - 0.9\cos {u}_{1}] - g\sin {x}_{2}\left/{(1 + {x}_{3})}^{2}, \right.\\ \dot{{x}}_{2} = 0.6cp{x}_{1}^{2}\sin {u}_{1} + {x}_{1}\cos {x}_{2}\left/[R(1 + {x}_{3})] - g\cos {x}_{2}\right/[{x}_{1}{(1 + {x}_{3})}^{2}], \\ \dot{{x}}_{3} = {x}_{1}\sin {x}_{2}\left/R,\right. \\ \dot{{x}}_{4} = {x}_{1}\cos {x}_{2}\left/ [1 + {x}_{3}],\right.\end{array}$$

where $\rho = 0.002704\exp (-4.26R{x}_{3})$, R = 209, g = 0. 00032172, and c = 26600.

The initial data $x(0) = (0.36,-0.141372,0.019139,0.0)$ and terminal conditions x(t _k ) = (0. 27, 0. 0, 0. 011962, { unbounded})are given, while the parameter t _k is not fixed. It is required to find such control u(t), t ∈ [0, t _k ] and such smallest value of parameter t _k that the fulfillment of terminal conditions is guaranteed, while the functional

$$I(u) =\int\limits_{0}^{{t}_{k} }{x}_{1}{[\exp (-4.26R{x}_{3})]}^{1/3}\,\mathrm{d}t$$

should attain the smallest value.

This problem was solved by the above linearization method and also by the projected Lagrangian method, in iteration of which the nonlinear Lagrangian with linearizable constraints is minimized [11]. Approximate solution (the accuracy w.r.t. boundary conditions is 10^− 3) was found in 282 and 215 iterations, respectively. The solution with the same accuracy, that was obtained with the multimethod algorithm including these two methods, was found in 164 iterations. The value of parameter t _k equals 72.412, while the functional I(u) attains the value equal to 24.59.

5 Conclusion

Thus, we can conclude that for each problem under consideration there exists an appropriate sequence of steps based on different methods which provides more effective search for the optimal control. In the multimethod algorithms the construction of such a sequence is accomplished automatically according to some given criterion estimating the efficiency of optimization process at each stage of the problem solving. The use of the technology described above is based on the application software, for example, [5–11, 14], which includes the methods of first and second order for solving the optimal control problems with constraints of different types.