SUPPORT METHOD FOR OPTIMAL CONTROL
OF LINEAR DYNAMICAL SYSTEM
Nguyen CHAN
Center for System
and Management Research
P.O. Box 626, Bo Ho, Hanoi
VIETNAM
ABSTRACT. In this paper we construct a method for solving
the problem of optimizing the maximal deviation of the real
plan (or the trajectory, the technological process...) from
some ideal one. The mathematical model of the dynamical
system being considered is a system of linear differential
equations with a control function. The method is based on
some ideas of the so-called support method proposed by R.
Gabasov and F.M. Kirillova.
After introducing support controls and establishing
their relation with controllability of the system, we de-
rive a criterion (which can be easily verified) for a sup-
port control to be optimal. Then we briefly describe an
iteration for improving the existing control if it has not
been optimal yet. Finally we present an illustrative
example.
I.PROBLEM STATEMENT
Many situations arising from economic and technical
practice can be formulated in the form of the following
problem: Minimize the functional
L(y,u(.))=A= max§]a'x(t)-o(t)|, te t= [o,0°], (r)
with respect to the control (y,u(.)) and the phase trajec-
tory x(.) which satisfy the constraints:
x(t)= A(t)x(t)+b(t)u(t)te(t), bE, (2)
x(0)= x,t Gy, YS ye y*, (3)
usu(t)eu", te T, Hx(t™)= bh (4)
Here x(t) is the state of the dynamical system (2),x(t)
€R", a(t) is an (nxn)-matrix, b(t)e R", c(t)eR", u(t) is
the scalar control function, té 71, y is the control para-
meter, yé R, G is an (nxr)-matrix, H is an (mxn)-matrix,
rank H= mén, x,€ R™, dé R", heR™, a'd(t)#0, te, the
symbol ' denotes transposition of vector or matrix, all
the vectors are column vectors.
For example if x; (t) is the quantity of the i-th type
Page 98
System Dynamics '91 Page 99
product, i= I1,2,...,n, y is the control of the store at the
initial time moment, u(t) is the control of the technologi-
cal process, c(t) is the wear and tear, x(t) is the given
in advance ideal plan of production at time moment t. Then
L(y,u(.)) will be the maximal deviation from the given plan
which we seek to minimize.
The problem (I)-(4), as we can see from the minimax and
the absolute-value function in (I), is non-smooth and clo-
sely related to optimal control problems with state const-
raints. It is known that such class of problems is especi-
ally complicated to solve numerically and in recent years
considerable efforts have been made to construct efficient
methods and algorithms. In (Chan I986, 1989) we investiga-
ted some simplified versions of the problem with o(t)=nK,
A(t)= A, b(t)= b, c(t)= 0, G=0. Moreover, the results gi-
ven in those papers were based on a strong non-singularity
property of so-called support controls. In the present pa-
per we shall consider another non-singularity property
which seems to be the most natural one for the problem .
This essential improvement became possible thanks to a new
approach to prove the optimality criterion with using ano-
ther type of control variations and applying the implicit
function theorem. We exploit here mainly the ideas of Ga-
basov - Kirillova's support method which has been success-
fully used to solve a wide class of optimization problems
(Gabasov and Kirillova 1980, 1984).
The plan of the paper is as follows. In Section 2 we
introduce a support, a support control, and show the rela-
tion between existence of support and controllability, in
a certain sense, of the system. An optimality criterion
for a support control will be established in Section 3.
Section 4 is devoted to description of a scheme for nume-
vical solution of the problem. Finally, in Section 5 we
present an illustrative example.
2.SUPPORT AND CONTROLLABILITY
In the following an admissible control is any pair (y,
u(.)) where y is an r-vector, u(.) is piece-wise continu-
ous function, which satisfy all the cogstgaints (2)-(4).
We says that the admissible control (y",u°(.)) is optimal
iff Beh < L(y,u(.)) for every admissible control
(y,ut.
*Let (y,u(.)) be an admissible control and the maximum 4
(see(I)) be attained on the set 1 of segments or isolated
. . mX_ xi i ae =
points: T= Ls : [e, ,crl]oa, Meer <siiy ier} where
I is a finite index set. Moreover, Genote Lefier: min
*o. . i
fact), vertf-of, Tefier: minfo(t), tem t= of, t=
Page 100 System Dynamics '91
fos ie rg, wtejat, ier"l, w(t) (t) for tem, =
wot) for tene* where w(t)= a'x(t)-x(t)+A(the lower devi-
ation), wt) = Aare (6), téT (the upper deviation).
Definition 2.1 (support controllability). The deviation
w(.) is said to be controllable on T2 provided - that for
any piece-wise-smooth function z2(.)= fate) ene ) there is
such variation Ay, 4u(t), téT and AA that
a'dx(tg AA=2(t), tem , (5)
HAx(t” ) = 0 x (6)
where 9;= 4 aif iél, , “2ifiel,
AOE - peath) Be ales tet, (7)
On gx equation (5) is equivalent to the following con-
ditions:
a'dx(t,)+ 9, Ar=2(2;), (8)
a@Ax(t)= 2(t). (9)
Combining (9) with (7), we obtain
Au(t) = [2(t)-d' a(t )Ax(t)J/a'o(t), (Io)
Ax(t) = A,(6)Ax(t) + b(t) 2(t) (11)
where A.(t) =[B-b(t)a'/a'b(t)] A(t), bft)= b(t)/a'b(t), té
si » Eis the identity diagonal matrix.
Denote by F(t,v), téT, the solution of the matrix dif-
ferential equation
-F(t,7)A(C), CE m= = o\%,
aECH20/80=9 acuays,(e),ten8 St,
F(t,t)=E,
and put F(t,?)=0 for %>t. Using the Cauchy formula for a
solution x(.) of the differential equation (7) (for té
1) and (II)(for +é¢T%), we rewrite (8) and (6) into the
form
a'R( 7, ,0)Gdy + J a'R(G, ,t)b(t)Au(t)at+ 9,4 =
cg
n
System Dynamics '91 Page 101
12(eq) +208) + f np, Cere(rrar, (12)
"3
HE(t* ,o)Gdy + 5 ER(t* ,t)b(t)du(t)at = Fi2(t,) +
Ty
race) + f nceyecejae (a5)
mx
8
where all the vectors z(t) =(2(7,),...,2(U-)))', 2(e)=
a 4 |x|
(2(04),...,2(8 Ith). (the symbol |I|stands for the number
of elements of the set 1), ¥y=(Siqseeer Mi igp)"s X*= a
von sb in )', the matrices F, and F°, and the functions
hp, (%), VET, iét; ao(©), vere can be computed from the
data of the problen.
Thus we obtain a system of /I|+m linear algebraic equa-
tions with respect to unknowns Ay, Au(t), té ox ana MA.
Controllability of the deviation a(.) on m= means that
the system (I12)-(13) is solvable for every value of the
right-hand side. We are going now to establish a construc-
tive condition for solvability of the system, To this end
we define the (|I/+m)xr matrix
os
pe. (;
poe
where 708 ‘ene
LE
G
) , PB. HE(t",0)G and let pp=
os °
é be the k-th column of P°, ké K=4,..0 26.
Theorem 2.1. For controllability of the deviation a(.)
on big it is necessary and sufficient that there exist
such columns Pes ké KgC K, and points t5é a, jéd, that
one of two the following cases takes place:
a) (simple case): [K,/+/3|=/I/+m and det P,#0 where
the matrix
Page 102 System Dynamics '91
a'B(r, sb 5)B(t5), Jed
Po= | Pg it P= (pf, ke Ky)
* 2
HE(t,t5)b(t5)
os
: (3 ) .
oc ?
Ps
b) (main case): [Kg [+ o|=[z]+m-4 and det P, # O where
the matrix
a'B(Y, t5)b(5), jéed Si
iél
HR(t™ ,¢5)b(t 5) t)
(Here one of the sets Kg and J may be empty).
To prove Theorem 2.I one has to note that if, for exam-
ple, the case a) is realized, then there exists such a
neighbourhood N, of the point it, jEéd, that det B # 0
where the matrix
= co}
Pg = | Fg
S ance, ervce), sea
Ny
P= Pg iél
s HE(t* ,t)b(t)at
Ny
Moreover, if ale), kéK, are continuous linearly inde-
pendent in T functions, then there exist such xl points
t.€T, jJEK, that the matrix (a,(t5)) . is non-singular.
5) d°° kK,
In the main case, considering Au(t) = const in a small
interval t[j] of tj jéd, and then taking the limits as
the length of the intervals converges to 0, formally we
come to the following formula which plays an important
part in the rest of the paper:
MA= 5h Avy +f A (e)du(t at os 4,(t)2(e)at +
n s (I4)
ZA, (826%) + Stacety ]
iét
System Dynamics '91 Page 103
where dy, Ayy, A(t), tem, A(t), tee, 6, ot, ied,
can be computed from the data of the problem, ay is the
last line of the matrix Q,= Pst.
Furthermore, denote wg =ft5, jest, macs Une, ot.
a\ny . te fTe ey we Ue.
Definition 2.2. We say that the set Ky Ts ¢ is a_support,
the set o is a dynamical support, the set SK 3 isa
working support of the problem iff det P gt Oo.
Definition 2.3. The pair igen. Kgs by =f where Cy,u(.))
is an admissible control and 3K, at is a support, is,cal-
led asi rol. We say the a support control zy,
u(.); Ky,T gis optimal,if the control (y,u(.)) is optimal,
and non-singular,if it possesses two the following proper-
ties:
i) Yen < I< ve > KEKy 4 wsu(t)<ur ’ bens 3
x
M(t)>0, t¢ TE, , w(t)>0, t ¢ at
ii) every tjECS is either a continuity point of
the control function u(.) and then us u(t 5)<u" or
a discontinuity point of ul.).
We are ready now to establish the following
3.OPTIMALITY CRITERION
Theorem 3.1. The main case and the following relations
are necessary and sufficient for optimality of a non-sin-
gular support control zy sul. )3Kg.2 sf?
20, Y= Vyy >
One *) $9 Fe= Ves (15)
*
#05 Ji < Wye < Wyo KE Ky 5
Page 104 System Dynamics '91
>0, u(t)= wos
A440, ult)= a" , (16)
=0, u< u(t) < u*, tem 3
2 £0, wX(t)=0
Ag(t) 20, Ww (t)=0, A(t ? é , (17)
=0, % (t)>0, =0, W(t)>0,
very, ters",
e 0, B(%)=0, ae pay
il = 0,@ (t,)>0, 5 (=0, w (v*)>0,
iéL
%?
(18)
ee wo) =0, ihe w()=0,
i *
tL 0, wu)>0, =0,4 (v*)>0,
ier”.
The proof of Theorem 3.I is not simple and needs more
than one page. To prove the necessity one has to consider
control variations of the following type:
O, tEN(t,)s
x; signé,, teft,.t5+ é5¢ » JETy, 00K, <
jutt)e minju(t)-u, , u*-u(t), te[t,-é,t,te]f, |e|<e,
[act ,)-uce,+ 0)] signe, : betes ty +éh,d€ J,
© otherwise, seme )
where t, is a point of oe where the relations (15)-(18)
do not hold, N(t,) is a small neighbourhood of t,, J, is
the set of continuity points of u(.), 3,= I\Tqs éisa
given positive number, and to apply the implicit function
pyeonen to the following (|1(+m)-dimensional vector-func-
ion
£'(0;4y, ke Kgs £523 5,44) = (®g 4yg)' +
System Dynamics '91 Page 105
8 i a'R(G, ,t)b(t)as + 2, f a' R(t; ,%). '
N(t, ) Jed, ftj.t5 t+ e5? nc
sb(t)at X; signe, + 7 J a' F(t, »tyb(t)ab. Fe
+ Ge i 1;
€d, fests + & ¢
-[a(tj)-a(t + 0)Jsigné, + g4a, tel, (6 § HE(t* jt). i
N(t, ) |
*
b(tat+ 2 f a'E(G ,t)b(t)at «signe,
JET, ftgrt y+ yf
g 2 a(t” st)b(¢)at [a(t 5)-u(t 5+ 0)] sign Li
3 6]
Jeg, ftgst,t ef |
&)' . Note that the sufficiency remains valid for any at
(not’ necessarily non-singular) support control.
4.CONTROL IMPROVEMENT zB
Assume that the support control fyul.) Kyo, ¢ being y
considered does not satisfy the optimality criterion yet. |
We are going now to describe briefly an iteration of the Be
procedure of mee the support control. ,
I |
Using the formula (14), we seek to minimize AA subject
to the constraints
(7s ¥ ~ys Ay cy*~y, Aye R™; Hdx(t*) =05 as
wy -u(t)< Au(t) u‘-u(t), te@. |
To this end we take positive parameters Ga Gg1Gs g
and define sets
s={tem : (Ac bG os sp-{eeak: At> Gy,
sy=ftem: A(t) <-6.$, myalq, %t 1), N= |
Cet-,ct], ny = LY, Muay NT).
Put ; x ,
Ayg= 5 GgrV) 4£ Fye> Os =H -¥,) if Ane
40, =O if Oy,=0, k eky y (20)
Page 106 System Dynamics '91
Au(t)= -6,Lace) + sign Ad, tE8,,020,4 4, (21)
a'dx(t)+ AA=-6,03(t), te sy\ M3 (22)
athx(t)-Ar=@,0%(t), tesr\n,, 066,21. (23)
Furthermore, assume that Ny
lities:
cee. Here are three possibi-
1) S A,cora carat > max§t, 6,4(%)? + In this case
il
we introduce the condition (22) for Nias
2) Fyu(C)e maxSE, f Ag(tay (tar? : Introduce
“il
a new condition: a'Ax(v,)+A4A=-G,n(t,), 0¢ 9,4 4;
5) E> max $6,22(%), By Ag(t)eo (tare: We take out
the interval Nj, from the set Nj. .
Analogously we consider every interval Nui Ny, let.
Goo system of conditions will be numbered by
es
The problem (I)-(4) formulated in terms of variations
Ay, Au(t), té1,Aa, with the additional constraints (20)
-(24) is called a continuous support problem. Dividing
the set T\(s,U Sf U SZ UN,) into intervals 1/,)= [tps
£0], 6-0.) 1, and putting Au(t)= vy), te Bp 5
réR, we arrive at a discrete support problem in the spa-
ce of Ayg= Ay, 2ke Kg), Vi» TER, AA, g veers Oy» Which
may be solved by the method of (Gabasov-Kirillova 1980).
Thus transition to a new (improved) support control is
completed.
5. EXAMPLE
To illustrate the method described in Secs. 2-4 we ta-
ke the following example: Minimize the functional
L(y u(.))= max$/x(t), ¢€2=[-45 4]
subject to the constraints
xX (t)- x(t) = u(t), tet; x(0)=x(0)=0, x(O)= y,
aéyS2, |u(t)/24, tet, (et4)x(4)- (6-4)X (4) =e-4 .
System Dynamics '91 Page 107
Note that x(0)=y 24. Therefore we have always L(y,u(.))
24.Moreover we shall consider only odd control functions
u(t) =-u(-t), -12t<0. .
We begin at the initial control y=1, u(.)20. For this
ponte a have ¥(t)=/exp(t) + exp(-t)]/2. Hence L(1;0) =
(e+t/e)/2. .
The computations of Secs. 2-4 lead to the optimal cont-
rol yO=1, u(t)=-1, O<¢21, u(b)=4, -1gb <0 with
L(y? u°(.))=4
REFERENCES
Gabasov, R. and Kirillova, F.M. 1980. Methods for Linear
Programming. Part 3: Special Problems. Minsk: University
Press.
Gabasov, R. and Kirillova, F.M. 1984. Constructive Methods
of Optimization. Part 2: Control Problems. Minsk: Universi-
ty Press. ;
Nguyen Chan 1986. Direct Support Method for Solving a Con-
tinuous-Time Minimax Optimal Control Problem in Linear Or-
dinary Systems. Doklady of the Byelorussian Academy of Sci-
ences. 6: 500-503.
Nguyen Chan 1989. Support Method for Solving a Linear Mi-
cae Problem of Optimal Control. Optimization. 20, 4:
3-50L.
