An optimal control problem with a nonsmooth objective function defined on a polytope is studied. A scheme reducing the original problem to the problem of maximizing the sum of matrix elements lying above the main diagonal is constructed. Necessary conditions of optimality for this finite-dimensional optimization problem are established. A method of searching for the global maximum is suggested.
Introduction Optimal control problems with nonsmooth objective functions of the form (1)
Formulation and Discussion of the Problem M - is a polyhedron x(0) = 0; x(1) ∈ X; X ∩ M ̸= 0:
This problem arises in the study of the following important class of problems (2) (3) (4) (5) (6) (7) (8)
U (x(t)) = {u : K(x(t)) = u(t) = L(x(t)); M (x(t)) > N (x(t))}; where M (· ) − is an m × n matrix; L(· ) − is an m × 1 matrix; K(· ) − is an k × n matrix; N (·) − is an k × 1 matrix:
With the implementation of the procedure of continuation of the optimal trajectory
Gi(x( )) = Gj (x( )); i ̸= j i; j ∈ p0; p0 ⊂ p:
Without loss of generality, we may assume that p0 = p: This case is studied in detail in
un+1 → max un+1 > ⟨ai; u⟩; i ∈ p; where ai = grad Gi(x0); u ∈ M; M − polyhedron;
u ∈ Rn: The second-order degeneration occurs when grad Gi(x0) = 0; i ∈ P: To remove degeneracy, let us put into consideration grad Gi(x˙ ) x=x0 = x=x0 u; and, under the assumption @2Gi(x)
@x2 x=x0 the objective function of problem (2) – (5) became x=x0 = Pi: And J [v] = min i ⟨Pi x(t); u(t)⟩dt → max; i ∈ P: u Further we assume that P − is a skew-symmetric matrix, because a symmetric part of the matrix we may to take out from under the integral sign.
Reduction of the Problem The vectors Ri can be considered as columns of the matrix R = {Ri}N n; and it is easy to see that x(t) = R ∫0t v( )d ; y(0) = 0; Integrants of the objective function take the form
⟨Ciy(t); v(t)⟩; where Ci = RT AR: Finally, the problem (2) - (5) takes the form: when t ∈ [tL 1; tL] where Ci = RT PiR:
This problem is easily rewritten in the form of a problem of mathematical programming with a quadratic (bilinear) constraints. Using the skew-symmetric property of matrices Ci, we can derive the following equality, L 1 1 L 1 ∑ ∑⟨Ciy ; y ⟩ = ∑ where t0 = 0; tL = 1:
It is clear that, when t ∈ [ti 1; ti]; Let us introduce the notation v (t +1 − t ) = y : Substitute the obtained y(t) and y ; = 0; L into the objective function (9) into constraints (10) and (11)), and get ∫ t
0 y(t) = v( )d = i 1 ∑ v (t − t =0
1) + vi(t − ti):
L 1 J [v] = min ∑ i =1 =0
1 ∑⟨Ciy ; y ⟩ → max
fyig L 1 ∑ y = y(1); Ry(1) ∈ X =0 ⟨y(1); 1N ⟩ = 1; y(1) > 0; 1N = (1; 1; : : : ; 1)T ;
| {z }
Z → max;
L 1 Z 6 ∑
L ∑ ⟨Ciy ; y ⟩; =1
= +1 L ∑ y = y(1); =0 ⟨y(1); 1N ⟩ = 1; y(1) > 0; R y(1) ∈ Z: Proof. Let us replace problem (15) - (18) by the set of bilinear programming problems with linear constraints of the form and finally have 5
The Theorem on the Bypass of the Vertices of the Polyhedron Let us return to problem (2) - (5).
T h e o r e m 2. The solution of the problem (2) - (5) exists and can be always realized at the vertices of the polyhedron M: and the number of switchings does not exceed N; where N – is the number of vertices of polyhedron M: Proof. Consider the sequence vL(t) of simple (step) functions converging to a measurable function v(t); which gives the optimal solution to the problem (9) - (11). and let us solve each task separately, and among the solutions of problem (15) - (17) we will choose the one which has the maximum value of the objective function. (Obviously that this technique makes sense to use only in the proof).
Reasonable computational procedures will be discussed later. Thus, the task is came down to the problem
of the form (19) - (20). This problem is investigated in detail in
This theorem has important corollary.
C o r o l l a r y 1. Let the vector y(1) ∈ RN has a N0 6 N non-zero components. Then, whatever L (the number of splits when constructing difference schemes), the solution of the problem (15) - (17) (and hence (15) - (18) can be realized no more than N0 of mutually orthogonal vectors J : lim vL(t) = v (t);
L!1 lim yL(t) = lim L!1 L!1 0 ∫ t vL( )d → y (t) =
v ( )d : ∫ t 0 Let to each L there is a task (12) - (14), the solution of which, beginning with number N0 due to a corollary of Theorem 1) does not depend on L: Therefore y (t) = {y }; = 1; N0. That is, the solution of problem (9) - (11) is completely determined by the solution of the problem (12) - (14) (finite-dimensional analogue). The transition from problem (9) - (11) to problem (2) - (5) is obvious. Theorem is proven. (15) (16) (17) (18) (19) (20) (21) (22)
Properties of the Solution of the Difference Problem (12) - (14) By theorem 1, a vector y has only one nonzero component all nonzero components of vectors are the components y of the vector y(1): The essence problem (12) - (14) is to find the suitable traversal of vertices of the polyhedron M .
Let us we go back to the maximization of the expression
In
Thus, even in the case of i = 1; to solve problem (22) should be involved methods of search for global extremum. However, the use of conditions(23) in problem (22) when i > 1 allows one to apply the method of branches and boundaries.
Acknowledgements This work was supported by Russian Scientific Foundation, Project 16-11-10352. [Milyutin et al., 2004] Milyutin A. A., Dmitruk A. V., Osmolovskii N. P. (2004). Maximum principle in optimal control Moscow State University, Faculty of Mechanics and Mathematics. Moscow, 168 p. [Dikusar et al., 2001] Dikusar V. V., Koshka M., Figura A. (2001). A Method of continuation on a parameter in solving boundary value problems in optimal control. Differents. equations, 37:4, 453–45. with the sum of the above-diagonal elements 6 + 2 − 7 + 3 − 2 + 10 = 12 satisfying the condition (23), by using the permutation (3; 4; 1; 2) can be reduced to the matrix
0 −6 −2 7 −102 ;
0 −3 2 6 0