# Adaptive Method for Solving Optimal Control Problem with State and Control Variables

Authors: Louadj Kahina; Aidene Mohamed
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

The problem of optimal control with state and control variables is studied. The variables are: a scalar vectorx and the control u(t); these variables are bonded, that is, the right-hand side of the ordinary differential equation contains both state and control variables in a mixed form. For solution of this problem, we used adaptive method and technology of linear programming.


---

## Body

## 1. Introduction

Problems of optimal control have been intensively investigated in the world literature for over forty years. During this period, a series of fundamental results have been obtained, among which should be noted the maximum principle [1] and dynamic programming [2, 3]. Results of the theory were taken up in various fields of science, engineering, and economics.The optimal control problem with mixed variables and free terminal time is considered. This problem is among the most difficult problems in the mathematical theory of control processes [4–7]. An algorithm based on the concept of simplex method [4, 5, 8, 9] so called support control is proposed to solve this problem.The aim of the paper is to realize the adaptive method of linear programming [8]. In our opinion the numerical solution is impossible without using the computers of discrete controls defined on the quantized axes as accessible controls. This made, it possible to eliminate some analytical problems and reduce the optimal control problem to a linear programming problem. The obtained results show that the adequate consideration of the dynamic structure of the problem in question makes it possible to construct very fast algorithms of their solution.The work has the following structure. In Section2, The terminal optimal control problem with mixed variables is formulated. In Section 3, we give some definitions needed in this paper. In Section 4, the definition of support is introduced. Primal and dual ways of its dynamical identification are given. In Section 5, we calculate a value of suboptimality. In Section 6, optimality and ɛ-optimality criteria are defined. In Section 7, there is a numerical algorithm for solving the problem; the iteration consists in two procedures: change of control and change of a support to find a solution of discrete problem; at the end, we used a final procedure to find a solution in the class of piecewise continuous functions. In Section 8, the results are illustrated with a numerical example.


## 2. Problem Statement

We consider linear optimal control problem with control and state constraints:(2.1)J(x,u)=g(x(tf))+∫0tf(Cx(t)+Du(t))dt⟶max⁡x,u,
subject to
(2.2)x˙=f(x(t),u(t))=Ax(t)+Bu(t),0≤t≤tf,x(0)=x0,x(tf)=xf,xmin⁡≤x(t)≤xmax⁡,umin⁡≤u(t)≤umax⁡,t∈T=[0,tf],
where A,B,C, and D are constant or time-dependent matrices of appropriate dimensions, x∈Rn is a state of control system (2.1)–(2.2), and u(·)=(u(t),t∈T), T=[0,tf], is a piecewise continuous function. Among these problems in which state and control are variables, we consider the following problem:
(2.3)J(x,u)=c′x+∫0tfc(t)u(t)dt⟶max⁡x,u,
subject to
(2.4)Ax+∫0t*h(t)u(t)dt,0≤t≤tf,(2.5)x(0)=x0,(2.6)xmin⁡≤x(t)≤xmax⁡,umin⁡≤u(t)≤umax⁡,t∈T=[0,tf],
where x∈Rn is a state of control system (2.3)–(2.6); u(·)=(u(t),t∈T), T=[0,tf], is a piecewise continuous function, A∈Rm×n; c=c(J)=(cj,j∈J); g=g(I)=(gi,i∈I) is an m-vector; c(t), t∈T, is a continuous scalar function; h(t), t∈T, is an m-vector function; umin,umax are scalars; xmin=xmin(J)=(xminj,j∈J), xmax=xmax(J)=(xmaxj,j∈J) are n-vectors; I={1,…,m}, J={1,…,n} are sets of indices.


## 3. Essentials Definitions

Definition 3.1.
A pairv=(x,u(·)) formed of an n-vector x and a piecewise continuous function u(·) is called a generalized control.Definition 3.2.
The constraint (2.4) is assumed to be controllable, that is for any m-vector g, there exists a pair v, for which the equality (2.4) is fulfilled.
A generalized controlv=(x,u(·)) is said to be an admissible control if it satisfies constraints (2.4)–(2.6).Definition 3.3.
An admissible controlv0=(x0,u0(·)) is said to be an optimal open-loop control if a control criterion reaches its maximal value
(3.1)J(v0)=max⁡vJ(v).Definition 3.4.
For a givenɛ≥0, an ɛ-optimal control vɛ=(xɛ,uɛ(·)) is defined by the inequality
(3.2)J(v0)-J(vɛ)≤ɛ.


## 4. Support and the Accompanying Elements

Let us introduce a discretized time setTh={0,h,…,tf-h} where h=tf/N, and N is an integer. A function u(t), t∈T, is called a discrete control if
(4.1)u(t)=u(τ),t∈[τ,τ+h),τ∈Th.
First, we describe a method of computing the solution of problem (2.3)–(2.6) in the class of discrete control, and then we present the final procedure which uses this solution as an initial approximation for solving problem (2.3)–(2.6) in the class of piecewise continuous functions.Definitions of admissible, optimal,ɛ-optimal controls for discrete functions are given in a standard form.Choose an arbitrary subsetTB⊂Th of l≤m elements and an arbitrary subset JB⊂J of m-l elements.Form the matrix,(4.2)PB=(aj=A(I,j),j∈JB;d(t),t∈TB),
where d(t)=∫tt+hh(s)ds, t∈Th.A setSB={TB,JB} is said to be a support of problem (2.3)–(2.6) if detPB≠0.A pair{v,SB} of an admissible control v(t)=(x,u(t),t∈T) and a support SB is said to be a support control.A support control{v,SB} is said to be primally nonsingular if d*j<xj<dj*,j∈JB;f*<u(t)<f*,t∈TB.Let us consider another admissible controlv¯=(x¯,u¯(·))=v+Δv, where x¯=x+Δx,u¯(t)=u(t)+Δu(t),t∈T, and let us calculate the increment of the cost functional
(4.3)ΔJ(v)=J(v¯)-J(v)=c′Δx+∫0tfc(t)Δu(t)dt.
Since
(4.4)AΔx+∫0zh(t)Δu(t)dt=0,
then the increment of the functional equals
(4.5)ΔJ(v)=(c′-ν′A)Δx+∫0tf‍(c(t)-ν′h(t))Δu(t)dt,
where ν∈Rm is called potentials: ν′=qB′Q, qB=(crj,j∈JB;q(t),t∈TB), Q=PB-1, q(t)=∫tt+h‍c(s)ds, t∈Th.Introduce ann-vector of estimates Δ′=ν′A-c′ and a function of cocontrol Δ(·)=(Δ(t)=ν′d(t)-q(t),t∈Th). With the use of these notions, the value of the cost functional increment takes the form
(4.6)ΔJ(v)=Δ′Δx-∑t∈Th‍Δ(t)Δu(t).A support control{v,SB} is dually nonsingular if Δ(t)≠0,t∈TH,Δj≠0,j∈JH, where TH=Th/TB,JH=J/JB.


## 5. Calculation of the Value of Suboptimality

The new controlv¯(t) is admissible, if it satisfies the constraints:
(5.1)xmin⁡-x≤Δx≤xmax⁡-x,umin⁡-u(t)≤Δu(t)≤umax⁡-u(t),t∈T.
The maximum of functional (4.6) under constraints (5.1) is reached for:
(5.2)Δxj=xmin⁡j-xjifΔj>0,Δxj=xmax⁡j-xjifΔj<0,xmin⁡j-xj≤Δxj≤xmax⁡j-xjifΔj=0,j∈J,Δu(t)=umin⁡-u(t)ifΔ(t)>0Δu(t)=umax⁡-u(t)ifΔ(t)<0umin⁡≤Δu(t)≤umax⁡ifΔ(t)=0,t∈Th,
and is equal to
(5.3)β=β(v,SB)=∑j∈JH+‍Δj(xj-xmin⁡j)+∑j∈JH-‍Δj(xj-xmax⁡j)+∑t∈T+‍Δ(t)(u(t)-umin⁡)+∑t∈T-‍Δ(t)(u(t)-umax⁡),
where
(5.4)T+={t∈TH,Δ(t)>0},T-={t∈TH,Δ(t)<0},JH+={j∈JH,Δj>0},JH-={j∈JH,Δj<0}.The numberβ(v,SB) is called a value of suboptimality of the support control {v,SB}. From there, J(v¯)-J(v)≤β(v,SB). Of this last inequality, the following result is deduced.


## 6. Optimality andε-Optimality Criterion

Theorem 6.1 (see [8]).
The following relations:(6.1)u(t)=umin⁡ifΔ(t)>0,u(t)=umax⁡ifΔ(t)<0,umin⁡≤u(t)≤umax⁡ifΔ(t)=0,t∈Th,xj=xmin⁡jifΔj>0,xj=xmax⁡jifΔj<0,xmin⁡j≤xj≤xmax⁡jifΔj=0,j∈J,
are sufficient, and in the case of non degeneracy, they are necessary for the optimality of control v.Theorem 6.2.
For anyɛ≥0, the admissible control v is ɛ-optimal if and only if there exists a support SB such that β(v,SB)≤ɛ.


## 7. Primal Method for Constructing the Optimal Controls

A support is used not only to identify the optimal andɛ-optimal controls, but also it is the main tool of the method. The method suggested is iterative, and its aim is to construct an ɛ-solution of problem (2.3)–(2.6) for a given ɛ≥0. As a support will be changing during the iterations together with an admissible control, it is natural to consider them as a pair.Below to simplify the calculations, we assume that on the iterations, only primally and dually nonsingular support controls are used.The iteration of the method is a change of an “old” control{v,SB} for the “new” one {v¯,S¯B} so that β{v¯,S¯B}≤β{v,SB}. The iteration consists of two procedures:  (1)
change of an admissible controlv→v¯,(2)
change of supportSB→S¯B. Construction of the initial support control concerns with the first phase of the method and can be performed with the use of the algorithm described below.At the beginning of each iteration the following information is stored:(1)
an admissible controlv,(2)
a supportSB={TB,JB},(3)
a value of suboptimalityβ=β(v,SB). Before the beginning of the iteration, we make sure that a support control {v,SB} does not satisfy the criterion of ɛ-optimality.


### 7.1. Change of an Admissible Control

The new admissible control is constructed according to the formulas:(7.1)x¯j=xj+θ0lj,j∈J,u¯(t)=u(t)+θ0l(t),t∈Th,
where l=(lj,j∈J,l(t),t∈Th) is an admissible direction of changing a control v; θ0 is the maximum step along this direction.


#### 7.1.1. Construct of the Admissible Direction

Let us introduce a pseudocontrolv~=(x~,u~(t),t∈T).First, we compute the nonsupport values of a pseudocontrol(7.2)x~j={xmin⁡jifΔj≥0,xmax⁡jifΔj≤0,j∈JH,u~(t)={umax⁡ifΔ(t)≤0,umin⁡ifΔ(t)≥0,t∈TH.
Support values of a pseudocontrol {x~j,j∈JB;u~(t),t∈TB} are computed from the equation
(7.3)∑j∈JB‍A(I,j)x~j+∑t∈TB‍d(t)u~(t)=g-∑j∈JH‍A(I,j)x~j+∑t∈TH‍d(t)u~(t).With the use of a pseudocontrol, we compute the admissible directionl: lj=x~j-xj, j∈J; l(t)=u~(t)-u(t), t∈Th.


#### 7.1.2. Construct of Maximal Step

Sincev¯ is to be admissible, the following inequalities are to be satisfied:
(7.4)xmin⁡≤x¯≤xmax⁡;umin⁡≤u¯(t)≤umax⁡,t∈Th,
that is,
(7.5)xmin⁡≤xj+θ0lj≤xmax⁡,j∈J,umin⁡≤u(t)+θ0l(t)≤umax⁡,t∈Th.
Thus, the maximal step θ0 is chosen as θ0=min{1;θ(t0);θj0}.Here,θj0=minθj:
(7.6)θj={xmaxj-xjljiflj>0,xminj-xjljiflj<0,+∞iflj=0,j∈JB,
and θ(t0)=mint∈TBθ(t):
(7.7)θ(t)={umax⁡-u(t)l(t)ifl(t)>0,umin⁡-u(t)l(t)ifl(t)<0,+∞ifl(t)=0,t∈TB.
Let us calculate the value of suboptimality of the support control {v¯,SB} with v¯ computed according to (7.1): β(v¯,SB)=(1-θ0)β(v,SB). Consequently,(1)
ifθ0=1, then v¯ is an optimal control,(2)
ifβ(v¯,SB)≤ɛ, then v¯ is an ɛ-optimal control,(3)
ifβ(v¯,SB)>ɛ, then we perform a change of support.


### 7.2. Change of Support

Forɛ>0 given, we assume that β(v¯,SB)>ɛ and θ0=min(θ(t0),t0∈TB;θj0,j0∈JB). We will distinguish between two cases which can occur after the first procedure:(a)
θ0=θj0,j0∈JB,(b)
θ0=θ(t0),t0∈TB.Each case is investigated separately.We perform change of supportSB→S¯B that leads to decreasing the value of suboptimality β(v,SB). The change of support is based on variation of potentials, estimates, and cocontrol:
(7.8)ν′=ν+Δν;Δ¯j=Δj+σ0δj,j∈J,Δ¯(t)=Δ(t)+σ0δ(t),t∈Th,
where (δj,j∈J,δ(t),t∈Th) is an admissible direction of change (Δ,Δ(·)) and σ0 is a maximal step along this direction.


#### 7.2.1. Construct of an Admissible Direction(δj,j∈J,δ(t),t∈Th)

First, construct the support valuesδB=(δj,j∈JB,δ(t),t∈TB) of admissible direction(a)θ0=θj0. Let us put
(7.9)δ(t)=0ift∈TB,δj=0ifj≠j0,j∈JB,δj0=1ifx¯j0=xmin⁡j0,δj0=-1ifx¯j0=xmax⁡j0,(b)θ0=θ(t0). Let us put
(7.10)δj=0ifj∈JB,δ(t)=0ift∈TBt0,δ(t0)=1ifu¯(t0)=umin⁡,δ(t0)=-1ifu¯(t0)=umax⁡.
Using the values δB=(δj,j∈JB,δ(t),t∈TB), we compute the variation Δν of potentials as Δν′=δ′BQ. Finally, we get the variation of nonsupport components of the estimates and the cocontrol:
(7.11)δj=Δν′A(I,j),j∈JH,δ(t)=Δν′d(t),t∈TH.


#### 7.2.2. Construct of a Maximal Stepσ0

A maximal step equalsσ0=min(σj0,σt0) with σj0=σj1=minσj,j∈JH;σt0=σ(t1)=minσ(t),t∈TH, where
(7.12)σj={-ΔjδjifΔjδj<0,+∞ifΔjδj≥0,j∈JH,σ(t)={-Δ(t)δ(t)ifΔ(t)δ(t)<0,+∞ifΔ(t)δ(t)≥0,t∈TH.


#### 7.2.3. Construct of a New Support

For constructing a new support, we consider the four following cases:(1)
θ0=θ(t0),σ0=σ(t1): a new support S¯B={T¯B,J¯B} has two following components:
(7.13)T¯B=TB{t0}∪{t1},J¯B=JB,(2)
θ0=θ(t0),σ0=σj1: a new support S¯B={T¯B,J¯B} has the two following components:
(7.14)T¯B=TB{t0},J¯B=JB∪{j1},(3)
θ0=θj0,σ0=σj1: a new support S¯B={T¯B,J¯B} has two following components:
(7.15)T¯B=TB,J¯B=JB{j0}∪{j1},(4)
θ0=θj0,σ0=σ(t1): a new support S¯B={T¯B,J¯B} has two following components:
(7.16)T¯B=TB∪{t1},J¯B=JB{j0},A value of suboptimality for support control β(v¯,S¯B) takes the form
(7.17)β(v¯,S¯B)=(1-θ0)β(v,SB)-ασ0,
where
(7.18)α={|u~(t0)-u¯(t0)|ifθ0=θ(t0),|x~j0-x¯j0|ifθ0=θj0.(1)
Ifβ(v¯,S¯B)>ɛ, then we perform the next iteration starting from the support control {v¯,S¯B}.(2)
Ifβ(v¯,S¯B)=0, then the control v¯ is optimal for problem (2.3)–(2.6) in the class of discrete controls.(3)
Ifβ(v¯,S¯B)<ɛ, then the control v¯ is ɛ-optimal for problem (2.3)–(2.6) in the class of discrete controls.If we would like to get the solution of problem (2.3)–(2.6) in the class of piecewise continuous control, we pass to the final procedure when case 2 or 3 takes place.


### 7.3. Final Procedure

Let us assume that for the new controlv¯, we have β(v¯,S¯B)>ɛ. With the use of the support S¯B we construct a quasicontrol v^=(x^,u^(t),t∈T),
(7.19)x^j={xmin⁡jifΔj>0,xmax⁡jifΔj<0,∈[xminj,xmaxj]ifΔj=0,j∈J.u^(t)={umin⁡,ifΔ(t)<0umax⁡,ifΔ(t)>0,∈[umin⁡,umax⁡],ifΔ(t)=0,t∈Th.
If
(7.20)A(I,J)x^+∫0tfh(t)u^(t)dt=g,
then v^ is optimal, and if
(7.21)A(I,J)x^+∫0tfh(t)u^(t)dt≠g,
then denote T0={ti∈T,Δ(ti)=0}, where ti are zeros of the optimal cocontrol, that is, Δ(ti)=0,i=1,s¯, with s≤m. Suppose that
(7.22)Δ˙(ti)≠0,i=1,s¯.
Let us construct the following function:
(7.23)f(Θ)=A(I,JB)x(JB)+A(I,JH)x(JH)+∑i=0s‍(umax⁡+umin⁡2-umax⁡-umin⁡2sign⁡Δ˙(ti))∫titi+1h(t)dt-g,
where
(7.24)xj=xmin⁡j+xmaxj2-xmaxj-xmin⁡j2sign⁡Δj,j∈JH,t0=0,ts+1=tf,Θ=(ti,i=1,s¯;xj,j∈JB).
The final procedure consists in finding the solution
(7.25)Θ0=(ti0,i=1,s¯;xj0,j∈JB)
of the system of m nonlinear equations
(7.26)f(Θ)=0.
We solve this system by the Newton method using as an initial approximation of the vector
(7.27)Θ(0)=(t¯i,i=1,s¯;x¯j,j∈JB).
The (k+1)th approximation Θ(k+1), at a step k+1≥1, is computed as
(7.28)Θ(k+1)=Θ(k)+ΔΘ(k),ΔΘ(k)=-∂f-1(Θ(k))∂Θ(k)⋅f(Θ(k)).
Let us compute the Jacobi matrix for (7.26)
(7.29)∂f(Θ(k))∂Θ(k)=(A(I,JB);(umin⁡-umax⁡)sign⁡Δ˙(ti(k))h(ti(k)),i=1,s¯)
As detPB≠0, we can easily show that
(7.30)det⁡∂f(Θ(0))∂Θ(0)≠0.For instantst∈TB, there exists a small μ>0 that for any t~i∈[ti-μ,ti+μ],i=1,s¯, the matrix (h(t~i),i=1,s¯) is nonsingular and the matrix ∂f(Θ(k))/∂Θ(k) is also nonsingular if elements ti(k),i=1,s¯,k=1,2,… do not leave the μ-vicinity of ti, i=1,s¯.VectorΘ(k*) is taken as a solution of (4.6) if
(7.31)‖f(Θ(k*))‖≤η,
for a given η>0. So we put θ0=θ(k*).The suboptimal control for problem (2.3)–(2.6) is computed as
(7.32)xj0={x¯j0,j∈JB,x^j,j∈JHu0(t)=umax⁡+umin⁡2-umax⁡-umin⁡2sign⁡Δ˙(ti0),t∈[ti0,ti+10[,i=1,s¯.
If the Newton method does not converge, we decrease the parameter h>0 and perform the iterative process again.


## 7.1. Change of an Admissible Control

The new admissible control is constructed according to the formulas:(7.1)x¯j=xj+θ0lj,j∈J,u¯(t)=u(t)+θ0l(t),t∈Th,
where l=(lj,j∈J,l(t),t∈Th) is an admissible direction of changing a control v; θ0 is the maximum step along this direction.


### 7.1.1. Construct of the Admissible Direction

Let us introduce a pseudocontrolv~=(x~,u~(t),t∈T).First, we compute the nonsupport values of a pseudocontrol(7.2)x~j={xmin⁡jifΔj≥0,xmax⁡jifΔj≤0,j∈JH,u~(t)={umax⁡ifΔ(t)≤0,umin⁡ifΔ(t)≥0,t∈TH.
Support values of a pseudocontrol {x~j,j∈JB;u~(t),t∈TB} are computed from the equation
(7.3)∑j∈JB‍A(I,j)x~j+∑t∈TB‍d(t)u~(t)=g-∑j∈JH‍A(I,j)x~j+∑t∈TH‍d(t)u~(t).With the use of a pseudocontrol, we compute the admissible directionl: lj=x~j-xj, j∈J; l(t)=u~(t)-u(t), t∈Th.


### 7.1.2. Construct of Maximal Step

Sincev¯ is to be admissible, the following inequalities are to be satisfied:
(7.4)xmin⁡≤x¯≤xmax⁡;umin⁡≤u¯(t)≤umax⁡,t∈Th,
that is,
(7.5)xmin⁡≤xj+θ0lj≤xmax⁡,j∈J,umin⁡≤u(t)+θ0l(t)≤umax⁡,t∈Th.
Thus, the maximal step θ0 is chosen as θ0=min{1;θ(t0);θj0}.Here,θj0=minθj:
(7.6)θj={xmaxj-xjljiflj>0,xminj-xjljiflj<0,+∞iflj=0,j∈JB,
and θ(t0)=mint∈TBθ(t):
(7.7)θ(t)={umax⁡-u(t)l(t)ifl(t)>0,umin⁡-u(t)l(t)ifl(t)<0,+∞ifl(t)=0,t∈TB.
Let us calculate the value of suboptimality of the support control {v¯,SB} with v¯ computed according to (7.1): β(v¯,SB)=(1-θ0)β(v,SB). Consequently,(1)
ifθ0=1, then v¯ is an optimal control,(2)
ifβ(v¯,SB)≤ɛ, then v¯ is an ɛ-optimal control,(3)
ifβ(v¯,SB)>ɛ, then we perform a change of support.


## 7.1.1. Construct of the Admissible Direction

Let us introduce a pseudocontrolv~=(x~,u~(t),t∈T).First, we compute the nonsupport values of a pseudocontrol(7.2)x~j={xmin⁡jifΔj≥0,xmax⁡jifΔj≤0,j∈JH,u~(t)={umax⁡ifΔ(t)≤0,umin⁡ifΔ(t)≥0,t∈TH.
Support values of a pseudocontrol {x~j,j∈JB;u~(t),t∈TB} are computed from the equation
(7.3)∑j∈JB‍A(I,j)x~j+∑t∈TB‍d(t)u~(t)=g-∑j∈JH‍A(I,j)x~j+∑t∈TH‍d(t)u~(t).With the use of a pseudocontrol, we compute the admissible directionl: lj=x~j-xj, j∈J; l(t)=u~(t)-u(t), t∈Th.


## 7.1.2. Construct of Maximal Step

Sincev¯ is to be admissible, the following inequalities are to be satisfied:
(7.4)xmin⁡≤x¯≤xmax⁡;umin⁡≤u¯(t)≤umax⁡,t∈Th,
that is,
(7.5)xmin⁡≤xj+θ0lj≤xmax⁡,j∈J,umin⁡≤u(t)+θ0l(t)≤umax⁡,t∈Th.
Thus, the maximal step θ0 is chosen as θ0=min{1;θ(t0);θj0}.Here,θj0=minθj:
(7.6)θj={xmaxj-xjljiflj>0,xminj-xjljiflj<0,+∞iflj=0,j∈JB,
and θ(t0)=mint∈TBθ(t):
(7.7)θ(t)={umax⁡-u(t)l(t)ifl(t)>0,umin⁡-u(t)l(t)ifl(t)<0,+∞ifl(t)=0,t∈TB.
Let us calculate the value of suboptimality of the support control {v¯,SB} with v¯ computed according to (7.1): β(v¯,SB)=(1-θ0)β(v,SB). Consequently,(1)
ifθ0=1, then v¯ is an optimal control,(2)
ifβ(v¯,SB)≤ɛ, then v¯ is an ɛ-optimal control,(3)
ifβ(v¯,SB)>ɛ, then we perform a change of support.


## 7.2. Change of Support

Forɛ>0 given, we assume that β(v¯,SB)>ɛ and θ0=min(θ(t0),t0∈TB;θj0,j0∈JB). We will distinguish between two cases which can occur after the first procedure:(a)
θ0=θj0,j0∈JB,(b)
θ0=θ(t0),t0∈TB.Each case is investigated separately.We perform change of supportSB→S¯B that leads to decreasing the value of suboptimality β(v,SB). The change of support is based on variation of potentials, estimates, and cocontrol:
(7.8)ν′=ν+Δν;Δ¯j=Δj+σ0δj,j∈J,Δ¯(t)=Δ(t)+σ0δ(t),t∈Th,
where (δj,j∈J,δ(t),t∈Th) is an admissible direction of change (Δ,Δ(·)) and σ0 is a maximal step along this direction.


### 7.2.1. Construct of an Admissible Direction(δj,j∈J,δ(t),t∈Th)

First, construct the support valuesδB=(δj,j∈JB,δ(t),t∈TB) of admissible direction(a)θ0=θj0. Let us put
(7.9)δ(t)=0ift∈TB,δj=0ifj≠j0,j∈JB,δj0=1ifx¯j0=xmin⁡j0,δj0=-1ifx¯j0=xmax⁡j0,(b)θ0=θ(t0). Let us put
(7.10)δj=0ifj∈JB,δ(t)=0ift∈TBt0,δ(t0)=1ifu¯(t0)=umin⁡,δ(t0)=-1ifu¯(t0)=umax⁡.
Using the values δB=(δj,j∈JB,δ(t),t∈TB), we compute the variation Δν of potentials as Δν′=δ′BQ. Finally, we get the variation of nonsupport components of the estimates and the cocontrol:
(7.11)δj=Δν′A(I,j),j∈JH,δ(t)=Δν′d(t),t∈TH.


### 7.2.2. Construct of a Maximal Stepσ0

A maximal step equalsσ0=min(σj0,σt0) with σj0=σj1=minσj,j∈JH;σt0=σ(t1)=minσ(t),t∈TH, where
(7.12)σj={-ΔjδjifΔjδj<0,+∞ifΔjδj≥0,j∈JH,σ(t)={-Δ(t)δ(t)ifΔ(t)δ(t)<0,+∞ifΔ(t)δ(t)≥0,t∈TH.


### 7.2.3. Construct of a New Support

For constructing a new support, we consider the four following cases:(1)
θ0=θ(t0),σ0=σ(t1): a new support S¯B={T¯B,J¯B} has two following components:
(7.13)T¯B=TB{t0}∪{t1},J¯B=JB,(2)
θ0=θ(t0),σ0=σj1: a new support S¯B={T¯B,J¯B} has the two following components:
(7.14)T¯B=TB{t0},J¯B=JB∪{j1},(3)
θ0=θj0,σ0=σj1: a new support S¯B={T¯B,J¯B} has two following components:
(7.15)T¯B=TB,J¯B=JB{j0}∪{j1},(4)
θ0=θj0,σ0=σ(t1): a new support S¯B={T¯B,J¯B} has two following components:
(7.16)T¯B=TB∪{t1},J¯B=JB{j0},A value of suboptimality for support control β(v¯,S¯B) takes the form
(7.17)β(v¯,S¯B)=(1-θ0)β(v,SB)-ασ0,
where
(7.18)α={|u~(t0)-u¯(t0)|ifθ0=θ(t0),|x~j0-x¯j0|ifθ0=θj0.(1)
Ifβ(v¯,S¯B)>ɛ, then we perform the next iteration starting from the support control {v¯,S¯B}.(2)
Ifβ(v¯,S¯B)=0, then the control v¯ is optimal for problem (2.3)–(2.6) in the class of discrete controls.(3)
Ifβ(v¯,S¯B)<ɛ, then the control v¯ is ɛ-optimal for problem (2.3)–(2.6) in the class of discrete controls.If we would like to get the solution of problem (2.3)–(2.6) in the class of piecewise continuous control, we pass to the final procedure when case 2 or 3 takes place.


## 7.2.1. Construct of an Admissible Direction(δj,j∈J,δ(t),t∈Th)

First, construct the support valuesδB=(δj,j∈JB,δ(t),t∈TB) of admissible direction(a)θ0=θj0. Let us put
(7.9)δ(t)=0ift∈TB,δj=0ifj≠j0,j∈JB,δj0=1ifx¯j0=xmin⁡j0,δj0=-1ifx¯j0=xmax⁡j0,(b)θ0=θ(t0). Let us put
(7.10)δj=0ifj∈JB,δ(t)=0ift∈TBt0,δ(t0)=1ifu¯(t0)=umin⁡,δ(t0)=-1ifu¯(t0)=umax⁡.
Using the values δB=(δj,j∈JB,δ(t),t∈TB), we compute the variation Δν of potentials as Δν′=δ′BQ. Finally, we get the variation of nonsupport components of the estimates and the cocontrol:
(7.11)δj=Δν′A(I,j),j∈JH,δ(t)=Δν′d(t),t∈TH.


## 7.2.2. Construct of a Maximal Stepσ0

A maximal step equalsσ0=min(σj0,σt0) with σj0=σj1=minσj,j∈JH;σt0=σ(t1)=minσ(t),t∈TH, where
(7.12)σj={-ΔjδjifΔjδj<0,+∞ifΔjδj≥0,j∈JH,σ(t)={-Δ(t)δ(t)ifΔ(t)δ(t)<0,+∞ifΔ(t)δ(t)≥0,t∈TH.


## 7.2.3. Construct of a New Support

For constructing a new support, we consider the four following cases:(1)
θ0=θ(t0),σ0=σ(t1): a new support S¯B={T¯B,J¯B} has two following components:
(7.13)T¯B=TB{t0}∪{t1},J¯B=JB,(2)
θ0=θ(t0),σ0=σj1: a new support S¯B={T¯B,J¯B} has the two following components:
(7.14)T¯B=TB{t0},J¯B=JB∪{j1},(3)
θ0=θj0,σ0=σj1: a new support S¯B={T¯B,J¯B} has two following components:
(7.15)T¯B=TB,J¯B=JB{j0}∪{j1},(4)
θ0=θj0,σ0=σ(t1): a new support S¯B={T¯B,J¯B} has two following components:
(7.16)T¯B=TB∪{t1},J¯B=JB{j0},A value of suboptimality for support control β(v¯,S¯B) takes the form
(7.17)β(v¯,S¯B)=(1-θ0)β(v,SB)-ασ0,
where
(7.18)α={|u~(t0)-u¯(t0)|ifθ0=θ(t0),|x~j0-x¯j0|ifθ0=θj0.(1)
Ifβ(v¯,S¯B)>ɛ, then we perform the next iteration starting from the support control {v¯,S¯B}.(2)
Ifβ(v¯,S¯B)=0, then the control v¯ is optimal for problem (2.3)–(2.6) in the class of discrete controls.(3)
Ifβ(v¯,S¯B)<ɛ, then the control v¯ is ɛ-optimal for problem (2.3)–(2.6) in the class of discrete controls.If we would like to get the solution of problem (2.3)–(2.6) in the class of piecewise continuous control, we pass to the final procedure when case 2 or 3 takes place.


## 7.3. Final Procedure

Let us assume that for the new controlv¯, we have β(v¯,S¯B)>ɛ. With the use of the support S¯B we construct a quasicontrol v^=(x^,u^(t),t∈T),
(7.19)x^j={xmin⁡jifΔj>0,xmax⁡jifΔj<0,∈[xminj,xmaxj]ifΔj=0,j∈J.u^(t)={umin⁡,ifΔ(t)<0umax⁡,ifΔ(t)>0,∈[umin⁡,umax⁡],ifΔ(t)=0,t∈Th.
If
(7.20)A(I,J)x^+∫0tfh(t)u^(t)dt=g,
then v^ is optimal, and if
(7.21)A(I,J)x^+∫0tfh(t)u^(t)dt≠g,
then denote T0={ti∈T,Δ(ti)=0}, where ti are zeros of the optimal cocontrol, that is, Δ(ti)=0,i=1,s¯, with s≤m. Suppose that
(7.22)Δ˙(ti)≠0,i=1,s¯.
Let us construct the following function:
(7.23)f(Θ)=A(I,JB)x(JB)+A(I,JH)x(JH)+∑i=0s‍(umax⁡+umin⁡2-umax⁡-umin⁡2sign⁡Δ˙(ti))∫titi+1h(t)dt-g,
where
(7.24)xj=xmin⁡j+xmaxj2-xmaxj-xmin⁡j2sign⁡Δj,j∈JH,t0=0,ts+1=tf,Θ=(ti,i=1,s¯;xj,j∈JB).
The final procedure consists in finding the solution
(7.25)Θ0=(ti0,i=1,s¯;xj0,j∈JB)
of the system of m nonlinear equations
(7.26)f(Θ)=0.
We solve this system by the Newton method using as an initial approximation of the vector
(7.27)Θ(0)=(t¯i,i=1,s¯;x¯j,j∈JB).
The (k+1)th approximation Θ(k+1), at a step k+1≥1, is computed as
(7.28)Θ(k+1)=Θ(k)+ΔΘ(k),ΔΘ(k)=-∂f-1(Θ(k))∂Θ(k)⋅f(Θ(k)).
Let us compute the Jacobi matrix for (7.26)
(7.29)∂f(Θ(k))∂Θ(k)=(A(I,JB);(umin⁡-umax⁡)sign⁡Δ˙(ti(k))h(ti(k)),i=1,s¯)
As detPB≠0, we can easily show that
(7.30)det⁡∂f(Θ(0))∂Θ(0)≠0.For instantst∈TB, there exists a small μ>0 that for any t~i∈[ti-μ,ti+μ],i=1,s¯, the matrix (h(t~i),i=1,s¯) is nonsingular and the matrix ∂f(Θ(k))/∂Θ(k) is also nonsingular if elements ti(k),i=1,s¯,k=1,2,… do not leave the μ-vicinity of ti, i=1,s¯.VectorΘ(k*) is taken as a solution of (4.6) if
(7.31)‖f(Θ(k*))‖≤η,
for a given η>0. So we put θ0=θ(k*).The suboptimal control for problem (2.3)–(2.6) is computed as
(7.32)xj0={x¯j0,j∈JB,x^j,j∈JHu0(t)=umax⁡+umin⁡2-umax⁡-umin⁡2sign⁡Δ˙(ti0),t∈[ti0,ti+10[,i=1,s¯.
If the Newton method does not converge, we decrease the parameter h>0 and perform the iterative process again.


## 8. Example

We illustrate the results obtained in this paper using the following example:(8.1)∫025u(t)dt⟶min⁡,x˙1=x3,x˙2=x4,x˙3=-x1+x2+u,x˙4=0.1x1-1.01x2,x1(0)=0.1,x2(0)=0.25,x3(0)=2,x4(0)=1,x1(25)=x2(25)=x3(25)=x4(25)=0,xmin⁡≤x≤xmax⁡,0≤u(t)≤1,t∈[0,25].Let the matrix be(8.2)A=(00100001-11000.1-1.0100),h(t)=(1000010000100001),g=(0000),xmin⁡=(-4-4-4-4),xmax⁡=(4444).We introduce the adjoint system which is defined as(8.3)ψ1=-ψ3+0.1ψ4,ψ2=ψ3-1.01ψ4,ψ3=ψ1,ψ4=ψ2,ψ1(tf)=0,ψ2(tf)=0,ψ3(tf)=0,ψ4(tf)=0.Problem (8.1) is reduced to canonical form (2.3)–(2.6) by introducing the new variable x˙5=u,x5(0)=0. Then, the control criterion takes the form -x5(tf)→max. In the class of discrete controls with quantization period h=25/1000=0.0025, problem (8.1) is equivalent to LP problem of dimension 4×1000.To construct the optimal open-loop control of problem (8.1), as an initial support, a set TB={5,10,15,20} was selected. This support corresponds to the set  of nonsupport zeroes of the cocontrol Tn0={2.956,5.4863,9.55148,12.205,17.6190,19.0372}. The problem was solved in 26 iterations, that is, to construct the optimal open-loop control, a support 4×4 matrix was changed 26 times. The optimal value of the control criterion was found to be equal to 6.602054 in time 2.92.Table1 contains some information on the solution of problem (8.1) for other quantization periods.Table 1
h
Number of iterations
Value of the control criterion
Time
0.25
11
6.624333
2.72
0.025
18
6.602499
2.85
0.001
32
6.602050
3.33Of course, one can solve problem (8.1) by LP methods, transforming the problem (4.6)–(7.8). In doing so, one integration of the system is sufficient to form the matrix of the LP problem. However, such “static” approach is concerned with a large volume of required operative memory, and it is fundamentally different from the traditional “dynamical” approaches based on dynamical models (2.3)–(2.6). Then, problem (2.3)–(2.6) was solved.In Figure1, there are control u(t) and switching function for minimum principle. In Figure 2, there is phaseportrait (x1,x3) for a system (8.1). In Figure 3, there are state variables x1(t),x2(t) for a system (8.1). In Figure 3, state variables x3(t),x4(t) for a system (8.1). In Figure 4, state variables x1(t),x2(t) for a system (8.1).Figure 1
Optimal controlu(t) and switching function.Figure 2
Phaseportraitx1(t),x3(t).Figure 3
Optimal state variablesx1(t),x2(t).Figure 4
Optimal state variablesx3(t),x4(t).



---

*Source: 209329-2012-07-25.xml*