This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
(M) consisting of .Notice also that observability is a global concept; it gl'· .. ,gn' and by § the smallest linear subspace of rmght be necessary to travel a considerable distance or for C~(M) containing go which is closed with respect to Lie a long time to distinguish between points of M. Therefore differentiation by elements of ~ 0. An element of § is a we introduce a local concept which is stronger than ob- finite linear combination of functions of the form servability. Let U be a subset of M and xo,x lEU. We say 1 O X is Uslndistinguishable from xl (xOlux ) if for every control (U(/),[tO,/I]), whose trajectories (xo(t),[tO,t 1]) and where fj(x) = f(x,u j ) for some constant u' EQ. (x1(t),[tO,t 1) from XO and Xl both lie in U, fails to If h1,h2EGX(M) and cpECCXl(M) then distinguish between XO and Xl, i.e., if xO(t)E U and x1(t)E l U for tE[tO,t ] , then L (L (cp)) - L (L (q») = L h ] ( cp). hl ( t,x),p( x), v( I,A,e») restrictive than the usually given condition j(x A+x B)+ 8 and QB analogously
h2
h2
1h"
hl
2
From this it follows that § is closed under Lie differentiaU-indistinguishability is not, in general, an equivalence relation on U for it fails to be transitive. This is related to the fact that I restricted to U is not necessarily complete. (See Sussmann [27] for a fuller discussion of this point.) However, we can still define ~ to be locally observable at XO if f~r every open neighborhood U of xO, I u( x 0.> = { x°), and ~ IS locally observable if it is so at every x E M. On the other hand one can weaken the concept of observability; in practice it may suffice to be able to distinguish xO from its neighbors. Therefore we define ~ to be weakly observable at XO if there exists a neighborhood U of XO such that I (x~ n U = {XO} and ~ is weakly observable if it is so at every x EM. Notice once again that it may be necessary to travel considerably far from U to distinguish points of U, so we make a last definition, ~ is locally weakly observable at XO if there exists an open neighborhood U of XO such that for every open neighborhood V of XO contained in U, Iv(x~ == {x"] and is locally weakly observable if it is so at every x EM. Intuitively, ~ is locally weakly observable if one can instantaneously distinguish each point from its neighbors. It can easily be seen that the relationships between the various forms of observability parallel that of controllability, i.e., ~
locally observable Jj, ~ locally weakly observable
=>
~
observable
~
~
weakly observable.
JJ
tion by elements of Cj" also. Let ex *(M) denote the real linear space of one forms on M, i.e., all finite C~(M) linear combinations of gradients of elements of COO(M). These are represented by row m-vector valued functions of x. The pairing between one forms and vector fields denoted by (w,h>E COO(M) is just multiplication of 1 X m and m X 1 matrix valued functions of x. We define a subset of ~X,*(M) by d§o={dq>:
Lh(w)(x) =(
a;:* (S)h(x»)*+w(x) ~~(x)
where wE 'X *(M), hE 'X(M) and * denotes transpose. The three kinds of Lie differentiation are related by the following Liebnitz-type formula
Lh l (W,h2 ) = (Lh rw,h 2 )
+ (w, [ h"h 2 ]>.
If w = dq;, then L h and d commute i, ( dcp) = d ( i; (cP)). From this it follows that d§ is the smallest linear space of one forms containing dgG which is closed with respect to Lie differentiation by elements of ~ 0 (or 'J). Elements of d§ are finite linear combinations of one forms of the form
In general there are no other implications but for autonomous linear systems it can be shown that all four are wherejj(x)=f(x,uJ ) for some constant uJEn. As before equivalent. The advantage of local weak observability we denote by d§ (x) the space of vectors obtained by over the other concepts is that it lends itself to a simple evaluat!ng the elements of d~ at x. The space d§ (x") algebraic test. To describe it we need some additional determines the local weak observability of L at xo. L is tools. said to satisfy the obseroability rank condition at XO if the Let CCX)(M) denote the infinite dimensional real vector dimension of' d§ (x") is m, L satisfies the obseroability space of all Coo real valued functions on M. Elements of rank condition. if this is true for every x E M. CX(M) act as linear operators on CCX)(M) by Lie difTheorem 3.1: If ~ satisfies the observability rank conferentiation. If hECX(M) and cpECOO(M) then L,,(tp)E dition at XO then ~ is locally weakly observable at xc. C~(M) is given by The proof depends on the following. Lemma 3.2: Let V be any open subset of M. If xu, x 1 E V and xOlvx 1 then q;(X~=
Proof" If xOIVX I then for any k >0, any constant controls u 1,. •• ,Uk EQ, small Sl'·· ,Sk ~o and gi' i= I,. · . ~n, we have f·
1
-1
Here y;(x) denotes the flow offi(x)=f(x,u i ) . Differentiating with respect to Sk" • • ,Sh at 0 yields
-1
Fig. 1. Dynamics and observers of Example 3.4.
g is spanned by functions of this form so the lemma
0
follows.
maximal rank. A necessary and sufficient condition for
Proofof Theorem 3.1: If the dimension of dg (x") = m the quotient topology on M / R to be Hausdorff is that R then there exists m functions {J)I'·· ,qJmE§ such that be a closed equivalence relation, that is, the graph of R be a dfP(x~,· · • ,dCPm(x~ are linearly independent. Define a closed subset of M X M. An equivalence relation R which map admits a Coo structure on M / R compatible with the projection is called regular. A necessary and sufficient condition for regularity is that the graph of R be a The Jacobian of
It is not hard to see using the continuity of solutions of I v(x~ = {xo} so ~ is locally weakly observable at xo. 0 differential equations with respect to initial conditions From. this we see that if ~ satisfies the observability that for any Coo system L the relation I is closed. Howrank condition then ~ is locally weakly observable. The converse is almost true as we shall see later on in Theo- ever, the following example due to Sussmann shows that it need not be regular even when the controllability and rems 3.11 and 3.12. observability rank conditions are satisfied. Suppose (~, x~ is a realization of an input-output map Example 3.4.· Let uEQ={(Ut,U2):Uj >O) xEM=R, Y which is not observable in any of the above senses. We 2 ER and tum our attention to finding such a realization (~',z~ of x= UtI} (x) + u2f2 (x) the same input-output map. To understand the difficulties involved consider the following. YI=gl(X), Y2=g2(X). Example 3.3: Let uEfl=R, xEM=R,yER 2, x(O)= We choose ./;,gj :R~R to be C'" functions with the xO=O, and following graphs. See Fig. 1. x=u Y.=cosx Y2=SlnX. Since 11 and 12 have no common zeros the system satisfies the controllability rank condition and is locally Clearly the system satisfies both controllability and ob- weakly controllable. Since dg, and d82 have no common servability rank conditions. Therefore, it is locally weakly . zeros -the system satisfies the observability rank condition controllable and locally weakly observable. It is not ob- and is locally weakly observable. k=xo+2k." servable because XO and x are indistinguishFrom the graphs of 81 and 82 we see the only possible able for any xO and any integer k. . pairs of indistinguishable points are x and - x where To obtain an observable system with the. sa~e 10- Ixl> 1. Since J;(x) = I if x > I and J;(x) = -I if x <; -1 it put-output behavior as the original we must identify XO can be seen that these pairs are indistinguishable. and x", that is, define a system ~' on M' = the unit If we quotient the state space M = R by the equivalence circle by 0 (0)"" 0° = 0 and relation of indistinguishability, the result is clearly not a manifold for it looks like a circle with a ray attached. At 9=u Yl=COSO Y2=sin(J. this point one can ask what additional assumptions on ~ Note that (~,x~ and (~',8<>:> realize the same input-out- are needed in order to insure that I be a closed and put map. regular equivalence relation. Sussmann has proved the This example seems to imply that one can obtain an following. observable realization from one that it is not by "factorTheorem 3.5 [27}: If (~,xc) is a weakly controllable ing" by the relation I of indistinguishability, the new realization and either system lives on the state space M' = M / J. However, given a) ~ is analytic or an equivalence relation R on M it is not always true that b) }; is symmetric (i.e.,VuED 3vED such thatf(x,u) M / R with the quotient topology is Hausdorff and admits = - f(x, o) \:Ix EM), then I is a closed and regular equiva Coo structure in such a way that the canonical projec- alence relation. Moreover, there exists a system ~' on tion 'IT: M -+ M / R is a submersion, i.e., aC 00 map of M' = M / I such that (~', I (x~) is an observable and
S"
449
weakly controllable realization of the same input-output map. If ~ is analytic, then ~' is also locally observable. In some sense Theorem 2.3b is the dual of Theorem 3.5a and Theorem 2.4 is the dual of Theorem 3.5b. What we would like to discuss now is the dual of Theorem 2.3a. Proceeding analogously we might expect that I is a regular equivalence relation if the dimension of d§ (x) is constant over M but Example 3.4 shows this not to be the case. Just as we have used the relation WA in addition to A when studying nonlinear controllability so must we introduce another relation for nonlinear observability. We call this new relation strong indistinguishability, XO and x 1 are strongly indistinguishable (denoted by xOS/x J) if there exists a continuous curve a: [0, l]~M such that a (0) = xo, a(l)= Xl and xOla(s) for all s E[O, 1]. Clearly S/ is an equivalence relation, xOSlx 1 implies xOlx1, and ~ weakly observable at X O implies Sl(x~={xo}. As we shall demonstrate in a moment, if the dimension of d~ (x) is constant over M then S/ is a regular equivalence relation and the quotient M', possibly non-Hausdorff, inherits a locally weakly observable system ~' which realizes the same input-output map as I. Before proving this we must introduce some more machinery. Let X(x) denote the space of all tangent vectors at x which annihilate every element of d§ (x)
for i= 1,··· .k, Moreover if fE~T and dcpEd§ then Lf(dcp) E d§ so there exists functions J.Lir(t) such that k:
Lj, (dq;;)( Yt(xO, to)) = ~ llir(t)d
fori=l,.··,k. Combining these three equations we obtain
for i = 1,· .. ,k. This is a linear homogeneous differential equation so there exist invertible linear transformations A(t): Rk~Rk such that
(~j( t») = A(t)(A;j( to)). The lemma follows since d§ (x~ is spanned by m
dcp;(xO)= ~ A;j(tO)dxj )=1
for ;=}, .. ·,k and for small It-tOI, d§(Yt(xO,t~)a / aXYt(xo, to) is spanned by
X(x)= {TE TxM:
lemma.
dfl'i('Y,(XO, to»)
~'Y' (xO, to) = L ~\i t)dx x
j
j
fori=l,··,k. 0 Remark: The above depends heavily on the fact that the dimension of dg (x) is constant so that d§ is "locally finitely generated." For similar results see Hermann [10]. A curve a: [0, 1]--:)oM is piecewise Coo if it is COO at all but finitely many points of [0, 1] and left (right) limits of a and all its derivatives exist at every point of (0, I] ([0, I». We define another equivalence relation on M,xoHx l if there exists a continuous and piecewise C:lO curve a : [0, I] ~M such that a(O)=xo, a(I)=x 1 and
Lemma 3.6: Suppose the dimension of d§ (x) is k for every xEM. LetJ;(x) be a time-dependent vector field on M such thatJ,(·)E~ for every t [for example, if u(t) is an admissible control and ft(x) = f(x,u(t»). Let Yt(XO,t~ be the flow of it, i.e.,
~ 'Y,(XO,tO)=J;(y,(XO,tO)) 'to(xO, to) = xo. Then
~a(s)EX(a(s».
D if. S·InceYt+s ( x 0 ,I0\J=Ys «Yt X 0,10\j, t)·t rroot: ,1 SUIfiIces t0 consider only small It - tOt. Choose dcp.,··· ,dCPk E d§ which are linearly independent on a neighborhood U of xo. A straightforward calculation yields
0) ax
0)
d( . ( 0 aYt 0 dt (/(Pi 'Y, (X ,t) (X .t )
= LJ,(dq>;)('Y,(XO, to»
Corollary 3.7: Assuming the dimension of d{J (x) is constant, if xOHx· then xOSlx 1• Prooi: '). Let (u(t), [to, 11]) be any admissible control with flow Yt(x, t~. The ith component of the output at time t when the system is started at a(s) at time to is
Yi( t) = gi( Yt( a (s), {O)).
The derivative with respect to s is given by
~~ (XO,tO).
On the other hand we can choose functions A;j(t) such that
which is identically zero by the last lemma. This next result shows that 'J is a collection of symme450
try vector fields (in the sense of Sussmann (26]) for the relation H. Corollary 3.8: Assume that the dimension of d§ (x) is constant. Let jElff with flow Yt(x). If xOHx l then 'Y,(xo-,HYt(x l ) for all tER. Proof: Let a: [0, l]--+M be a continuous and piecewise C«J curve such that a(O) = xo, a(l) = xl and d/dfa(s)EX(a(s». Define a curve, f3:[O, l]~M by fJ(s) ==y,(a(s». Clearly fJ is continuous, piecewise C«J, and P(O)=r/(x~P(l)='Yt(xl).Moreover for cpE§
(tkp(P(s». ~ P(s»=
=
~fP(fJ(s»= ~ fP(Yt(O:(s»)
=(dqJ ( Yt(O:(S» ) =0. So djdsp(s)ex'(p(s».
aYt
Z/(W)==Wk
d
ax (0: (s». d<: o:(s»
u)
where 'lTk: Rm~Rk is the projection on the first k factors. Therefore z': V-+R k is a homeomorphism into and (V,z') a coordinate chart. In the coordinates (U,z) and (V,z') on M and M', the projection 'IT is just "'k and clearly a
0
Theorem 3.9: Suppose the dimension of d§ (x) is k, then SI is a regular equivalence relation and there exists a loca.lly weakly observable system ~' on the k-dimensional non-Hausdorff manifold M' = M / Sf which has the same input-output properties as I. More precisely if 'IT: M~M' is the canonical projection then (I,x~ and (I',fT(x~) realize the same input-output map for every XO E M. If ~ is (locally)(weakly) controllable then so is I'. If ~ satisfies the controllability rank condition then so does ~' and moreover M' is Hausdorff. Proof: An outline goes like this. From Coronary 3.7 we see that H equivalence implies SI equivalence. We first show that H is a regular equivalence relation and that we can define a system ~' on M' - M / H with the same input-output properties as ~. We then note that ~' satisfies the observability rank condition, hence I' is locally weakly observable from
submersion. M is covered by a countable number of charts (U,z) and so M' is covered by the corresponding (V,x'). Verifying that changes of coordinates on M' are C IX) reduces to checking that every rp':M'-+R is c» on (V,z'). But if fPe§ then on (U,z) d
coo.
so cp(Z)=CP(Zl'·· ,Zk). Clearly cp'(z')=cp(zi,··· ,Zk) is This shows H is a regular equivalence relation on M. Next we define ~' on M' locally. In the coordinate system (U,z) on M, the dynamics of ~ are given by
i=
;~ (x(z»j(x(z),u).
In particular for i= 1,.. ·· ,k
which it follows that H:= SI. Remark: By Corollary 3.7 xOHx· implies xOSlx1 which by definition implies xOlxl which by Lemma 3.2 implies
acp.
s, = a; (x(z»j(x(z).u)" Lf(·.I1)(fPj)(x(z».
cp(X~_cp(XI) for every q>E~.
Given any xOeM there exists tApt,··· ,drpkEdfJ which The right side is an element of § and hence pulls down to are linearly independent at xo. After reordering the x a functionf:(z',u) on V'. We define the dynamics of I' on coordinates we can suppose that d({JI'···' dCfJk' dxlc + t' · · · ,dx". are linearly independent at xo. Define ZI(X)='P;(x)-q>;(x~, i== 1,.·· .k, Zi(X)== x;- x?, i= k+
(V,z') by
I,.·· .m and
Clearly if z(t) is a curve in U generated by the dynamics of ~ under the control u(t) satisfying z(to.>==zo and if z'(t) is the curve in V generated by the dynamics of I' under the control U(/) satisfying z'(t~==w(zc; then for
i'=f'(z',u).
u== {x :lz;(x)1 < t:}.
If E is chosen sufficiently small, then (U,x) is a coordinate chart around xo. Claim If X 1,x 2 E H ( U ) then x 1Hx2 iff cp;(x 1) =
small It -
tOI
Z'(t) = w(z{t». From this it follows that if ~ is (locally) (weakly) controllable so is I'. Moreover each gi E § and hence pulls down to a funcon M' which we use to define the output of I' on tion (V,Z') as
451
g;
y =g'(z').
The outputs of ~ from
ZO under u(t) and I' from 1T(Z~ under u( t) are the same because g = g' o 'IT and so
g(z( t» == g' 0 w(z(t»
= g'(z'( t).
Notice M' is of dimension k.
On the other hand suppose cp(X~=rp(XI) for every cp E §. Using the controllability rank condition we choose 11'· .. ,1m E 'J which are linearly independent at xo. We also choose dep),· · . ,dCPk Ed § which are linearly independent at xO. Then the k x m matrix with i-jth element
We tum now to the relationship between ~ and § of ~
and 'fJ' and ~ of ~'. Note that I
j'(7T(X),U)=
~: (x)j(x,u).
It foUows from this and the definition of ~ and 'F' that exists an f E ~ such that
I' E (j' iff there
j'(7T(X»=
~: (x)j(x).
(fJ.' ··
In particular
.
c:f'(7T(X»=
a:
a
is of rank k at xo. Without Joss of generality we can assume the first k columns of this matrix are linearly independent at xo. The elements of this matrix are all in § so the first k columns are also linearly independent at Xl and therefore dcpJ' ... ,dcpk are linearly independent at Xl. As before we can construct a coordinate cube (Uo,z) around Xo using fIJI' . · . ,CPk'Xk + I'· .. , Xm • In a similar fashion using the same e and ,qJk but perhaps different Xk+I'··· 'Xm we construct a cub.e (U',z) around x'. Given 8 > 0 define m - k slices Sao and Sal in UO and U I by
(x)c:f(x).
sJ == {x E Vi: z;(x) =0,
and since 'IT is a submersion this shows that if }: satisfies the controllability rank condition so does }:'.
1,··· ,k and
i=k+I,··,m}.
Iz;(x)f<8,
Let Y$i(X) denote the flow of Ji(X) for i= 1,· .. .k and cl denote the cube of side 28 around 0 in R k • Define maps
Furthermore g'ow=g
Pj : C; x Si~M
and so Lfg;(x) =
j=
by
4' (g;)('lT(x»).
Q.
Pi
Repeated applications of this formula show that cp' E § '.iff there exists on q> E § such that
where x E
(sl' ... , sn' x) = Ysick
0
•••
I ,.of I
'V
(x)
si and Is;1 < 8 for j = 1,· .. ,k. Of course si is a
m - k dimensional cube so we can view these maps as
cp/( w(x») = q>(x).
z;
In particular the coordinate functions = cp; are in § so I' satisfies the observability rank condition and therefore is locally weakly observable. This also implies that H and Sf are the same relation. We have already seen that xOHx l implies xOSlx l • Suppose the converse does not hold; there exists xo,x 1 EM such that xOSlx· but xOHx l • Let a(s) be the arc of ~-indis tinguishable points joining XO,x 1, since ~ and ~' have the same input-output properties, '1T(a(s» is an arc of L'·indistinguishable points joining '1T(x~ and ?T(X 1). Moreover this arc is not constant because '1T(X~*'1T(XI). This contradicts the local weak observability of ~'. If I satisfies the controllability rank condition then M' can be seen to be Hausdorff. Given XO~Xl EM first suppose there exists a q>E§ such that qJ(X~*
pJ: C8m~M
I
VO= {x E M :lqJ(x) - cp(xO)1 < Iq;(x I) - q;(xO)I/2}
where C;' is an m-cube of side (Sl~· · . ,sm)E C;' then
2~.
More precisely if
pi (s),' . · ,sm) = f3} (s},· · . ,Sk'X) where xESj with z;(x)=O for i=l,··,k and Zj(x)=s; for i==k+ I,··· .m, For sufficiently small 8 these maps are diffeomorphisms onto open neighborhoods Wi of xi contained in UJ. In fact (Wj,SI'· · . ,sm) are coordinate charts at x/, If 8 is chosen sufficiently small then we can assume that for every xE Wi and for every (Sl'·· ,sn)ECl we have
Now suppose there exists pOE Wo, r' E Wi such that pOHp I. In particular suppose pO = Ys~ 0 • • • 0 y},( q~ where qO E $8°. Let .
U 1== { x E M :I«p(x) - q;(xl)1 > l«p(x I)-
ql = 'V~ 1 s.
0
•••
a
'V~ I
(pI).,
5",.
then by assumption ql E Vi and by Corollary 3.8, qOHql.
Since fP is constant on H equivalence classes
7T- 1(7T(Ui »)= u' and so '1T(U~ and '1T(V I ) are disjoint open neighborhoods of '1T(x~ and w(x').
Because qOES80, xOHqo so XOHql. This implies that epi(X~. =cp;(ql) for i= 1,··· .k and so by assumption (J);(ql)= cp;(x l ) for j= J,. .. .k, By our previous claim, q 1Hx 1 and so xOHxl •
452
We have just shown that if '1T(W~n'1T(WI)*0 then '1T(X~=='1T(XI). It follows that if 11'(X~*'1T(Xl) then these are disjoint open neighborhoods of 1T(X~ and etx'), D The following simple example shows that if ~ fails to satisfy the controllability rank condition then M' need not be Hausdorff. Example 3.10: Let M=R 2\ {( X1,O): X1
x=O
y=x 1•
The dimension of d~ (x) is one for all x so we can fonn the quotient ,M' =: M / Sf. However this is a non-Hausdorff manifold because '77'(0, 1) and '1T(0, -1) are distinct points without a pair of disjoint neighborhoods. Notice that factoring M by the closure of the relation SI is not a way around this problem for the closure of Sf is not a regular relation. Theorem 3.5a and b and Theorem 3.9 exhibit three situations where realizations can be made observable in some sense. If I is analytic then I' is locally observable, if ~ is symmetric then I' is observable and if dg (x) of ~ is of constant dimension then }:' satisfies the observability rank condition and hence is locally weakly observable. The converse of this last remark is "almost" true. Theorem 3.11: If I is locally weakly' observable then the observability rank condition is satisfied generically. Proof: For any system the observability rank condition is satisfied an open subset of M, possibly empty. Suppose there exists an open subset U of M where the dimension of d§ (x) < m. Without loss of generality we can assume dimd~(x)=k<m for xEU. Choose xOEU, an open set V such that xO E V ~ U and a COO function cp: M-+R such that q>(x) = 1 for all x E V, cp(x)=#=O for all xE U and cp(x)=O for all xEM\U. Consider thesystem I' defined by
on
x=cp(x}J(x,u) y=g(x)
in a similar fashion to the proof of that theorem to show the dimension of d§ (x) is constant. Let x I = Ys (xO:> where y denotes the flow of f E§'. The adjoint of (a/ax)'Ys(x~ carries one forms at Xl to one forms at XO according to the rule
W(XI)rH,'(X I )
a 'Ys(XO), ax
for wE~*(M). This map also has a Campbell-Baker-Hausdorff expansion
a
00
k
x
k=O
.
w(x1)-a 'Ys(XO)= ~ {Lf)*w{xO)sk'· In particular, if wEH then the adjoint of (d/dX)'Y.r(Xo-, carries dg(x 1) into d§(x~ so the dimension of dg(x l ) is less than or equal to the dimension d~ (x~. A similar argument using the adjoint of (a/ax»)' -sex)~ shows the reverse inequality. Therefore, if xOWAx1 then the dimensions of dg (x~ and d § (x 1) are the same. Since I is weakly controllable, this implies that the dimension of d§ (x) is constant. Suppose dimd~(x)=k then we apply Theorem 3.9 and identify strongly indistinguishable points. But ~ weakly observable implies there are strongly indistinguishable 0 points so k must equal m. To relate the results of this section to the well-known linear theory, we consider the following. Example 3.11: Consider the linear system
no
x=Ax+Bu y=Cx. In Example 2.5 we saw that §" was spanned by { Ax , A'B*·jr=O ' . , · .. , m -1 , J.= 1" · .. I} where B •.'} denotes thejth column of B. Let C;* denote the ith row of C then for r ;> 0, p:> 0
LAxC;*yA rx = C;.A
x(O) = xO.
LA'B
The state space of ~' is U and ~' is complete. It is easy to see ~/(X) =~(x) for all x E U. From this it follows that dl3'(x)=dl3(x) for all sE U~ and so dimd§(x)==k for all xE U. We can apply Theorem 3.9 to ~' on U so ~' is not locally weakly observable. Since ~ and ~' agree on V, ~ is not locally weakly observable either. 0 Recall that for analytic systems, weak controllability, local weak controllability, and the controllability rank condition are equivalent. With regard to observability an analogous result holds for analytic systems which are weakly controllable. Theorem 3.12: If ~ is a weakly controllable analytic system then ~ is weakly observable iff it is locally weakly observable iff the observability rank condition is satisfied. Proof: It suffices to show that weak observability implies the observability rank condition. By Theorem 2.6 ~ satisfies the controllability rank condition, we proceed 453
.j
r+l x
Ci.APx = Ci.A r+PB.j
LAxC;.APB.j = LA'B.,C;.APB.j =0. )
Therefore by the Cayley-Hamilton Theorem § is spanned by
r=O,.·· ,m-l} and d § (x) is spanned by
{Ci.A r : i= 1,··' .m, r=O,'" ,m-l}. Clearly d~ (x) is of constant dimension. The observability rank condition reduces to the well-known linear observability condition that
IV.
C CA
=m.
rank
If the observability rank condition fails then we define X(x) to be the .constant linear space of column vectors orthogonal to d§ (x), Two points x~ and Xl are H equivalent (or Sf equivalent) if x l - xOe X(x) because
a(s)= XO+s(xl - Xo) is a curve tangent to X(x) from x O to x '. Factoring M by X(x) results in a locally weakly observable system which because of linearity is also locally observable (Sl =1 for
linear systems). Example 3.12: Suppose the linear system is nonautonomous as in Example 2.6. As in formula 2.1 we add time as a state variable which we can observe directly. Then direct calculation shows that the observability rank condition is equivalent to
MINIMALITY
A linear system is said to be minimal if it is controllable and observable. As is well known, two minimal linear systems initialized at 0 which realize the same input-output map differ only by a linear diffeomorphism of the state spaces, [I], [4]. A nonlinear system which is observable, weakly controllable and either analytic or symmetric is called minimal by Sussmann [29]. He has shown that two minimal nonlinear systems which realize the same input-output map from their respective initial states differ only by a diffeomorphism of the state spaces. A nonlinear system ~ is locally weakly minimal if it is locally weakly controllable and locally weakly observable. Two locally weakly minimal realizations of a given input-output map need not be diffeomorphic as is seen by Example 3.3, but the following theorem shows they must be of the same state dimension which is minimal over all possible realizations. Let L, ~' be two nonlinear systems with control set O=O'~RI states spaces M and M' of dimension m and m' and output with values in R" given by ~:i=f(x,u)
C(t)
y=g(x) '2:' : i
=J'(z, u)
y=g'(z).
=m
rank
for every t E R where
AoC(t)==
~ C(t)+ C(t)A (r),
A~ C (t) == ~ A~-IC (1)+ A~-IC (t)A (t). See [3] or [5]. Example 3. J3: Consider the bilinear system of Exam..
Theorem 4.1: Suppose (~,x~ and (L',Zo.> realize the same input-output map. If ~' is locally weakly minimal then m » m', Proof: Without loss of generality we can assume that ~' satisfies the controllability and observability rank condition at zoo (If not, by Theorems 2.5 and 3.11 we can find a control (u(t),[tO,t l]) and a corresponding L' trajectory (z(t),[tO,t l]) with z(t~=zo, z(tl)=ZI such that these conditions are satisfied at z '. Moreover if .\"1 is the endpoint of the corresponding ~ trajectory then (L, x I) and (~', z I) realize the same input-output map.) Since ~' satisfies the observability rank condition at ZO we can find a neighborhood V of ZO and functions qJ~,. • • ,cp;", E §, such that the map
pie 2.8
ep'=col(fPi,.·· ,cp;"): V~Rm' I
x=Ax+ ~ u;B'x. i=J m
If M=R (or a subgroup of G/(h,R», let C be a nXm (n x h) matrix and
is a diffeomorphism into. Because I' satisfies the controllability rank condition, as in Theorems 2.1 and 2.2 we can find controls u 1, • • • ,U m and corresponding vector fieldsf'i(z)=f'(z,u i ) with flows y'~(z) such that the map
y=Cx,
,r,'(' T S · · · S ) =v rm I'
then
g = {C;xDx: i= 1,··· .n; DxE'J} d§ ={ CixD:i= 1,··· ,n; DXE'F}. See [3] for further details.
rrm
I S'"
0
I ( 0)
I '." I 5, ,-
• • • "1
,
is a diffeomorphism from some open subset S of the positive orthant of Rm' into M'. Let q>j, 4>, I'. v'. 'I' be the corresponding objects of L. Since (}:,x~ and (~', z~ realize the same input-output map <J> 0 'l' =4>' 0 '1" and so 454
'I'
(20) - " A generalization of Chow's theorem and the bang-bana theorem to nonlinear control problems," SIAM J. Contr., vol.
S~Rm'~M~Rm'
12, pp. 43-52, 1974.
is a diffeomorphism. But clearly this is only possible if [21] C. Lobry, "ControUabilite des systemes non Iineaires," SIAM J. COftt~,vo1.8,pp. S7~S, 1970. m)m'. [22J - ,~lques aspects Qualitatifs de la thme de la commaacle," These de doctorat d'etat, Universite de Grenoble, Grenoble, Corollary 4.2: If (~,x~ and (I',z~ are locally weakly France, 1972. , minimal realizations of the same input-output map then (23) T. Nagano, "Linear differential systems with singularities aDd an application to transitive Lie algebras," J. Math. Soc. Japan, vol. 18, their state spaces are of the same dimension. pp.398-404, 1966.
REFERENCES [1] B. D. O. Anderson and 1. B. Moore, Linear Optimal Control. EDalewood Oiffs, NJ: Prentiu-Hall, 1971. (2] W. M. Boothby, An IntrotktiOll to Differential Manifolds and Rientl1l1lian GetJnwtty. New York: Academic, 1975. (3] R. W. Brockett, "System theory on group manifolds and coset spaces," SIAM J. Cont,., vol. 10, pp. 265-284, 1972. [4 -Flllite Dimensional LiMQT Systems. New York: Wiley, 1970. [s W. L Chow, "Uber Systeme von Linearen Partiellen 00ferentialgl.eichungen erster Ordnung," Math. AM., vol. 117, pp.
l
98-105, 1939.
(6] H. D'Angelo, Linear Time-Vary;ng Systems.
[7] (8) [9]
(10]
[IIJ
[12] [13] (14] [IS]
[16] (17]
(18] [19]
Boston, MA: Allyn and Bacon, 1970. E. W. Griffith and K. S. P. Kumar, "On the observability of nonlinear systems, I," J. Math. Anal. Appl., vol. 35, pp. 135-147, 1971. G. W. Haynes and H. Hermes, "Non-linear controllability via Lie theory," SIAM J. Contr., vol. 8, J?p. 450-460, 1970. R. Hermann, "On the accessibility problem in control theory," in l"t. Sy"". 011 Nonlinear DifjeremioJ Equations and Nonlinear M«lIimics. New York: Academic Press, 1963, pp. 325-332. -D~rent;aI Geometry and the Calculus of Variations. New York: Academic, 1968. -CtThe differential geometry of foliations, II," J. oj Math. and Meek, vol. II, pp. 303-316, 1962. -"Some differential geometric aspects of the Lagrange variational.problem," J. Math., vol. Ill, no. 6, pp.634-673, 1962. -"EJDsteDce in the large of parallelism homomorphisms," TraM. Amer. Math. Soc., vol. lOB, pp. 170-183, 1963. -.-"Cartan connections and the equivalence problemfor geometnc structures," Contribution to Differential Equations, vol. 3, 1964, pp. 199-248. H. Hermes and J. P. Lasalle, Functional Analysis and Time Optimal Control New York: Academic, 1969. Y. M.-L. Kostyukovskii, "Observability of nonlinear contIoUed systems," Alllomal. Remole Comr., vol. 9, pp. 1384-1396, 1968. -~imple conditions of observability of nonlinear controlled g'Stems," AlllomtJI. Remote Contr., vol. 10, pp. IS75-1S84, 1968. S. R. Kou, D. L FJliot, and T. J. Tarn, "Observability of nonlinear system.s," Inform. COIIIr., vol. 22, P. 89-99, 1973. A J. Krener, "A BeneralizatioD 0 . the PontJyagin maximal princi-
f
ple and the bang-bang principle," Ph.D. dissertation, University of California, Berkeley, CA, 1971.
455
(24] J. P. Serre, Lie Groups and lie Algebras. New York: BenjamiD, 1965. [25] H. 1. S~ andY. J. Jur~jevic, "ControUability of nonlinear systems, J. Differentitll EquDtioru., vol. 12, pp. 95-116, 1972. [26] H. J. SUSSIDIJm, "Minimal realizatioDl of Donlinear systems," in Geometric M«hodr ill Systemr TIwry, MaYDe and BrOckett, Ed., Dordreeht, The Netherlands: D. Riedel, 1973. ,(27] - " A generalization of the closed subp-oup theorem to quotients of arbitrary manifolds," J. DiffemuiiIJ Chonwtry, vol. 10, pp.
ISI-I66, 1975. (28] -"Observable realizations of finite dimensional nonlinear autonomous systems," Math. Systems '1'It«Ny, to be published. . [29J -"Existence and uniqueness of miDimaI realizl.tioDS of nonlinear systems I: Initialized systems," Math. Systems T'heory. .
Analysis of Recursive Stochastic Algorithms LENNART LJUNG
INTEREST in identification algorithmsand their use in adaptive control commenced very early, the former having its roots in the literatureon time series analysisand the latter in dynamic programming which was immediately perceived, on its introduction in the 1950s,to be the natural tool for decision making under uncertainty. Adaptive control required recursive identification,stimulatinga substantialactivityin this topic. An obvious starting point for analyzing these recursive algorithms was the olderliteratureon stochasticapproximation [5], [8].However, in recursiveidentification, unlike the models consideredin the traditional stochastic approximation literature, the regression (observation) vector 4J(t) is allowedto dependon all previousvalues of theparameterestimate,preventing use of the oldertechniques. It was obviously important to answer questions about the convergence of such identification algorithms: for example,
ingon the currentparameterestimateanda so-calledobservation vector, 4J(t) which is drawn from the "true" system,but may be noisy;entriesof 4J(.) may be noise-contaminated inputsand outputs of the true system so that it is not necessarily a sequence of independent, identically distributed random variables commonly demanded by stochasticapproximation. Lastly, yeo) is a sequenceof positivescalars.Since there is interest in parameter convergence, and since in general Q varies randomly, it is clear that parameter convergence can only occur if yet) --+ 0
as
t --+
00
(2)
Thisis the typeof assumptionthatbecameveryfamiliarin theliterature on stochastic approximation. It carries with it the great advantage that analysis of a fundamentally stochastic system can be replaced by analysisof a deterministic system,and there is some degree of comfort in a theorem which says that parameters converge to a deterministic limit. On the other hand, • under what circumstances does the algorithm converge? there is also a great disadvantage. With y going to zero, less and • what is its rate of convergence? • what meaning can be attached to the point to which conver- less attention is paid to the "noisy" observations. This means that shouldthe plant whoseparametersare being estimated,and gence occurred? from whom observations are derived, not have constant paramThese questionshad startedto present themselvesin analyses eter values, but have parametervalues that change in time (perconducted several years previously, such as references 1-5 of haps slowly) the ability to track those varying parameters vanthis paper by Ljung. Among other things, these references had ishes as y goes to zero. In effect, only strictly time-invariant shownthatconvergence neednot necessarilyoccur,and alsothat plants can be identified. the convergence property could be associated with the stability It is important to understand at a broad level the basis of the properties of a deterministic ordinary differential equation de- argumentwhich allowsthe analysisto be done by consideration spite the fact that discrete-time identification algorithms were of an ordinarydifferential equation.There is a general appeal to being considered. averaging theory ideas. More precisely, suppose that in EquaThepaperby Ljungstartswitha verygeneralformof recursive tion (1) yet) is very small over a long interval. Then over this algorithm: interval, x(·) does not change much, and presumably 4J takes a large number of values with some statistical regularity properx(t) = x(t - 1) + y(t)Q(t; x(t - 1), 4J(t» (1) ties. These properties may well be x dependent, especially if a In this equation, x(·) is a sequence of vectors, of dimension n, controlleris being implementedto generateplant inputs,and the constituting parameter estimates. It is hypothesised that in the parametersin that controllerare computedusing the estimate x. background there rests a system described by a "true" parame- In this circumstance, the sequences 4J(t) and x(t) will certainly ter, and one would hope that the parameter estimates converge not be independent. to the true parameter. In Equation (1), Q is another n-vector, Considering x(t) as approximately a constant over a long inmost commonly not dependent explicitly on time, and depend- terval, and assuming that f/J(t) takes a range of values during 457
this interval, one agrees to replace say, s, successive updates of Equation (1) by an update involving a single gain t+s
Ly(k)
(3)
t+l
and to replace Q by its average value conditioned on x(t - 1). The result is still then a difference equation. However, one can regard it as an Euler approximation of an ordinary differential equation, and the ordinary differential equation comes out to be something like Equation (4) below, where f(x) is the expected value of Q conditioned on x.
(4) The above paragraph sets out a heuristic justification for the assertion that the behavior of the recursive algorithm can be linked to the behavior of the deterministic ordinary differential equation. Of course, the paper sets out a series of assumptions, under which formal theorems can be stated. Broadly speaking, these theorems are of the type: if the differential equation has an invariant set with an associated domain of attraction, and if the recursive equation gives a parameter estimate which from time to time lies in the domain of attraction, then the recursive equation will have a solution converging to the invariant set. If the invariant set is a point, then the unknown parameter vector can be considered as being learnt (identified). However, if it is not a point, the unknown parameter cannot be identified, although some of its properties can be learnt. The second group of results focuses on the question of learning the whole parameter vector. A third important result of the paper relates the trajectories of the deterministic ordinary differential equation and the stochastic recursive equation, putting a bound on the probability that these can never be far apart. Thus the trajectories of the differential equation illustrate how the parameter values will change on a transient basis-at least for a typical run. The value of the paper for applications is that a whole collection of important situations are captured by the general theorems of the paper. Important applications include equation error identification and self-tuning regulators. Stochastic approximation turns out to be a special case of the theory. Readers familiar with equation identification will probably be aware that in the presence of noise, bias in the parameter estimates is to be expected. It is a measure of the power of the theory of the paper that in this case, where parameters may
converge but not to the correct values, one nevertheless has a hard result. Where did the paper lead to? As might be expected, a series of incremental advances and a widening of the example classes were able to be found. Secondly, the paper flagged the great importance of averaging ideas for recursive identification and for adaptive control. The averaging derives from the fact that the time scale associated with the time-constants of all but the identification process, and the time constant of the identification process itself, are very different. This separation of time scales found application in more than one book dealing with adaptive control; for example, [1] and [6]. Systematic use was made of the the techniques of the paper to analyze and classify recursive identification algorithms (including the extended Kalman filter) in [4]. A simpler approach to averaging analysis that preserves its full power is presented in [7]. The same family of problems, using different machinery, is addressed in [3] and [2]. The paper also gave results underpinning later work addressing the very difficult issue of the behavior of algorithms in which the adaptive gain sequence does not go to zero. There had been earlier analysis of such algorithms, essentially for FIR systems (this was particularly driven by the school of Widrow, and many results can be found in [9]), but these earlier results fell completely short of addressing situations where there was closedloop control and the systems were not finite impulse response. Such situations are being addressed in isolated papers, but there seems as yet no textbook distillation embodying the key ideas. REFERENCES [1] B.D.D. ANDERSON et al., Stabilityof AdaptiveSystems, MIT Press (Cambridge, MA), 1986.
[2] A. BENVENISTE, M. METNIER, AND P.PRIOURET, AdaptiveAlgorithmsand Stochastic Approximation, Springer-Verlag (New York), 1990. [3] H.J. KUSHNER AND D.S. CLARK, StochasticApproximation Methodsfor Contrained and Unconstrained Systems, Springer-Verlag (New York), 1978. [4] L. LYUNG AND T. SODERSTROM, Theory and Practice ofRecursive Identifiction, MIT Press (Cambridge, MA), 1983. [5] H. ROBBINS AND S. MONRO, "A stochastic approximation method," Ann Math. Stat., 22:400'407,1951. [6] S. SASTRY AND M. BODsoN,Adaptive Control, Stability, Convergence, and Robustness, Prentice Hall (EnglewoodCliffs, NJ), 1989. [7] V. SOLO AND X. KONG, AdaptiveSignal Processing Algorithms:Stability and Performance, Prentice Hall (Englewood Cliffs, NJ), Information and System Science Series, 1995. [8] M.T.W. WASAN, Stochastic Approximation, Cambridge University Press (New York), 1969. [9] B. WIDROW AND S. STEARNS, Adaptive Signal Processing, Prentice Hall (EnglewoodCliffs, NJ), 1985.
B.D.O.A.
458
Analysis of Recursive Stochastic Algorithms LENNART UUNG, MEMBER, IEEE
A1JIIIw:f-
raa.a-
ft
......... '
rn.ew.n.
. . are rllMe Is tIIat tile
~
All IDaportIIIt
"......" or the· ......., e.a., Itodtastlc
I. INTRODUCTION
ECURSIVE algorithms, where stochastic R tions enterare common in fields. In the control ........................................, ......... and estimation literature such algorithms are widely dis. . . . . . .., depead oa
C8MIdnII
e.traI It II
equtIoa
CIa.~
.,
bIe~
_'..IIIc
oIl11e
.................................. nearrelltia ' \
observa-
many
.,.....
willi
• well daD 1M
The ...
tile .". CGIdnIL
"die
cussed, e.g., in connection with adaptive control, (adaptive) filtering and on-line identification. The convergence analysis of the algorithms is not seldom difficulL As a ...... ..... be
tbe ,• to JII'ObI-Ia 1tIIII1IIca.
rule, special techniques for analysis are used for each type of applicati9n and often the convergence properties have to be studied only by simulation.
In this paper a general approach to the analysis of the asymptotic behavior of recursive algorithms is described. In effect, the convergence analysis is reduced to stability analysis of a deterministic, ordinary differential equation. This technique is believed to be a fairly general tool and
to have a wide applicability. Applications to various probCopyrlaht CO J9T1 byThe Institute of Electrical and Electronics Engineers. Inc. Printed in U.S.A. Annals No. 708ACOOS Reprinted from IEEE Transactions on Automatic Control, Vol.AC-22,August 1977, pp. 551-575. 459
lems have been published in [lH4] and some theory was presented in (5]. The objective of the present paper is to give a comprehensive presentation of formal results and useful techniques for the convergence analysis, as well as to illustrate with several examples how the techniques can be applied. In Section II a general recursive algorithm is described and discussed. A heuristic treatment of the convergence problem is given in Section III and this leads to the basic ideas of the present approach. Section IV contains a discussion of the conditions which are imposed on the algorithm in order to prove the formal results. These theorems are given in Sections V and VI. The theorems suggest certain techniques for the convergence analysis, and these aspects are treated in Section VII. Several examples of how the theorems may be used, some of them reviewing previous applications are given in Section VIII.
observation q>(t) as the (lower dimensional) output of a dynamical system like (2), ep(t)= C(x(t -l»cp(t). However, this case is naturally subsumed in the present one, since
and the proofs for this case are given in [7]. Throughout this paper it is assumed that the estimates are desired to converge to some "true" or "optimal" value(s). Since Q(/,X(I - l),cp(/» is a random variable, with, in general, nonzero variance, convergence can take place only if the noise is rejected by paying less and less attention to the noisy observations, i.e., by letting
y( t)--+O II.
THE ALGORlmM
A general recursive algorithm can be written
x(t)=x(t-I)+ y(t)Q(t;x(t-I),fP(t»),
(I)
(3)
as
1--+00.
(4)
In tracking problems, when a time-varying parameter is to be tracked using algorithm (I), this condition is not feasible.. Then y(/) usually tends to some small, nonzero value, the size of which depends on what is known about the variability of the tracked parameters and about the noise characteristics. This case is not treated here, but it is reasonable to assume that analysis under the condition (4) also will have some relevance for the case of tracking slowly varying parameters. Suppose we have a linear, stochastic, discrete-time system, governed by a linear output feedback law, which at time t is determined by x(t - 1). Then the behavior of this overall system can be described by (2), with ,,(t) consisting of lagged inputs and outputs. Therefore the algorithms (I) and (2) can be understood as archetypical for adaptive control of a linear system. Indeed this setup is useful for analysis of certain adaptive controllers, as will be exemplified below, but the basic algorithm (I), (2) also covers several other cases of interest.
where x(·) is a sequence of n-dimensional column vectors, which are the objects of our interest. We shall refer to x(·) as "the estimates," and they could, e.g., be the current estimates of some unknown parameter vector. They could, however, also be parameters that determine a feedback law of an adaptive controller, etc., and we shall be precise about the character of x(·) only in the examples below. The sequence y(.) is assumed throughout the paper to be a sequence of positive scalars. The m-dimensional vector cp(t) is an observation obtained at time I, and these are the objects that cause x(t - 1) to be updated to take new information into account. (The notion "observation" does not have to be taken literally. The variable q> may very well be the result of certain treatment of actual measurements.) The observations are in" general functions of the previous estimates x(·) and of a sequence of random vectors e( .). This means that the observation is a random variable, which may be affected by previous estimates. This is the case, e.g., for adaptive systems, when the input signal is determined on the basis of previous estimates. If the experiment designer has some test signal at his disposal, this may be included in e(· ). The function Q(.; ., .) from R x R" x R m into R" is a deterministic function with some regularity conditions to be specified below. This function, together with the choice of the scalar "gain" sequence y(.) determine entirely the algorithm. We shall not work with completely general dependence of ,(I) on x(·), but the following structure for the generation of cp(.) will be used:
The algorithm (1), (2) is fairly complex to analyze, being a time-variant, stochastic, nonlinear difference equation. Notice also that the correction x(t)- x(t-l) depends in general via fP(/) implicitly on all old x(s). Therefore, while (I) certainly is recursive from the user's point of view, it is not so for analysis purposes. In this section we shall illustrate heuristically how a differential equation can be associated with (1), and bow it seems reasonable that asymptotic properties of (1) may be studied in terms of this differential equation. The formal analysis and results follow in the next two sections. Consider
fP(t)==A(x(t-l»q>(t-l)+B(x(t-l»e(t).
X(/)=x(t-I)+y(t)Q(x(t-I),.,,(t»),
III.
(2)
HEURISTIC ANALYSIS
(5)
where for simplicity we let Q be time independent.. As Here A (. ) and B (.) are mlm and mlr matrix functions. Remark: It is perhaps more natural to think of an remarked before, cp(l) depends on all previous estimates: 460
I
,(/)- I
j-I
(
) IIt A(x(i-I» B(x(j-I»)e(j).
(6)
(5) by I
i-j+}
T,==
I
y(k).
(12)
Ie-I
Now, if (2) is exponentially stable, then the first terms in We therefore have some reason to believe that the (6) will be very small and, for some M, sequence of estimates x(·) asymptotically should follow the trajectories x D ( •) of (11). I A(x(i-l»)B(x(j-l»e (We could also have related (9) to the difference equation Moreover, it follows from (5) and (4) that the difference (13) X(/)- x(l-l) becomes smaller as I increases. Therefore, fqr sufficiently large I, we have x(k)~x(/); I ~ k ~ 1- but the differential equation is easier to handle since it is time-invariant.) , 2M. Hence, It now seems reasonable that asymptotic properties of Ie k-«! algorithm (I), (2) may be studied in terms of the differencp(k)~ I [A(x(t»] JB(x(t»e(j) tial equation (11). This heuristic discussion is perhaps not j-le-M very convincing, but along a similar path, though with far Ie • (7) more technical labor, formal results to this effect can be JB (x(t»e(j) £ ~(k;x(t» ~ I [A(x(t» proven. These are given below. j-I
4p(t)~j.~M C.¥.
u).
t-
for I ;> k ;> t - M. Furthermore,
IV.
AssUMPTIONS ON THE
ALoolllTHM
Q (x( k ~ 1),cp(k»~Q (x( t),q;(k; x( I») == /(x(t» + w(k)
In order to prove the formal results, certain regularity (8) conditions on the functions Q, A, and B and on the driving "noise" term e, have to be introduced. Some of where these are fairly technical, but it is believed that none is very restrictive. Several sets of assumptions are possible, f(x)- EQ(x,q;(k;x») and we shall give a few. In particular, there is a possibility to treat the sequence e(·) either in a stochastic or in a and hence w(k) is a random variable with zero mean. deterministic framework. Using (8), we can approximately evaluate . We shall start by giving a formal definition of ~ used in the previous section. Let 1+$ x(t+s)-x(t)+ I y(k)Q(x(k-l),cp(k» Ds == {xlA (x) has all eigenvalues strictly i-,+1 1+3
I
~x(t)+f(x(t»)
I+.s
y(k)+
Ic-I+ 1
~x(t) + f(x(t»)
I
inside the unit circle}.
y(k)w(k)
k-t+ I
Then for each xEDs' there exists a A=A(x), such that
t+.r
I
A(X)< I.
(9)
y(k),
(14)
t+ I
Take xeDs and define the random variables ~(t,i) and where the last step should follow since the last term is a v(t,A,c), A< 1, by zero mean random variable which is dominated by the q;(t,i):aA(i)~(t-l,i)+ B(i)e(t); ~(O,i)==O second term. Expression (9) suggests that the sequence of estimates more or less follows the difference equation (15) x D ( T+~T)= x D ( T) +~"f( x D
(,,»
(10)
V(t,A,C)=-AV(t-I,A,c)+cle(t)l;
V(O,A, c) ==0.
(16)
Let DR be an open, connected subset of Ds . The regularity conditions will be assumed to be valid in DR. Now, the 1+$ first set of assumptions is the following. I y(k). A.I: e(·) is a sequence of independent random vari1+1 ables (not necessarily stationary or with zero means). It is useful to interpret (10) as a way of solving the A.2: )e(t)1 < C with probability one (w.p.l) all t. differential equation (4'T small), A.3: The function Q(t,x,cp) is continuously differentia.. hie w.r.t x and f for x E DR. The derivatives are, for fixed (II) x and cp, bounded in t. A.4: The matrix functions A ( .) and B ( .) are Lipschitz where the (fictitious) time" relates to the original time t in continuous in DR. where 4,. corresponds to
461
A.5: lim,.... ooEQ(/,X,q>(I,X» exists for xE DR and is denoted by f(X). The expectation is over e( · ). A.6: Ify(/)= 00 A.7: Iiy(t)P < 00 for some p. A.B: y(.) is a decreasing sequence.
x and
·(I + v( I,A,e») - k o { 1- 1,X,A,C) ]; (17)
kC)(O,x,A, c) ==0. (ISb)
Notice that for the common choice y(/)= I/t, (18a) imConditions A.S and A.. 9 are motivated by technical arguplies that ments in the proofs, but they have so far not appeared to be restrictive.. For example, it is easy to see that the z(t,x)-! Q(k;x,qi(k,x») sequence y(t)= Ct:" satisfies A.6-A.9 for 0< a c; 1. t k-l If we would like to alleviate A.2, further regularity conditions on Q are required. This gives us our second set and analogously for k,,(t,x,A,C). The assumptions then are of assumptions. (~(i,p) denotes a p-neighborhood of i, as follows. i.e., ~ (x,p) {xfli- x]
±
=
462
remaining in DR and boundedness of D can be avoided. Corollary J: Consider the algorithm (I), (2) subject to assumptions A, B or C. Let i5 be a closed subset of DR (possibly is= DR = R") such that (20) holds. Assume that there exists a twice differentiable function ~i (x) in DR" such that
convergence of (18) are given. In fact, conditions B imply that C.3 and C.4 hold w.p.l. It may in this context be remarked that there is actually a tradeoff between condi.. tion A.7 == B.9 and conditions B.2 and B.7. The largest p for which B.2 and B.7 need to hold is twice the p for which A.7 holds. Therefore, if y ( · ) is subject to (17), then only the fourth moments of e, Q, and ~i have to be bounded. This is discussed further in [5] and [8], and we shall not pursue it here. V. MAIN
V'(x).f(x) ~ 0
(22)
Then either x(l)~Dc={xlxEDR and
THEOREMS
V'(x)!(x)=O} \V .
The functionJ(·) defined in A.S, B.6, or C.3 is the basic object of interest. As the heuristic discussion in Section III or indicated the differential" equation
{x(t)} ( 19)
p ( x ( t) --+ ~'B (x *, p)) > 0
inf Ix( t) - xl-+O.
The phrase "w.p.l" naturally does not apply in the case with assumptions C. In order to verify the stability condition (21 ) analytically, usually the Lyapunov theory has to be applied. Theorem 1 can be given a formulation, which does not refer to any differential equation, but directly relates to a Lyapunov function associated with f(x). In that way also the assumption about the trajectories of (19)
0
for all p > o.
(23)1
Furthermore, suppose that Q(I,X·,~(t,x*» has a covariance matrix bounded from below by a strictly positive definite matrix,
x(t} ED and \cp(t)1 < C infinitely often (i.o.jw.p.l (20)
xEDr
has a cluster point on the boundary of DR'
Our second theorem concerns the set of possible convergence points. It can be used to prove failure of conver.. gence by showing that the "desired" or "true" parameter value does not belong to this set. Theorem 2.' Consider algorithm (1), (2) subject to assumptions A or B. Suppose that x* E DR has the property that
will be relevant for the asymptotic behavior of the algorithm (1), (2). The exact relationships between (19) and ( I), (2) are given in three theorems. The first one concerns convergence of (I). Theorem J: Consider the ~gorithm (I), (2) subject to assumptions A, B or C. Let D be a compact s.!!.bset of DR such that the trajectories of (19) that start in D remain in a closed subset DR of DR for T > O. Assume that 1) there is a random variable C such that
2) the differential equation (1.2) has an invariant set D, with domain of attraction D A :> D. (21) Then x(t)~Dc with probability one as 1--+00. 0 Remarks.' By (20) is meant that there exists with probability one a subsequence tk , p..2ssibly depending on the realization w, such that x(tk ) E D and Icp(lk)1 < C (w), k = I, 2" · · . This condition, which we may call the "bounded.. ness condition," is further discussed in Section VI. An invariant set of a differential equation is a set such that the trajectories remain in there for - 00 < T < 00. The domain of attraction of an invariant set D, consists ofthose points from which the trajectories converge into D; as T tends to infinity. It is obviously an open set. See, e.g., [9]. An interesting special case is when the invariant set D, is just a stationary point of (19) say x", with f(x*) = O. Then the theorem proves convergence of x(t) to x*. By x(t)~Dc is meant that
p. I as l-;~ "X;
(24)
and that EQ (I,X, <j)(t, x) is continuously differentiable with respect to x in a neighborhood of x* and the derivatives converge uniformly in this neighborhood as I tends to infinity.
Then (25a)
f(x*)=O
and H (x*) =
fx f(X)lx~x. has all eigenvalues in the LHP (Rez
< 0). 0
(25b)
The matrix H (x*) defines, of course, the linear differential equation obtained from (19) by linearization around x*. Therefore this theorem essentially states that the algorithm can converge only to stable stationary points of the differential equation (19). If j(x)= -(d/dx)V(x), which might be the case if the algorithm is based on, criterion-minimization, then J/ (x) can be chosen as a Lyapunov function for the differential equation (19). Since id] dT)V(X(T»= -If(x(T))1 2, \ve see
463
'P(A)-The probability of the event A.
x
that the stationary points of (19), together with the point {co}, form an invariant set with global domain of attraction. Moreo.ver, if the stationary points are isolated, it follows from Theorem 2 that .only stable ones, i.e., local minima, are possible .convergence points. It also follows from Theorem I that the estimates cannot oscillate between different minima. Collecting all this we obtain a corollary to Theorems 1 and 2. Coro/lary 2: Suppose that DR:: R", that f(x) = (dj dx) V(x) and that V(x) has isolated stationary points. Assume that 'cp(t)1 < C La. w.p.l. Then, w.p.I, X(/) tends either to a local minimum of Vex) (i.e., V"(x) positive semidefinite) or to infinity as t tends to infinity. Finally, our third theorem relates the trajectories of the differential equation (19) to the paths of the algorithm (I), (2). The result is formulated as follows. Let X(/), 1= to,' · ., be generated by (I), (2). The values can be plotted with the sample numbers I as the abscissa. It is also possible to introduce as before a fictitious time T by I
T,=
~ 1'(k).
(26)
k-l
t'
Suppose that the estimates X(/) are plotted against this time T. See Fig. l(a). Let XD(T,Tto,X(/ o» be the solution of (19) with initial value X(/o) at time Tto. Also plot this solution in the same diagram, as in Fig. l(b). Let I be a set of integers. The probability that all points X(/), I E I, simultaneously are within a certain distance E from the trajectory is estimated in the following theorem. Theorem 3: Consider algorithm (1), (2) under assumptions A or B. Assume thatf(x) is continuously differentiable, and that (20) holds. Assume that the solutions to (19) with initial conditions in D are exponentially stable, and let I be a set of integers, such that inf I'T; - 'Tjl == 60 > 0 where i=l::j and i,jE/. Then for any p~l there exist constants K. f(} and To that depend on p, D, and 60, such that for E < EO and to> To. P {SUPIX(t>-xD(Tt;Tto,X(to»)I>f} <; lEI.
t> 10
~ Jrf
(
.
xfli)
(a)
X
Fig. 1. (a) and (b) To illustrate Theorem 3.
preting (27) is that the gain sequence y(.) can be scaled so that x(·) stays arbitrarily close to x" (.), with an arbitrary high degree of probability. A result that is related to Theorem 3 in the case A (x)=O is given in [35]. Interesting connections between stochastic-approximation type algorithms and a corresponding differential equation have also recently been made by Kushner [36], [37], using weak convergence theory. The proof of Theorems I, 2, and 3 are long and technical. They are given in Appendices I, II, and III, respectively. The idea of the proofs of Theorems I and 3 follow the discussion in Section III. However, a considerable amount of technicalities are required to rigorously justify the "approximatively equal" signs. In Appendix V extensions of the theorems, e.g., to continuous time algorithms and to cases when the limit in A.5 or B.6 does not exist are also commented upon. VI.
(27) where N~sup i; iE I, which may be 00. Remark: In the proof of Theorem 3 it is assumed that the exponential stability of the solution x D ('r, Tl o ; x( 10» is ensured by a quadratic Lyapunov function for the (linear and time-varying) variational equation around this solution, cf., e.g., [10]. Although the proof of Theorem 3 provides an estimate of K from given constants, we do not intend to use (27) to obtain numerical bounds for the probability. The point of the theorem is that a connection between the differential equation (19) and the algorithm (1), (2) is established. In particular, we notice that, due to A.7 there is a p such that the RHS of (27) becomes arbitrarily small when 10 increases, and E is fixed. This means that the estimates stay close to the corresponding trajectory with higher and higher probability as 10 increases. Another way of inter-
x~ (7J 1f.(J .X(~J)
(b)
y(j)p !«
.. ...
THE BOUNDEDNESS CONDITION
In this section we shall discuss condition (20). The reason why it is required is twofold. First, obviously x( I) must be inside DR (with fP(t) not t09 large to prevent an immediate jump) for the differential equation to be valid at all, and also inside DA to get "caught" by a trajectory converging to Dc. Second, and perhaps less obviously, even if DR == DA = R" it may happen that x(t) tends to infinity. The reason for divergence is that if Q (/,X,
464
the measures to keep x(t) in a bounded area may not be completely arbitrary to obtain convergence. A feature that can be used when DR == DA = R", is to introduce a saturation in Q(.; ., .) so that IQ(r; x,
x(t)- [x(t-l)+ y(t)Q(t,x(t-l),cp(t)) ]0 1,02
if x(t - 1) ED) a value in a given compact subset of R m if x (t - 1) e D I
Z
(29)
It
2
if zED
={ some valuet in D2
if z r= D I •
It should be clear that D., D 2 cannot be chosen arbitrarily. Loosely speaking, the trajectories of (19) that start in D2 must not leave the-area'Dl~ Otherwise there may be an undesired cluster point on the boundary of D r- This may be formalized as follows. . Theorem 4: Consider the algorithm (28), (29) subject to assumptions A, B or C. Let D( C DR be an open bounded set containing the compact set D 2• Let fj == D I \ D 2 (D. "minus" D 2). Assume that D2 C DA , with DA defined as in Theorem I. Suppose that there exists a twice differentiable function If(x) > 0, defined in a neighborhood of D with properties sup U'(x)f(x) <0,
(30)
xeD
U(x) > C 1
for x f£ D 1
U(x)
forxED 2•
(31)
Then Theorem I holds without assumption (20). The proof of Theorem 4 is given in Appendix IV. Assumption (30) clearly makes U ( .) a, Lyapunov function in iJ, while (31) formalizes the- intuitive notion of trajectories from D2 never leaving Die We may remark that (30), (31) hold, e.g., if the trajectories of (19) do not intersect the boundary of D 1 "outwards" and D2 is sufficiently close to DrVII. How TO
USE THE THEOREMS
The intuitive content of the theorems of Section V is that the algorithm (1), (2),
x(t)=x(t-l)+y(t)Q(t,x(t-I),cp(t»
can be studied and analyzed in terms of the differential equation (33)
where f(x)== ,--.CX) lim EQ(t,x,~(/,X»).
(34)
(3~).
where D1 ::::> D2, and [ Z ]D D
(32b)
The precise statements about the relations between (32) and" (33) of Theorems 1-3 may be summarized in a somewhat looser language as follows. a) x(t) can converge only to stable stationary points of (28)
A(x(t-I»)cp(t-l)+ B(x(t-l»)e(t) cp(t) =
(32a)
b) If x(·) belongs to the domain of attraction of a stable stationary point x· of (33) i.o. w.p.l , then x (I) converges w.p.1 to x· as t tends to infinity. c) The trajectories of (33) are "the asymptotic paths" of the estimates x(')t generated by (32). These statements are fairly attractive intuitively, and they suggest certain unified techniques to analyze recursive algorithms. We shall illustrate this below, but let us here point out some aspects. By the result a) the possible convergence points of (32) may be determined and studied. That a possible convergence point must be a zero of (34) is fairly obvious and it may be derived without reference to any differential equation. However, the observation that among these stationary points only stable ones are candidates for being limit points of (32) is a most important complement and it is probably less obvious without the present interpretation in terms of the differential equation. Perhaps the main use of result a) is to prove failure of convergence. It may be remarked that usually an algorithm is constructed so that the desired limit indeed is a stationary point. Consequently the possible lack of convergence is then due to the unstable character of the stationary point, so it is the complement (25b) that is the key result for proving divergence. Result b) is the result by which convergence can be proved. In many cases it is not easy to find a proper Lyapunov function to prove global stability of (33), and sometimes the RHS of (33) is quite complex. For certain algorithms, though, in particular those arising from criteria-minimization, it is possible to do this analytically, and some examples will be given below. While analytic treatment of (33) may be difficult, it is always possible to solve it numerically when the dimension of x is not too large. In that way insight can be gained into the global stability properties of the differential equation, the stationary points and their character. In view of result c) the trajectories thus obtained are also relevant for the asymptotic behavior of the algorithm. Therefore, numerical solution of (33) is a valuable complement to simulation of (32). Due to the time scaling (26) in the differential equation, this reveals more rapidly the asymptotic properties and the stationary points of the algorithm. Since the estimates change more and more
465
slowly, due to (4), it is seldom not difficult to decide from simulations only whether the estimates have settled around a limit value or are just converging slowly. In addition, it might be difficult to tell from a simulation if a certain effect is an inherent feature of the algorithm or just depends on random influence. Numerical solution of (33) may resolve such questions. The regularity conditions A, B, or C are usually not very difficult to verify as demonstrated below. Notice in particular that the observation cp may have a "dummy" character, since it may have to be extended to fit into the assumptions (2) and A.I. For example, if the sequence ( e( ·)} in (2) is stationary process with rational spectral power density, then it can be modeled as the output of a stable, linear filter with independent random variables as input. Hence, by extending the vector cp and adjoining this filter to (2), assumption A.I will hold. Even if this may lead to a vector tp with a large dimension, the complexity of the algorithm and of the analysis is not affected. What matters is the calculation of
frequently used in Tsypkin's work, see, e.g., [15], [16], clearly can be understood as a stability condition for (33) with V(x)= lIx - x*lt 2 as the Lyapunov function. Tsypkin's condition
is then a variant of the "boundedness condition." The convergence results thus obtained are, however, essentially restricted to the case cp(.) being independent random variables (A (: )==0) and y(.) satisfying (17) which is quite restrictive for control and estimation application. These conditions are inherently tied to the use of martingale theory in the proofs and cannot easily be dispensed with. OUf Theorem 1 when applied to (36) is thus more general in that (J>(.) may be dependent (gerierated as white noise through a linear filter) and y(.) has only to satisfy A.7. This is satisfied, e.g., for y(/) = Ct :" 0< a < I, while (17) admits only 1/2< a ~ 1. Notice that slowly decreasing gain sequences may be of interest in practice to achieve fast convergence of the sequence of estimates. We must, however, admit that we in return EQ (/,x,qi( t,x») require more regularity of Q and of e(·). On the other and this can often be done without explicit expressions for hand, nonsmoothness of the involved functions is seldom a problem in applications, and we believe that our version A( ·),B(·), 9'( .), and even for Q(" ., ·). In the next section we shall apply the method to a few of the convergence theorem is more widely applicable. In addition, Theorems 2 and 3 are important results for examples and illustrate how the techniques of the items convergence analysis, and we are not aware of similar above may be used. previous results for the Robbins-Monro scheme. In many applications it is of interest to minimize a VItI. EXAMPLES function ErpJ(x,q»=P(x) with respect to x. If the derivative of J with respect to x can be calculated, the stationary Example l-i-Stochasttc Approximation Algorithms points of P(x) can be found as solutions of
a
Consider the problem of solving (35) for x. Here "E." denotes the expectation with respect to qJ, while the vector x is considered as a fixed parameter. Quantities Q(x,cp(t», t == 1,2,· · " are available for any x, where the distribution of the random vector q>( •) does not depend on ·x. Robbins-Monro (11] proved that under
certain assumptions the scheme ("the Robbins-Monro scheme")
x (t) =x (t - 1) + 'Y ( t)Q (x ( I - 1),9>( I) )
(36)
gives a sequence of estimates that converges to the (a) solution of ,(35) in the mean square sense. Convergence w.p.l of (36) has then 'been studied in several papers, e.g., [12H14], and the theorems of these studies do not differ very much conceptually ftom Theorem I. The functions used in the convergence theorems of, e.g., [12] or [13] can be interpreted as Lyapunov functions for the differential equation (33) and condition (20) of Theorem I is ensured by further conditions on this function, rather than by the more practically oriented 'Theorem 4, see, e.g., [12, condition A); or [13, condition B, p. 184]. It can also be
remarked that the conditton (37)
This is a problem that can be solved using the Robbins-Monro scheme and then Corollary 2 of Theorems 1 and 2 is quite useful. If the derivative of J cannot be calculated it seems natural to replace it with some difference approximation. This was suggested by Kiefer and Wolfowitz [17] and their procedure has also been used for, various control and estimation problems. Kushner has in several recent papers discussed interesting variants of this procedure, see e.g., [18], [19]. Our theorems are not directly applicable to the Kiefer-Wolfowitz scheme as they stand, since condition A.3 (or 8.3) is not valid. The reason is that the function Q in this case increases to infinity with t. For the case of additive noise to the function to be minimized, however, it can readily be shown that Theorems 1-4 hold anyway. Details are given in [5] and [7J. , Stochastic approximation algorithms have been applied to a broad variety of problems in control theory, see e.g., Tsypkin [15], [16], Fu [20], and Saridis el aI.. [21]. The approach is known as "learning systems," and in this framework estimation and identification problems, adaptive control, supervised and unsupervised pattern recognition, etc. can be treated. An approach that is related to stochastic approximation
466
is suggested by Aizerman et al. [13]. Their "Potential Function Method" can be applied to various problems in machine learning. Therefore the Robbins-Monro scheme appears in various disguises in many control and estimation algorithms, and consequently the described techniques can be applied 0 to these. A particular example is given below.
-J
c(t)=(x A (/)+x B (t»)/ 2 where
x A (t-l)+ y(t)[ qJ(t)- x A (t-l)], if qJ ( t) is classified as A x A ( t - 1), XB(/)
(39)
otherwise.
is defined analogously. Clearly, x A (I) is the mean
value of the outcomes classified as A. This scheme is discussed by Tsypkin [22] and Braverman [23]. Let cp(/) have the distribution shown in Fig. 2 consisting of two triangular distributions. The probability of outcomes in the left triangle is A. We assume that cp(.) is a sequence of independent random variables. Clearly, it is desirable that the classification rule, the number c(t), should converge to some value between - I and + 1. Introduce
x(t)==
XA(t) ] . [ xB(t)
Then (39) can be written
x(t)=x(t-l)+y(t)Q(x(t-I),cp(t»)
(40)
where
-I
0
Fig. 2. Probability density function of the random variable to be classified by the automatic classifier.
Example 2-An Automatic Classifier A classifer receives scalar valued signals tp(t) which may belong to either of two a priori unknown classes A and B. The classifier must find a classification rule, i.e., a number c(t) such that qJ(t) is classified as A if cp(t) <; c(t) and B otherwise. The number c(/) can, e.g., be determined as follows:
-t
Clearly, the algorithm (40) together with the observation equation
(41 )
is a simple case of (32). Since cp(.) = e( .) is bounded we may use assumptions A. Obviously A.I to A.5 are satis . . fied, and let us assume that y(.) is such that A.6-A.9 hold. (Here A.3 holds in virtue of our somewhat artificial modification of QA; but this example will illustrate that a heuristic use of the present convergence results will reveal important features of the algorithm.) E"Q(x,fP)=!(x) is readily computed as follows. For a given x the corresponding classification point is c(x) = (x A + x B)/2. fA (x) is then the mean value of the distribution left of the point c(x), minus x A • fB(x) is found correspondingly. The algebraic expression for f(x) as a fune .. tion of x and "'A is lengthy and is omitted. We first note that by construction, the estimates are confined to the area D: 3> x B :> x A > - 3. Therefore condition (20) of Theorem 1 is trivially satisfied. Analytical treatment of the differential equation x = f(x) is not easy, but its trajectories can easily be determined by numerical solution and they are shown in Fig. 3 for two choices of A. For the case A= 0.5, [Fig. 3(a)] there is convincing evidence that the point x* = ( - 2,2) is a stable stationary point with global domain of attraction. Therefore, for A=O.5 it follows from Theorem 1 that x(t)~x* w.p.l as t --+00, which gives a correct classification rule c· = O. The case A=O.99 [Fig. 3(b)] corresponds to a common situation where errors that occur rather seldom (I percent), "outliers," shall be detected. In this case there are two stable stationary points of the differential equation. x* = (-2,2) and x*·=(-2.3, -1.4). There is obviously a non.. zero probability that x(t) belongs to the domain of attraction of x·* i.o. Therefore Theorem 1 shows that for "'A = 0.99, and for any starting value x(O) there is a nonzero probability (that depends on x(O)) that x(t)~x·* as t~ 00. This gives an asymptotic classification rule = - 1.8, that classifies 39 percent of the "correct values" as out.. liers. For this case simulations of the classifier are shown in Fig. 4. In fact, the simulation leading to the undesired value c** appeared only after several (257) attempts and from simulations only it might have been tempting to conclude general convergence to c·. In this example it is cumbersome to find a suitable Lyapunov function for the stability problem. However, as seen in Fig. 3 numerical solution of the differential equation yields sufficient insight into the stability properties. Such detailed information can naturally be obtained only if the dimensionality of the problem is small.
c··
and A(
Q
A X
,x
B
)_{cp-x
,qJ -
0,
A
,
if
if
i(x x
i<x
A A where the values for + B) - 8 c cp ~ + X B) + 8 are such that QA is a continuously differentiable function
of qJ and x. Here 8 is some small positive number.
467
.....---------n
(a)
Fig. 4. Simplations of the classifier (40) for the case A-O.99.
the unit circle, i.e., D (q - I) is an exponentially stable filter. Even if an exact description of the system is impossible, a fJ can be determined that gives a model (44) which describes the recorded data as well as possible. Often 8 is determined by minimizing a criterion based on the equation error
,/ ;'
3 .,
(47) (b)
Fig. 3. Trajectorie, for the ODE that is aasociated with self-learning classifier (40). (a> A-O.S. (b) A-O.99.
Example 3-Equation Error Identification Methods A common way of modeling dynamic systems is as a vector difference equation (VDE),
Several algorithms based on the idea of somehow minimizing (47) have been suggested in the literature, see e.g., [24] and also [25] for a comprehensive treatment. The probably best known method of this type is the least squares algorithms, see, e.g., [24]. Then the sum N
~ lJy(t)- 8T~(t)1I2
(48)
1-1
y( t)+ A 1y (t - I)+ ' " +AIV"(t-n) · mimnuze . . . d w.r.t 9 to 0 btai . 9(N)based on IS tam the estimate = 8.u(/-1)+··· + B"u(t- n), (42) measurement up to time N. An important and well known feature of this method is that the sequence of estimates where y(t) and u(t) are column vectors and A; and B; are can be obtained recursively as matrices of appropriate dimensions. Introduce
8=(A." .A"B I " I
.
9 (t) ... 9 (t - 1)+ y(t)%(t) [y( t) - 9 (t -1) T\fi( t)
B,,)T
"'(/)= ( -Y(/-I) T... -y(t-n) Tu(t-I)···u(t-n) T)T. (43)
=iJ T1IJ( t).
(44)
(49a)
%( r) = R - 1 (I - I)",( t )
/[ 1+ y(t)(\fi(t)TR -I (t-l)\fi(t) - I)] == R - I (t)l/; ( t)
Then (42) can be written y (t)
r
R(t)=R(t-l)+y(t)[ \fi(t)\fi(t)T - R(t-l)]
(49b)
(49c)
We may remark that (44) also covers several other inter- (usually (49c) is written in terms of R -1(/), which makes esting estimation problems, not necessarily related to sys- it of "Riccati type"). For the minimization of (48) y(/) has tem identification. to be taken as 1/ t. Other sequences 'Y ( .) correspond to Usually, the true system cannot be described exactly in criteria where old measurements are discounted, which
the form (44). Suppose that it can be described as
Y (I) =8[1/I(t) + v( t)
often is relevant in practice. Let us assume that the input to the process is de(45) termined as
where v( .) is a disturbance that can be modeled as
V(t)=D(q-l)e.(t). (46) Here D (q - I) is a matrix with rational functions of the backward shift operator q -I as entries and e l( .) is a stationary sequence of independent random vectors with finite moments. It is assumed that the denominator polynomials in D(z) (z replacing q-l) have all roots outside 468
where F(q-I) and H(q-I,9) are matrices with rational functions of the backward shift operator q - I as entries. Let el( · ) be a stationary sequence of random vectors with finite moments, that are mutually independent and also independent of et(·). Moreover, H(q-I,8) is a causal operator that allows output feedback terms in the input.
This feedback law may depend on ,the current parameter estimate as is further discussed in Example 5. It is clear that the rational filters in (46) and (50) can be represented in a state space form,
Since e;(·) are stationary, q5(t,X) w~l approach stationarity exponentially, for all x, such that 8 makes the closed-loop system stable. Therefore the limits
f( i) = lim E~ (t,x)[ j( I,;) - 8T~ (I,X)] T (59a)
v(t) = (J O· · · O)zo(t)
I~~
(51) ZII (t
G(i)= lim E~(t,x)f{t,X)T
+ 1) == All( 8 (t) )Z., (I) + z., + B.e2(t + I) + BuyY (t + I); U(/)=(I O· . · O)ZII(t),
(52)
are well defined where y(/,X) and \fI(t,X) are the corresponding parts of ~(t,i), and
where zo(·) and z..(·) are the corresponding state vectors of appropriate dimensions. We may now form the "observation vector,"
lim EQ(t;x,~(I,X»= 1-+00
cp(t)== [ Y(I) T ,1/1(1) T ,Zo(l)T ,ZII(t)T]T
(59b)
1-+00
i -(1(O)_ _) 1 [colG(8)-R
(60)
(53)
so 8.6 is satisfied. Moreover, from (57) and (58) it follows that B.7 holds, since all moments of ~(t,x) and V(/,A,C) exist. Conditions B.8-B.ll about the sequence y(.) are e1(t») cp(t)=A",(8(/-l»cp(t-I)+ B", ( e ( t ) (54) assumed to be satisfied. 2 The conclusion therefore is that the differential equation where the matrix Atp( •) is formed from (45), (43), (51), (52) in an obvious manner. Its eigenvalues are the poles of the ; 8('1")= R -1 ('I")j(8('I") (61a) filters D(q-I), F(q-I) and of the closed loop system which is obtained for (42) with a constant feedback (50) d using 8 (t - I). There are also a number of eigenvalues in (6Ib) d'T R(T)==G(8(T»)- R(T) the origin, arising from the shifting of the vector 1/1(/). Notice that Arp(9) depends on 9 only since the feedback can be associated with the algorithm (49). In the remainfilter H(q-l;8) does. Let us take ing part of this example, we shall assume that the feedwhich obeys
back matrix H does not depend on 8 (i.e., there is no (55) adaptive feedback), that the matrix F(z) has full rank a.e. z and that e;(·) are full rank processes. (Adaptive feedback is further discussed in Example 5.) This means that (56) the matrix ACJ>(·) does not depend on fJ, cp(/,X)==cp(t), and y(t,X)= y(/), so the values in (59) are directly defined in
X(/)=( 8(t)T colTR (t)( Then (49) takes the form
x(t)==x(t-l)+y(t)Q(t;x(t-l);cp(t»
with an obvious definition of Q(I;X,cp) from (49). There- terms of input-output covariances. In particular, the fore the algorithm (49) together with (54) is of the general matrix G is independent of 8; G(fJ)= G. form (32). Let us check if assumptions 8 of Section IV are Introduce satisfied. Conditions B.I and B.2 are satisfied due to our assumptions. By straightforward calculations it is readily r = Ecp( t)v( t) T (62) shown that B.3 is satisfied in the open area DR == {xiR > and we have, using (45), OJ, [cf., (55)] e.g., with
f(9)= G·«(Jo-8)+r.
:JC,(x,cp,p, v) == (191 + p)(l + Icpl + V)2 /( 1- pi R -11)2 (57) for p=p(x)<
l/IR -II. Then
Hence, (61) can be rewritten as
B.4 will be satisfied with
~(x,cp,p,v,w)-(191+p)(lcpl+2w+ v)/(I-pIR
2
; 8 ( r] = R - I ('1") G[(80 + G - 1,) - 8 ( r) ]
-II) . (58)
d .
Condition B.5 is satisfied if the matrix H(q-I;(J) is With Lipschitz continuous in 8. For condition B.6 we define
~(/,x)::z A",( i )~(t -
(63)
l,x) + B", (e l (I») e2 ( / )
and
(i = (iT colTR)T). 469
d"R(T)==G-R(T).
(64a) (64b)
we have
{A(t)}. Take in this example the observation to be
~ V(O (T),R (T»)= -20 TG9+OT (G- R(T»O == -
iT (1")( G + R (1"»)9 (1") <; 0
11 ( /) ) cp( t) = ( colA( t)
(69)
(65) and in (32b) A (x):=O, B(x):=/. The estimate is as before given by (55). The condition C.I has already been verified and XI can this time be taken as
so that V is a Lyapunov function for (64) or (61) that assures that the stationary point
'X,(x,cp.P, v) = I + Ixt + p+ IAI + c.
(66)
(70)
has a domain of attraction equal to DR' Therefore condi.. tiIon.(21) 0 f Th eorem l 1S i sa t'ISC·red WI with D D T0 Ch ek cCondition C.2 IS. trivially satisfied, The vanable z(t,X) A == R. , . condition (20) we note first that the assumption on full defined by (18a) IS given by rank and finite moments of "e;( .) implies that CI > G > 81 for some 8 > 0, C < eo. Therefore also (8/2)1 < R (t) < !R -I [1J(s) - A(s)8] 2CI and IqJ(t)1 <2C i.o, w.p.l. We also note that (49a) can t $=1 for large 9(t-l) be written z(t,i)= II
•
•
0
0
0
0
•
•
±
1
(J ( t) ~ (I -
col
R - I (t) \fI( t)'"(t) T )9 (t - 1)
R- 1
that
==
w.p.l as
t
~ [A(s)- i] s==1
which shows that 9(t) can, w.p.l, not tend to infinity. Hence x(t) belongs to a compact subset of DR i.o, w.p.l and condition (20) is satisfied. Theorem I now implies 9(t)~9·
t
1-+00.
col
{[! ± t
1J(S)]-[+
±A(S)]e}
s-1
s=1
(71)
[+ ±A(S)] -colR s-1
In particular, we see that the least squares estimate is
\.
consistent only if r =0, which essentially is the same as where requiring that v(·) is a sequence of uncorrelated random variables, and that the current u(t) is uncorrelated with future v(s), s ~ t. colR Other variants of equation error methods are treated analogously. These facts are, of course, well known, [24], (25], at least Therefore, if the sequences (1J(s)} and for the case y( t) = 1/ t, but one reason for this example is that that the analysis extends into less trivial problems. 0 1 t - ~ 1J(s)-+.q 1 £-1 Example 4-Equation Error Methods-Assumptions C
x==( e ).
The model (44) and the criterion (48) appear in several contexts, like curve fitting, etc., where a stochastic framework often is not imposed. Let y( I) == 1/t and denote
"'(t)y(t)T ==1)(t)
(67a)
1/J( I)1/;(t) T == A( t).
(67b)
{~\(s)}
are such
(72a)
and
(72b) then C.3 holds with
(73)
Then the algorithm (49) can be written
8(/)-8(1-1)+!R -I (/)[1J(/)-A(/)8(/-l)]
(68a) Since A and B do not depend on x (see C.?) condition C.4 is satisfied if
t
R(t)-R(/-l)++[A(/)-R(/-l)].
(68b)
1 I - ~ IA(s)1 t 3-1
converges
(74)
We shall in this example illustrate how assumptions C can be applied to the algorithm (68) to infer convergence which is implied by (72b) if A(s) == ~(s)1/;(S)T. The directly from the properties of the sequences (.,,(t)} and boundedness condition of Theorem I has been verified in 470
Example 3. The differential equation
methods, like Landau's scheme [28] etc. Since a companion paper [29] is devoted to the last two schemes we shall d' - not go into any detail here. Further analysis of some dr 8(T)= R -I (T)[ 71- A8(T) ] (75a) recursive identification schemes using the present approach can also be found in [I], (30), and [31 [, ;R(T)="A-R(T) (75b) It was remarked above that the structure (32) can be understood to be patterned after adaptive control of linear is as shown in Example 3 globally asymptotically stable systems. We shall therefore conclude with such an example. with stationary point (76) Example 5-Selj-Tuning Regulators
if A is positive definite. Hence Theorem 1 implies that 8(,) given by (68) converges to e* defined in (76) for any sequences {A(s)}_and {ll(s)} such that (72) holds with a positive definite A. This is by no means surprising since (68) in fact only is a way of recursively writing -I
9(/)=
L~I A(S)] S~I 7I(s)
using the matrix inversion lemma, However, it illustrates that our method of analysis does not bring in "unnecessary" assumptions, even though it is concerned with a more general algorithm. Moreover, for a stochastic approximation version of (68), 8(/)=8(/-l)+! [71(/)- A(t)8(1 -1)] I
(77)
We shall in this example discuss an application to the self-tuning regulator, described in [32]; see also [2] and [4]. This regulator is based on least squares identification, (49), and the output feedback law is determined from the current parameter estimates. Usually the feedback law is chosen to be a minimum variance regulator, [32], but here it could be a general linear regulator as in (50), where perhaps in most cases F is zero. In this case the matrix ACJi«(J) in (54) does depend on () since the feedback term does. However, the point now is that, in contrast to conventional analysis of the least squares algorithm, most of what was said in Example 3 still holds. Up to (61) the development was quite general. This differential equation is valid also in the case of adaptive feedback. although G and r now are functions of 8. If v(') is a sequence of independent random variables, then r=O and (64) and (65) hold. (Equation (65) does not hold if r~O depends on fJ.) We therefore still find that the points defined by
we have exactly the same convergence result under the condition (12), since the associated differential equation then is form an invariant set with global domain of attraction. (78) Clearly ·BoE D~ . and whether D~ contains more points depends on the choice of feedback law and model order. In this case no explicit expression for 8(/) is available to There is a further complication before Theorem I can be infer this result directly. In fact, the algorithm (77) has applied. In this case the area Ds is unknown" i.e., the area been studied in [26], [27] using fairly elaborate methods, of such (J that inserted in a constant feedback law (50) d d" e(,,)=~-Ae(T).
since it was found that the usual stochastic approximation
makes the closed-loop system stable (Acp(9) in (54) has all
convergence results could not be applied due to the correII lation in the sequences {A(s)} and (1I(s)}. These four examples have all been for the case where A(·) in (32b) actually does not depend on x, The convergence part in this case can, at least under further assumptions, not seldom be treated by more conventional statistical methods. When A ( .) does depend on x, conventional approaches become much more difficult, and in fact, also in the proof of Theorem I, a major burden is to keep control over the coupled stability questions in (32a) and (32b). The inclusion of x-dependent A -matrices becomes necessary for more elaborate recursive identification methods in which the observed data are processed through filters that are formed from current parameter estimates. This is the case, e.g., for the extended Kalman
eigenvalues inside the unit circle). Therefore we cannot guarantee stability by projecting 9 into Ds . Hence condition (20) of Theorem I has to be verified by other consid.. erations, e.g... by showing that the overall system has a certain stability property as in [33]. But when this is shown, Theorem 1 proves convergence of 9(/) into D, w.p.l. Let us repeat that this holds for the case of arbitrary feedback law, but under the assumption that r(·) is white noise. For general noise c( ·) the convergence analysis is more cumbersome. but it can be performed in certain special cases" [2], [4]. [29]. We refer also to these papers for more details on how Theorems 1. 2. and 3 can be used in the analysis of self-tuning regulators. Numerical solution of the associated differential equation has turned out to be a valuable tool here, and it has been used in [34] as well as in the references above.
filter, the extended least squares method, output error
471
IX.
CONCLU.SIONS
W." The abbreviation "i.o." denotes as before "infinitely often." U
Recursive algorithms like (I) have been analyzed in various contexts. However, we would like to stress again that when cp in (I) is generated as in (2), the analysis becomes more difficult. The reason is that (1) no longer is recursive in x for analysis purposes: the whole history of x(·) enters in each step of (I). Moreover, the coupled stability problems between (1) and (2) are intricate. But the structure (1), (2) is nonetheless common in estimation and control problems; a typical example is adaptive control of linear stochastic systems. The analysis of this case is also known to be usually very difficult. • With the present approach we are able to give a general treatment of (1), (2) under assumptions that do not appear to be restrictive. The examples indicate that the theorems may be applied to rather diverse problems, and perhaps the technique also may serve as a basis for a unified approach to the analysis of adaptive controllers. In addition, an extension is obtained for the conventional convergence results in the simple case where A ( .) in (2) is independent of x. We may remark that the analysis is restricted to the asymptotic behavior, convergence, possible convergence points etc. of the algorithm. Two related algorithms which are associated with the same differential equation may differ noticably in transient behavior and convergence rate. In the described theory, we would like to stress the intuitive content of the theorems and the methodology of analysis as outlined in Section VII. I t is no doubt important to appreciate" the exact formulations of the theorems and to know the exact conditions under which they are valid. But it is perhaps equally rewarding to use the properly defined differential equation as a general instrument for analysis in a more heuristic fashion. This may be exemplified in Theorem 3, which has a fairly technical formulation. and' is probably more valuable as a "moral
ApPENDIX
I
PROOF OF THEOREM
I
Outline
In order to prove Theorem 1, we shall first show that the estimates provided by the algorithm locally and asymptotically follow the trajectories of the associated differential equation. This will be done in Lemma 1 under assumptions C and the proof of this follows the intuitive outline of Section III. After that the local behavior of the algorithm is thus established, this is used to prove that all cluster points of the sequence {x(t)} must belong to Dc. This is done by means of a Lyapunov function, the existence of which is inferred from the stability condition (21). A possible clusterpoint outside the set D, would yield a decreasing value of the Lyapunov function along the corresponding trajectory of the differential equation. Since Lemma 1 proves that we follow this trajectory asymptotically, a contradiction is obtained. The value of the Lyapunov function is decreasing outside D, and it is not possible to return a given point outside D, infinitely often. This is the intuitive path of proof. The many technicalities tend to obscure the simple idea, and the proof will be structured as much as possible to enhance the basic ideas. Finally it is proved in Lemma 2 that assumptions A or B imply assumptions C for the case y(n) = 1/ n. An outline of the general proof will also be given, but the details of this are omitted, and the reader is referred to [7] for them. Lemma 1: Consider the algorithm ( l ), (2) under assumptions C. Let .~ E DR and define the number m(n,a'T) such that
support" for studying the trajectories of the differential
m(n.~'T)
equation, than in its literal sense.
~
y(t)~aT
asn-+oo.
(1.1)
n
Assume that
ApPENDICES
The proofs of Theorems 1--4 are given in Appendices I-IV. They are slightly compressed versions of the proofs in [7], in that some calculations of technical nature are omitted. Proofs for a simple special case of the algorithm (1), (2) are also given in [6]. These are naturally less technical than the present ones, and reveal perhaps more clearly the underlying ideas. The basic path of the proofs of Theorems 1 and 3 follows the heuristic outline of Section III. Some notational conventions in the proofs should be noted. "C" will denote any constant, that need not be the same in different parts of the proof. Important dependencies of the constants will be given as arguments, while indexed constants are "global" throughout the proof. "~5 (x,p)" denotes as before an open p-neighborhood of x. Realizations in the sample space n will be denoted by
s. p)
(I.2a)
is sufficiently small
(I.2b)
x ( n) E ~~ (
where p = p( x)
and that (1.3)
Then, there exists a value aTo=~To(;'p) and a number No= NoC'i,p) such that for ~T
(1.4) where m=m(n.. ~'T) and
472
ql (n,m,x)~O
as n-+oo
(1.5)
and
p = p( x)
(1.12)
where A(X) is defined by (14). The idea obviously is that since the matrix A (X) is where C1 and C2 depend on x and p, but not on n> No or exponentially stable, exponential stability of the timevarying difference equation (2) given by A(x(k» will be aT. Proof of Lemma 1: The proof is structured into 4 guaranteed if x(k) varies in a sufficiently small neighborhood of x. The formal proof consists of straightforward steps. In Step 1 an explicit expression for xC)~ where calculations given in [7], but omitted here. The "sufficiently small" p mentioned-in (1.2b) refers to the fact (1.7) that p should be so small that (1.12) implies (1.11). From (2) it follows that is derived. This expression shows that if certain terms are small, then xC}) is close to what would be obtained if Q(t,x(t ~ 1), cp(t» is replaced by Q(t,x,~(t,X) [with [ IT.A(X(k»]B()e() ~(t,X) defined by (15)]. As a first step to show that these cp(t)= [ k-n j-" ks«] terms indeed are small an expression for cp(t)- q;(t, X) is derived in Step 2. This expression is used in Step 3 to (1.13) prove that assumptions C.3 and C.4 imply that the terms are small. A complication so far has been that in order to which together with (1.11) and (1.3) implies that prove these things it must be assumed that x(s) remains in t for n <; s <; l- In Step 4 it is a small neighborhood of Icp( t)1 < C·C.,X I-n + ~ eX I-JIB (j)lle(j)1 (1.14) proved that x(s) actually will remain in this neighborhood j-n up to s = m(n, 41") if 41" is chosen sufficiently small (and dependent only on X) and n sufficiently large. This will if (1.12) holds. Since the variable conclude the proof. ep (t) ~ cp ( t) - ~ ( t; x) Introducej= j(,,) such that
IT A(X(~»lcp(n)+ ~
x
(1.8) obeys and
ep (t + 1) == A ( i)ep (t) + [ A ( x ( t)) x(k) E
k = n,n + 1,. · · ,j - l.
~ (x,2p),
A (x) ] ~ ( t)
(1.9)
+ [B(x(t»)- B(x) ]e(t+ 1) (1.15)
Step I-An Expression for x(j) Directly from the algorithm (I) the following expression we have that is obtained: j
~
x()=x(n)+
y(s)Q(s;x(s-I),cp(s»
1-1
+ ~ A(x)'-S[{A(x(j»-A(x>}cp(j)
s-,,+1
j-n
j
==x(n)+ ~ y(s)Q(s;x,iP(s;i»)
l
n+l
+ { B (x(j») - B (x)} e(j + 1)
(1.16)
j
+ ~ y(s) [ Q(s, x(s -1 ),«p(s») - Q(s; x,~(s; x») J
If KA and KB denote the Lipschitz constants of A(.) and (1.10) B (.), respectively (see assumption C.2), then from (1.16) and (14) it follows that
n+1
where q>(s; i) is defined by (IS). End Step 1. The first goal is to show that the last term in (1.10) is "small," and in order to do this we first consider qJ(s) -
lep(t)1 <;
f.A(X)/-n {1
~(s;i).
+ c ~ A(X)'-i[ KAlx(j) - ~Hq>(j)1
Step 2-An Estimate for Iq>(t)- q;(t,X)1 'We claim that I
II A (x(k»)";
k-"
c[
1+A( -) 1-"
X]
2
j-n
+ KBJx(j) - ille(j + 1)1].
~ CX(x),-n
(1.11) Clearly, with v(n,A,c) defined by (16),
c{I«p(n)1 + ,,( n,x)l} c v(n,A( x),c)
if x(k) E ~ (i,2p);
n ( k <; t
(1.17)
for sufficiently small
for some constant c. 473
(1.18)
Now, inserting (1.14) and (1.18) in (1.17) gives
We thus find that
lcP (/)1 c A(i)'- nv( n,A(x),C) + c- max (KA , Ks -)
j
x(j) = x(n)+ ~ y(s)f(x)+ R. (n,j)+ R2 (n,j)
(1.23)
s-n
where I-I
+
j
j
R 1 (n,j) = ~ y(s)[ Q(s,i,lj)(s;i")- f(i)]
~ ~ A(i)/-JXJ-k)e(k)1
$.
j:snk-n
(1.24)
n
and
Sum first over j in the double sum and introduce c' and A where such that
A< 1.
·{I + V(S,A,C)}
Then 19'(t)-q;(t,i)1 (A(X),-nV(n,A(x),C)
+ max
n<j
~(j) -
(1.26)
and
x1 ·V(t,A,C).
(1.20) Q4(n,}) ==
ma~ n<s<j-t
{'X1(i,cP(s; x),2p,V(S,A,C») j
.v(s,A, c)'"'(s) }. ~ heX) s- n.
In particular,
(1.27)
,s-n
h(x),-nv(n,~(i),c)'-; C(t,A(X),C)
Step 3a-maxn<J<m(n,~1')IR.(n,j)I-+O as n-+oo Let the maximum be attained forj=j*(n). Solving (18a) we obtain
and therefore also
Iq;(t)- ~(t,i)1 (V(t,h,C)
(1.21)
j*(n)
~ y(k) where A can be taken as (3+A(X»/4 and c is a constant k=n+l that is obtained from c.' c in (14), C in (1.11), c~ in (1.19).. KA , KB , and maxIB(x)l(xE~(x,p». However, since ·[Q (k,x,cP(k.x») - z(k - Lx)]. assumption C.4 shall hold for any finite c, there is no point in tracing the expression for c through the calcula- Now, let n tend to infinity. By assumption C.3 tions. lim z(n,x)= lim z(j*(n),x)=f(i) We summarize this step as follows: Choose 2p in (1.9) n--.oo n--.oe so small that (1.12) implies (1.11) for this p. Then (1.20) and hence and (1.21) hold for n <: t
z(j*(n) ..x)=z(n.i)+
n--oc
IQ(s,x(s - 1),
End Step 3a. Step 3b: There exists an N 1 such that
· [lx(s-l)-xl+lcp(s)-~(s;x)l]
(
max
n
Ix(k) -
forn>N 1,
il' 9(1(x,~(s,i),2p,V(S,A,C»)
·{I + V(X,h,C)} + %1(x,q;(s,x),2p,v(S,A,C») 'A(x)s-lI v(n,A,c)
wherethe last inequality follows from (1.20).
where kf) is the limit of kv(t,x,A,c) defined in C.4. This step is completely analogous to Step 3a, using the defini(1.22) tion (ISb) and assumption C.4. End Step 3b. Step 3c-q4(n,)(n))-+O as n-+oo 474
It now follows from (1.33)-(1.35) that
From (18b) y( s )·v(s,A,c)' %.( x,q>(s,x), 2p, v(s,A,c»
Ix()) -
il < 2p
== kv(s) - kv(s - 1)+ y(s)ko(s - I). and hence that (1.30) and (1.31) hold. End Step 4. The RHS tends to zero according to C.4 and C.6 and the From (1.33)-(1.35) it also follows that claim is proved. End Step 3c. IX(j) - xl ~ If(x)I~T + qs( n,m(n,~,,» Expressions (1.23)-(1.27) together with Step. 3 would complete the proof of Lemma I, if }(n) were equal to +4jii1T'k:, + tx(n)- xl. (1.36) m(n,4T), that is if x(k) remains in ~(i,2p) for all k up to m(n,~7'). This is proven in the final step. Since the RHS does not depend on), this inequality holds Step 4 for all n « ] <; min, ~T) for sufficiently small aT and large There exists a ~TO== a"o(x,p) and a No=: No(x,p) such n. that for ~T < LlTo and n> No, the expression (1.9) will hold Therefore, from (1.23)--(1.27) and (1.36) for j == m(n, ~T). By the definition of j(n) x( m(n,4T») = x(n) + aTf(x) + q. (n,m,x) + q2(m,n,x) x() - I) E ~~ (x,2p) (1.28) (1.37)
and
where
max
n<.k<'j-I
Ix(k) -
xl < 2p.
We shall show that (1.28) and (1.29) imply that also x(j)E~~(x,2p)
(1.39)
aT.
By induction it then
for sufficiently large n and small follows that x(k) E
~ (i,2p)
and
Iq2(n,m,x)1 c 2k:,.11"[ I/(x)l- a1" +4pad~:' + Ix( n) - xl]
k==n,···,m(n,d'T).
(1.31)
(1.39)
We have
for aT < ~TO and n > No. The expression (1.37) with (1.38) and (1.39) is the assertion of the lemma since q.(n,m(n,dT)X} lends to zero j according to Steps 3a-3c and (1.1) [remember that qs is
xl ( Ix(j) -
x(n)1 + Ix(n) -
xl
tR.
and C.4 hold and such that condition (20) of Theorem I
+4p·aT·~ + Iq4(n,j)1 +p
holds. It follows from the converse stability theorems (see e.g.,
strictly less than V(x(nk » if x+x*. The formal proof is somewhat lengthy and involves several elaborate choices of constants.. The result is, however, intuitively clear. The proof of Step 1 extends to (1.45). Step 2: From the above result it is quite clear that x* must be a cluster point to x(n), since V(x(n» has a tendency to decrease everywhere in DA except for x==x*. Step 3: If there is another cluster point to {x(n)} than x·, say X, the sequence must move from x* to x infinitely many times. But then V(x(n) is increasing, which contradicts the result of Step 1. Hence, only one cluster point exists and convergence follows. Step 1: Any cluster point of (x(t)} outside D; yields strictly decreasing values of V. From assumption (20) of Theorem 1 there exists a subsequence, such that
Then (1.44) implies that by a proper choice of e, aT, and K (see [7] for a detailed account), we have V(x(m(nk,aT») < V(x)-aT6/64
k>K.
(1.45)
End Step 1. This means that if x is a cluster point different from x* the sequence x(n) will i.o.. be interior to D={xlxE~ and V(x) < V(X)-~T8/64}. The conclusion that xED R follows from our assumption that trajectories that start in DR remain in there. This is r~quired in o!der to apply Lemma I to new points in D. The set D is compact. Consequently, another cluster point must exist that yields a smaller value of V. Moreover, since x(t)E~(x,2p) nk < t <; m(nk,d'T) we have from (1.14) k"
1
w
Xk - k'le(k + l )1
k=-=k'
(1.46) Since D is compact, there exists at least one cluster point and hence 1
as k--+oo..
(1.41)
Consequently, for arbitrarily small E: > 0,
Step 2: Suppose (1.. 45) holds for any subsequence {x(nk ) } that converges to a point different from x* . Then lim infV(x(t»)=O.
(1.47)
1'-+00
(1..42)
Consider inf V(x) taken over all cluster points in DA • Let this value be U. Since the set of cluster points in DAis compact, there exists a cluster point X, such that V(x)= U. If now U > 0, V'(x)f(i) will be strictly negative (= where m is defined as in Lemma I. Denote nk= k~ and 8) and from (1.45) V (x (k» takes a value less than Um(nk,AT)==k", and use the mean value theorem. This 5~'T/64 i.o.. , which contradicts U being the infinum. gives Hence, U=O, which means that x· is a cluster point. End Consider now
0
S~p2
V[x(k")]- V[x(k')] = V'(f)[x(k")-x(k')]
Step 3.* From (1.45) and (1.47) it follows that
t~~supV(x(t»=O.
=V'(i)[x(k")-x(k')]+[€-it
(1.48)
. IIy Let p* = p(x*) be the region for w hich (2)·IS exponentia stable for x(k) E ~ (x*, p*), as in (1.11), (1.12). where ~ and f' belong to ~(i,E+41"). Suppose that Now take e P(X), and we can in view of (1.42) apply Lemma 1 to x(nk ) , which gives (1.49) lim sup V(x(n»= W>O. .V"(t.')[x(k")-x(k')] ~
(1.43)
n~oo
x(k") - x(k') :=A".f(x) + ql (k',k",x)+ q2(k',k",x)
Take W < W such that
where q; are subject to (1.5), (1.6). Insert this into (1.43)
{xIV(x)( W}cB(x·,p*)
and consider the interval 1=[ W /3,2 W /3].. (We may of course choose any subinterval; there is no particular rea(1.44) son to divide it up in thirds.) Since x· is a cluster point and since V (x(n» is where supposed to have a subsequence tending to W, this interR3(~T,nk,i) =(f - x)TV"(f')(x(k") - x(k'») val I is crossed "upwards" and "downwards" infinitely many times by V(x(n). + V'(x){ ql +q2}· shall now proceed to show that (1.49) would imply that there must be a subsequence of V(x(n» that belongs Now suppose that the cluster point x is different from the to I, by proving that in ~(x*,p·) the "step size" x(n+ I) desired convergence point x·. Then V'(X)f(i)== - 8, 8 > - x(n) tends to zero. o,
V[ x(k")] - V[ x(k')] :aA'TV'(x)f(x) + R) (~T,nkx)
We
476
We shall now proceed to prove that assumptions A or B imply assumptions C.3 and C.4. This will be done only for the case Y(t) == 1/ t, which anyway should be the most common one. We may also remark that since the correction term Q(·, ., .) may be time-varying, this case also includes cases where
First, let x(iik ) be a subsequence tending to x", such that Jcp(nk)1 < C. (The existence of such a sequence follows from Step 2 and the stability argument (1.46), using the fact that p =p(i) is bounded from below by a positive constant in D.) For t > nk' but such that x(t) "remains" in B(x·,p·) we have, (1.46)
c(t) y( I) = -t- ; c( I)--+C
Icp(t)1 < eX 1-"*fcp(nk)1
(1.56)
be redefining the factors of the product
t
I
+ CIBt
as 1-+00
Xt-kle(k+ 1)1
y(/)Q(t,x,
ie-nit
Lemma 2. Suppose the algorithm (I), (2) is subject to assumptions A B. Assume that y(/)= lit. Then C.3 holds w.p.1 as well as Steps 3b and 3c of the proof of Lemma I. If, in addition
with v(t,A,c) defined by (16). Hence,
or
ly(t)Q(t,x(t),cp(t»1 c y(t)1Q(t,x·,O)1
+ y(t)X.(x·,O,p·, v(t,X,c) )(Ix(t) - x·1 + Icp(/)1)
E ~(x, ep( I,X), p(x), v( I,A, c)( I + v( I, A, c»)
< Y(/)IQ (t,x·,O)1 + y(t)X1(x· ,O,p*, v( t,~,c») ·(p*+v(t,A,c»
converges at t~(X), then also C.4 holds w.p.l. Proof: For y(t)= I/t we have from (18a)
(1.50)
±
where the first inequality follows from assumption C.l. (1.57) z(t,x)= 1. Q(k;x,lj)(k,x». It follows from Step 3a. of the proof of Lemma 1 that t k-I the first term of the RHS of (1.50) tends to zero and from Step 3c that the second one tends to zero. Consequently, We shall apply the following ergodicity result of Cramer inside B (x·,p·) the step size tends" to zero, and hence and Leadbetter [38, pp. 94-96) to (1.57). there will be a subsequence of V(x(n» entirely in the Let f(k) be a sequence of random variables with zero interval I. Consider now a special, convergent sequence of means and covariances "upcrossings," that is a subsequence of this. kP+s P Let the sequence n:C be defined such that O<2p
».>
V(x(nk+sk»>2 W I3 where SIt
I
I
t
k == I
-I
(1.53a)
f(k)-+O
w.p.l as t~oo
II
(The proof in [38] is given for the continuous time case, is the first s for which V (x(n" + s) ~ J (I.53b) but it goes through without changes for the discrete time x (nk)-+.i
as k~oo.
(I 54) case.)
· In order to calculate the covariances, introduce for From (1.51) and (1.52) it-is clear that V (x) == W /3 and let k > s the variable V'(x)j(i) =- 8. From (1.45) we now have that
V(x(m(nk'~1'»)< W/3-8~T/64.
~(k,x)
(1.55) by
This means that V(x(n k + si» ~ I where Sk = m(ni,~T) -
n".Suppose now that there is a Sk<·S" such that V(x(n,,+
Ij)sO(k + I,x)" A (x)lj)sO(k,x) + B (x)e(k + I);
Ij)sO(s,x) =0.
This variable is independent of ep(s,i) according to
sk»>2W/3. However, V is continuous and x(n,,+s), assumption A.l==B.l, and (s<m(nk,~f')-nk)
will belong to an arbitrarily small neighborhood of x(nk) for sufficiently small A". according I~( k,x)- cp~(k,x)t (C-A(X)Ic-.r,q;(s,x)1 to Lemma I. Therefore (1.55) implies a contradiction to .( <; V(k,h(X),C». the existence of a subsequence ni with properties (I.SIHI.S4). Hence, no interval I may exist, W must be zero and (1.48) follows, End Step 3. Hence, using assumption A.3 or B.3 Equation (1.48) implies according to the properties of IQ(k,i,q>(k,x»- Q(k,i,~(k,x»l V(·) that x,,-+x*. This concludes the proof of Theorem 1. c %l(x,q)(k,x),O,v(k,A(X),C»)CA(i)k-.rI~(s,i)t. End proof of Theorem 1. 477
Moreover, from A.2, A.3 (according to which %1 and are bounded) or B.7,
We shall need the estimate (1.61) in Appendix III, and let us therefore prove (1.61) for p = I. The case with general p is proven analogously, though with more techni.. cal labor. The details are given in [7]. Denote for short
~(s,i)
EIQ(k,x,q>(k,x)- Q (k,x,~(k,x»12 <; C·A(X)"-J. (I.59a)
QIc = Q(k,x,ip(k,i»)
Now I COy
and assume that Qk is a scalar and that EQk =0. Then
{Q( k,i,,(k,i», Q(s,i,q;(s,x»)} 1
2
= ICOY{ Q(k,x,~( k,x»
- Q(k,x,~(k,x»
EC~n Y(k)Qk) = k~n .r~n y(k)y(s)EQkQ.r
+ [ Q(k,x,~ (k,x»
],Q (s,x,~(s,x»}1
m
"J
(n)2 C ~ ~ A1k -JI c Cy(n)2(m- n) (1.62) k -n s'==n
-IO+cov{ [Q(k,x,~(k,x"»-Q(k,x,~(k.x»],
where the first inequality follows from assumption A.8 Q(s,x,~(s,x»}1c C.).(X)k-$, (I.59b) and (I.59b). It remains now only to prove that where the second equality follows since ~(k,X) and ~(s,X) are independent, and the last inequality follows from Schwarz' inequality, (1.59a), and assumption B.7.
(m(n~~T)-n)(c/y(n).
Since y(.) is decreasing
Hence, (1.58) holds and
! t
m
2~T ~ ~ y(k) )(m - n)y(m)
±[Q(k,x,~(k,i»- EQ(k,x,~(k.i» ]_0
n
or
k-l
w.p.l as 1-+00
which according to assumption A.5 = B.6 implies that
!
t
±Q(k,x,~(k,i»-f(x)
(1.63)
w.p.l as
(m-n)(c/y(m).
(1.64)
Moreover, from assumption A.9 __I y(n+ I)
I~OO.
k-I
I_
(1.60) we have
Notice that (1.60) holds for any given x w.p.l. For a given y ( n + 1) > y ( n)( 1- cy( n + I)., realization '" outside a null set it does not immediately follow that it holds for all x E DR. To conclude that, we or, upon repetition first note that (1.60) will hold w.p.l simultaneously over a m dense denumerable, subset of DR. (The union of a de- y ( m) > y ( n) II (1 - cy (j )) numerable number of null sets is a nullset.) Hence, for a n+1 given realization outside a null set (1.60) holds for all x in a dense subset of DR- But since Q(., ., -) and f( .) are -..,y(n)exp (- cYU)).--c'y(n). continuous in x, we may extend this set to DR itself. n+1 The proof of the second part of Lemma 2 is analogous, (Under assumptions A it is trivial.) This, together with (1.64) implies (1.63) and the proof of End proof of Lemma 2. (1.61) is complete for p = I. The proof for general sequences {yen)}, subject to A.S, Proof of Corollary 10 Theorem 1: The function V(x) A.9 is achieved by first proving that with the property (22), whose existence is assumed in the corollary plays the role of the Lyapunov function m(",~.,.) throughout" the proof of Theorem I. Since. in the formulaE ~ y(k)[ Q(k,x,q;(k,i») tion of the corollary there is no guarantee that x(m(n, ~'T» k-" will belong to DR even if x(n) does, the possibility of a 2p cluster point on the boundary of DR cannot be excluded. - EQ(k,x,ci(k,i»)] < C·y(n)p (1.61) Moreover, if D is unbounded the existence of a cluster point in D is not guaranteed. But if no cluster point exists, then the sequence (x(n)} will tend to infinity, which in and then proving convergence by the Borel-Cantelli that case will be a boundary point of DR" End proof of corollary. Lemma and assumption A.7.
:2
478
that T(m) will, with probability one, not tend to zero as m tends to infinity. Hence, x(m) will not converge to 0 (= x·) with nonzero probability. To prove (25a) we first assume thatf(x*)*O. The general case is proven by linearization around x· We first note that according to Lemma 2, assumptions and the additional terms are taken care of by appropriate A or B imply that (1.4)-(1.6) hold w.p.l. approximations. Like in the proof of Lemma 1, this leads Let .!IT( x*) - .!l",* be "the sufficiently small" ~". as de- to several technicalities, but the basic idea remains the fined in Lemma I. same as above. Take To keep the Appendices within reasonable size, these technicalities will not be given here. The full proof can be (11.1 ) p. < ~"'*lf(x·)1/4 found in [7]. Proofs for related algorithms are given in [6] ApPENDIX
II
PROOF OF THEOREM
2
and let Sl·"-{~Ix(t)-+~(x·,p·)} with P(O*)=P*>O. If x(t) converges to ~ (x·,p·), it is in particular inside ~1 (x·, 2p*) infinitely often. Therefore, there is a cluster point x inside ~(x·,2p·). Also, inside ~(x·,2p~) the observation equation (2) will be stable for sufficiently small o", according to Step 2 of the proof of Lemma I. Hence, we can select a subsequence {x (nk)} tending to X, such that Icp(nk)1 < C, i.e., (1.3) holds. Then Lemma 1 implies that
and [1]. ApPENDIX
III
PROOF OF THEOREM
3
The idea of this proof is to apply Lemma I to obtain local estimates of how much x(t) differs from the corresponding trajectory, and then linking such estimates together making use of the stability property. Heuristic Outline of How the Estimates are linked Together
asymptotically as k -+ 00 for '" EO· except on a null set. The idea of how the local estimates are extended to This means according to (11.1) that x(m(nk'~"'·» is outside ~ (x·, 2p·), and the assumed convergence is con- global ones can be geometrically expressed as follows, cf. Fig. 5. tradicted. Assume that the estimate at time Tic is in the interval A. To illustrate the basic idea of the proof of (25b), conThe trajectories that start in A belong at time Tk + .!l1"/( to sider the special case the interval B which is smaller than A since the trajectory Q(t,x,(JJ(t + 1») == Ax + e(t + I) is stable. Now, the estimates obtained by the algorithm differ from the trajectories with a small quantity accordwhere A is an ntn matrix and e(·) is a sequence of ing to Lemma 1. Denote this distance by C. During the independent random variables with zeto mean values. time interval .1'T , the estimates have not diverged from k Suppose that A has an eigenvalue A with ReA> 0, and let the nominal trajectory if A <; B+2C. L be a corresponding left eigenvector. Let T(n)- Lx(n) To achieve this, A and ark must be chosen with care. and E(n) = Le(n). The condition on cov Q implies that The interval ~7'k must be large enough to let the trajecto{E(n)} is not identically zero. Then the algorithm (I) can ries converge sufficiently, "and small enough to limit secbe written ond-order effects and the noise influence. The formal proof will be developed in 5 steps. In Step I T(n+ 1)=T(n)+ y(n+ l)[AT(n)+E(n+ 1)] the details of the application of Lemma 1 are given. Step 2 deals with the implications of the stability assumption. In and Step 3 an interval for t1Tk is selected, corresponding to ~Tk not being too small nor too large as described in the heuristic outline. In Step 4 it is shown that the estimates T(m)=f(n,m)· {T(n)+ n+1 stay with the given e-region as depicted in Fig. 5 if certain stochastic variables are less than a given value. Step 5 where calculates the probability that they are less than this value. Step 1-App/ication of Lemma 1: f(n,m)= (1 +;\;y(k»)-exp {A Y(k)} (11.2) Order the set of indices J =-{ n;} such that
f
Pk~(k)}
f
IT
n~1
n+l
n I < n2 < . · .
and
Denote ~7'k = Tn I - T". Then by taking i Lemma I we obtain
k
~k=y(k)
< nk < nk + I < ·..
I. ...
II (l+Ay(j»-I. n+1
Since T(n) and the sum of random variables are independent and r(n,m) tends to infinity as m increases, it follows
~
= x(n,.) "
In
x( nk+.) - x( nk) + aTJ[ x( nk)]
479
(111.1)
Step 2-Stability of the Trajectories
According to the assumptions of the theorem there exists a function V(Ax,1') that is quadratic in Ax and such that
A
c so
(111.9)
Pia- S. To illustrate the idea of the proof of Theorem 3.
along solutions of the variational equation of (19). Since we assume V(aX,'T) to be quadratic in ~x it is no additionalloss of generality to assume that
where Q2(nk,nk+ I,X) is given by (1.6) and (1.39). Since
V (AX,T) == IAxl 2
since it is always possible to make a (time-dependent) (111.2) change of metric. Moreover ql(nk,nk+l'X) is given by (1.38). From Lemma 1 we also know that (111.1), (111.2) are valid only if A'1k is sufficientty small and nk so large that
Iq. ( nk' nk+ .,x(nk»)1 < p12.
Then (111.9) implies that Ix D ('T + 41"; 1",x + 4x ) - x D (T+ d1" ;1",x )I « I - Ad'T )IAx l (111.10)
(111.3)
for some I >A>0. We first note that the c01!!tant C2 in (111.2) can be taken End Step 2. to be globally valid in D, according to the e~ression Step 3-Selection of an Interval for A'Tk (1.39) and since 1/(x)1 and kf) are bounded in D. Mor~ To obtain the upper and lower bounds for ~Tk disover, there is a common lower bound to ~10(X) for xED, cussed under the heuristic outline, let which can be realized as follows. . (460M ~T oM4 4"\ rz: ) The radius 2p, which is so small that (1.12) implies (1.11) (0 = mm -A- , 3;\ 'X v pM · (II1.11 ) depends on x and is a measure of how fast A (x) changes in a nei&.hborh~d of x. Since A (x) is Lipschitz continuChoose « (0. Then automatically ous in D and D is compact, the radius P(X) will have a positive lower bound as x varies over D. Denote this by p. all k (111.12) Let [cf., (1.34)] since 4'Tk > 80 according to the assumptions of the theoa'To= inf (111.4) rem. An upper bound for &1"k can be obtained by possibly xED 11(x)I' 16~ extending the set I, cf., beginning of Step 1. Do this so that whi.£h is strictly positive, since I!(X)I and k., are bounded in D. (111.13) Then (111.1), (111.2) is valid for tJ.'Tk < ~TO if (111.3) holds. By solving the differential equation (19) from 'T to The resulting set I may depend on E. According to T + dT with x as the initial condition we have (111.11), automatically !:!Tk < ~TO. End Step 3. Ix D (1" + £\T;T,X) - ( x + 41" f (x»)1< L4T 2 (111.5) Step 4-The Estimates Remain in an e-Neighborhood of the where L can be taken globally in D. Introduce the follow- Corresponding Trajectory if q.(nk + .,nk,x(n/<) is Sufficiently ing abbreviated notation Small, all nk E I Assume that D X;D (j) = x (1",; 1"~,x(n;»). (111.6) (111.14a) Iq1(n k + r- nk, x (nk )) I< r ( f) Equations (111.1), (111.2), and (111.5) now imply in the notation of (111.6) where
(--L _1_)
e
Ix( nk + I) -
D Xk
(k + 1)1 « c2 + L)aT2 + q. (nk + I,nk,x( nk »)
A2( 2· 3
(111.7)
(III.14b)
r(E)<8/2.
(III.I4c)
According to (111.11),
if (111.3) holds. Introduce M=C2+L.
r(E)= M.16 ·
(111.8)
The estimate (111.7) with the expression (1.38) for q. is the basis for the rest of the proof. End Step 1.
Assume also that
480
txf(k)-x(nk)l
c E.
(111.15)
Since ~'T'k now is assumed to be less than ~10 and since (111.14) is assumed to hold, Lemma 1 can be applied, giving according to (III.7) and (1II.J4) [notation as in (111.6)]
fx(nk+1)-xf(k+ 1)1 <; M·a'Tf+r(E).
according to assumptions B.7 (or A.3) and 8.10. Analogously to the first term of (111.19) its 2p-absolute moment around the mean is bounded by C·y(n)p. (Much better estimates are possible, but uninteresting.) Denote the two first terms of (III.19) by q~ (m,n,X) and the last one by (111.16) qf(m,n,X). Then
Now
q, (m,n,i)= q~ (m,n,i)+ qf (m,n,i)
Ixf(k + 1)- x(n/c+ .), (Ixf(k + 1)- xf(k + 1)1
where
+IXkD(k+ 1)-x(nk+I)1
(111.21 )
«I-A~'Tk)txf(k)- x(k)1
and
+ M·i1'Tf+ r(E)
Iq~ (nk+ .,·nk,x(nk»)1 < r( E)/2,
~2E2·3
~(l-.;~~hk)E+M·~TI+ M.16 =
E
+ M[ (~Tk -
4A~ )( ~Tk - ~~ ) ] ~ E
(111.20)
(111.22)
Chebyshev's inequality gives, using (111.21) (111.17)
P(lq~ (nk+l,nk,x ( nk»)1> r(f)/2) 2p
where the second inequality follows from (111.10) and ~( 'C-y( nk)p· (III.23) (111.16), the third from (111.15) and (III.14b), and the last one from (111.13). The probability that (111.14) does not hold for some The conclusion is that if x(nlc) lies in an e-neighborhood »;» N I , nJc E I is thus bounded by of the trajectory, so will x(nlc+) if (111.14) holds. If (111.14) holds for all nk E I, then
rtE»)
sup Ix(nk) - xf (k#)1 < e. nk E /
End Step 4. It remains now only to estimate the probability that (111.14) holds for all nJc E I. Step 5-The Probability That (111.14) Holds The expression for q.(n"+I,nk,x(nk» may according to
(1.38) and (1.22) be decomposed as follows
Iql(m,~,i)I<1
f
y(k)
Combining the conclusion of Step 4 with this result gives the assertion of the theorem. The number To mentioned in the theorem equals N 1 defined by (111.22). Remark: The inequality in (111.24) is somewhat wasteful. For example, if y(t)= l/t, then with
k-n
· [Q(k,x,q;(k,x»- EQ(k,X,q;(k,X»]1 implies that nk+l~nk(l +a'Tk ) for small A'Tk and taking
III
+
I
Ie-"
p = 1 in (111.24) an upper bound for the LHS of (111.24) is
y(k)XI(i,~(k,x),2p,v(k,A,C»)
given by
·A "-lIv(n,~,c)
+ I~Tf(X)-
f
(
y(k)EQ(k,X,q;(k,X»I· (111.19)
k-n
_2 r(E)
)2.C'
f
I
nk-NINI(l+~.,o)k 2
<: _1
(--1..-) .C. 4M <. C/(5. r(E) hE
NI The last term in this expression is deterministic and tends to zero according to assumption A.S =B.6 .and according End proof of Theorem 3. to (1.1) (m - m(n,~1"». Let N I be such that this last term is less than r(E)/2 for nk> Nt. ApPENDIX IV For the first term of (III.I~) the estimate of its 2p-ab-
solute moment, (1.61) holds. The second term of (111.19) has a mean that is bounded by
PROOF OF THEOREM
(111.25)
4
In virtue of the projection we know that X(l) belongs to a compact area i.o. that is part of DR. We could therefore apply Theorem 1 directly, apart from the fact that the
III
C' ~Y(k)Ak-"~ l~A y(n) 481
projection algorithm (28), (29) differs from the algorithm (1), (2) treated in Theorem 1. It therefore suffices to show that the "projection" takes place at most a finite number of times w.p.l. After the last time x(t) is forced into D 2 the projection algorithm coincides with the basic algorithm (1), (2) and the proof of Theorem 1 is valid. If indeed, the estimate x(t) were outside D. infinitely often, then it would have to pass from D 2 to outside D. i.o., i.e., to a higher value of U (x( t» (see (31» in spite of the force trying to decrease U according to (30). In Step 3 Theorem 1 it was proved that this is of the proof impossible, and hence the projection facility in (28) is used only a finite number of times. Also, the estimates cannot remain in D from a certain time on, since condition (30) shows that (using Step 2 of the proof of Theorem 1) they will be forced into D2•
0'
ApPENDIX
ON SOME
V
e«
m(n.~1')
y(k)f(x,k)-+a'Tf(x)
Equation (V.4) if of course just a special case of the general, nonlinear dynamics (3). To treat this case let i(X) denote the limit of the recursion
and define ~(t,X) through ~(t,x")
I,x) + B (i (x) )e(t).
(V.6)
Iz(t)-z(t,i)I< C· max li-x(k)1 r « k<1
if z(r)=z(r,x)
(V.?)
li( x) - z( l,x)1 <; CJL I. Ii (x) - z(O,x)I; #L < 1 (V.8)
as n--+oo
Jz(1)1 + Icp( t)1 < c i.o.
(V.9)
To prove this we note that assumption A.4, (Y.7) and (V.8) imply that
'A(z(j»)-A(i)l
+ cJLJ-nli (x) -
z(n)l.
If we use this estimate in (1.16) together with (V.9) we arrive at the same expression as in (1.17) and the proof continues without further changes.
(V. I) ACKNOWLEDGMENT
I would like to express my sincere gratitude to Profs.
K. J. Astrom, H. J. Kushner and Ya, Z. Tsypkin for
±
(V.2)
f(x,k)-f(x)
important discussions on the subject of this paper. I have
also benefitted from the referees' competent suggestions on how to improve the readability of the Appendices.
k-l
Notice that (V. I) or (V.2) very well may hold even if A.5 =B.6 does not hold. It is consequently unnecessarily restrictive to assume convergence of f(x,t) as t~oo. Moreover, if (V.I) does not hold, it is sufficient to require the existence of a twice differentiable function V(s) [which plays the role of Lyapunov function for the in this case undefined differential equation] such that m(n,A.,.)
V'(i)
=A (i (.~))~( t -
The theorems will then hold in the same formulations as before, if the following three conditions on (V.4b) hold:
which, for the case y(k) = 1/ k is equivalent to
t
(V.5)
z(t.x)=h(z(t-I,x),x),
k-n
1
(V.4b)
and
EXTENSIONS
Continuous Time Algorithms: It should be clear that the theorems and proofs given here are valid also for continuous time algorithms, with proper and straightforward modifications. The Case when Assumption A.5 = 8.6 does not hold: The basic assumption, defining the RHS of the differential equation is A.5 =8.6. X) be denoted by f(i, I). In the proof Let EQ (t, X, it is only used that ~
:(/)=h(z(t-l)~x(t».
[
I
y(k)f(i,k)
1
< -6(i)·~T
(V.3)
k-n
for all sufficiently large n, where 8 (X) >0 for xfi. Dc. More Complex Generation of the Observations: In some cases, like for the extended Kalman filter, which is presently being analyzed using the methods of this paper, a more complex mechanism replaces (2): cp(t)==A(z(t--l»cp(t-l)+B{z(t-l»e(t) (V.4a) 482
R~FERENCES
(I) L LjUD& T. SOderstrom, and I. Gustavsson, ·'Counterexamples to generaJ convergence of a commonly used recursive identification method," IEEE Trans. Aulomat. Contr., vol. AC·20, pp. 643-652, Oct. I?,S. (2] K. J. Astrom, U. Borisson, L. Ljung, and B. Wittenmark, "Theory and a~lications of adaptive regulators based on recursive identification, in Proc. 6th IFAC Congress, Boston, MA, 1975. An extended version of this paper will appear in Automauca, Sept. 1977. . (3] L Ljunl and S. Lindahl, "Convergenceproperties of a method for stale estimation in power systems," Int. J. Contr.; vol. 22, pp. 113-118, July 1915. (4] L. LjUDI and B. Wittenmark, "Analysis of a class of adaptive regulatOrs," in Proc. 1FA C Symp. on StocNutic Control, Budapest, Sept. 1974. [5] L. Lj\IDI, "Convergence of recursive, stochastic algorithms. n in Proc. IFAC Sy"". on StocJuutic Control, Budapest, Sept. 1974. (6) ··Stroq coDveraence 01 a stoehutic approximation algorithm," Annals of Sttltiltics, to be published; alSO available as Rep. LiTH-ISY-I-0126. LiDkopinl University, LiDkOping, Sweden. [7] wrheorems for the asymptotic analysisof recursive, stochastic alloritlulls," Dep. Automat. Contr., Lund Institute of Technology, Lund, Sweden, kep. 7522.
(8] "Convergence of recursive stoeltastic a110rithms," Division of [27J D. C. Farden, "Stochastic approximation with correlated data," Automatic COntrol, Lund Institute of Technology, Lund, Sweet,.., Dep. Elect. EDI., Colorado State University. Fort Collins, CO, Rep. 7403, Feb. 1974. aNR Tech. Rep. 11. [9J W. Hahn, Stability of Motion. Berlin, Germany: Springer·Verla& [28] I. D, Landau, 6&Unbiased recursive identification USinl model 1967. reference adaptive techniques," IEEE TrtUU. AU'Omtl'. Con" .• vol. (IOJ R. W. Brockett, Finite DimerLr;OMI LinetU Systems. New York: AC·21, pp. 194-202, Apr. 1976. Wiley, 1970. (29) L. LjUDa, "On positivereal transfer functions and the convergence [11) H. R.obbins and S. Monro, .tA stochastic approximation method," of some recursive schemes, this issue, pp. 539-551. AM. MflllI. StilI., vol. 22, pp. 400-407, 1951. (30] T. SOderstrom, L. LjUD& and I. GUitaVSlOn, "A comparative study (12] J. Blum, "MultidimensiotW stochutic approximation methods," of recunive identification methods," Automatic Control, Lund AM. "'lItla. Slat., vol. 25, pp. 737-744, 1954. Institute of TechnolOI)', Lund, Sweden, Rep. 7427, 1974. (13) M. A. Aizermann, E. M. Braverman, and L. I. Rozonoer, "Metod {31] L. LjUDI! ''Convergence of an adaptive filter algorithm." Int. J. Potentsialnykh fUDktsij v teorii obuchenija mashin" (The method Comr.; ) 977, to be published. 01 ~teIltial functioDi in the theory of machine learning). I zd. [32J K. J. AstrOm and B. Wittenmark, "On self-tuning regulators," Ntlillca, Moscow, 1970 (in R.ussian). Automtl,;ctl. vol. 9, pp. 185-199, 1973. (14) M. T. Wuan, Stoclttu'ic Approximtltion. Cambridge University [33] L. LjUDI and B. Wittenmark, "OIl a stabilizina pr~ty of adap~~I~. . tive reaUlators," in p,.ri"U 4th IFA C s,,,,,. IdMIijicat;on, Part 3, (IS) Va. Z. Tsypkin, Adtlption lind ua,n;", in Automatic Systems. Tbilisi, pSSR, Paper 19.1, pp. 380-389, 1976. New York: Academic, 1971. [34] K. J. Astrom and B. Wittenmal'k, "Analysis of a self-tuning [161 - , Fou1lda';01l$ of 1M TMory of Learning Systems. New York: reaulator for nonminimum phase systems," in Proc. IFAC Synp. Academic, 1973. on S,ocluu,;c Control, Budapest, 1974. [17] J. Kieferand J. Wolfowitz, "Stochastic estimation of the maximum (35) D. P. Derevitskii and A. L. Fradkov, "Two models for analyzing of a regression function," Ann. Malh. Slat., vol. 23, pp. 462-466, the dynamics of adaptation alaoritbms,·t AutOmtl'. and Remole 19S2. Comr., vol. 35, pp. S9~7, 1974. [18J H. J. Kushner, "Stoehutic approximation algorithms for the local (36] H. J. Kushner, "General CODveracnce results for stochastic apoptimization of functions With non-unique stationary points," proximations via weak CODVerpace theory," Brown University, IEEE TI'tIIII. Auto,,",t. COIIIr., vol. AC·17, pp. ~SS, 1972. Providence, RI, LeDS Tech. Rep. 76-1, 1976. (19) H. J. Kushner and T. Gavin, 6IStochutic approximation type (37] - , "Convergence of recursive adaptiveand identification procemethods for constrained systems: Algorithms and numerical redures via weakconvergence theory," IEEE TralU. Automat. COllI'., suIts," IEEE TrarLr. Automat, Cont,., vol. AC·19, pp. 349-3S8, to be published. 1974. (38J H. Cramer and M. R. Leadbetter,KStati01ltUY and &Iated (20) K. S" .Fu, "Learnilll system theory:' in System 1Mory, L. A. Zadeh Stoc1l4flic Processes. New York: Wiley, 1967. and E. Polak, EdI. New York: McOraw·Hill, 1969. pp. 425-466. (39] N. N. Krasovskij, Stability of Motion. Stanford, CA: Stanford (21] G. N. Saridia, Z. J. Nikolic, and K. S. Pu, "Stochastic approximaUniversity Press, 1963. tioD a110ritbms for sxstems identification, estimation and decom- (40) W. Hahn, StiUJi/ity of Motion. Berlin, Germany: Sprinpr-VerIa& position 01 mixtures, IEEE Trans. S,st, Sci. Cybem; vol. sse-s, 1967. pp. 8-1S, 1969. (41) V. I. Zubov, Methods of A. M. Llt1J11lN1V and tlteir Applications. (22] Va. Z. Tsypkin, "Self..learninl-:-What is it?," IEEE Trans. AutoGroningen, Holland: Noordhoff, 1964. nult. Co,,'r., vol. AC·13, pp. 608-612, 1968. (23] E. M. Braverman, "The method of potential functions in the problem of training machines to recognize patterns without a teacher." Automtlt. R.1IIOt. COItl,., vol. 27, pp. 1748-1770. 1966. (24] K. J. Aatrom and P. Eykhoff, "System identification-A survey," AlltOlfUlt;ca, vol. 7, pp. 123-164, 1971. (2S] J. M. Mendel, DUcrele. T«ltniqws of ParalMte, utiffUJlion. New York: Marcel Dekker, 1973. [26J L. L. Scharf and D. C. Parden, "Optimum and adaptive array processing in frequcnce-wavenumber space," in Proc. IEEE Conf. ....... LjIIDa (S'74-M'75), for a photograph and biography see page 5SI of this issue. on Decuion and Control, Phoenix, AZ, 1974, pp. 604-609. tt
483
Discrete-Time Multivariable Adaptive Control GRAHAM C. GOODWIN, PETER J. RAMADGE, AND PETER E. CAINES
ADAPTIVE control, so great is its appeal, has been studied for almost forty years. Its early history is one of diverse, but interesting, heuristic endeavors. One of the first problems studied, and one that has formed the focus of much subsequent research, is that of adaptivemodelreference control in which the controller employs an estimate of the unknown plant to cause the output y to track y* = H r, where r is the reference, H a prespecified reference model, and y* the desired output. Another consistent theme is certainty equivalence, regarding (and using) the estimated plant as if it were the true plant; the motivation is obvious ... if the estimated parameters converge to the true parameters, the certainty equivalent controller converges to a satisfactory (optimal) controller for the true plant. However, adaptive controllers can perform satisfactorily even if, as is often the case, the estimated parameters do not converge to their true values; this was dramatically shown in the paper by Astrom and Wittenmark [1], also included in this volume. Early use of Lyapunov theory to establish stability was restricted to minimum phase plants with relative degree one. Plants with a relative degree higher than one posed a major problem [17] that was not satisfactorily resolved until the late 1970s; indeed, the paper by Goodwin, Ramadge, and Caines was a major contribution to the resolution of this formidable problem and a substantial stimulus to subsequent research. Suppose the system to be controlled is described by
where YE := (1/ E)y, UE := (1/ E)u, () is a vector of the coefficients of the polynomials Rand S, and the regressor vector ¢ has components qi y E, i = 0, ... , n - 1, and qi UE, i = 0, ... , n. The estimation equation y = ¢T e may be used in many different ways to provide an estimate of the unknown parameter e. Suppose the desired closed -loop transfer function is H = (N / E) so that the desired output is y* = H r, and that b.; = Sn = 1 is known. To determine the control, the system equation may be written in the form
e
E2Y = RYE l
Ey = Ry
where 1/J:=E2 ¢ (the vector 1/1 has components qi YE l , i = 0, ... , qiUEl' i = 0, ... , n). The degree of E 1 is n so that 1/JT emay be written as 1JT e + u. If eis known (and the system is minimum phase), the control u may be chosen (as u = E2Y* 1JT ()) to cause the output to satisfy E2Y
= 1JT e + U = E2Y*
so that the tracking error y - y* decays to zero (and all signals remain bounded). If () is unknown, a tempting strategy is to employ the certainty equivalent control u = E2Y* - 1JT with the result that E 2 y* = 1/JT and the output is now given by
where E = E 1E2 is monic and Hurwitz, and £1 and E2 have degrees nand m, respectively. Hence (ignoring exponentially decaying terms)
e
e,
E2Y = E 2y* + 't/JTe The tracking error er := Y - y* satisfies et
+ Su
= 1/JT e
n - 1, and
Ay =Bu where A and B are polynomials of degree nand m, respectively, in the shift operator q, and A is monic; for continuous-time systems q is replaced by the derivative operator d / d t. The system may be re-parameterized (as shown in [1] and [15], the latter in 'state-space language') to obtain
+ SUEl
y
= e + er
e
e
where := ¢T is the estimated output, e := Y - Y = ¢T is the prediction error (Monopoli's augmented error), := () is the parameter error, and er := (y - y*) is an estimate of the tracking error eT. Since
eT
e
e
= [(1/ E2)l/!T]e - (1/£2)[ l/IT OJ
e e
it is also known as the 'swapping error'; eT is zero if is constant, but otherwise depends on the rate of change of (in the continuous-time case it is proportional to (d / dt)e). Monopoli [15] proposed use of the certainty equivalent controllaw in conjuction with a simple gradient estimator (d/ d t)O = ¢e; however, as was later pointed out, convergence of the
485
tracking error to zero was not established except for the case of unity relative degree. The first proof of convergence (for continuous-time systems) was achieved in [4] by modifying the controller; nonlinear damping was added to ensure convergence of eT to zero; this enabled convergence of er (and boundedness of all signals) to be proven. Because of the complexity of the controller, and of the accompanying analysis, the paper [4] did not have the impact it deserved. The second and much simpler proof (for discrete-time, systems), presented in this paper by Goodwin, Ramadge, and Caines, achieved convergence by modifying the estimator; the rate of change of 8 was reduced (thereby reducing eT ) by the introduction of error normalization (replacing e in the estimator algorithm bye := e/[I, + 1c/J1 2]1/2). Error normalization was independently proposed in [3]. The relevant result is Lemma 3.1 of the paper by Goodwin, Ramadge, and Caines, which essentially states:
(a) Suppose the estimator is such that the normalized prediction error e = e/[1 + 1c/J1 2]1/2 lies in f 2 • (b) Suppose the controller is such that the regressorvector c/J satisfies the growth condition 1c/J(t)1 2 ~ c[1 + max{le(r)1 2 IrE [0, t]} for all t Then:
~
o.
(i) Ic/J(t) I is uniformly bounded, and (ii) e(t) ~ 0 as t ~ 00.
The result is simple to state and prove. It provided a simple means for establishing convergence (and boundedness of all signals) for a wide range of adaptive controllers and contributed to an explosive re-awakening of interest in adaptive control. An important feature of the result is its modularity: condition (a) on the estimator can be established independently of (b), i.e., independently of the control law. The result was presented in an electrifying seminar at Yale University (New Haven, Connecticut) in late 1978 and was rapidly extended to the deterministic continuoustime case in [16] and [21]. All three papers appeared in the same issue of the IEEE Transactionson Automatic Control; ironically, the paper by Goodwin, Ramadge, and Caines was the only one that did not appear as a regular paper. A parameter estimation perspective of the continuous-time results was given in [5], providing an analogous modular decomposition of the conditions for convergence. Stochastic versions of the paper by Goodwin, Ramadge, and Caines and of [5] appeared, respectively, in [7] and [6]. Research on convergence and stability has continued to this day. For example, the earlier nonlinear damping approach of [4] was extended in [11] to deal with 'true' output nonlinearities for which certainty equivalent adaptive controllers are inadequate, and backstepping [13] was developed as a systematic tool for designing adaptive controllers for linear and nonlinear systems with high relative degree. Furthermore, switching was introduced to enforce convergence when structural properties
(e.g., relative degree) are unknown [18], and modifications were made in the basic algorithm to ensure robustness [19], [9], [12]. Research results of this period were rapidly consolidated in texts such as [8], [20], [14], [2], [22], and [10]. The paper by Goodwin, Ramadge and Caines is an important milestone in the evolution of adaptive control. It contributed much to the richness of a subject that has progressed far and that now appears poised for further significant advances.
REFERENCES
[1] K.1. ASTROM AND B. WITTENMARK, "On self tuning regulators," Automatica, 9:185-199, 1973. [2] K. 1. ASTROM AND B. WITTENMARK, Adaptive Control, Addison-Wesley (Reading, MA), 1989.
[3] B. EGARDT, StabilityofAdaptiveControllers, Springer-Verlag (NewYork), 1979. [4] A. FEUER AND S. MORSE, "Adaptivecontrol of single input, single output linear systems," IEEE Trans. Automat.Contr., AC-23(4):557-569, 1978. [5] G. C. GOODWIN AND D. Q. MAYNE, "A parameter estimation perspective .of continuous time adaptivecontrol," Automatica, 23:57-70,1987. [6] G. C. GOODWIN AND D. Q. MAYNE, "Continuous-timestochasticmodelreference adaptivecontrol," IEEE Trans. Automat.Contr., AC-36(ll): 12541263, November 1991. [7] G. C. GOODWIN, P.J. RAMADGE, AND P. E. CAINES, "Discrete time stochastic adaptive control," SIAM J. Contr. Optimiz., 19(6):829-853,1981. [8] G. C. GOODWIN AND K. S. SIN,AdaptiveFiltering, Prediction and Control, Prentice Hall (EnglewoodCliffs, NJ), 1984. [9] P. A. IOANNOU AND P.KOKOTOVIC, AdaptiveSystemswithreducedmodels, Lecture Notes in Control and Information Sciences, Vol. 47, SpringerVerlag(New York), 1983. [10] P. A. IOANNOU AND 1. SUN, Robust Adaptive Control, Prentice Hall (EnglewoodCliffs, NJ), 1989. [11] I. KANELLAKOPOULOS, P. V. KOKOTOVIC, AND A. S. MORSE, "Adaptive output-feedbackcontrol of systems with output nonlinearities," IEEE Trans. Automat.Contr., AC-37(11):1666-1682, 1992. [12] G. KREISELLMEIER AND B. D. O. ANDERSON, "Robust model reference adaptive control," IEEE Trans. Automat. Contr., AC-31(2): 127-132, February, 1986. [13] M. KRSTIC, I. KANELLAKOPOULIS, AND P. V. KOKOTOVIC, Nonlinearand AdaptiveControlDesign, John Wiley, New York, 1995. [14] P. R. KUMAR AND P. P. VARAIYA, StochasticSystems: Estimation, Identification and AdaptiveControl, Plenum Press (New York), 1986. [15] R. V. MONOPOLI, "Model reference adaptive control with an augmented error signal," IEEE Trans. Automat.Contr., AC-19:474-482, 1974. [16] A. S. MORSE, "Global stability of parameter-adaptive control systems," IEEE Trans. Automat.Contr., AC-25(3):433-439, 1980. [17] A. S. MORSE, "Overcoming the obstacle of high relative degree," Journal of the Societyfor Instrumentand ControlEngineers, 34:629--636,1995. [18] A. S. MORSE, D. Q. MAYNE, AND G. C. GOODWIN, "Applicationsof Hysteresis Switching in Parameter Adaptive Control," IEEE Trans. Automat. Contr., AC-37(11):1343-1354, 1992. [19] S. M. NAIK, P. R. KUMAR, AND B. E. YDSTIE, "Robust Continuous-Time Adaptive Control by Parameter Projection," IEEE Trans. Automat.Contr., AC-37(2):182-197,1992. [20] K. S. NARENDRA, Adaptive and Learning Systems-Theory and Applications, Plenum Press (New York), 1986. [21] K. S. NARENDRA, Y.-H. LIN, AND L. S. VALAVANI, "Stable adaptive controller design, Part II: Proof of stability", IEEE Trans. Automat. Contr., AC-25(3):440-448, 1980. [22] S. SASTRY AND M. BODSON, AdaptiveControl: Stability, Convergence and Robustness, Prentice Hall (EnglewoodCliff, NJ), 1989.
D.Q.M. & L.L.
486
Short Papers
m.eaD-Iquue output is bouaded wheDevcr the sample mean-square of the HOWC\W, the questioD of stability remaiDI
Dllaet&-11IIIe M _ Adapdve Coatrol GRAHAMc. GOODWIN, ....... JIIIB, PETER. J. RAMADGI!, AND PETER. E. CAINES. MJ!I88I. IBI!B
.4....
nil
Ur
-..,--.It ...... .,.... ............................. . . . . . . . . . . . . . .'
6
II
•••• "rde
I.
tIIIt
uaauwerecllor atoebutic adaptive aJaorithmL The study of discrete-time determiIlistic aJaorithms is of indepeDdent intereat but also provides iDsiaht mto stability qucatioDl in the stoehutic cue [12~ (IS]. Recent work by 100000U ad Monopoli (13) bu been concerned with the exteDlioD of the results in (2) to the cliIcrete-time cue. AI for the continuous cue, the aupICIlted error method is used. In tbiI paper we preIeIlt 11ft' resu1tI nIatecI to clilCJ'ete-time ~ iatic adaptiw coatroL Our approKh diffen from previous work in several ~or respects altbouP ca1aiD upectI of our approach are
..
. - . ••• c-.. .. 'II'cl ........ wII-..
,
.-.u
noiIe is bouaded.
iaspirecl by the work of Feuer aDd MOlle(5]. The uaIysia preIeIltecl here does Dot rely upon the use of aupDeDted erron or awdlWy iD.putI. Moreover, the alpithms have a Vf!IIY simple structure and ue applicable to lDultipltHDput multiple-output systems
IN'raoOUCl10N
A_ problem ill control theory has been the questioD 01 the . . . . . . oIlimp1e.llot.lIy COD". . .t adaptivecontrol alpithmL By t1IiI we III8Ul aJaoritlulll which, for all iDitial I)'IteID aad aJaoritbm . . . C&1IIe the outputl of a liveD IiDear system to _ track a daind output IICIueDCet aDd achieve this with a bounded-iDput
with
rath. pnera1 UlUlDptioDI.
11le paper praenta a paeraI metbod of auIyIiI for dilcrete-time detenD.iDiltic adaptive control alpithmL The JDethod is iDUitrated by .tablilbiDa slobal converpDCe lor thJee simple alpithmL For clarity of prIMIltatioD, we shall first treat a simple IiDIIo-iDput siqIe-output alpitbm in detail. The reaults wiD then be exteaded to siqIo-input aiqIe-output aJaoritlulll iDdudiDa thole hued on recunive least squarea. Piully, die exteDIioD to DlaltipJe..iDput multiple-output systems will be prIMIlteeL SiDce the results in this paper were prIMIltecl a Dumber of other authon [16]-[18] have presented related resultl lor diacrete-time determiDiltic adaptive control alpitbms..
IeqUeDCL
11lere is a CODIidcrable amoUDt of literature OD continuous-time determiDiltic adaptive control alaoritbma [IJ. However, it is 0DIyrecendy that aJobal stability aacl conv-aeace of these aJaoritlulll bas been studied UDcler a-aeraI uaumptioDl. Much interest wa paerated by the iDDovative CODfipration pI'OpC)Ied. by Moaopoli (2) whereby the feedback piDI were directly .timated and aD aupleDted error sipal aDd awdlWy iilput aipaII were introduced to avoid the use of pure dif· fereDtiaton ill the aJaoritbm. UDfortunate1y, as pointed out in [3J the 8I'JUIIleD.tI livea ill (2) CODCeI"DiDa stability are incomplete. New proofs for related aJaorithma have recently appeared (4], (S]. In (4] Narendra and. VaiavaDi treat the cue where the difference in orders between the DUIUI'&tor aad deDomiDator 01 the system traDller function (relative etearee) is laa thaD 01' equal to two. In (5], Feuer and Morse propose a solution for paeralliDear systems without coDltrainta OD the relative dep'ee. The alpithma ill [5] use the auplented error concept and auxiliuy iDputi U in [2J. The Feuer and Morse result seems to be the moat paeral to date for siDale-input siqle-output continuous-time syatau. Howevw, these results are teclmicaJ1y involved and caDDot be directly applied to the dilcrete-time case. 11lere hal also been interelt in'dilcrete-time adaptive control for both the determiDiatic ADd Itocbutic cue. This ana baa particular relevance ill view of the iDcreuiDa ute of ctiaital tecJmolo&y in control applications
0""
II.
PaOBUDlI STATBMENT
In tbiI paper we shall be coacemed with the adaptive control of liDear time-iavariant fiDite-dimeDlioDal systemI haviq the lollowina state apace repreaentation: X(I+ 1)-Ax(I)+ B,,(I):
1(1)- Cx(t)
x(O)-xo
(2.1)
(2.2)
wha'e X(I), u(t), y(l) are the 11X 1 state vector, rX I input vector, and m x 1 output vector, respectively. A staDdard result is that the system (2.1), (2.2) can also be represented ill matrix IraetioD, or ARMA, form u
(6), (7). ldUDI [8], [9J bU proposed a pneral techDique for auaIyziDa conver· of diacrete-time Itocbutic adaptive alaoritbms.. However, in this auIyIiI a q..aioa which is yet to be reaoIved ccmcems the boUDdednesa of the .,... vuiabl-. For OM particular aJaorithm [10], it baa been arpecI iD [II] that the alpiduD poIIeII the property that the sample
aence
(2.3)
with appropriate initial conditioDS. In (2.3), A(q-I), BU(q-l) (;1,··· ,m;j-l,··· ,r) denote scalar polynomials in the unit delay opera-
q-'"
tor q-l aDd the 'acton represent pure time delays. Note that it is not UIUIIled tbat the system (2.1), (2.2) is completely controllable or completely observable, DOl' is it IIIUIDeCl that (2.3) is imclucible. The system will be required, however, to satisfy the conditioDa of Lemma 3.2. It is UIUIDed that the coefficientsin the matrix. A, B, C in (2.1), (2.2) are UDbown and that the state %(t) is Dot directly m.surable. A feedback coatrollaw is to be dcaiped to ltabilize the system and to
caue the outpu~ (y(I», to track a liven reference sequence {y·(I)}. Reprinted from IEEE Transactions on Automatic Control, Vol. AC-25 , 1980, pp. 449-456. 487
Specifically, we requireye'l and u(t) to be bounded uniformly in lim y~(I)-YI·{t)-O
i-I,-·· ,me
LentmtJ 3.2: For 1M syJtem (2.3) with r - m, and subject to
I, and
(2.4)
zdu-dIBII{Z)
' ....00
det
UI. KEY Tl!cHNlCAL LBMMAS Our aualysil of discrete-timemultivariable adaptive control a1p'ithma will be buecI OD the loIlowiDa technical results. UmmtI 3.1: 11 lim '-+00
: [
s(/)2 -0 bl(I)+~(t)cr(/)Tcr(')
(3.1)
for
(3.6)
Z~I-~B"'I(Z)
Izi < 1 WMn 14- I <j<", min tlu
i-I,··
·,m,
if max 1)',(t+4)1-~
(3.7)
O
w1Mre (b.(I», (~I», IIIttI (aI(/)} tire retIl XG1tIr ~ tIIItl (CJ(t)} i.r II 1WII Jl-tJ«IfJr .....,.eei . . Alb}«1 10
'11M ,.,. uin COfUItUttI m,. "4 whicll an ~ of T witA 0
1) fIIIi/DnII~ CtJIIdltlort
(3.2)
O
for aliI > 0 tIIIIl 2) . . . ~ COIIIlltitIII
lIer(t)H < C, + C2 max I.r(1')1
(3.3)
0<.,.<,
wIleN 0 < CI < 00, 0 < C2 < co, il follow8 tMt
(3.4)
lim 1(1)-0 ' ....00
tIItIl {UCJ(I)JI} i8 bouItdttd. Proof: II (I(/)} ill a bounded sequence, thea by (3.3) (IIcr(1)1I) is a bouDdecIleqUeDCe. Thea by (3.2) and (3.1) it follows that
hoof: The rcault ilataDdard ad simply follows from the fact that (3.6) eaaunI that the system hu • stable inverse. 0 III the remainder of the paper thae reaul. will be used to prove Blobal CODV...... of a Dumber of adaptive control aJaorithma. Sections IV-VII will be concemed with adaptive control of siqle-input ~ output ayatemI. SectiODI vm and IX will extend these results to the mul1iple-iDput multip~utput cue.. IV. SINGU-1NPtrr SlNGu-otrrPur SYSTBMS
It is well known that for the siD&le-input single-output (SISO)case, the system output of (2.1), (2.2) can be described by
lim 1(/)-0. 1-+00
Now IIIUJIle that (.t(t)} is unbounded. It follows that there exists a lubiequeDce (I,,) such that
lor(',.)1- 00 1,.-+00 lim
(4.1)
whero (u(t)}. (yet)} denote the input and output sequences, respeolively, mel A(q-I). B(q-I) are polynomial functiODS of the UDit delay operator q-l,
ad
I.r< t)1 < '8(,-)1
for I
< I".
..4(q-I)-I+G,9- 1 + ... +1I,.q-"
(3.S)
B(q-I)-bo+b1q-I+ ..• +b",q-"';
Now aloDa the aublequenee {t,,}
I
I
[ b.(..>+ ~1.)_( t,.)TG( '.) ]
18(1..)1
>
.r(t.)
1/'1
[K
d repJaeJltl the system time delay. The initial conditions of (2.1) arc replaced by iDitial values of y(t), 0> t > -11, and u( t). - d > t» - d - m.. The loIlowiq 'UI1IIDptioDl will be made about the system. A&ru1It'tiM Set 4: a) d is Imown. b) AD upper bound for " and m is known. c) B(z) hal all zeros strictly outside the closed unit disk. (This is neceaary to easure that the control objective can be achieved with a bounded-input sequence.) We note thalt by successive substitution, (4.1) can be rewritten u
uaiDa (3.2)
+ KII_(',.)112] 1/2
lJ(t,,)1
> x 1/ 2 + X I / 2 Ucr(t,.) fI :>
18(1,,)1
gl/2+ KI/, C. + C 1.r( t,,)1] 2
uaiDa (3.3) and (3.5).
Hence, lim ,--+ao
I[b.(I,,)+~(I,,)a(t,,):rcr(tll) ]1/2 I> .r(tJ
bo+O..
y(t+ d)-a(q- J)Y(/) + /l(q-I)u(t)
_1_ >0 K'/2('2
(4.2)
where
but this contradicta (3.1) IIld heDce the assumption that (8(/)} is unbounded it falae ad the remit follows. 0 ID order to 1110 this lemma ill proviDa pobal CODveqence of adaptive control alpithma it will be necessary to verify (3.1) (with .r(t) interpre.ted u the trackiDa error) aDd to check that IlllUlDPtioDa (3.2) and (3.3)
As previously stated, the control objective is to achieve
are satiafied. The nat lemma will be used to verify that the linear boundedDCSI conditioD (33) is .tiIfied by an important e.... of linear timo-invariant ayatemI. This c1ua comspoDda to tho. tiDear timo-invariaDt systemI for which the control objective (2.4) CUl be achieved with a bounded-input sequence aDd lor which the trackiDa error caD be reduced to zero if the
lim [Y(I)- y·(t)J-O
(4.3)
' ....00
where (y·(t)} is a reference sequence. It is assumed that (y·(t)} is kIlowD II priori and that
systaD parameten are known.
(4.4) 488
V.. SISO PROJECTION ALGoRITHM I Let '. be the vector of system parameters (dimensionp - n + m + d).
for all values of tp(1 - d) provided 0 <0(/) < 2.. This is satisfied by definition (5.8). Then, since 111(/)112 is a bounded nonincreuing function it converges. Setting
(S.I)
lben (4..2) can be written
(I). - ,,(1- d)T;(/-l) [and DOtin. that
(5.2)
y(t+d)_cp(t)T,O
tI(I)[ -2+11(1)
,,(I-d)T,(I-d)
]
[1 +f)(t-d)7'cp(t-d»)
where ,<1)7'-(y(t),·· . ..,(/-11+ 1),"(/),·· · ,11(/- m- d+ 1».
(5.3)
Now doIiDe the output trackiDI error as ~I + d)
'0 -
y.( 1 + d).
(5.4)
and hence
chOOliDa (II( t)} to satisfy
it is evideat that the tractiDI error is identically zero. However, since is UDbaowD, we replace (5.5) by the foUowinl adaptive aJaoritbm:
if1-
(5.14)
(5.5)
cp(/)T'O·y·(/+d)
i(t) -
is boUDded away from zero, with a(/) defmed u in (S.8») we conclude, from (5.12), that
- y(l+ d) - ,·(1 + d) • cp( I) T
By
(S.13)
'0
Now using (5.13)and (5.11) it follows that «(I). -4p(t-d) rz I(/-d)-
I) + a( t).(1- d)[ 1+ .p(t - d) Tq>( 1- d)]-1
d-I ~ ~ I-I
11(1- i)
A
· [y(t)- cp(t-d) T.1(/-1)
(S.6)
]
.
f(1-d{!
where i(t) is a }I-vector of reaIs depeadiDa on an initial vector i(O) and Then uaina (5.4) and (S.7) we have that ony(t'). 0<.,<1. u(1'), O<.,
a(/)-1
(5.8)
e(l)
(I)
[ 1+ cp(t - d) T«p( 1- d)] 111
This choice of pin constant prevents the computed coefficient of u(I) in (S.7) beiDa zwo. We also remark that the purpose 01 the coeffICient 1 in the term [I +f(t-d)Tf(/-d)]-1 of (S.6) is solely to avoid diviaioD by zero. ADy positive c:oDltaDt could be used in place of the 1. Apart from the llbove modificatioD, the al.orithm (5.6) is an orthogolUll projection of 1(/-1) onto the hypersurfacey(/)-tp(t-d)T,.O. In the auJyaiaof this alJorithm, we wiD rust show that the Euclidean Dorm of the vector i(,) '0 is a noniDcreainl fUDCtion alODI the trajectories 01 the a1lOrithm. This leada to a characterization of the limitin. behavior of the alaorithm which will allow us to use Lemma 3.1 to establish poba1 coDveraence.
i-I
[I +4fJ(t-d)T.,(t-d)]1/2 ,,(I-d-i)
( t - i)
•
. (5.16)
[I +cp(t-d- i)Trp(t- d- ;)]1/2 Now by the Cauchy-Schwarz inequality and the fact that la(t)1 < 2 0<
I
0(/- i)tp(t- d)T
fP(t-d- ;)
[I + '<,- tl)TCP(t_d)]1/2 [1+.(t- d-i)T.,(t-d- i)]1/2
(5.9)
f(1-1) · [1 +tp(/-d- i).ct-d- ;»)1/2
7',-
Proof:
-' d)T y\/-
[1 +cp(t-d-i)T'
lAmmJI 5.1: Along 1'- 801ution.r of (5.6), (5.7),
I--.CO
4-1
- ~ 0(/-;)
1<,)-
lim
(5.15)
Hence,
otherwise where y is a constant in the interval (e:.2-e:). y.".1 and 0<<<< I.
- y
f(l-i).
[I +.ct-d-i)TqJ(t-d-i)]
(S.7)
tp(1)Ti(t)-Y·(I+d)
tit) 1(/) -0. [1+9(t)T4p(t)]l/2
I
(5.10)
UIiDa the dermitiOD of i(t), (S.6) may be rewritten as
I
I
2(1- i)
< [I +cp(I-d- j)Tcp(I_d_ i»)1/2 • Then using (5.14) it follows that
i(t) - i(/-l) - a(t)4p{t- d)[l + q>(t- d)T.(1 - d)J-l
·,,(t-d)Ti(t-l). (S.lt)
Hence, ,,(t-d-;)
";(1)11
2-
Ui(t-l)tf2.tJ(t)[ -2+11(1)
,,(I-d)TCP(I-d)
[1+ .,( t - d) T, ( t - d)]
[1 +,,(t - d - i) Tq>( t - d _ ;)] 1/2
]
. i(1-I)Tf(I-d)f!I-d)Ti(,-I) <0 (5.12) [I +.p(/-d)T,,(t-d)]
.
489
(1-
i)
[I + ,,(1- d- ;)Ttp(t_ d- i)t / 2
1-
0
for ;-1,2, .. ' td-1.
(S.l7)
Hence, usiq (5.16), (S.I7), and (5.14)
where
-0.
lim
e(l)
1-+00
[I +e,(/-d)Tf'{/-d)]1/2
cp(t)T-( -y(t)_·· -y(t-n+ 1), - u(/-l)···
(S.18)
-u(t-m-d+ l),y·(t+d»
Thia eatabliahea (S.IO). 0 Note that we do Dot prove, or claim, that i
(ft!'-
'0-
",T ' P 'I'··· '~+d-I' R' o _ -". ••• ,«,,-It PoI ) .
It is evident that the traekiD& error can be made identicaUy zero by ehooaina (u(t)l such that (6.3) However, since '0 is UDknown, the control law will be reeursively estimated. The foUowina adaptive aJaoritbm will be considered:
(5.19)
lim [Y(/)- y·(t)]-O.
t-.ao
foralll
1
(6.4)
"(t) _.,(/)Ti(/)
(6.S)
Po
hotI: Lemma 5.1 CDIlII'eI that condition (3.1) of Lemma 3.1 is aatiafiecl, with 1(/) - e(/). the traekiq error, and 0(1)- cp(1- d) the vector defiD.ed by (5.3). Also 6.(/)-1, and 62( / ) -I. It foBows that the UDiform bouDdedaell CODdition (3.2) is satisfied. AasumptioD 4c) ad Lemma 3.2 ensure that Ju(k-tI)f<m,+m. max IY(1')1
i(t)-i(t-d)- ~.,(t-d)[l+cp(t- d)T'
where A, is a flXecJ CODStaq,t and i(t) is a p-vector of reals depending on d initial values 1(0),••• ,I(d-I) and on y(.,), 0<., cr, u(T). 0<1" < t - d - 1 via (6.4). Note that (6.4) is aetuaI1y d separate recunioDl interlaced. (It bas recently been pointed out (18] that it is also possible to analyze a _pe recursion without iaterlaciDa lIIiq a different technique but the same aeneral priacipals.) The aualysia of projection a1aoritbm n bas mudl in common with the analysis for projection alptbm I. We wiD therefore merely state the analop of Lemma S.l and Theorem S.I for the algorithm (6.4), (6.S). ummtJ 6.1: DejiM
TberefOl'et lIIiq (5.3)
lIt'
but
;(/)- i(/) -
Hence,
_
1<.,<1
1<.,<1
..
0
0
and it follows that the linear bounc1edness condition (3.3) is also satisfied. The reaultDOW foDows by Lemma3.1 and by noq that boundedness of {II,(/)II) eIIIURI boundedDess of {IY< '>I} and {IN(t)I}· 0 VI. SISO
(6.6)
TIJsJ IIlI(t+d)U1-1I1(/)lfz< 0 aJOIIg witla tlw lOhdioru of (6.4) and (6.5) tmd
lI,
'o.
PaOJBC1"lON ALoOIU1llM
IJo Ilo
0< -:- <2.
II
o
Lemma 6.1 is used to prove Theorem. 6.1 in the same lIl81U1er that
In this seetioo we present an algorithm differing from that of Section V in that the cootrollaw is estimated dirccdy. This approach is adopted in [5), and essentially involves the factorization of fJo from (4.2). A related procedure is used in the self-tuDing replator (10) where it is assumed that the value of IJo is mown. AD advaDtqe of the aJaoritbm is that the precautions required in Section V to avoiddivilioo by zero in the calculationof the input are DO lonler neceaary. However, a disadvantap is that additionalinformation is required; specificaDy, we need to know the sign of fJo and an upper bouDd lor ita mapitude. PactoriDl flo from (4.2) yields
Lemma S.I is used to establish Theorem S.1. We obtain the foUowina theorem in this way. '1'heomn 6.1: Subject to AUIIIPf'tioIu 4a)-c) and for 0
(6.6)
' ......00
We Dote that the condition 0
y(t+d)-JIo(crOy(t) + ... +c(_ly(t-n+ 1)+11(/)
VII.
+ lJ;u(t-I)··· + fJ:,,+d_I"(t-m-d+ 1». (6.1)
ADAPTIVE CoNn.OL USING
R.Ect1RsJvE LBAST SQUARES
The wide-spread use of recursive least squares in parameter estimation
Let
indicatesthat it may find applicationin the adaptivecontrol context We treat the unit delay cue 01 algorithm I with the projection (5.6) replaced
e(/+ 4)-y(t+d) - Y·(I+d)
by recursive least squares.
-Po(lI(t) + crQy(t)·•• ~_Iy(t-II + 1)+ 1I1 ( t - l)
The adaptive control algorithm then becomes
11
;(t)-i(t-l)+
~ ... + 1I.:.+4-1"(t- m-d+ 1)- ~y.(t+d») -1Jo( U(/)- .,(1)7'0)
a(I)p(t-2).(t-l)
[1 +a(t)cp(/-l)Tp(t-2)cp(t-l)] (6.2)
490
[ y( t) - cp( t - 1) Ti( t - 1) ]
(7.1)
P(t)-[l-
P(t-I),,(t)f(I)Ta(t+ 1) ]P(t-l) 1 + CP(t)TP(t-l)cp(t)a(t+ 1)
.(1)Ti(t>.y·(t+ I)
(7.2)
Now
(7.3)
1,(t)12 [I +a(t)cp(t-l)Tp(t-2)cp(t-I)]
where p(t) is . , Xp matrix and the recanion (1.2) is 8II1UIled to be iDitialized with p( -1) equal to any positive defiDite matrix. The ICI1ar G(t) in (7.1), (1.2) playa the same role u in SectionV and is required 0D1y to avoid the noapDeric pOllibility of divisioD by zero in (7.3) wh. evaluatiq II{t). Hence, G(I)-1 will almoIt always wort IDd for tl(1)-1 we observe that (1.1) aDd (1.2) are the .tuldard recursive leut IqlIU'eI aJaorithm. The sequence {tI{t)} may be choIeD u in (5.8). u.. 1.1: AItmg with 1M 8OIutItH&r of (1.1), (1.2), (1.3) , . /tIItctiolt Y(1)-i(t)TP(t-l)-li(t) U II bount/ed, IIOIIMIt'tiN, PJOIIinc1W&filfr jwIctioII tIIIIl lim
'-.00
(7.12)
Hence, from (1.11) and (7.12) -0.
(7.13)
''''00 [1 +2(Up(t-2»))U«p(t-l)U 2 ]
TbiI will be recopized as beiDa condition (3.1) with .f(1)- ce(t), b.(I)1, and bi') - 2(A..,J.p(t - 2)D. To establish the UDiform boundednesa condition (3.2) we proceed as foUows. From (7.2) and the matrix inveniOD lemJDa,
pet) -1- P(I-l)-I + a(t)cp(t)9(/)T.
(7.4)
Hence,
~ i(t)-i(/)-,o-
Proof:
2
1!<1)1
lim
r-
.(1-1) '(I-I) -0 [1 +a(t)cp(I-l)7'P(t-2)CP(I-I)]1/2
;>
le(t)12 [I +2U.(I-l)1I2
XTp(t)-l x >xTp(t-l)x
Prom (7.1),(S.2),
• ... a(I)P(I-2)tp(I-l)cp(t-l)T;(I-l) 1(1)-1(1-1).
[I +tI(t)CP(I-I)Tp(,-2).(t-I)]
>A.ua[p(/-l)-ll llx Il 2
(7.S)
for each xEA'.
(7.14)
Now choose x as the eigenvector corresponding to the minimum eigenvalue of [P( t) - I ~
Then uain& (1.2),
Then from (7.14)
A.m[P(I)-I] >A.m(P(t-l) -I].
;(I)_P(I-I)P(I-2)-I;(/-I).
So AaJp(t) -I] is a nondecreasing function bounded below by
Thus,
A-JP(-I)-I]-X- I >0. P(t-l)-I;(I)-P(t-2)-Ii(,-l).
Now defllliD& V(I)
Hence from (7.13), o
(7.6)
i(, -1)TP(t -1);(1 -I) we have
U
Y(t)- Y(t-l)_;(t)Tp(l-l)-I;(t)_;(t-I)Tp (t - 2) - Ii(t - I ).
VIII.
MULTIPU-1NPur
MULTD'LB-<>urPuT SYSTEMS
For the case m- r» 1, the system (2.1), (2.2) can be represented in the form
UIiq (1.6)
Y(t)- Y(t-I)- [i(I)-i(t-l)]TP(t-2)-1i(t-l)
_ -a(t) i(t-I('PC t- l7
(7.1)
where we have used (1.5). It is clear from (/.7) that V(I) is a bo~ DODDeptive, DODiDcreuina function and hence converp8. Thus. from fl.1), aDd since a(t) is bounded away froJDzero, •
•• u(t)
r-
T
lim 1(1-1) .(1-1),(1-1) '(1-1) -0.
,-.00 [I + tI(t)4p(t-l)Tp(t-2)cp(t-l)]
where Ak(q - I) and BIc/(q -I) 1
Hence, lim
e(/)
,.....ao
[1 +a(t)cp(t-l)Tp ( I - 2)cp(t - I»)' / 2
-0
(7.8)
where
and
4- 1<)<". min (dil}'
(7.9)
o
lim [.,,(1)-)'-(1»)-0.
I-.ao
(7.10)
Yl(t~dl) ] _ [al{~-I) [
,.(1+ tJ...)
~ ]y(t) a".(q-l)
0
~1I(q-l)
Proof.' From Lemma 7.1
e(l) -0. ''''00 [1 +a(t)cp(t-l)7'P(t-2)9(t-l»)1/1
i-I,···,nI,
(8.1) can be written
1'II«Jmn 1.1: Subj«t to Amlnpliolu 4tI)-c) if I. aI,orilltm (7.1), (1.2), (1.3) i8 ."Ii. to 1M IYstem (2.1~ (2.2) (r- m-l), IMn {Yet)}, {fI(I)} are botI1ItJ«J and
lim
(8.1)
q -tC-.B...... (q-l)
+
(7.11)
: [ I3lftl(q-l)
491
...
where ~(t) is !-P, (- ~ + m(m, +~» vector of reals depending upon an initial vector ',(0) andy,(.,.), 0<"
where
and ",(q-l)-Ii(q-I)BU(q-l)q44-~.
(8.3)
a
It can be seeD that (8.2) consists of a set of multiple-input siDIle-output (MISO) systems haviDa a common input vector. The foUowiq asaumptioDl will be made about the system.
11(0). 2) For I:> 1 the proceduJe of Lemma 9.1 below guarantees the 101vability01 the algorithm equatiou for II(I). Um1IIII 9.1: I" ortIttr tItat 1M IIttII1U t1/ cM/fidm/8 of u(1) in (9.5) i.r 1tOfLfbIIultv for Gill:> I U u III/fIdett for a(t) I" (9.4) 10 be cIIomt 4r jollowl:
A""".tltHt Set B: a) d1, - · · ,tl. are known. b) An upper bound for the order of each polynomial in (8.2) is knoWD. c) The system (8.1) satisfies condition ,lIIu-.t'Bu(z)
det[ z4a-4l(.B..,(z)
.. •
•.•
zd••-tllB.",(Z)] .... o '4.- ....B....(z)
rr:
f
for Izi < 1.
where
lim [y,(/)- yt(t»)-O
i-l,···,m
eipavalue of - R -1(~-l)Y(/) with (9.6)
Condition Ie) daervea commenL Firat, for ally output colDpOnentYI' 1
O<e< 1 and G(/)-l is not an
and
Y(/) ~
ro.,··· '011I]'
(9.7)
'. in (9.6) is the vector of coefficients of II{t) in ',{t - 1), that is, T;-
S,',(t-I)
(9.8)
when (9.9)
", in (9.6) is the vector of cbaDps in the coefficient of 11(/), that is,
where ""(/) is a reference sequence. It is assumed that each (yt(t)} is known a priori and that ly,·(/)f <ml < co for aU I, ;~ 1,- _. ~m.
0,- Sir CPI(t-~)(l + 9,(/- ~)TcpI(t-~»-I
-1»)].
·(,,(/)- ,;(t-~)T'I(1
(9.10)
IX. MIMO ADAPrIVB CoNTllOL Proof: The proof will be by induction and we first observe that This section wiD be concerned with the multivariable versions of the from (9.4) and (9.6)-(9.10) adaptive control algorithms introduced in Sections V and VI. The multivariable version of the allOritbmof SectionVII also foDows analoR( I) - R( 1- I) + a( I) V( I). (9.11)
gousty. A. MIMO Proj«tioft Algorithm I Let
'&
be
the
vector
of
parameters
in
(1,(9 -.)
and
Then: i) R(O) is nODlinpiar by the initial choice of ;~O), ; - I, ... t m. ii) Assume R(I-l) is nODSinplar. Then from (9.11), usinJ a(t)+Ot
fJll(q-I). • • fJ,.(q-I). Then (8.2) may be written ill the form
",(1+ ~)- cp,(t)T,&.
1<; <m
detR(t)-[detR(t-l)][det(l+a(t)R(t-I)-1 V(t»] -ldetR(/-l»)(Q(/»"'[ de~
(9.1)
where
-0
if and ODly if
~/»)I+ R(/-I)-I V(t)]
at/) is an eigenvalue of
-R(t-l)-I yet).
Defme ·1('+~)-YI(t+~)-,t(t+4)
_~(t)T'~_Y:(/+~).
(9.2)
It is evident that the trackiD& error may be made identically zero if it is possible to choose the vector u(/) to satisfy
1
(9.3)
Obviously (9.3) is a set of simultaneous equations in ..(t). Now the matrix multiplying 11(/) is nonsinplar since in (8.3) det(diaIJi(z»-t at z-O and Assumption Ie) holds. ~ence a unique solution "(1) of (9.3) exists at the true parameter value IJ.
But the definition of a(/) euures a(t)-I is not an ei&envalue of - R(t-l)-IV(t), hence R(/) is nonsingular.. However, by i) R(O) is nODSingular and it foDows by induction R(t), 1 ;> 0 is noDSiDplar. 0 We note that the above choice of a(t) hu been included for technical completeness and that a( I) - I will almost always work since it is a Dongeneric occurrence for t to be an eigenvalue of - R(/-l)-IY(/). Also since - R(1- 1)- I Y( t) bas only a fmite Dumber of eigenvalues it is always possible to find an a( t) to satisfy the lemma by computation of the eigenvalues of R( 1- 1)- I Y(I). 'I'Morem 9.1.· Subject to Ammption.r &I)-c) if tlte algorithm (9.4), (9.5) if applied 10 tlw system (2.1), (2.2) with r=m, then (y(/)} and (II(I)} an bou1ukdand
Consider the foUowilll" adaptive algorithm:
lim 1.1;( t) - y/.( 1)1-0;
i,(t)-~(t-l) +a(t).,(t- d,)[ 1+ CPi(t~t4)T,,(t- d,)]-I ·(YI(I)-CPi(t-~) T"';(t-I) )
cp,(t)T~(t)_,,"{/+ ~),
1 «t <m
1
' ....00
Proof: Usins Lemma (5.1) for each i, we have
(9.4) (9.5)
492
lim ' .... 00
.
[1 + 41>;(1 -
e.(t) f
~)Tcp;(1 -~) ]
1/2
-0
•
where d-max(d1t • • .Jt(J. i(t)T is aD ntXn' matrix of reala depeactiq II iDitial matrices I(f)T, 1 <;
The proof DOW followa that of Theorem. 5.1, except in the case that the vector )'(1) is unboundecL In this case there exists a subsequence (I,,) such that lim II,(/..)U- co
OD
I.. ~CIO
and IY/(I + ~)I < IYJ('-)('- + ~,-~I
for some I
gT + K - KTg i.r poritiw (9../5):
It thea follOWl by Lemma 3.2 that there exist coDltanti O
11.,('..)"
I
a) trace[ i(I+d)Ti(t+d)]
b)
lim t....
SiDce m is fiDifet there ail.. a further subsequence {t,,} of the sub{III} .uch that
MqueDC8
11.,(,.,)11
dI/iItit-, t"', tIlotw
1M tTtIjectorla of (9.14),
-trace[ i(t)Ti(t)] <0.
e,(t+~) -0, [I +,
I
Proof: a) We caD rewrite (9.13)
for at least one i, 1
UIiD& (9.1S) u
&lid (1,(,.,+4)} is ubouDded. The remaiDder of the proof then followl dlat 01 Tbeonm 5.1 where we note that
o
Ie,(I)I-IY,( t) - yt( 1)1·
Heace, from (9.14) B. NINO Pro}«tioIJ Al,orltllm II
z-o.
From (8.2). (8.3) the fact that 1'j(z)-1 for i-I,· .. ,lit uad by AuumptioD Ie) we can factor out the nonsiDgular matrix r o (-(IJ,(O)D
and
givinl
trace( i(1+tI)Ti(t+ d) -trace(i(I)Ti(t»
_-trace[(KT+K-KTK where
f(t)T,(t)
)
(I +.
.(i(t)T.,(t)[1 +.,(t)T.,(t)r l.ct)Ti(t» ]
<0 b)
aDd tim
1-+00
~
if gT + K- KTK is positive dcfiDite.
ill the proof of Lemma (7.1) it foDows that
traee(xr +K-XTK [I +.
Define
SiDce gT + K - KTX is positive defmite then
- : ]_[JlI(t;d ]_[JlW;d [ e",(t+ tI..) y",(t+tI..> y':(/+ t(..> l
l
) ]
)
or
yf(t+dt) -ro u(t)+C(q-l)y(t)+D(q-l)u(t-l)-r;1 : [ y':(t+d,..) [
- r 0< u( t) -
'OT.<
]1
tim
''''00
roll "." ][1 ·
d
1 +9
-..(t+t.(.J
0
Thia iJDpliea that (9.17) holds.
t»
(9.13)
UIiDa Lemma 9.2 and foDowiDa the proof of Theorem 9.1 we have the
t.
where 'oT ia an 111 X,,' matrix whose itb row coataiDa the parameten folJowiDl. '1'II«nm 9.2: Subject to AulurptioJu &I)-c), and K T + K - KTK po.r;from the ith fOWl of C(q-I). D(q-I), and E-r f(/) is an ,,'X 1 tiw definite, if Q/pritltm (9.14). (9.15) ;" appli«l to 1M .rystem (2.1), vectorcoataiDiDa the appropriate delayed veniou of y(t). u(t -I~ and (2.2) willi r- m, ,hDJ 1_ fJ«10I'.J y(I) awl II(t) tW bormd«IlIIId y·(t):
o'.
4p(1)T_( _ y(t)T, _ y(t- J)T,•.• , - fI(I_I)T,
lim IY,(t) - y;e(t)I-O,
-U(t-2)T, ... ,yr(t+d.),··· ,y,:(t+tJ..».
ADaIoaoUlly to Section VI we introduce the followina adaptive control
X.
alpithm, el(t+d.) ] i(t+d)T _i(i)T -p
:
[
lIe t) - i( If",,( t)
I «t <m.
1-+00
[l+'P(t)TfJ(t)]-I.(I)T (9.14)
_.(1+ d".) (9.1S)
o
NON'LINBAIl SYSTBMS
Altho. the aaalysia in the paperbaa been carried out for deterministic Jinear systems, it is clear that it could be readily exteDded to certaiD cIuIea of nODlinear systems of bowD form. The essential points are the form 01 (5.2) or (6.2), and the IiDear bound CODdiIiOD (3.3). The latter point would indicate that systems with cone bounded nODlinearitiea would satisfy the conditioD&.
493
xr,
CoNCLUSION
The paper hu analyzed a pneral class of discre.time adaptive control alaorithma and has abown that, under suitable conditions, they will bealobaI1y convcqent- The alaorithma have a very simple structure and are applicable to both sinl1e-input siD&10-0utput and multiple-iDput multiplo-output systems with arbitrary time delays provided only that a ,table coatrol law exists to achieve zero trackiD& error. The results resolve a loDa staDdiDg question in adaptive control reprdina the existence of simple. atobally converpnt adaptive algorithms.
(1) I. D. LaDdau. "A lurvey of model refa'OllCC adaptive tec1miqua-Tbeory aacl appticaltall." A........, vol pp. 353-319, 1974(1) R.. V. MoaopoIi. "Model ref..- adaptive COIltrol with all a teeI error Ii lEU TMu. AI....,. e-tr., vol. ACI', pp. 474-415, OcL 191.... (3) A. P , 8. R. BarmiIb, aDd A. S. Mone. NAD astable dyDUDic:al ayltem UIOCiatecl wi1b aodeI nllNIICe adaptive control," IEBB TPrIIIf. Coftt,•• vol AC23. pp. 499-5001' Jae 1971. (4J K. S. NaNDdra ucl L S. Valavui, -Slable adaptive COIltroUer cIeIipa-Direct coatrol.·,BU TNar. Alii....,. CfIIIIr.. vaL ACn. pp. S70-S83. A.... 1911. (5) A.'eur ad S. Mane, .. Adapti¥c QOIltrol of ...........t ~. tiMar .,......" IEEB n-t. A......,. C."..• wi. ACD, pp. 557-570. A.... 1971. (fi) G. A. DuIoDt ud P. L Bitaqer, --seu-hIIliq coatrol oI.litaaiUDl dioxictekiIa." IBEE n.u. Aw..... CMIr., 'VOl. A~Z3. pp. 532-531, A-. 1971. (7) K. J. Aatrim, U. IIoriIIoa, L liUDIt aDd B. WitteDmUk, -rbeory ud appticatiou of . . t replaton." A........, 19. pp. 457-476. 1977. (I) L li "AuIyIiI 01 recuniw .toebutic aJaoritJu.," IEEE TIwu. A...... C.",.., voL Aen. pp. '51-575. A-. 1m. (9) -,"OD poei,," nal traDII. hactio. aDd tIM COIlwrpllCe of IOID8 recursive . . . . .,.. 1BEE TIwu. C.."., wL ACn, pp. 539-551, A~ 1m. (10) K. J. A.aim ud B. Wkteamark. -oa leIf-tuaiAa replatan," A ~ vol. 9. lIP- 195-199, 1973. 1'1) L lsillDl ad B. WiUlllUDal'k. "OD • ltabiIiziDa property 01 adaptive replaton," ".,.,.II'AC rtIMtl/blltJlt. TbiIiIi. u.s.s.R., 1976. (11] 8. I!pftb. -A uaiIied approIdl to aaodeI rei..... adaptiYe.,..... aIlcllelf tuaiAa replatan," Dep. Automat. CoDtr., LuaclIDat. TedmoL Tech. Rep., Dec. 1m. [131 T.t......... L V. MoDopoIi, "DiIcrete IDOcIeI refereace adaptive CODtrol with aD ........ error 1ipaI," AIIItIfIIIIIktJ. vol 13. lIP- 507-517. Sept. 1m. (t4) J. L WiIkaI, 5MbIIUy,....". of D,,..,.aI S)..... New York: 1970. (IS) G. Co 000cIwiD. P. J. Ramadp. ucl P. Eo CaiDeI, MDiIcreCe time .todautic adaptive ooatrol."SIAM J. c.u,. OptiMiz•• to be pubIiIbecL (lfi) A. S. Mone, -cHoba1atability of parameter adaptive OODtrol.,...... Yale UDiv.• S A IS Rep. 1I02L Mar. 1979. (17] x.. S. Nueadra aDd V-H. LiB. -Stable ctilcrete adaptive ccmtrol," Yale UDiv., S • IS Rep. 79011' Mar. 1979. [II) B.1!pftb. -Stability of modcI refcreace adaptive and IeJf tUDiq rqulaton," Cep. Automat. CaatrOf Lad last. TecbAo1., TedL Rep., Dec. 1978.
to.
A.....,.
,A.,..,.
sy"". __
494
Feedback and Optimal Sensitivity: Model Reference Transformations, Multiplicative Seminorms, and Approximate Inverses G.ZAMES
T
HIS paper is credited with the introduction of the subject of H 00 control theory, a topic at the center of control research during the 1980s and 1990s. The symbol H'" refers to the Hardy space of bounded analytic functions. For continuous-time systems, this corresponds to the space of stable, proper transfer functions (analytic and bounded in the right half-plane). The H'" norm of a stable transfer function is its maximum modulus, that is, the peak value on the Bode magnitude plot. Such peak values for closed-loop transfer functions had always been an important measure of performance and robustness in control. In fact, it defines the induced L2-norm, and its importance in control comes from this connection. The paper was motivated mainly by three considerations: 1. The classical approach to feedback design for single inputsingle output plants, in the style of Bode and others, takes place in the frequency domain: The open-loop frequency response is shaped by the addition of a compensator, such as a lead or lag compensator. Zames wondered whether such controllers can be induced by some precise frequencydomain optimality criterion. If so, then multivariable extensions might follow readily, whereas classical methods had not extended satisfactorily. 2. In the H 2 (equivalently, the LQG, or Wiener-Hopt) design formulation, the exogenous inputs (e.g., disturbances or sensor noise) are modeled as stationary signals with known stochastic characteristics. Zames suggested the need to be able to handle a different set of exogenous signals. He reasoned that a natural choice was a weighted ball in the space of finite energy time functions. This leads to an Hoo-type minimization problem. One can think of the H 2 approach as relatively optimistic. White noise scatters its energy over all frequencies. Zames's scheme is instead a worst case approach. The disturbance energy is allowed to be concentrated at the worst possible frequency. 3. Often, plant uncertainty is modeled in the frequency domain. Zames argued that robustness with respect to state models is artificial in many situations, such as where high-
frequency dynamics are neglected in obtaining a lower order model. The paper has two main contributions. First, the formulation of the problem of minimizing the H'" norm of the weighted closed-loop sensitivity function for a nominal plant; and second, a study of the ability of feedback (as in the case of the feedback amplifier, discussed in the paper of Black elsewhere in this volume) to reduce uncertainty. Of the two, the first sparked the most research. The literature on H 00 control is vast (the reference list includes twenty-two books, a sampling of merely the books treating the subject in various settings and at various levels), so a survey of the entire landscape is not possible. Research in the 1980s was devoted mainly to developing a variety of solutions to the pure mathematical problem of H'" optimization. A beautiful collaboration arose between control theorists and operator theorists, and the H'" sessions at the conferences of the day were charged with excitement. Surprisingly, it turned out that the best way to solve ROO optimization problems was to convert them to state-space form. In fact, a breakthrough occurred in 1988 with Doyle and Glover's state-space solution (the formulas for the controller were announced in [11], the full treatment with proofs appearing later in [7]). Their solution involved two Riccati equations, just as for the LQG problem, but in addition a remarkable coupling condition. The 1990s saw a number of interesting developments. The two-Riccati solution highlights the fact that the ROO problem can be posed as a two-person zero-sum differential game: the control signal as the minimizing player versus the disturbance signal as the maximizing player. Basar and Bernhard [1] developed H'" theory in this way and extended it to time varying, finite horizon, and nonlinear problems. A more recent trend is the formulation of the H 00 criterion as a linear matrix inequality, e.g., [3], leading to a convex optimization problem solvable numerically by interior-point methods. Since one of Zames's goals began with classical control, it is fitting that H'" control has filtered down from research journals into undergraduate textbooks, e.g., [2]. In an undergraduate course, the treatment usually involves three problems. In the
495
nominalperformance problem, a suitable closed-loop transfer function, such as the weighted sensitivity function, is optimized in H'" norm for a nominal plant. The closed-loop shape is altered via the weighting function, and this supersedes the older approach of open-loop shaping. In stability robustness, a perturbation model of the plant is assumed and a controller is sought that maximizes the size of the perturbation while achieving closed-loop stability. Both of these problems are amenable to analytical solution. The third problem is performance robustness, where closed-loop performance and stability are guaranteed for all plant perturbations not greater in size than a prespecified bound. This problem has remained intractable, though it initiated a great deal of study, such as that by Doyle [6] on the structured singular value. The importance of Zames's paper is that it breaks a trend, a trend away from stochastic control as a way of dealing with uncertainty, and it initiates the trend to give robustness the place in control that it deserves. REFERENCES
[1] T. BA~AR AND P. BERNHARD, HOO-Optimal Control and Related Minimax Design Problems: A Dynamic Game Approach, 2nd ed., Birkhauser (Boston), 1995. [2] P. BELANGER, Control Engineering: A Modern Approach, Saunders College Publishing (Philadelphia,PA), 1995. [3] S. BOYD, L. ELGHAOUI, E. PERON, AND V.BALAKRISHNAN, LinearMatrix Inequalities in Systemand ControlTheory, SIAM (CherryHill, NJ), 1994. [4] T. CHEN AND B.A. FRANCIS, Optimal Sampled-Data Control Systems, Springer-Verlag (New York), 1995. [5] R.F. CURTAIN AND H. ZWART, An Introduction to Infinite-Dimensional Linear SystemsTheory, Springer-Verlag (New York), 1995. [6] J.C. DOYLE, "Analysis of feedback systems with structured uncertainty," lEE Proceedings, Part D, 133:45-56,1982. [7] J.C. DOYLE, K. GLOVER, P.P. KHARGONEKAR, AND B.A. FRANCIS, "Statespace solutions to standard H 2 and H'" control problems," IEEE Trans.
Auto. Contr., AC-34:831-847, 1989. [8] r.c. DOYLE, B.A. FRANCIS AND A. TANNENBAUM, Feedback ControlTheory, Macmillan (New York), 1992. [9] A. FEINTUCH, Robust Control Theory in Hilbert Space, Springer-Verlag (New York), 1998. [10] B.A. FRANCIS, A Course in H oo Control Theory, Springer-Verlag (New York),1987. [11] K. GLOVER AND J.C. DOYLE, "State-spaceformulaefor all stabilizingcontrollers that satisfy an H'" norm bound and relations to risk sensitivity," Syst. Contr. Lett., 11:167-172,1988. [12] M. GREEN AND DJ.N. LIMEBEER, Linear Robust Control, Prentice Hall (EnglewoodCliffs, NJ), 1995. [13] B. HASSIBI, A.H. SAYED AND T.KAILATH, Indefinite-Quadratic Estimation and Control: A UnifiedApproachto H 2 and H'" Theories, SIAM (Cherry Hill, NJ), 1999. [14] lW. HELTON AND O. MERINO, Classical Control Using H oo Methods, SIAM (Philadelphia,PA), 1998. [15] R.A. HYDE, H oo Aerospace ControlDesign:A VSTOLFlightApplication, Springer-Verlag (New York), 1995. [16] H. KIMURA, Chain-Scattering Approach to H'" Control, Birkhauser (Boston), 1997. [17] J. MACIEJOWSKI, Multivariable Feedback Design, Addison-Wesley (Reading, MA), 1989. [18] D.C. McFARLANE AND K. GLOVER, RobustController Design UsingNormalizedCoprimeFactorPlantDescriptions, Springer-Verlag (New York), 1990. [19] M. MORARI AND E. ZAFIRIOU, Robust Process Control, Prentice Hall (EnglewoodCliffs, NJ), 1989. [20] D. MUSTAFA AND K. GLOVER, MinimumEntropy H oo Control, SpringerVerlag(New York), 1990. [21] M.A. PETERS AND P.A. IGLESIAS, Minimum Entropy Controlfor TimeVarying Systems, Birkhauser (Boston), 1997. [22] S. SKOGESTAD AND I. POSTLETHWAITE, Multivariable Feedback Control: Analysisand Design, Wiley (New York), 1996. [23] A.A. STOORVOGEL, The H'" ControlProblem: A State-Space Approach, Prentice Hall (EnglewoodCliffs, NJ), 1992. [24] M. VIDYASAGAR, Control System Synthesis: A Factorization Approach, MIT Press (Cambridge,MA), 1985. [25] K. ZHOU WITH lC. DOYLE, AND K. GLOVER, Robustand OptimalControl, Prentice Hall (EnglewoodCliffs, NJ), 1996.
B.A.F.
496
Feedback and Optimal Sensitivity: Model Reference Transformations, Multiplicative Seminorms, and Approximate Inverses G. ZAMES, FELLOW, IEEE
A bsl,al:l-lo this paper, the problem of sensitivity reduction by feedback is fonnulated as an optimization problem and separated from the problem of stabilization. Stable feedback schemes obtainable from a given plant are parameterized._ Salient properties of sensitivity reducing schemes are derived, and it is shown that plant uncertainty reduces the ability of feedback to reduce sensitivity. The theory is developed for input-output systems in a general setting of Banach algebras, and then specialized to a class of multi variable, timeinvariant systems characterized by n X n matrices of II~ frequency response functions, either with or without zeros in the right half-plane. The approach is based on the use of a weighted .fem;norm on the algeb...a of operators to measure sensitivity, and on the concept of an approximate itwerse. Approximate invertibility of the plant is shown to be a necessary and sufficient condition for sensitivity reduction. An indicator of approximate invertibility, called a measur« of .dngularity, is introduced. The measure of singularity of a linear time-invariant plant is shown to be determined by the location of its right half-plane zeros. In the absence of plant uncertainty, the sensitivity to output disturbances can be reduced to an optimal value approaching the singularity measure. In particular, if there are no right half-plane zeros, sensitivity can be made arbitrarily small. The feedback schemes used in the optimization of sensitiviiy resemble the lead-lag networks of classical control design. Some of their properties, and methods of constructing them in special cases are presented.
d
FILTER Fig. I.
of sensiuvrty or plant uncertainty that are natural for optimization? how does plant uncertainty affect the possibility of designing a feedback scheme to reduce plant uncertainty? At a more practical level, the theory will be illustrated by simple examples involving single variable and multivariable frequency responses. The questions here are: can the classical "lead-lag" controllers be derived from an optimization problem? How do RHP (right half..plane) zeros restrict sensitivity? in multivariable systems without RHP zeros, can sensitivity be made arbitrarily small, and if so how? A.
I.
INTRODUCTION
I N THIS paper we shall be concerned with the effects of feedback on uncertainty, where uncertainty occurs either in the form of an additive disturbance d at the output of a linear plant P (Fig, I), or an additive perturbation in P representing "plant uncertainty." We shall approach this subject from the point of view of classical sensitivity theory, with the difference that feedbacks will not only reduce but actually optimize sensitivity in an appropriate sense. The theory will be developed at two levels of generality. At the higher level, a framework will be sought in which the essence of the classical ideas can be captured. To this end.. systems will be represented by mappings belonging to a normed algebra. The object here is to obtain general answers to such questions as: how does the usefulness of feedback depend on plant invertibility? are there measures Manuscript received October 8, 1979; revised December 4, 1980 and December 17, 1980. Paper recommended by A. Z. Manitius, Past Chairman of the Optimal Systems Committee. An earlier version of this paper [23J was presented the 17th Allerton Conference. October 1979. The author is with the Department of Electrical Engineering, McGill University. Montreal, P.Q., Canada.
v
u
Motivation
A few observations might serve to motivate this reexamination of feedback theory. One way of attenuating disturbances is to introduce a filter of the WHK (Wiener- Hopf- Kalman) type in the feedback path. Despite the unquestioned success of the WHK and state-space approaches" the classical methods.. which rely on lead-lag "compensators" to reduce sensitivity, have continued to dominate many areas of design. On and off, there have been attempts to develop analogous methods for rnultivariable systems. However. the classical techniques have been difficult to pin down in a mathernatical theory, partly because the purpose of compensation has not been clearly stated. One of our objectives is to formulate the compensation problem as the solution to a well defined optimization prohlem. Another motivating factor is the gradual realization that classical theory is not just an old-fashioned way of doing WHK, but is concerned with a different category of mathematical problems. In a typical WHK problem, the quadratic norm of the response to a disturbance c is minimized by a projection method (see Sections III'-A' and IV-C); in a deterministic version. the power spectrum
Reprinted from IEEE Transactions on Automatic Control, Vol. AC-26, April 1981, pp. 301-320.
497
Id(jw)1 is a single, known vector in, e.g., the space L 2( - 00,00); in stochastic versions, d belongs to a single random process of know'; covariance properties. However, there are many practical problems in which ld(jw)1 is unknown but belongs to a prescribed. set, or d belongs to a class of random processes whose covariances are uncertain but belong to a prescribed set. For example, in audio design, d is often one of a set of narrow-band signals in the 20-20K Hz interval, as opposed to a single, wide-band signal in the same interval. Problems involving such more general disturbance sets are not tractable by WHK or projection techniques. In a feedback context, they are now usually handled by empirical methods resembling those of classical sensitivity. One objective here is to find a systematic approach to problems involving such sets of disturbances. Another observation is that many problems of plant uncertainty can be stated easily in the classical theory, e.g., in terms of a tolerance-bind on a frequency response as in [2], but are difficult to express in a linear-quadratic-statespace framework. One reason for this is that frequencyresponse descriptions and, more generally, input-output descriptions preservethe operations of system addition and multiplication, whereas state-space descriptions do not. Another reason is that the quadratic norm is hard to estimate for system products (see Sections iII/-A' and IV-BI), whereas th~ induced norm (or "gain") that is implicit in the classical theory is easier to estimate. We· would like to exploit these advantages in the study of plant uncertainty. Finally, sensitivity theory is one of the few 'tools available for the study of organization structure: feedback versus open-loop, aggregated versus disaggregated, etc. For example, feedback reduces complexity of identification roughly for the same reason that it reduces sensitivity [12], [13]. However, it is hard to draw definitive conclusions about the effectsof organization without some notion of optimality, and such a notion is missing in the old theory.
that sensitivity reduction is possible if there
IS
such an
inverse.
C.
Background
Many of the ideas in this paper are foreshadowed in the classical theory [1], [2] of single-input single-output convolution systems, especially as presented by Horowitz [2], who derived various limits on sensitivity imposed by the plant, and stressed the need to consider plant uncertainty in design. The author posed the feedback problem in a normed algebra of operators on a Banach space, and introduced [4], (5] perturbation formulas of the type (l-P)-I-(J-Po)-I =(1- p)-I( r- Po)( j - Po)
·1
(1.1 )
which were used to show that high-gain feedback reduces the sensitivity of linear amplifiers to large nonlinear perturbations [3]-[5]. Desoer studied a related problem in [6], and recently [7] has obtained results for the case of P and Po both nonlinear (also see footnote 8). Perkins and Cruz [8] used perturbation formulas similar to (1.1) to calculate the sensitivity of linear multivariable systems. Porter [9] posed various sensitivity problems in Hilbert space, and in a paper with Desantis [10] obtained circle type conditions for sensitivity reduction. Willems (11] has stressed the Banach algebraic aspects of feedback theory. In [1]-[10], the disturbance is either a fixed vector, or lies in some band of frequencies, and sensitivity is measured in terms of an output norm. as opposed to an induced operator norm. The approach of using weighted operator norms, and relating optimal sensitivity to weighted invertibility via a fractional transformation was used in [12], but has since been reworked and expanded. D.
Two Problems
We shall be concerned with the system of Fig. 1. Here, P is a given plant with a single (possibly multivariable) input B. Weighted Seminorms and Approximate Inverses l' accessible to control, and an output y to which a disOne way of defining the optimal sensitivity of a feed- turbance d, not accessible to control, has been added. The back system, and of addressing some of the issues men- plant input v is generated by a filter whose only inputs tioned in SectionI-A, is in terms of an induced norm of the consist of observations on the plant output y and a refersensitivity operator. However, it will be shown in Section ence input u. Two types of problems will be considered. Problem J -Disturbance Attenuation: This problem will III'-B'that the primary norm of an operator in a normed algebra is useless for this purpose. Perhaps that is why be the subject of Sections V-VII. Suppose that u= O. The operator norm optimization has not been pursued exten- input-output behavior of the system between the nodes (2,3) can be modeled by the flowgraph of Fig. 2, which sively in the past. Instead, we shall introduce an auxiliary "weighted" consists of the plant P and a single additional operator F seminorm, which retains some of the multiplicative proper- in the feedback path. The disturbance d is uncertain in the ties of the induced norm, but is amenable to optimization. sense that it can be anyone of a set of disturbances. Plant uncertainty will be described in terms of belongingto Initially (through Section VI) P is assumed to be known exactly, but later (Section VII) to be uncertain .. We would a sphere in the weighted seminorm. like to characterize the feedback operators F which attenuate Approximate invertibility of the plant is one of. the features which distinguishes control from. say, communi- the response y to d in some appropriately optimal sense, and cation problems. We shall define the concept of an ap- examine the effects of uncertainly about P on disturbance attenuation. proximate inverse under a weighted seminorm, and show 498
d
v Fig. 4.
Fig. 2.
may be found in such texts as Naimark [19). Occasionally, it will be assumed that a normed algebra is a Banach algebra. i.e., has the property that every convergent sequence of elements of the algebra has a limit in the algebra. It will be assumed that all linear spaces and algebras are over the real field.
d
A. Algebras of Frequency Response Systems
y
The frequency response of a stable, causal, linear timeinvariant system is a function analytic in the right-half of the complex plane. An accepted setting for such functions involves the HI' Hardy spaces [15], which we shall employ with some modifications to accommodate unstable systems. The algebra consists of functions fi{· ) of a complex variable s=a+jw, each of which is analytic in some open half-plane Re(s»op possibly depending on p(.), and is bounded there, i.e., p(s)~const. for Re(s»ap • The functions in H': will be referred to as causal frequency responses. If jJ is in H':, then the domain of definition of p can be extended by analytic continuation to a unique, maximal, open half-plane of analyticity Re(s»opm' where ap m ~(Jp. In general, p need not be bounded on this maximal open RHP, but if it is, then it can further be extended to the boundary by the limit p(0pm +j", ~ lim CJ -+ CJ p{0+ jw), which exists for almost all fA) provided approaches the boundary nontangentially from the right. Assume that all functions in H': have been so extended. The algebra H«) (of stable causal frequency responses) consists of functions p of H~ for which 0, Ei; 0, i.e., the region of bounded analyticity includes the RHP. The norm IIpll=sup{lp(s)l: Re(s»O} is defined on H«J, making H«J a norrned and, indeed, Banach algebra. A strictly proper function in H:' satisfies the condition ft{s)--+O as Isl--+oo in Re(s)~ap. The symbols H:6 and H will denote the algebras of strictly proper frequency responses in H': and Boo, respectively. By a straightforward application of the maximum modulus principle, the nonned algebra H't of strictly proper stable frequency responses has the property that Ilftll=esssup{lft(jw)l: w real} for any Pin H't, i.e., the norm can be computed from jw-axis measurements. Spaces of Inputs and Outputs: For any integer 1~q< 00, the linear space Hi consists of functions Q( ·) of a complex variable, each u being analytic in some open half-plane Re(s»a., inwhich the restriction of u to any vertical line is in Lq and f~oola(a+jw)lqdwE;const. for all a>ou. Again, the domain of definition of each uin is extended by analytic continuation to a maximal open RHP of ana.. Iyticity and then, if u is Lq-bounded in this RHP, to its boundary by a nontangentiallimit. The space H" consists
Hr:
Fig. 3.
Problem 2-Plant Uncertainty Attenuation: (Problem 2 is the subject of Section VIII.) Suppose that d=O, and the plant P is uncertain to the extent that it can be anyone of a "ball" of possible plants centered around some nominal value PI. If the filter is linear, the behavior of the system between nodes (I, 2, 3) can be modeled by the flowgraph of Fig. 4. The filter can be characterized by a pair of operators (U, F). We would like to find operators (U, F) which shrink the ball of uncertainty but leave the nominal plant invariant; to find bounds on the optimal shrinkage and to look at its dependence on plant uncertainty. E.
Outline of the Paper See Synopsis following Appendixes. II.
SPACES AND ALGEBRAS OF SYSTEMS
The purpose of this section is to specify the meaning which will be attached to the terms "frequency-response" and "linear system," and to summarize their properties for later use. A feature of the input-output approach is that systems can be added, multiplied by other systems or by scalars, and the sums or products obtained are still systems, i.e., they form an algebra. Frequently, it will be assumed that the largest amplification produced by a system can be measured by a norm, typically the maximum frequency response amplitude over some region of analyticity; under this assumption the algebra of systems becomes a normed algebra. Normed algebras provide the natural setting for the study of system interconnections such as feedback. Their elementary properties will be used freely here, and
499
a+Jw
o
H:
inverse (I + P) - I exists in A. and for any F in A the products PF and F·P are in A .\,. The elements of A s will be called strictly causal operators. (The concept of an algebra of "realizable" systems was introduced by the author in [14]; the related notions of strong causality of Willems [11], and later strict causality of Porter, Saeks, and Desantis are compared in a paper of Feintuch [20].) An example of the space ~X of inputs and the algebra A of causal operators is provided by the space Hi of (trans.. forms of) inputs and the algebra H~ of causal frequency response operators. In this context the algebra H~) of strictly proper frequency response operators is an example of an algebra A.f of strictly causal operators. Henceforth, we shall refer to the strictly proper operators as strictly causal. In the case of stability, we shall need the fact that a stable input-output system produces a finite amplification of inputs that can be measured by a suitable norm, and that stable systems form an algebra (see, e.g. [5]). Accordingly, we postulate the following. ~~ is a Banach subspace of :X whose elements will be called bounded inputs or outputs [for example, H 2 or L 2(O . 8 is a normed subalgebra of A containing the identity I, whose elements will be called stable causal IIPIIHx=llp"H~' The stable operators in H 00 map H", which is a proper operators, under the following assumption: the norm of subspace of into H", and are in fact completely de- any P in B is the ~~ - induced norm, that is. termined by their behavior on H". They can therefore be IIPll ~ sup{IIPull/llull: u in ~f), u*O}~ the sup being represented by their restrictions of the form P: H" ~ H". finite.' In sections devoted entirely to stable systems, we shall If H ~ is taken as an example of A., then IHI ec IS an concentrate on operators of the form P: H" ~ H" without example of B. distinguishing them as restrictions of operators on Hi. B, is the subalgebra of B obtained by intersecting As
of functions u in Hi for which CJu ~O, and is a Banach space under the norm \I II = supo>o {f~:x Iu( 0 + jw)1q dw }l/q. Inputs and outputs will belong either to or one of the Hi spaces, 1~ q< 00. In the special case q= 2 it follows from the Paley- Wiener theory that every function of H 2 is a Laplace transform of a time function in L 2(0, (0) and vice versa. In the general case of H'I, some functions can be viewed as transforms of time functions, and the others as frequency functions that do not appear in physical applications and can be disregarded. Frequency Response Operators: Let q be any integer" 1 ~q~ 00.. which will be held fixed. For any causaJ frequency response jJ(.) in H~ an operator P: Hi -+ is defined by the multiplication h(s)=P(s)u(s). P will be caned a causal frequency response operator" and the algebra of all such operators win be denoted by the bordered capital H~. Similarly. for each of the algebras of frequency responses Roo. H:O~ and H~, an algebra of operators mapping Hi into itself is defined and denoted by the corresponding bordered capital. i.e., Hoo, ":0, or "0. In the case of normed frequency response algebras, the corresponding operator algebras are similarly normed, e.g.,
u
He:
H:
00».
H:.
and B~ consisting of strictly-causal stable operators. It should be noted that B, is not a radical of 8" as P stable does not imply that ( 1+ P) - I is stable. We would like to take an axiomatic approach to the For the purpose of estimating the effects of small perproblem of sensitivity reduction by feedback" i.e., to single turbations, it will be assumed that Bs has the small-gain out the relevant properties of linear systems and postulate property; i.e., for any P in Os' if II P II < 1 then (J + P) - I is them as axioms. For example, the related properties of in B. If B is complete, i.e., a Banach space, this assumption causality.. realizability, and strong or strict causality have is redundant for then the series J- P + p2 -- ... converges definitions [see, e.g., [14] and [11]) reflecting the fact that to the inverse in B of (I + P). However, we have applicathe response to a sudden input to a physical system can not tions in mind in which completeness of B is replaced by anticipate the input, and cannot occur instantaneously. other assumptions. These properties of physical systems preclude the pathoA frequency response pE HOC which is not strictly proper logical phenomena associated with instantaneous response can not be realized exactly, but can be approximated by a around a feedback loop" and ensure that the feedback sequence of strictly proper responses of the form n( s +. operator (I + P) - I is well defined. However.. these details 11) - I p(s ), 11 == L2~ . . .. The sequence n( s + n) .. I is an are not relevant here. The only items of interest are that example of an "identity sequence." More generally, idencausal systems form an algebra of mappings, and that tity sequences will be used to construct strictly proper strictly causal systems form a subalgebra whose salient approximations to improper responses" and are defined as feature is the existence of the inverse (I + P) -) for all of its follows: an identity sequence {I" }c:= I for B is a sequence of members, i.e., a "radical." Accordingly we postulate the operators in B with the property that for any F in B the following. sequences II InF- F II and II FI" - F II approach 0 as n ~ 'YJ. ~ is a linear space whose elements will be called inputs It is assumed that 8", contains an identity sequence for B. or outputs. A is a linear algebra of linear mappings P: The following well..known (cf. Naimark {19. p. 162]) ~X,-+~, with identity I, whose elements will be called causal properties of a normed algebra will be crucial in many operators. A s is a radical of A, i.e.,I a proper nontrivial subalgebra of A with the property that for any P in A .~'l the
B.
More General Algebras of Systems
I The
properties of radicals are discussed in Naimark [19. p. 162].
2Whcnevcr the norm of .\' is not identified by a subscript. it should hi' taken to be the principal norm of the space to which .r belongs. 500
parts of the paper. For convenience they are proved in Appendix I. Let P and Q be in B. Proposition 2.1: a) If (I+PQ)-I IS In B, then (/+ QP)-I is in B~ and the formula P(I+QP)-I =(/+ PQ)-Jp is valid. b) If R is a radical in Band P is in R, then P has no inverse in B. (Strictly causal operators have no inverses in B.) c) If P and (1 + P)-1 are in B and tfPIJ
We shall be interested in situations in which P is at or near some nominal value PI' and the feedback F appears as an operator variable in an optimization problem whose object is to minimize response to d. Unstable operator variables are difficult to handle, and so our first step will be to show that F has an equivalent realization in terms of a stable operator. A.
The Model Reference Transformation
The flowgraph of Fig. 3 is described by the equations
FEEDBACK DECOMPOSITION: STABILIZING AND STABILIZED STAGES
We proceed to derive a decomposition principle to be employed in disturbance attenuation. Suppose that there is no plant uncertainty, and that the plant and feedback are constrained not to be simultaneously unstable. Under these hypotheses. any closed-loop stable feedback design can be decomposed into two stages: a first stage involving plant stabilization (which can be omitted for stable plants); and a second stage, involving a model reference scheme in which only stable elements are used, and which is automatically closed-loop stable. The choice of a stabilizing stage is independent of, and does not prejudice the choice of the second stage. Having established this fact, we shall be free to concentrate on the second stage of the disturbance attenuation problem under the condition that the plant is stable (or has been stabilized), without loss of generality. Consider the system of Fig. 2. The plant input v, output )', and disturbance d are all in ~. and satisfy the equations y=Pv+d (3.la) v= -F}'
(3.3a)
v= -Q(y-Ptv)
(3.3b)
in which .,Y, u, and d are in ~X, and P, PI' Q are in AJ' Equation (3.3) will be called a model reference scheme with comparator Q. as the output of the plant P with disturbance d added is compared to the output of a model PI of the plant without disturbance, and the difference actuates Q. The two sets of equations (3.1) and (3.3) are called equivalent iff every input- output triple i d, u, y) in 'X 3 satisfying (3.1) satisfies (3.3), and vice versa. Their equivalence will be established under the assumption that the equations Q=F{ 1+ P.F )--'
( 3.4a)
F=Q(I-PtQ)-1
(3.4b)
hold. If either equation in (3.4) is valid.. then so is the other. and
(3.lb)
in which P and F are operators in A s (see Remark 3.le)]. We shall refer to (3.1) as a feedback scheme with plant P and feedback F. Since P is strictly causal, the inverse (I+PF)-I exists in A. Therefore, for each d in ~, (3.1) have unique solutions for v and y in ~, given by the formulas y= (1 + PF) -1 d
y=Pv+d
(3.5)
To derive
(3.5)~
suppose (3.4a) is valid. Therefore,
!-P1Q=/-PJ F( 1+ P, F) ··1
=(I + PI F)( I + PI f~) - I -
PI F( I + PI F) --- I
=(J-tPIF)-l
(3.2a)
v= -F(/+PF)-'d. (3.2b) Let K 32 : :X~~"X, denote the "closed..loop" operator mapping d to v. K 32 is an operator in A given by K 32 =- F( J +
and (3.5) is true: here the expression 1-::: ( I + P 1 F )(I -+PI F) -I and the distributive law for multiplication on the right was used. Equations (3.4a) and (3.5) can now be used to give the identi ties
PF)-I.
The flowgraphs in this paper are simple, and will be approached informally in order to avoid lengthy definitions. Expressions for some of the subsidiary c.l. (closed- so (3.4b) is true as claimed. The converse proposition is loop) operators. which can be found by inspection, will be proved similarly. Assumption: For the present, and until the end of Section listed without derivation as needed. For a system to be physically realizable on an infinite VI, assume that P= Pit i.e., there is no plant uncertainty. TheorenI t. time interval, it is usual to postulate (14] that all c.1. input-output operators must be stable. though "open.. loop" a) Any ciosed.. loop stable feedback scheme (3.1) with operators such as the plant P and feedback F may be stable plant P E 18.~ and (not necessarily stable) feedback unstable. The set of c.l. operators for (3.1) consists of: FE A s is equivalent to a rnodel reference scheme ",'hose K 22 = ( J+ FP ) - I.. K 23=PK z2 • K 33=(I+PFr- l .. and K 32 branches are all stable . i.e.. QE8s and P, -= P where f' and specified above. Accordingly, the feedback scheme (3.1) Q are related hy (3.4). Conversely.. any model reference will be called c.l. stable if Kij is in B for i.. l> 2 or 3. scheme with stable branches is closed-loop stable.. and 4
501
guide to perturbation analysis. I t will also appear that model-reference schemes have a useful plant-invariance
equivalent to a closed-loop stable feedback scheme subject to (3.4).
property.
b) If (3.4) holds, and d and y satisfy either the feedback or model reference equations they satisfy the equation (3.6)
Proof' a) For any feedback scheme (3.1), if (d, u, y)ECX,3 satisfies (3.1) and F is given by (3.4b), then (d, v, y) satisfies (3.3), and conversely.Therefore, (3.1) is equivalent
to (3.3). If the feedback scheme is c.l. stable, then Q must be stable as it equals - K 32 • If, in addition, P is assumed stable, then all branches in (3.3) are stable, as claimed. Conversely, by a similar argument, any model reference scheme (3.1) is equivalent to a feedback scheme (3.3). Suppose that the branches of (3.3), namely, PI' Q, and p =PI are all stable. Then, all the cJ. operators of (3.3), namely, {K ij };, j : 2.3.4. S' must be stable because they can be expressed in terms of sums and products of the stable operators P, PI' Q, and I. The last assertion follows from the expressions for the diagonal c.l, operators K;; of (3.3), namely, K 22 =I-QP J , K 33 =/-P1Q, K 44 =K ss =/ and the fact, easily checked by inspection, that the remaining c.l. operators Kij' i=l=J, are products of the Kji by P, PI' Q, or I. It follows that (3.3) is c.l. stable. b) If P=P t and (d, y) satisfies (3.1) or (3.3), and (3.4) holds, then (3.6) is obtained by substitution of (3.5) into (3.2a). Q.E.D. The operator (J - PIQ) appearing in (3.6) will reappear as a factor in most expressions for sensitivity. It will be called the sensitivity operator and denoted by E. For equivalent schemes E=(I+P1F)-'. Remarks 3.1: a) The model-reference scheme has some remarkable features. Unlike most feedback arrangements, it is a realization which cannot be made unstable by any choice of Q, at least for stable plants in the absence of plant uncertainty. Under these assumptions.? any allowable feedback law can be realized in the form of an equivalent model reference scheme, with the guarantee that all branches will be stable, and the closed-loop system automatically stable. The design of Q, whether for small sensitivity or other purposes, canbe accomplished without concern for closed-loop stability. In engineering applications, model reference schemes are realizable in principle, but may have undesirable features. For example, they may have high sensitivity to errors in the realization of Q. Unstable inner loops, obtained whenever (J-p.Q)-1 is unstable, may present reliability problems. Even then, the fractional transformation remains advantageous from the viewpoint of theory, as potentially unstable feedbacks F are replaced by stable operators Q. In later sections on plant uncertainty, the flowgraph interpretation of the model reference scheme will provide a convenient 31( P is unstable. the parameterization or d. stableschemes by a single operator Q is obviously still possible. However, some of our other conclusions, concerning existence of a feedback realization with stable elements, structuralstability,or decomposition properties, may no longer
be valid.
b) Implicit in our notion of an allowable feedback is the view that each feedback realization involves a graph, and that although most of the internal details of the realization may be unimportant, closed-loop stability at all internal nodes is essential. c) Theorem 1 holds even if F and Q are in A but not strictly causal. However, strict causality is a prerequisite for physical realizability, and will therefore have to be assumed in subsequent theorems. B. Unstable Plants
The assumption in Theorem I that the plant P is stable will now be relaxed. Consider a plant Po EA s with disturbance d at the output, which is unstable but for which there exists a stabilizing feedback, i.e., an operator Fo E A which gives a c.l. stable feedback scheme on being fed back around Po. The stabilized system can be incorporated in a model reference scheme, by letting P be the stabilized c.l. operator Po( 1+ FoPo)- J and d be the stabilized disturbance (I+PoFo) - ld o, and Q (or F) can be selected as for a stable plant. At this point the question arises: "can Fo be selected independently of Q (or F), or could the prior choice of Fa prejudice the class of achievable systems?" In general, the choices are not independent, even for stable plants, because the application of two unstable feedbacks in succession may give a result different from the application of a single feedback equal to their sum. ConLet sider the follo"wing f~equency response example in p(s)=l a~dfl(s)=f2(s),,=s-I'4Theapplication of a single feedbackf(s) equal to!I(s)+h(s) gives a c.1. stable feedback scheme,with c.l. responses. 1, (s + 2) -I, and s(s + 2) -I. However, if the feedback is split into two branches, the c.l. response across either one of these branches is (s + 1)/s(s + 2), i.e., the system is not c.l. stable. Popular belief notwithstanding, c.l. stable systems do not form an additive group under feedback if the complete set of c.l. operators is considered. However, if feedbacks are constrained to be stable then choices are independent, as the following construction shows. Let Po E A s be an unstable plant which can be stabilized by either one of two feedbacks. Fu and Fh in A S1 and label the resulting feedback schemes (a) and (b), respectively. We would like to find an operator ~h EA s which on being fed back around scheme (a), as shown in Fig. 3(a)~ produces a two-stage feedback scheme equivalent to scheme (b). (Observe that the two-stage feedback scheme has extra nodes in the feedback branches to allow for the possibility of noise sources there.) Proposition 3.2: If Fa and Fh are stable, then the stable feedback Fo h ~ F; - Fu makes the two-stage feedback scheme c.l. stable and equivalent to scheme (b). Proof' The two-stage scheme is obviously equivalent to scheme (b). and is c.l. stable because its c.l, operators consist of: i) the c.l. operators K 22 , K 23 , K 32 , and K 33 of h () h sc erne Q or sc erne (b), which are stable by hypothesis, or ii) sums and products of the operators listed in i), and
502
Hr:.
inverses is hard to study. This is a serious limitation in feedback problems in which expressions such as (I + PF) - I play a major role. By contrast, the "Mm spec which is widely used in classicaldesign measures the maximum frequency response magnitude, and is essentially the induced operator norm II PI/ ~ sup {.II Px" L 2 / 11x II L 2 : x EL 2 } , which has the multiplicative property, and is therefore convenient to estimate in cascaded systems. By describing plant uncertainty in terms of a sphere of specified radius in a norm having such a multiplicative property, it is possible to obtain a genera) approach to problems involving disturbances/random processeswhich are unknown but belong to prescribed sets. as we shall see in Section IV. Minimization of an induced norm in effect amounts to a minimax solution. Minimax methods do not necessarily represent uncertainty with .greater fidelity than quadratic methods. However, the concern here is iess with fidelity than with the ability to handle product systems.
the operators Fa or Fb which are stable by hypotheses.
Q.E.D. The following decomposition principle can be obtained immediately from Theorem 1 and Proposition 3.2. Let Po E A s be any unstable plant stabilizable by a set of stable feedbacks in 8.1. An)' closed-loop stable feedback scheme employing a stable feedback around the plant Po is equivalent to a closed-loop stable scheme consisting 0/: i) a stabilizing feedback Fo ER.s which can be selected arbitrarily, followed by ii) a modelreference scheme with stable operators Q and
U
PI· It follows that under our hypotheses,' and in particular under the assumption that plant and feedback. are not
simultaneously unstable, the problem of, sensitivity reduction can be decomposed into two independent problems: stabilization followed by desensitization of a stable system. Henceforth, we shall confine ourselves to the second problem. III'.
ApPROACHES TO FEEDBACK-SENSITIVITY
B'.
MINIMIZATION
A'.
Quadratic versus Induced Norms
The main properties of feedback cannot be deduced without some notion of uncertainty. Suppose that the disturbance d is uncertain but belongs to some subset OJ) of possible disturbances in ~. From (3.6) it is clear that for disturbances to be attenuated, (I-P.Q) must be small on 6D, i.e...' Q must act as an approximate inverse of PIon "D. The various approaches to the disturbance 'attenuation problem are differentiated by the way in which uncertainty is described, and this approximate inversion is metricized and calculated. A typical WHK approach in a deterministic version could be viewed as follows: 6D consists of the set of disturbances d in L 2(0, 00) possessing a single, fixed, known power spectrum Id( jw >1 in L 2( - 00, 00), and the object of design is to find a filter Q that minimizes the quadratic distance If d- P.Qd II L'2 where in general Q depends on Id( j~ )1. In the stochastic analog of this problem 6D is a random process characterized by probability-covariance functions and metricized by a quadratic norm. This description of uncertainty has certain limitations that we would like to circumvent, namely, the following. I) The covariance properties of the random process must be known. In practice, they are often unknown elements of prescribed sets. This is merely a limitation on the class of random processes for which WHK is valid. More serious from the point of view of feedback theory is the following observation. 2) The quadratic norm on plants employed in the WHK method lacks the multiplicative property II PQ II L, E; II P II L, tI QII L,' and in general it may be difficult or impossible estimate the norm of a product PQ from the norms of P and Q. The product norm II PQII L, may be large even though II PilL, and II Q II L, are small. . Consequently, if plant ·uncertainty is metricized by the quadratic norm, its propagation through products and
to
Constraints on the Norm of a Sensitivity Opera/or
It is natural then to try to pose sensitivity reduction problems in terms of the minimization of norm of the sensitivity operator, and to employ a norm having multiplicative properties. The primary norm of a Banach algebra has such properties, but the following propositions show it to be useless for this purpose. . Proposition 3.3: If P and Q are in a Banach algebra B and 111- PQ II < I, then PQ has an inverse in B. Proof: Denote (I - PQ) by E. As II E II < 1, the power series [- E + E 2 - • •• converges to an operator which Q.E.D. inverts (1- E). As (I-E)=PQt (PQ)-I exists. Proposition 3.3 has occasionally been interpreted as showing that invertibility is necessary for sensitivity reduction. This interpretation is empty. In fact, since strongly causal operators never have inverses in B [see Proposition 2.1b)], we have the following. Corollary 3.4: If PQ is in B", then 111- PQ II ~ 1. It is impossible to make the sensitivityoperator less than this simply means that the 1 in the original II norm. in frequency response of PQ approaches 0 at infinite frequen-cies and (1- PQ) approaches 1. An obvious idea at this point is to make (/- P1Q) small in norm over some finite frequency band, i.e., over an invariant subspace. The next proposition shows that norms over invariant subspaces usually are not useful measures of sensitivity for optimization purposes. Let ~ I be a subspace of ~t II a projection operator onto ~ I' and suppose that ~I is invariant" under 8, i.e., RII=llRII for each R in B. Let a denote the norm of (1- p.Q) restricted to the subspace ~ 1 and optimized over all Q, i.e., a ~ infQEB,slip{II(I-PIQ)IIdll: de(j, and IIdll= I}. Proposition 3.5: For any P in Bs ' a= 1 or a=O. The proof is in Appendix I. If a =O. sensitivity can be made arbitrarily small over the subspace ~~ ,. In practice there are special cases involving "minimum phase" systems
Hr
4More generally, Proposition 3.5 holds if B is replaced by any of its
;0:~:Ting extensions. Note that Il is not necessarily in the algebra
503
2) Let oD be the set into which W maps flat disturbances. in which solutions that approach a=O may be useful. More i.e., WOi) I =uV. 6D is also the set typically, this resultis achieved at the expense of increasing the sensitivity without bound on complements of qB I; in such cases, the norm of a restriction of ([- P JQ) is not a candidate for minimization. Corollary 3.4 and Proposition 3.5 delineate some of the peculiarities of the sensitivity optimization problem. In one form or another these peculiarities were recognized in the classical theory, and are probably the reason why it stopped short of optimization. We shall try to circumvent them by introducing an auxiliary (semi) norm to which they do not apply-
oD can be described as the unit ball in the seminorm 11·11 r
defined on the range of W (which is a proper subspace of H by the equation IIdli r ~ ItW - Jdlt. There are many engineering problems in which the apriori information about disturbances is in the form of an upper bound to the magnitudes of their possible frequency responses. The seminorm description 2) is natural for such problems, and I) occurs in inverse problems. IV. MULTIPLICATIVE SEMINORMS AND The seminorm II· II, employs an up-weighting, and U·11 r ApPROXIMATE INVERSES employs a down-weighting. These two examples generalize into the notion of left and right seminorms, defined as Uncertainty in a disturbance (or plant) in a linear space folJows. can be specified in terms of belonging to a ball of disturbances (or plants) centered at some nominal value, and A. Seminomas lor Inputs and Outputs" of radius specified in some norm. Such a description of uncertainty may be cruder than a probabilistic description, Let "ll be a II·ll-normed linear space. Let II-II t be any but is usually more tractable in feedback problems. seminorm defined on all of ~, and 11·.11, a seminorm One of the axioms of a norm asserts that only the zero defined on some nontrivial subspace ~, of 09. The semielement has zero norm. This axiom is often not needed, norm 11·11 T is said to dominate 11·11 t iff II yilt ~ 11 y II r for all)' and with its elimination a norm is replaced by the slightly in ~,; this dominanceis denoted by 11·11, ~ 11·11 r: more general concept of a seminorm. Definition: A left seminorm is any seminorm defined on A ball in any seminorm can be shown to be a convex all of ~ with the property that U·II, E;; II· It. A right semiset.' Conversely, any convex setS in a linear space gener- norm is any seminorm defined on a nontrivial subspace '"Yr ates a seminorm (see Rudin (22, p. 24]) known as the of e;y with the property that n· It ~ 11·11 r: For example, if W is any H~ filter of unit norm, the Minkowski functional of that set. In linear spaces convex sets" of uncertainty can therefore always be described in expressions II y II f ~ II Wy II and II y II r ~ II W - Iy II define terms of seminorms. We shall employ seminorms to obtain left and right seminorms, on H OIJ and the range of W, a systematic approach to such sets of uncertainty (cf. the respectively. The range of W is a subspace of H«J, proper whenever w(s) has zeros in the right half-plane or at 00. objectives outlinedin SectionI-A). In the next section, we shall define classes of left and right seminorms. To motivate the definitions, let us find B. Weighted Seminorms for Plants seminorm descriptions for two disturbance sets which can be generated by the interaction of filters and certain "flat"
disturbance sets. Henceforth, W will denote a stable causal operator of unit norm, which will play the role of a weighting filter. For concreteness, W can be thought of as an operator in H W: BOO -.Hoc, with response w(s)=k(s+k)-I. U1) will denote a flat disturbance set (analogous to white noise) consisting of the unit ball in the space of inputs, in this
o,
case in H~:
o)
Definition: A weighted seminorm is any seminorm II· If ~.
on the B with the property that ". fI w ~ /I ·11. The terms "weighted" and "left" are synonymous. We shall use the term "weighted" to distinguish the left semi.. norms on B used as measures of plant sensitivity from the others. A weighted seminorm on B is induced by a pair (tI-It!, 11·11 ,), where fI-1f r is a left seminorm on the space ~ (of outputs), and 11·11, is a right seminorm on a subspace ~, C~ (of inputs), iff 11·11 w is defined for A E B by the equation
whose elements are frequency functions of unknown but IIAflw=sup{IfAullr/lfull,: uecj,and ffullr:;t=O}. bounded magnitude, Consider two situations. It follows that II I II w .so;; I. I) Let 6j) be the set mapped by W into flat disturbances, i.e., W6D=6J)I' Gj) can be described as the unit ball in the In control problems, weightings are often introduced by seminorm 11·11 I. defined on H" by the equation /I d /I f filters, which act on disturbances either before entering a ~ II Wd IJ. plant or after leaving it. For example, let We and w:. be linear mappingsin ~x ~, each of unit ~-induced norm. A 'Satisfying the following additional assumptions: I) if x is in the linear
space, then ax is in tbe set for somereal a; 2) if y is in the set then so is
rv-
beomsention: Wheneverx belongs to a space on which several norms are defined, the unsubscripted norm II x II denotes the principal norm. Wei&hted norms will be designated by subscripts.
504
~ II WrCVII for CEB, and II DII WI ~ II V -IDw:.U for DE B,. Then, II·II w has the multiplicative property claimed, as
left seminorm is defined on
tlCDIl w = II W,CD~II E; II WrCV 11·11 V -IDJt;.1I ~ II~-lull. The pair (1I·1I"It·II,) induces the weighted seminorm IIAII w = II W,A ~II on the space B. =IICllw,IIDll w l • Although weightings produced by filters will be emphasized in this paper. they can be produced by other A symmetric seminonn can be viewed as a special case of means. For example. a weighted seminorm on "0 is given a multiplicative seminorm on the space of products B· B,.. by the supremum over a shifted half-plane. in which Br =B and the multiplicativeinequality holds for each of two pairs of seminorms, namely, (11·11 w,II·II) and II PII w =sup {I fl{s)l: Re(s )~a}~ a>O. t
In gen.. eral, weighted seminorms lack the multiplicative property It CD II w ~ II C II w 11 D II W of algebra norms. In problems involving the attenuation of a single disturbance (or single random process) this need not matter, as multiplications can be avoided. However, in problems involving plant uncertainty, closed-loop perturbations have the product form ([- PQ)AP. We shall employ seminorms with weaker multiplicative properties suitable for such products. Definition: A symmetric (weighted) seminorm on the algebra B is a weighted seminorm 11·11 w on the space B which satisfies the multiplicative inequalities J) Multiplicative Seminorms-s-Symmetric Case:
UCDll w
(4.1)
Any operator W: 'X--+ 'X of unit 'i>-induced norm which commutes with all operators of 8 defines a symmetric (weighted) seminorm by the equation II A II w ~ II WA II
=
IfAWII.
Symmetric seminorms have the property that II J II w = I.
1) Multiplicative Seminorms-s-General Case: In multi-
variable systems the plant perturbation dP always appears on the right of the product ([- PQ) a P, and often does not commute with i l>: PQ). In such cases a more general class of multiplicative seminorms will be used. If ~p is strictly causal. then the product (1- PQ) a P lies in a proper subspace of B (which is a left ideal, although we have no immediate use for this fact). With such products in
(11·11,11·11 w)·
c. Approximate Inverses and Singularity Measures Many problems of feedback theory. both classical and modem, can be reduced to the construction of an approximate inverse. Let II ·II w be a fixed, weighted seminorm on the space B. . Definition: For any operator P in B, an approximate right inverse (in B,,)of P is any operator Q in 8" for which8 11/-PQ II w < 11/11 w; the right singularity measure (in Bs ) of P (under 11·11), denoted by J&{P), is
p.( P)=inf {1I/- PQ II w: Q in s.}. In general, p,(P) is a number in the interval OE;p,(P)< 1. The last inequality follows from the observation that Q 0 gives II/-PQI1 w =11111 w· In all of the following H co examples, II·II w will be the symmetric weighted norm defined by II A II w ~ II WA II for A EHQO, where WEH: is a fixed (strictly causal) operator of unit norm, For example, W can be the "low-pass" frequency response w(s)=k(s+k)-I, k>O. As 11·11 w is symmetric, it has the multiplicative properties defined in Section IV-B1). Example 4.1: Pa is a plant in H~ with frequency response Pa(s)=a(s+a)-I, a>O. The sequence of operators Qn in "0 with frequency responses tln(s)=a"-J(s+a) ·n 2(s + n) - 2, n = 1,2,. · ., satisfies the equation
=
mind, we make the following definition.
Ilw(I-Ptln)IIH =
Definition: Let H,. be any subspace of B, and B· B,
1C
denote the space of products {CD: C in 8 and D in B,.}. A multiplicative seminorm on the space of products B· B,. is any weighted seminorm on the space B · B,. with the following additional property: there is a left seminorm 11·11 wt defined on B, a seminorm 11·11 WI defined on B,., and the inequality IICDllw
2
sup Re(s);"O
W(S)( 1-
n
(.\'+n)
2).
(4.1)
The right-hand side (RHS) of (4.1) approaches 0 as n --. co. Therefore, the singularity measure in "0 of Pu under lI·1I K' is IJ( Pu'>=O. The operators Qn are approximate inverses.
and the sequence Qn is an example of what will be called an inverting sequence. Example 4.2: Pa is the operator of Example 4.1; P" is the "nonrninimum phase" operator in HOC with frequency responsep,,(s)=
'The definition can obviously be generalized for the case of perturba-
KRecall that 11111 w
tions appearing on the left.
505
__ I.
and 11111 ... = I if 1I·1i w is symmetric,
Section V-A and Corollary 6.l it will be established that in fact 1£( PI ) = Iw(P )1·
In these examples we have emphasized approximate inverses under a multiplicative seminorm, In passing, it may be worth mentioning that WHl( problems can be viewed as approximate inversion problems in which the weighted seminorm of (I - PQ) is obtained' by weighting by a fixed vector d E;:L2(0, (0), to obtain 11 1- PQ Uw = II(I-PQ)dU L 2. Here p,(P) is the irreducible error, However, U· II w lacks the multiplicative properties. No matter which seminorm is used p,(.) has the following property, Proposuio« 4.3: For any PII and Pb in B, p(PbPa ) -p(Pb ) ·
a) 111
Proof: If the contraryis assumed to be true, there is a Q in B, for which 11/- PbPQQIl w
SENSITIVITY TO DISTUlUJANCES AND ApPROXIMATE INVEIlTIBILITY
°
o
o
'The fact that fiven pea, the closed-loop system is stable iff F(l + P1F)-1 is stable 15 ~iDted out by Desoer-Ch8n (21, Theore~ 3)! who scrutinize the relatioDsbip betweenopen- and closed-loop stabIlity m the context of convolution algebras.
10Po / Ph are often referred to as all-pass/minimum phase or inner/outer factors.
506
Filters optimal in this sense are known to be very p,(jlJJ )/Pb(}IIJ) for all real w, and Po has no zeros in Re(s)~O. Optimal sequences will be constructed for Po sensitive to plant uncertainty, and are practical only where accurate plant models are available. and Pb separately. Ph coincides with the operator of Example 4.2. By the reasoning of that example we get the lower bound I£(P,)~ B. Unstable Plants Iw(P>I; in fact, for the Ph factor alone, IIw(I-Phq)IIH:lC~ If Po is an unstable plant in A$ with output disturbance
Iw( P)I
whenever q preserves the analyticity of wp htl in
Re(s)~O.
We observe next that the function 'ih: ft ~ ¢, qb ~ Pb l(s)[I-w(P)w -'(s)] exactly minimizes II w( 1-
Pbtlb)II, since w(s)[l-pb(s)qh(s)] equals the lower bound w(!3) for all s in
do in qI;'1 and there is a stabilizing feedback £0 with the
property that Po(I+FoPo)-1 and (/+PoFo)-1 are in a, then we can let PI in Theorem 2 be the stabilized system Po( J + Fo Po) - I, and d be the stabilized disturbance (I + poFo)-ldo. In that case, (3.6) takes the form
P to cancel the pole Phi.
y=(I-P,Q)(/+PoFo)-l do.
(5.3)
We now combine qb with enough high frequency attenuation to obtain an H«J sequence:
The term (I + PoFo) -I contributed by stabilization appears in (5.3) as an extra right weighting on (I - p.Q). Provided 11·1\ w is modified to inlude the extra weighting, Theorem 2 Qbm(S )=Pb I(S)[ l-w(P)w-1(s)] m£(s+m)-e remains valid. Remark: We have preferred to separate feedback m=1,2,··· . synthesis into two consecutive stages: I) stabilization and (It will become apparent that the attenuation me(s+m)-t 2) desensitization of (input-output) stable systems. From will be at a high enough frequency to have arbitrarily little the point of view of input-output sensitivity theory, the effect on weighted sensitivity.) The factor Pa(s) can be separation is in a certain sense unavoidable. as the perinverted by the sequence in H turbations allowed for robust stabilization are radically different from those for desensitization. This point is n= 1,2,···. elaborated in Appendix II.
o,
The sequence tim of (5.1) is constructed from the product of qun and qbm' The validity of this construction is established c. Optimal Sequences: Symmetric Case in Corollary 6.1. Usually, optimal filters for sensitivity reduction are not Remarks: I t may be worth looking at a special case of strictly proper and can not be attained, although they can (5.1) to get a better feel for the kind of feedbacks our be approached by sequences of filters of increasing bandapproach generates. Let pu(s)=a(s+a)-I and w(s)= width. The behavior of such sequences is conveniently k(s+k)-I, a>O, k>O. Equation (5.1) gives described in terms of the concept of an "identity sequence," tlm( s ) =c m( s+ P)( s+ m) -1(S+ n m) -2. (5.2) or "approximate identity" drawn from Banach algebras. Here we shall summarize those properties of identi ty se2n quences which are employed in our filter construction. Cm ~ m m (k + p )- I. This optimal 4m consists of the Let 11·11 w be a fixed, symmetric" weighted seminonn on "lead" factor c( s + P), and high frequency poles whose the algebra B. A weighted identity sequence (widseq) is any purpose is to make qm(s) strictly proper. The feedback law sequence 1m , m =1,2, · .. in B with the property that i(s) produced by I1m(s) [via (3.4b)] is alead-Iag network II 1mIt = I and, for any A in B, II A - [nAil wand IIA -AInli w typical of classical control. approach 0 as n.-+ 00. For any P in A, a sequence Qn' If the high frequency poles are neglected, the sensitivity n = 1,2,· · ., is a right weighted invertingsequence (winvseq) operator E ~ I-P.Qm has the frequency response e(jw) iff PQn is a widseq. == w( P)w - l( s); e is small at highly weighted frequencies Whenever III-PQn11w--'O as n-+oo, Qn must be a and vice versa. If e( jeu) is compared to the value that right winvseq for P; for then, the inequalities would be obtained by letting q(s)= 1, it appears that qnt(s) PQnAII w ~ 11/- PQ" II wll All, has the effect of trading undesirable low-frequency phase lags arg p{ jw), for undesirably large magnitudes IIA -APQn ll w~IIAII·IIJ-PQnll w. , ft( jw )q( jw)t at high frequencies, where they matter less, at least if the specified weighting is correct. This, too, is a obtained using the multiplicative property of symmetric seminorms, have left-hand sides which converge to 0 as typical strategy of classical design. n ---+ 00. The growth of li(jw)1 as w-+ 00 depends on the decay For example, in HOO the sequence of operators with of t w( jw)l; if the former is too high, the choice of the latter frequency responses nr(s+n)-", n= 1,2,·· . and r>O any was inappropriate, if II w( jw)1 is bounded from below, then constant integer, is a widseq for the weighted norm' of Ie( jw)1 is bounded from above. The dependence of the optimal filter on the weighting W is not surprising, as W II Without symmetry a distinction between left and right identity sedescribes the convex set of disturbances to be attenuated. quences, etc., must be made.
"A -
507
Example 4.1. The sequence Q,,' of that example is a winvseq for
A,
r;
It will be shown that in certain cases an optimal sequence of approximate inverses for a product PbPa can be obtained from separate sequences for the factors Pa and Ph' and consequently some optimization problems can be decomposed into simpler ones. Let II· II a ~ II· II b be a pair of symmetric, weighted semi norms on the algebra B. Let P; in Hs and Pb in 8 have singularity measures Ila(Pa) and J1.b( Pb) under II·U Q and 1I·1l b' respectively, and optimal sequences {Qam}:=1 in a; {Qblll:O=t in B, i.e., III-P;Qinll; ~",;(P;) as n~oo for i=a or b. Lemma 5./: If lLa(Pa)=O, then ILb(P"Pa)=p.,,(Ph ) , and PhPu has an optimal sequence of \l.1I h-weighted right approximate inverses in 8 s of the form Qan Qhm" where for any m =1'1 2,· .. , n nr is a sufficiently large i~ teger. In fact. for any £>0 and O
o.;
II/-P"Pa Qan Qbmllh~p,,(Ph)+(. III
(5.4)
Proof: a) P-h(PhPa);;':P.h(P,,) by Proposition 4.3. Let us establish the opposite inequality. For any nl>O, n>O, we have
II J- PhPaQanQ"nlll" = II J- P"Qhm - Pn( PaQan - [)Qhm II" ~ 1\ [ - P"Qbm II b + II P"Il·IIPaQan -lllallQbm II
(5.5)
where the triangle inequality. the multiplicative property of symmetric seminorms, and the dominance tl·ll b ~ 11·11 a have been used. The integers m and n specified in the hypothesis exist by definition of p,,,( Ph) and by the hypothesis that #La(Pa)=O. (5.4) now follows from (5.5). As f was arbitrary, (5.4) implies that It,,( PhPQ)~P,,,( P,,). Therefore, IL,,( PhPa ) =P.h(Ph ) . and Qafl",Qm is an optimal sequence.
VI.
MULTIVARIABLE SYSTEMS IN
Hoo N
Q.E.D.
Terminology
N is a fixed integer. 1/ 2 N is the Banach space consisting of the N-fold product of H2~ on which the norm of any :, (~N IFl • Th e vector u" =(,... U J ~ U 2.: . .• U..). .\' IS II U"'I = ~ 1== t II" ", II'".. ).'..
elements of H21~· can be represented by columns of input or output Laplace transforms, Hoo N is the algebra of NXN matrices, P=[Pij]' whose elements are causal, stable, freqpency responses in H~. For any P in H«JN and s in ft., o[P(s)] denotes the square root of the magnitude of the largest eigenvalue of [P(s)]*p(s), where * denotes the conjugate transpose of a matrix. BooN is a Banach algebra under the norm II PII =
eij
suPwa[P(jw)].
Each frequency response matrix P in H(XjN determines an operator P: H 2N ~H2N, h=Pu. The algebra of such operators is denoted by HOIJN, and is a Banach algebra under the norm II P II H ooN = /I PII H~N The norm defined in this way coincides with the norm induced on H ooN by H 2 N , i.e., sup{UPull: u in H 2 N and lIull=l). A frequency response P in H~N is called stricti>' proper iff each of its components Pi} is strictly proper; the corresponding operator P in H~N is called strictly causal. The subalgebras of strictly proper or strictly causal elements in H~N or H ccN are denoted by H ON or HaN, respectively. Let K' be a (scalar) weighting function in H~. The weighted seminorm II P II H-' ~ II ",p II /IY.." is defined on Hoc. Observe that wcommutes with all operators in "XlV. so that 11·11 w is symmetric" and the multiplicative inequalities (4.1) are satisfied. B. A Decomposition Theorem
We shall be interested in frequency response matrices whose rate of approach to zero as s --+ 00 is comparable to that of a power of (1 +s ), and employ the following. Notation: For any integer 11.. (1 +s)nHccN denotes the set of functions P( s) with the property that (1 + s ) -" P( J) is in H oe N •
In the rest of Section VI.. plants will be decomposed into products PaPh of strictly causal and approximately invertible parts under the following assumption: a) PQ is a strictly causal operator in HON~ and b) Pb is in H ooN• The frequency response Ph has a minimal approximate right inverse Qb in (1 +s)rH~N; i.e., WPbQb is in H«JN and !Iw(I-Pb Qb)II H ooN =p,(Pb ) . Theorem 3: If i) det Pa(s):;60 for Re(s)~O and ii) there are constants c>O, p>O, and an integer k>O for which the inequality Is,ka[Pa(s)]~c is valid in the region Isl>p, Re(s)~O, then
At present there is much interest in the design of multivariable systems along classical lines, but there is little formal theory. Our next objective is to show that the theory outlined in Sections 111-V provides a suitable framework for multivariable design. Multivariable frequency responses will be viewed as elements of an n-dimensional version of the Hardy space HOIJ • Our approach will be to decompose the frequency response matrix into a product of nearly invertible and noninvert.. ible parts, and to design a feedback for each part sepa) Il(PbPa)=P,(Pb ) , and arately. The validity of approaches based on decomposib) PbPa has an optimal sequence of approximate right tions will be established in Theorem 3. The optimal sensiinverses Qm in H with frequency responses tivity scheme of Section V-Awill be obtained as a corollary. Another corollary will validate the common hypothesis Qm(.r)~ Pa-I(s )Qb(S)[m(s+m nm(s+n".r I that sensitivity can be made arbitrarily small if the plant is nearly invertible. Finally, a lower bound to sensitivity in where for any m 1,2,. · ., n; is a sufficiently large integer (given explicitly in Lemma 5.1). terms of the location of RHP zeros will be derived.
o"',
r T[
=
508
Jr·
The conclusions of Theorem 3 are now true by Lemma 5.1. Here 1I·ll a=II·ll b=II·U w, and Qm is the product
Theorem 3 is an application of Lemma 5.1. Qm will be constructed out of separate optimal sequences for Pu and Ph' both under the symmetric 11·11 w norm. First, however. a lemma will be proved. For any integer r>O, let denote the sequence in H ooN with "low-pass" frequency responses
r:»; IQbJ~.
Q.E.D. Corol/ary 6.1: The conclusion of the example of Section V-A is true.') That example is simply a special case of Theorem 3 for N=k= 1, and tlh =p; 1(I-w(,9)w- l ) in
J:
(1 +s)fH oo •
n= 1,2,···.
J:
Lemma 6.1: II 1:11 =1; is a weighted identity sequence.P i.e., for any r>O, II I II w ~ 0 as n -+ 00. Proof: First of all, II 1:11 = II I II sUPwln(jw+n)-II' = 1. Second, we have
-J:
III-J:ll w = suplw( j w)l. w
E;2
1-( . n
J(JJ+n
))r
sup Iw(jw)I+J1wll 1'-'1<6 sup 11- ( -.jc-r_n_)' 1 n
(6.1)
(6.2)
Iwl--8
8>0 being any number. Let (>0 be given. As wis in H
o,
c. Sensitivity Reduction in Nearly Invertible Multivariable Systems Consider the feedback scheme of equations (3.1)-(3.3). Suppose that the plant P1(s) is in H ON and satisfies the restrictions: det PI(S)~O for Re(s)~O, and Islka(P.(s)] >c in some region Isl>p, Re(s)~O, where c, p are constants and k is an integer. The sensitivity 1J~ IIJ-P.QII w is defined" as in Section V. Corollary 6.2:15 The sensitivity 111- p.Qn II w can be made smaller than any (>0 by a comparator Qn in H ON with frequency response
there is a 8>0 for which the first term in (6.2) is less than (/2; for fixed 8 there is an integer n for which the second term is less than (/2; i.e., lim,.-.oo II /-J;tI w =0. Q.E.D. Proofof Theorem 3: First, let us show that the sequence Qall with frequency responses QAtin @;; p a- lj IIk + 1'
n= 1,2,···
n being a (sufficiently large)'integer. Proof: The hypotheses of Theorem 3 are satisfied, with Pa =PI and Ph =/. Therefore, p.( PI) =0 and 11/(6.3) . PIQnllw~Oasn-+oc. Q.E.D.
is a right weighted inverting sequence in H ON for Pa • As det(Pa(s»+O, Pa- 1( s) is analytic in Re(s)~O. The inequality is Ik a[ s)];;a. c ensures that the functions defined by (6.3) are in H ON • Now, III-PtlQanllw=II/-Jnk+lllw ~O as n~ 00, by Lemma 6.1. Therefore, p.(Pa}=O and Qan is a right winvseq in H ON for Pa. Next, consider Pb. By hypothesis, Pb has a minimal approximate right inverse Qb in (1 +S)tH«JN. The frequency responses
es
m=I,2,·· .
(6.4)
lie in BooN, and determine operators Qbm in H oc N • Let us show that Qbm is optimal. Certainly, It [- PbQbm II w ~
D. Lower Bounds to Sensitivity
It might be expected that the singularity measure of an H ooN frequency response matrix would be limited by the location of its RHP zeros, and that the optimal sensitivity would be similarly limited. The following theorem shows this to be true. Let 11·11 w be any weighted seminorm on HXlV of the form II P II w = II ~.p II, w being (a scalar function) in H"t. For any plant P in H ocN , let the RHP zeros of P be the points Si in Re(s)~O i= 1,2,···, at which del[P(s;»)=O. Theorem 4: ,u( P) ~ sup {I ».( 5,)1: i = I ~ 2.... }.
p,(Pb ) . Now,
11/-PbQbm II w = 11(/-
PbQb)J~ + I-J~ II w
Proof: For any Q in H ocN let e« ([-PQ). For any RHP zero Si' let ~ be a unit vector in the nullspace of the E; 111- PbQb II wll J~+III + III-J~II w matrix P(s;)Q(s;). Let j: C~C be the function f(s>= by the triangle inequality and the multiplicative property ~*w(s )£(s )~. Since pes; )Q(Sj) =0, f(s;) =~*~w(s;) w( s.). of symmetric seminorms. As 11/- PbQbII w = p.( P,,) by hy- Now I(s) is an H function. and by the maximum modpothesis, and by Lemma 6.1 II J~+ III = 1 and lim m -.. QC 11/- ulus principle attains its maximum on the jw axis, i.e.. J~lIw~O. we obtain limm-+oolll-PbQbmllw~p.(Pb)' As Ij(jw)I~lw(s;)1 for some w. But for any transformation A this upper bound coincides with the lower bound obtained in Euclidean N-space, and any unit N-vector~ . a( A)~~* A~. above, lim; .... ooIlI-PbQbmllw=P(Pb), i.e., Qbm is a right The last assertion is established by the inequalities winvseq in HcoN for Ph.
o
=
13Forsimplicity we have considered inputs in HJ. here. but the conclu-
12For a symmetric weighting, IIA -J;'A fI ~ III-J: II w 1\ A II, so II AJ;AII Jf,"7'0 w~enev~r 1I.1-J:f1 w doe~; simi~ly for IIA -AJ:II w. Therefore, J~ IS a widseq Iff limll _
cc
lll - J" II w ==0.
sion is easily extended to HI', I
509
t~* A~12~1~·121 A~12 = IA~12
We shall be interested in the way in which closed-loop operators such as K 33 behave as functions of the open-loop =(A*A~)*~ ~IA*A~I'IEI operators P. PI' Q, and F. In particular, let us define two ~a2(A)I~12 =o2(A). functions mapping open-loop into closed-loop operators. Let IE: A 3s --+A" E(P'I PI' Q)=K 33 be the function relating We employ this fact to obtain K 33 to the model reference variables, and Ef : A~ --+A'I E/(P, F)=K 33 ~he funct!on. for the feedback vari~bl~s. p.( p);;. It Ell = sup a[ w( jw )E( jia )] ~ sup I f( jw )1 ~ Iw( s,)1· Any pair td, .Y) In <X, 2 satisfying (3.1) or (3.3) also satisfies w the equations The theorem follows. Q.E.D. y=IEf(P.f~)d=f.(P.PI'lQ)d. (7.2) Remark: Theorem 4 implies that no feedback can produce small sensitivity if a plant zero is present in any The c.l. (closed-loop) operators Kij. i.. )=2.3.. of the heavily weightedpart of the right half-plane. For "low-pass" feedback scheme (3.1) were introduced in Section III. and weightings such as k(s+k)-I, k>O, this means that if are well defined for the model referencescheme (3.3) under sensitivity is to be reduced, the only RHP zeros possibly the assumed equivalence. The model reference scheme allowed are those at very high complex frequencies. I~; I»k. shown in Fig. 3 has two extra nodes labeled 4 and 5. We shall avoid the lengthly but straightforward calculation of the remaining c.l. operators. and instead assume the followVII. EFFECTS OF PLANT UNCERTAINTY ON ing elementary properties of the model reference schem~: DISTURBANCE ATTENUATION , I'" define the operators K 44 =[I+(P-P.}QJ- and K 5S = Two opposing tendencies can be found in most feedback [J + Q( P - PI)] - I and let K be the sextuplet of operators systems. ·On the one hand, to the extent that feedback {K 44 , K S5 ' PI' Q. I}; the set {Kij};.j=2 of all c.l. operareduces sensitivity it reduces the need for plant identificators consists of algebraic combinations (i.e.. involving sums tion. On the other hand, the less information is available and products only of) the operators in K: furthermore about the plant, the less possible it is to select a feedback to reduce sensitivity. The balance between these tendencies K 32 = -QK 44 • establishes a maximum to the amount of tolerable plant . A. Stabilizing Feedbacks uncertainty and, equivalently, a minimum to the amount of identification needed. It is well known that any stable plant which is stabilized It can be argued that the search for such a minimum . by feedback is surrounded by a ball of "admissible" pershould be basic to the theory of adaptive systems. Actually, turbations which preserve closed-loop stability. Here.. the even the existence of such a minimum appears not to have radius of such a ball will be calculated.. and sensitivity will been stated. perhaps because plant uncertainty is so dif- be defined with respect to plant uncertainty within the ball. ficult to study in the WHK framework in the absence of Suppose a right seminorm 11·11, to be defined on B,. and the multiplicative properties (4.1), and because there is no recall that 1I·11,;;=t II· II. The true plant P will be supposed notion of optimality in the classical setup. to lie in a ball of uncertainty of radius 8;>0 in B, around Here, we would like to take a step in the direction of the nominal PI' b( PI' 8) ~ {P in B,: It P - Pili r ~ 8}. Since articulating these issues, by defining the tradeoff between II p- PIli ~ II p- PIli,. b( PI' 8) is a subset of the ball of minimal sensitivity and plant uncertainty and deducing its radius 8 in B. An operator K in A which depends on PEB, will be simpler properties. Sensitivity to disturbances will be considered in this section, and to plant uncertainty in the next. called bounded over a ball b(P., 8) iff K is in B and there is Let B, be a subspace of the causal operators Os· Con- a constant c~o with the property that II K II ~c for all P in sider the feedback (3.1) and model reference (3.3) schemes. b(P I , 6). A feedback or model reference scheme will be e.l. Suppose that some nominal plant PI in 0, is specified and (closed-loop) bounded on b(P1'l8 ) iff all its c.l. operators are (3.4) hold, so the two schemes are equivalent. The true bounded on b(P.,8). plant P in B, will differ from PI in general. Let K 33: Proposition 7. J: The following statements are equivalent ~-+~, K 33(d)=y be the operator in A mapping dis- on any ball h( PI~ 8). i) The feedback scheme is closed-loop turbances into outputs. Kn can be expressed in terms of F bounded; ii) Q is in 8 and K ~ [J +( P - PI )QI . 1 is ~
r.
44
[using (3.2a»),
K33 = ( I + PF) - I
or in terms of P, and Q [using 3.4b»)..
K33 =[J+ PQ(J- P1Q)-I]-1 = [( J- p.Q+ PQ)( J- P1Q) -1]-1
=(l-P,Q)[/+(P-PI)Q]-I.
bounded: iii) the model reference scheme is closed-loop bounded. Proof: We shall prove the sequence of implications. i)=>ii)==>iii)~i). If i) is true.. then K 44 is bounded by definition. Also" K 32 is bounded by definition. and therefore in B for all P in b(PI.8). But PI is in h(P,.8).. and KJ 2 = -Q when P=P,; therefore. Q is in D.. and ii) is t.rue. If ii) is true then K 55 is also bounded. as the equations (7.1) K S5 =[J+Q(P-P,)]-' =/-QK44( P - PI ) imply that 510
with the proviso that the sup is replaced by 00 if Q is not stabilizing. For any fixed nominal plant" PI in 8 s ' .,,( PI' 8) is a positive-real valued function of 8> O. Theorem 5: For any nominal plant PI in Bs ' the minimal sensitivity to plant uncertainty .,,( PI' 8) is a monotone nondecreasing function of 8 for 8~O; .,,( PI' 8) approaches the singularity measure p.( P,) as 8 ...... 0; and TI( P l , 8)= III II u.' for 8=" Pili r: Lemma 7.3: For any PI and Q in a; 1J( PI' Q; 8) is a monotone nondecreasing function of 8;;,0, finite for 8 in s. d contains the interval [0.11 QII -I]. For any 8 in [0, II Q II -I], the inequalities
IIK5511~1+IIQII·IIK44II·6,
for any P in b(P I . 6 }. Therefore, and by the assumed property of the Ki j , each c.l. operator K i j , i, }=2,·· ',,5. is an algebraic combination of the operators of K, which are bounded on b( PI' 6). It follows that each Kij is bounded there, and that (3.3) is c.l. bounded" i.e., iii) is true. If iii) is true then i) is true, as (3.1) and (3.3) are equivalent. Q.E.D. Again, only stable Q need be considered. The operators F in A sand Q in Bs will be called stabilizing for b( PI' B) iff (3.1) and (3.3), respectively, are c.l. bounded on b(P.,,8). The set of all Q in Hs stabilizing for b( PI" 8) will be denoted by Br ( PI' 8). For any PI and Q in 8,f' the set of real points 8 for which Q is stabilizing for b( PI" 8) will be denoted by a( PI' Q), and abbreviated to ~ when dependence on (PI' Q) is not of interest. The next lemma shows that any stable Q gives a c.l. bounded scheme (3.1), and is therefore stabilizing, for 8 small enough. Let PI and Q be in Bs ' Proposition 7.2: If 8 satisfies 0 ~ 8 < II Q II - I, then 8 is in ~ and for any P in b( PI' 8) the inequality
II{/+(P-P I )Q} -I U« 1- 8I1 QII ) - 1
(7.3)
~ is a half-open interval, [0,6 1 ) , Proof: Under the hypothesis, II(P-p.)QII
holds.
ur;
111- p.Qll w ~TI( PI' Q; 6)~ 11/- PIQII Ht'
+1I/-P.Qll w 6I1 Q II( I - 8 I1 QII ) · I and. if 11·11 w is symmetric, also the inequality
lJ(PI.Q;8)~II/-PIQllw(I-81IQII)·1
(7.S)
are satisfied. Proof of Lemma 7.3: The symbol i will denote a monotone nondecreasing function of 8~O. By definition of a, Q is stabilizing for any b( PI. 8) with 8 in a. so 1J( PI' Q; 6) is finite on ~. By Proposition 7.2~ d is an interval containing [0, "Q II - I]. 8 is a f function on L1 since it is a sup over sets b( PI' 8) which are nested and nondecreasing as 8 increases. From (7.1) we get
E( P, PI' Q)=(l- P1Q){ 1-( PI - P )Q[ 1+ (P- PdQ]
-I}.
(7.6 )
The triangle inequality and dominance condition 11"11 give
B. Sensitivity
11·11 w ~
IIIE( P. PI' Q)II JV ~ 1/ [ - P1Q II K"
Suppose that right and left seminorms are defined on ~~ as in Section V, and induce a weighted seminorm 11·11 w on B. For the plant P in any ball of uncertainty b(P 1, 8 ), and any feedback F in A s or comparator Q in Hs ' the sensitivity to disturbances under plant uncertainty of the equivalent schemes (3.1), (3.3) is defined to be
1J( PI' Q; 8)== sup
(7.4)
sup {Ilyll r/lld Il r: din 'j1r . lld II r =t=0}
PEb(P1,B)
-t-II(/-P1Q)(P1-P)Q[/+(P'-PJ)Q]
'-1.
(7.7)
For 8 in [0.11 QII - I]. the upper bound in (7.4) is obtained from (7.7) by (7.3) and the multiplicative property of norms. The lower bound is valid as PI is in b( P J8). and £(PI.PI~Q)=I-PIQ. If II·lI w is symmetric, the multiplicative property of symmetric seminorms applied to (7.1) gives
if Q is (stabilizing) in B.r(PI , 8 ), and l1(P , Q ; 8)=00 otherwise. For any stabilizing Q.
11(( P. Pt. Q)II w ~ 11/- P1QII w II {J+ (P- PI)Q} . 111
J
and (7.4) follows. Q.E.D . Proof of Theorem 5: From Lemma 7.3 and the inequality 11/- PIQ II ~y ~ p.( P it can be concluded that for any Q in by (7.2). (Recall, also, that IE( P. PI' Q) =: Ef { P. F).) D.", .,,( PI' Q: 8) is a t function with values in [JL( PI), ec]. T1( PI' Q, 8) is the smallest assured sensitivity for P in the As lJ(PI~8)=infQEB1J(PI~Q;c5) by definition. TJ(P is ball. We are interested in finding Q to minimize this the inf of a set of i functions with values in [1-£( PI' .X)]. sensitivity. Accordingly" we define the minimal sensitivity 10 Therefore, lJ( PI" a) is t and TI( PI ~ 8) ~ J.L( PI). Since 0 is in plant uncertainty to be
.,,(P.,Q;8)=
sup
111E(P,P1,Q)IIu-'
PEh( PI_ 8)
J
),
J.8)
16Again, the assumption that plant and feedback are both stricti" causal can be relaxed in Theorem 5. Lemma 5.3, etc, .
511
OS'
l1(Pt"O;~)
is in the set; and T1(PI'l ~)~TJ(Pl'O; ~)=
II1II w, where the last identity is true by (7.1). Let us show that lim.,.... o1J(P., 8)=IL(P,). By definition of Il(P 1) , for any £>0 there is a Q in 9 5 satisfying 11/-P,QfI w ~JL(PI )+{/2; as the RHS of (7.4) approaches 11/-P1Q II w as 8-+0" there is a 8>0 for which 71(P, Q; 8) ~JL(PI)+f. Since ( was arbitrary, and it has been shown tha t .,,( PI" 8);;;;:' p.( PI)' the conclusion follows. Finally, let us show that 1J(P.,ItPI II,)= ll l ll w. Suppose the contrary to be true. It has been shown that Tl( PI' II PI" ,)~ 11/11 w"· so TI( PI' II PIli r)~ II I II w' Therefore, there is a Q in Os for which IfE(P, PI' Q)II w < II I II w' Now, o is in b(P 1, II P,II ,) and, by (7.1), .11(PI,IfPlllr)~ IIE(O, PI' Q)II w =II J II w which is a contradiction. Q.E.D. Remark: Theorem 5 implies that whenever feedback reduces sensitivity for the nominal plant PI' there are points in the interval [0, II PIli] at which 11( PI' 8) increases, i.e., where "the less we know about P, the less able we are to construct a feedback to attenuate disturbances."
VIII.
Fig. 5.
versions of the problem" by allowing the plant invariant scheme to be multiplied by a constant R I' representing a desired nominal control law. A.
FILTERING OF PLANT UNCERTAINTY: INVARIANT SCHEMES
We now turn to the second problem outlined in the introduction, Section I-D. The plant P lies in a ball of uncertainty'? around some nominal value PI' and one object of using feedback is to shrink the size of the uncertainty. Of course, uncertainty can be reduced to zero by disconnecting the input (u in Fig. 4) from the system, but then PI is also transformed into zero. Clearly, the problem is trivial unless there is a normalization or constraint on the control law that transforms PI into a closed-loop system. We would prefer as far as possible to separate the reduction of uncertainty from the transformation of PI'l and therefore seek a definition of uncertainty which is independent of the eventual closed-loop system. . If PI were a real number, uncertainty could be normalized by specifying it as a percentage of the nominal value. This possibility is not open for noninvertible plants. Instead, we shall achieve a normalized definition of uncertainty by employing the device of a plant-invariant scheme, which leaves the nominal plant invariant while shrinking the ball of uncertainty. Such a scheme will be shown always to be realizable in the form of a model reference scheme. This device will also enable us to separate the design process into two consecutive stages: 1) reduction of uncertainty and 2) transformation of the nominal plant into a nominal closed-loop system (cr. the separation into estimation and control stages in Kalman filtering). A possible disadvantage to this approach is that the two stages may be dependent" and yield a suboptimal sensitivity. We shall try to get. the best of both worlds, and simultaneously formulate normalized and unnormalized 17D~artures of the true plant from the nominal can be interpreted as
uncertain in some applications; in others, they may simply represent known perturbations to be attenuated.
512
Plant Invariant Schemes
Any feedback arrangement of the type shown in Fig. 1, incorporating a plant P with a single accessible input, has an equivalent description in terms of the flowgraph of Fig. 4. This flowgraph is completely specified by the two additional operators U and F, which may be unstable even though the original arrangement is closed-loop stable. Note that Fig. 4 is an enlargement of Fig. 2 by a new branch, U., connected to a new node labeled 1. For simplicity, it will be assumed that d=O. The new feedback scheme equations are
y=Pv
(8.1a)
v= Uu- Fy
(8.Ib) in which PEAs, FEA s ' and" UEA are operators.. and u, o, and y are in ~. (Equations (8.1) represent an enlargement of (3.1) by the term Uu, under the constraint that d=O.) As P is strictly causal, (I+FP)-I exists in A, and for each u in ~, (8.1) have unique solutions for v and y in given by the equations
ex,
v=(I+FP)-IUU
(8.2a)
y=P(I+FP)-·Uu.
(8.2b)
Let K I2 and K I 3 be the operators mapping 'X into ~x, which satisfy, K I2( u ) = V, K I3( U) = y . By (8.2), K I2 =(l+FP)-IU and K 13 = P( I + FP )- lU. The full set of closed-loop operators of (8.1) consists of 6 /'. K 12 , K 13 K lI = I~ Kil == 0.. and the operators Kij defined in Section III, where i, j= 2, 3. A variant of the model-reference transformation of Sec.. tion III-A will be used. The flowgraph of Fig. 5 is described by the new model reference scheme equations '1
y==Pv
(8.3a)
v=Ru-Q(y-P1v)
(8.3b)
in which P, P, ED s ' REA, and u.. u, yE~. For any uE~X, (8.3) have unique solutions for v and y in ~., as P. PI" and Q are strictly causal. (Equations (8.3) can be viewed as an enlargement of (3.3) by the term Ru, and subject to the constraint that d=O.) The schemes (8.1) and (8.3) will be called equivalent iff t8In order to be physically realized, U would have to be approximated by a strictly causal operator. We prefer not to assume that U EAr as this simplifies the presentation. As U is followed by a strictly causal element, and has no feedback around it, there is no loss of generality.
every triple (u, v, y) in ~ 3 satisfying (8.1) satisfies (8.3) and vice versa. Equivalence will be established subject to the equations
(8.7b)
Q=F(J+P.F)-·
(8.4a)
F=Q(I-P.Q)-1
(8.4b)
d) For any R 1 EB, K is plant invariant (XR 1) iff R=R I +Or' where 0, EB is any right zero of PI' Proof' a) If (u, v, y) satisfies (~.l), then we have
R=(I+FP1)-·U
(8.5a)
(1- QP1 )v=( [- QP1 ) ( Uu- Fy)
U=(I+FP.)R.
(8.5b)
Equation (8.4) is a repetition of (3.4). If either of (8.5) holds then, clearly, both are true. For equivalent schemes, let E( P, PI' Q) be defined as in Section VII; Let K be the function K: A~xA-+A, K(P, p.,Q, R)=K I3 , which maps operators appearing in (8.3) into the c.1. (closed-loop) operator K 13 • Whenever all operators .except P are regarded as fixed, K(P. p.,Q, R) will be denoted by K(P). K(P) can be expressed in terms of the model-reference scheme operators, by the formula
which is obtained from the following sequence of equations. For any (u, e, )') in ~ 3 satisfying (8.3), we have
v=Ru-Q(P-PI)v [I + Q( P-
=(/- QP.)[(I+ FP.)Ru- Q(1- p.Q) -I r]
[by (8.5b) and (8.4b)]
=( 1- QP1)[(I- QP.) -I Ru-( /_QP. )-IQv] =Ru-Qu where the second last equation was obtained using the identity (I+FPt)=(I-QP,)-1 [see (3.5») and Property 2.1a. Hence, (u e, y) satisfies (8.3). The reverseassertion is proved similarly. It follows that (8.1) and (8.3) are equivalent. b) From (8.4), K(P,)=P1R; if (8.1) is closed-loop stable, then the c.l. operators K 32=F(1+PI F ) - 1 and /(12 =(I+FP)-Iu are stable, and equal Q and R. c) From (8.4) the following sequence of equations is obtained: t
K(P)-K(P.)=P[ I+Q(P- PI)] -I R- P.R
r, )] v =Ru
y=Pv=P[I+Q(P-PI)]-I Ru
[by (8.1b)]
={p-P 1[ J+Q(P-P t ) ] } [J+Q(P_p.)]-l R
(8.6b)
from which (8.7a) follows; (8.7b) is obtained by Proposiin which the inverse exists in A as Q( P- PI) is strictly tion 2.1a. causal. Since K 13 maps u into y, K 13 must coincide with the d) K is plant invariant (XR 1) iff K(PI)-P1R. =P1(R last operator of (8.6b), and (8.6a) is true. -R1)=O, i.e., R-R 1 =0,. Q.E.D. The set of c.l. operators of the model reference scheme Remark: Plant invariant schemes allow us to divide any (8.3) is defined as in the preceding Section VII, except that control-law synthesis into two stages: 1) filtering of plant K is augmented by the operator R. uncertainty P- PI and 2) design of a control law for a For any PI in A I ' K will be called (nominal) plant nominal plant PI' with the assurance at least that the invariant iff K(Pl)=PI; and, for any R 1 in A, plant in- filtering stage will improve the design. In general, there is variant (XR,) iff K(P.)=P,R •. From (8.4) it is clear that no "separation principle" to guarantee optimality of the K has these properties whenever R = J or R =R I' respec- division. tively. Either stage may come first. Therefore, in our theorems, An operator 0, EB is a right zero'" of PI iff p.O, =0. P can be interpreted either as a plant without controller, Theorem 7: for which a controller will be designed eventually; Of, as a a) Any feedback scheme (8.1) with (P, F, U) in A~ XA plant with controller attached, which requires additional is equivalent to a model reference scheme (8.3) with filtering only to the extent that P differs from PI. (P,P"Q,R) in A~XA, in which (F,U) and (P1,Q,R) are related by (8.4)-(8.5); and vice versa. If (8.4)-(5) hold, B. Stabilizing Feedbacks then we have the following. In the rest of Section VIII it will be assumed that: P and b) If P assumes the (nominal) value PI EA $' then K( PI) =PI R, and if the feedback scheme is closed-loop stable, PI belong to a subspace Or of the strongly causal operators then Q and R of the model reference scheme are stable B$' on which a right seminorm 11·11, is defined; P lies in a ball ·b( PI' B), defined as in Section VII-A, of what can be (although F and U may be unstable). c) The differences K(P)-K(P1) and P- PI are related interpreted either as uncertainty or perturbations; and the equivalence'conditions (8.4), (8.5) hold, so that the feedby the formulas back and model reference schemes (8.1), (8.3) are equivalent. K( P)-K(PI)=(J- P1Q)(P- PI){I+ Q( P- PI)} -I R Q in Asand R in A are sought which givelow sensitivity (8.7a) and maintain c.l. boundedness. In view of Theorem 7b), the assumption that Q is in B., and R in 8. i.e., that both 19More simplr, 0, is an operator whose range is in the nullspace of PI. The term u zero" is appropnate for a DOnned algebra are stable, can be made without loss of generality. 513
For any b( PI' a), the definitions of a bounded operator.. c.l, bounded scheme. and stabilizing Q were given in Section VII-A. The set B,(P I , B) of Q in s, stabilizing for b( PI" 8) was introduced. Proposition 8.1: Under the present hypotheses, Propositions 7.1 and 7.2, are valid for the feedback scheme (8.1) and model reference scheme (8.3), and the' set of Q in Hs stabilizing for b(Plt8) coincides with B.f(PI , 8). Proof: As R is in B, the set K augmented by R consists of operators bounded on b( PI' 8) iff the unaugmented set K consists of operators bounded on b( PI' 8). Therefore, {Kij)~.j=1 are bounded iff {Kij}tj=1 are bounded. The conclusion follows. Q.E.D.
(8.10) shows that sensruvmes JJ smaller than 1 can be achieved whenever ,,( PI ) < 1. In effect, the plant perturba.. lions supply their own weighting. This example has the alignment property.. as II CW II (' =
C. Sensitivity to Plant Perturbations or Uncertainty
by the multiplicative property of 11·11 v' and as
IICllwIlWII I ·
Proof of Lemma 8.2: v( PI' Q, J; ~) is a i function of 6, as it is a sup over sets b(P 1,8) which are nested and nondecreasing with aE~, and is 00 for "fi~. For any P in h(PI.8) and stabilizing Q, we have the inequalities ItE(P~ PI~Q)(P-P.)lIv8-1 E:; IIE( P ~
PI' Q)II w II P- P.II.6- 1
~ II E( P ~ PI ' Q) II
Suppose that a pair of seminorms (II· II w, \I · II.) is defined on the spaces (8,8,), respectively. We assume 11·11 HI to be a left seminorm, but leave open the possibility that II· II. is not a right seminorm, and assume instead that II· II. < 11·11,. i.e., 11.11 1 is dominated by the right seminorm 11·11,. A weighted seminorm 11·11 v is assumed to be defined on the set of products B .1;1,. and to have the multiplicative property. UCDU v -- lie II wll Dlt I for all C in Band D in H,. The pair (11·11 w' 11·11 I) will be called aligned iff there is a DEB, for which the preceding inequality is an equality for all C in B. For the plant P in any ball of uncertainty b(P I , B), and any (FEA J , UEA), or (QEBJ , REB), the sensitivity to plant perturbations (or uncertainty) of the equivalent schemes (8.1)-(8.3) is defined to be
J+'
(
8.12)
UP-PI It • ~11P-Pll1r~8
is obtained by taking the sup of both sides of (8.12) over all P in b( PI' B). If II·11 1 11·11 rand (11·11 w,II·11 r) is aligned there is an operator DEB, for which IIE(P.. Pl~Q)Dllv= IIE( P. PI" Q)II HI II DII,. The operator Po ~ PI +8D II DIIr- I is in b(P.,8) and IIE(Po• P.,8)(P-p.)lI v 8 - · = IIE(PI~ Pl,Q)llw~I£(P.). The sup in (8.9) must have the lower bound p.(PI)' and (8.11) follows. Q.E.D.
=
D.
Assumptions on R
As R=O gives 11=0. the attainment of a small sensitivity is trivial unless R is constrained. In many problems a target value of the c.l. operator K 13 is specified for some nominal value of the plant. By Theorem 7b), the target value can be attained iff it has the form P1R. We therefore make the ,,( PI' Q. R; 8)= sup {IIK( P) -K(PI)11 vB' -I} following assumption. peh(P•• 4) Assumption 1: An R I E B is given for which the equation (8.8) K(P,)=PIR. must be satisfied, i.e., K is plant invariant for Q stabilizing (i,e., in B.I(PI,B». and ,(PI' Q, R,; B)= 00 (XR I ) . J;ly Theorem 7d), R=R I +0" where 0, EB is any right zero of PI' There are now two variables to be optiotherwise. For any stabilizing Q. (8.7) gives the equation mized, Q and 0,. Their simultaneous optimization can be ,,(P•• Q,R;B)= sup {tlE(P,P.,Q)(P-P.)RII.,8- 1} . difficult, and we make the following simplifying assump.. PEh(P•• I) tion. Assumption 2: 0, =0. Assumption 2 may constrain the (8.9) class of allowable feedbacks and thereby give suboptimal The following lemma relates the disturbance and plant sensitivities. However, it is clear from (8.7b) that there is perturbation sensitivities, ." and II, to each other, and to the no such constraint if the condition 1I • II w -singularity measure J.L( p.), when R =/. Lemma 8.2: ,(PI' Q, I; B) is a monotone nondecreasing (p-P,)Or=O (8.13) function of 8;;.:0 satisfying the inequality is fulfilled. Equation (8.13) is fulfilled whenever N( PI) (nullspace of PI) is contained in N(P) for all P in b( Pl' 8); for then, for any uE'X., either O,u=O, or O,uEN(P.> and and if 11·11. = 11·11 r and the pair (II· II w, II· II ,) is aligned then so O,uEN(P). In either case. (P-PI)O,u=O.. i.e.• (8.13) is true. If N( PI") is trivial. then, of course. (8.13) is fulfilled. .,(P,.Q, J; B):;;'J.L{P I ) . (8.11) For example.. N( PI) is trivial for any nonzero PI in H o\ Remark: 11·11 u can coincide with the principal norm 11·11. because functions analytic and not identically zero in Re(s);;'O have at most a countable number of Re(s)~O For example.. if W is in H" II W II = I, IICII w ~ IICWII, and zeros. UDU 1 ~ HW-1Dlt, then the principal norm has the multiAs R in (8.6) is now fixed, cR can be absorbed into the weighting for some constant ~ in (0. 1] by replacing II· II v plicative property IICDll v--IICll wIlDtI. and may be used as the 11·11 v norm. Even though JI·II provides no weighting, with the new seminorm llCll , ~ AlleRll v ' and similarly ,,(PI.Q,I;B)~,,(PI.Q;8);
(8.10)
514
for 11·11 r- Without loss of generality, we can therefore make the following assumption. Assumption 3: R I. We prefer to absorb R rather than to show it explicitly, as this approach reduces the number of variablesand allows sensitivity to be related to weighted invertibility.
=
E.
Minimal Sensitivity
For any PI in B" and 8>0, the minimal sensitivity to plant perturbations is defined to be
,(Pt,a)= inf {,(P J,Q,I;8)} (lEB
= inf
sup
{lIE(P,PI,Q)(P- P I)II .,8- 1}
QeB PEb(P.. I>
provided the last sup is replaced by
00
for nonstabilizing
Q. For fixed PI' ,(PI , 6) is a function of, 8~O which represents the dependence of perturbation sensitivity on plant uncertainty. Theorem 8: For any nominal plant PI in B the minimal sensitivity to plant perturbations ·p(P I , 8) is" a monotone nondecreasing function of 8;;.0. ,(PI' 8) satisfies the upper bound conditions ,,( PI' 8) E; 1J(PJ,8) and lim,-.o,(P•• 6)
Q in B
Remark: The ratio II Pili v II PIli; I is a measure of the amount by which the II-II u norm weighs down the nominal plant. Provided norms are used for which the weighting is not excessive, in fact whenever the ratio exceeds p.( PI)' there must be points in the interval [0, II PI II,] at which any increase in plant uncertainty causes a worsening of minimal sensitivity. ApPENDIX
I
Proofof Proposition 2. J,' a) If(J+PQ)-' exists in B, let R ~ /_Q(/+PQ)-lp. Now" (/+QP)R=I.. because
(/+QP)R=/- Q( I+PQ)-1 P+QP_QPQ(/+ PQ) -I P
= 1- Q( 1+ PQ) - •P + Q[[_ PQ([ + PQ)- I] P
=1- Q( 1+ PQ)
-I P+
Similarly.. R(I+QP)=I, so R is the inverse of (/+QP) in B. The required formula is obtained by multiplying both sides of the equation (I + PQ)P=P( 1+ QP) by (I + PQ)- I on the left, and by (I+QP)-1 on the right. b) If P is in Rand P -I in B, there is a contradiction: any F in B belongs to R as F= PP -IF, so R is not a proper subspace and not a radical. c) Let R ~ ( J + P ) - I and observe that R = J- PR. By the triangle inequality. II R II <; I + II P 1111 R II and, as II P II < 1, IIRIIE;(I-IIPII)-'. Q.E.D. Proof of Proposition 3,5,' Since 11(1 - PQ)nll = I when Q=O, the infimum a satisfies 0< 1. Suppose 0=1= I; then there is a Q in Os for which 1I([-PQ)nn ~ a l < I. It will now be shown that given any (>0, there is a QI in B.f for which II(J-PQI)nu«, and so the proposition is true. Let n be any integer for which an
II
UNSTABLE PLANTS: REMARKS
Consider the problem of input-output stabilizing an unstable plant Po in H:Q by identity feedback, given that the a prior; information about P consists of jJ( jw) and the number N + of Re(s );;'0 poles of P. By Nyquist's criterion; uncertainty as to N + translates into uncertaintyj" as to the number of unstable poles of (J + Po) - I. N + must not be underestimated if stability is to be assured. However, it is impossible to be sure that N+ has not been underestimated from purely input-output measurements. For example, let Sit j= 1,2" . · -n, be any finite set of frequencies, and Pm(s;) a set of n measurements of Po(s) of tolerance e, i.e., IPm(s;)-Po(s)I<£. It is impossible to deduce N+ from the measurements, as it is always possible to find a dipole, (s + a) (s + a + 6) - I, with 6 >0 so small that multiplication of Po(s) by the dipole changes Po(s;) by less than (, but increases N + by 1. In our particular setting, it appears that input-output stabilization cannot be accomplished using solely input-output data. The implication is that some information concerning internal structure is essential.. and that stabilization is not a legitimate problem for a purely input-output theory. On the other hand. desensitization can be achieved using input-output data. If P is in H and p( t) satisfies appropriate restrictions on smoothness and convergence to 0 as t ...... 00" then p{ jw) has a finite modulus of continuity, and p can be located in a e..ball of H~ by a finite set of measurements [14). This is sufficient for the purpose of desensitization. as sensitivity depends continuously on p in HtXJ (see Theorems 5 and 7).
o'
Q( J + PQ)-I P=I.
lOA
515
more complete discussion isin Zames and El-Sakkary (114).
SYNOPSIS
REFERENCES
The main results of this paper are the Theorems 1-7. Section II: Spaces of frequency responses and algebras of input-output mappings are defined, and their relevant properties summarized. Section III: A decomposition principle 'is derived. The disturbance attenuation problem is separated into two independent stages: stabilization, followed by desensitization of a stable system. The second stage is a model reference scheme. Section III': Some constraints on sensitivity norms are displayed. It is shown that the induced operator norm is useless as a measure of sensitivity. Section IV: The concepts of a weighted seminorrn, approximate inverse, and measure of singularity are introduced and illustrated by examples. Section V: The plant is assumed to be stable and known precisely. Sensitivity is defined. Approximate invertibility is shown to be a necessary and sufficient condition for sensitivity reduction in Theorem 2, and optimal sensitivity is shown to be equal to the measure of singularity. An example of sensitivity minimization is solved in Section V-A. Unstable plants are discussed in Section V-B. Identity and inverting sequences are introduced in Section V-C, and a lemma on products of inverting sequences is proved. Section VI: Devoted to multivariable systems. In Theorem 3, an optimal sequence of compensators is derived for a plant factorable into a product of nearly invertible and noninvertible factors. Corollary 6.2 specializes this result to a single-input single-output plant with a RHP zero. Corollary 6.2 gives conditions under which the sensitivity of multivariable systems without RHP zeros can be made arbitrarily small. Theorem 4 shows that sensitivity can never be made small if there are zeros in any heavily weighted part of the RHP. Section VII: The plant is assumed to lie in a ball of uncertainty around a nominal value. Feedbacks stabilizing over a ball are.defined. Optimal sensitivity is shown to be a monotone nondecreasing function of uncertain ty in Theorem 5, and various bounds are obtained. Section VIII: Problem 2 is formulated, again in terms of an equivalence between feedback and model reference schemes, this time subject to a plant invariance property, in Theorem 6. Sensitivity to plant perturbations is defined, bounded, and optimal sensitivity is shown to be a monotone nondecreasing function of plant uncertainty in Theorem 7.
[1] H. W. Bode, Network Analysis and Feedback Amplifier Design. Princeton, NJ: Van Nostrand, 1945. [2] M. Horowitz, Synthesis of Feedback Systems. New York: Academic, 1963. (3) G. Zames, "Nonlinear operators- Cascading inversion, and feedback" M.I.T., R.L.E., Quart. P.R., vol. 53, pp. 93-107, Apr. 1959. [4] ' - , "Nonlinear operators for system analysis," Res. Lab. Electron., M.I.T., Tech. Rep. 370, Sept. 1960. [5] - , "functional analysis applied to nonlinear feedback systems," IEEE Trans. Circuit Theory, vol. CT-IO, pp. 392-404, ~t. 1963. [6] C. A. Desoer, "Nonlinear distortion in feedback amplifiers," IRE Trans. Circuit Theory, vol. CT-9, pp. 2-6, Mar. 1962. [7] - , "Perturbation in the 1/0 map of a nonlinear feedback system caused by large plant perturbation," J. Franklin Inst., vol, 306, pp. 225-235, Sept. 1978. [8] 1. B. Cruz, Jr. and W. R. Perkins, "A new approach to the sensitivity problem in multivariable feedback system design," IEEE Trans. Automat. Contr., vol. AC-9, PI? 216-223, 1964. (9} W. A. Porter and C. L. Zahm, "BasIC concepts in system theory," System Eng. Lab., Univ. of Michigan, Tech. Rep. 33, 1969. (10] R. M. Desantis and W. A. Porter, "A generalized Nyquist plot and its use in sensitivity analysis," Int. J. Syst. Sci.. vol, 5- 12, pp. 1143-1153, 1974.
[II] 1. C. Willems, The Analysis of Feedback Systems. Cambridge, MA: M.I.T., 1971. [12] G. Zames, "Feedback hierarchies and complexity:' in Proc. IEEE Conj. Decision Contr., Dec. 1976, addenda. [13] - - , "On the metric complexity of causal linear systems, e-entropy and e-dimensionfor continuous time," IEEE Trans. Automat. Contr .. vol. AC-12, pp. 222-230, Apr. 1979. [14) - - , "Realizability conditions for nonlinear feedback systems," IEEE Trans. Circuit Theory, vol. CT-ll, pp. 186-194, June 1964. [15] R. G. Douglas, Banach Algebra Techniques in Operator Theory. New York: Academic, 1972. [16] B. A. Francis and W. M. Wonham, "The internal model principle for linear multivariable regulators," J. Appl. Math. Optimiz., vol. 2, pp. 170-194, 1975. [11] D. M. Bensoussan, "High-gain feedback and sensitivity," Ph.D. dissertation, Dep. Elec. Eng., McGill Univ., to appear. [18] A. K. El-Sakkary, "The gap metric for unstable systems," Ph.D. dissertation, Dep. Elee. Eng., McGill Univ.; also in G. Zames and A. K. EI-Sakkary, PrO'. is« Allerton Con[., Oct. 1980. [19] M. A. Naimark, Normed Rings. Groningen: Noordhooff, 1964. [20] A. Feintuch, "Strong Causality Conditions and Causal Invertibility," SIAM J. Contr. Optimiz., vol. 18, pp. 317-324, May 1980. [21) C. A. Desoer and W. S. Chao, "Feedback interconnection of lumped linear time invariant systems," J. Franklin Inst., vol, 300. pp. 335- 3S I, 1975. [22) W. Rudin, Functional Analysis. New York: McGraw Hill, 1973. [23} G. Zames, "Feedback and optimal sensitivity: Model reference transformations, weighted semmorms, and approximate inverses," in Proc. 17th Allerton Conf., Oct. 1979, pp. 744- 752.
ACKNOWLEDGMENT
The author thanks C. A. Desoer for many useful suggestions concerning the draft of this paper. 516
Index
BOO control, 124, 147,495 B 2 optimization,82 Absolute stability, 199 Absolutely stable asymptotically, 201 Accessibility, 444 strong, 381 Action risk, 181, 186 Adaptivecontrol, 423, 485, 487 stochastic, 182 Adaptivecontrol algorithm globally convergent, 487 Adaptivemodel reference control, 485 Adjoint differentialequation, 219 Aizerman conjecture, 197 Algorithm globally convergent adaptive control, 487 projection, 490 recursive stochastic,459 shooting, 219 stochastic approximation, 466 Amplifier feedback, 25,26, 31,47, 51 Amplitudo margin, 45 Analysis non-smooth, 114 Approach behavorial, 240 innovation, 168 RMS-error, 82 Approximation algorithm stochastic,466 Approximation in policy space, 122 ArgumentPrinciple, 2 Asymptotically absolutely stable, 201 Asymptotically autonomous, 316 Asymptotically stable exponential, 161 uniformly, 161 Attainability, 381 Attenuation,47, 49
disturbance, 389, 498 plant uncertainty, 499 Augmentederror, 485 Autonomous asymptotically, 316 Available storage, 389, 397 Averaging theory,457 Behavorialapproach, 240 Bode plot, 46 Bode relation, 46 Boundness linear,488 uniform, 488 Brownianmotion, 92 Calculus of variations, 124, 160, 223 Canonicalform Lur'c, 276 Canonical structure theorem, 254 Caratheodory method, 113 Causality, 121 Certaintyequivalence, 182, 485 Characteristic ideal cutoff, 46 Circle criterion, 2, 233, 283 Circle theorem, 296, 300 Closed-looptransfer function, 107 Completelycontrollable, 154 uniformly, 156 Completelyobservable, 251 uniformly, 158 Conditionalinvariance, 321 Conditionalstability, 1 Conic sector theorem, 283 Conicity, 290, 298 Control BOO, 495 adaptive, 423, 485, 487 adaptivemodel reference,485 dual, 182, 183, 190 geometricnonlinear, 340 linear optimal, 143
517
minimumvariance,423, 426 model predictive, 124 noninteracting, 321 optimal, 149 stochasticadaptive, 182 stochasticoptimal, 181 Control algorithm globally convergent adaptive, 487 Control function, 150 Control theory nonlinear, 364 Controllability, 147, 250 local, 364 nonlinear, 367, 441, 443 Controllability Grammian, 147 Controllability of group manifold, 353 Controllability subspace,321, 325 Controllable, 154 locally,444 locally weakly, 444, 448 uniformlycompletely, 156 weakly, 444 Controllablesubspace,323 Controlledinvariance, 321 Convergent adaptivecontrol algorithm globally, 487 Coset space, 359 Criterion circle, 2, 233, 283 Nyquist, 197,283 Popov, 198,414 Welerstrass, 128 Criterionfunction, 116 Curve integral, 370 Cybernetics, 81 Damping nonlinear,424 Decoupling disturbance, 321 output, 329
Index
Describing function, 2 Design LQG, 495 nonlinear feedback, 442 Wiener-Hopf, 495 Differentiable manifold, 363 Differential equation Riccati, 147, 159 Differential game, 113 nonzero-sum, 147 zero-sum, 147, 495 Differential geometry, 342 Dissipation rate, 403 Dissipativo, 392, 397 Dissipative dynamic system, 389 lossless, 402 Dissipative system, 391 Disturbance attenuation, 389,498 Disturbance decoupling, 321 Dual control, 182, 183, 190 Duality relation, 252 Duality theorem, 151 Dynamic game stochastic, 181 Dynamic program, 113 Dynamic programming, 115 Dynamic system lossless dissipative, 402 Dynamic team stochastic, 181 Dynamical equation, 244 Dynamical system, 243 dissipative, 389 Equation adjoint differential, 219 dynamical, 244 Euler-Lagrange, 124 Hamilton-Jacobi, 113, 149 Hamilton-Jacobi-Bellman, 113 Hamilton-Jacobi-Isaacs, 114 matrix Riccati, 149 Riccati, 148 Riccati differential, 147, 159 Wiener-Hopf, 81,167,175 Equation error identification method, 468 Equilibrium state, 150 Equivalence certainty, 182, 485 topological, 246 Ergodic theory, 92 Error augmented, 485 . swapping, 485 Error identification method equation, 468 Error normalization, 486 Escape time finite, 159 Euler-Lagrange equation, 124 Excitation
persistency of, 310 Exponential asymptotically stable, 161 Extended space, 283 Factorization spectrum, 86 Feed forward, 437 Feedback, 31 negative, 31 output, 148 positive, 31 state, 148 Feedback amplifier, 25, 26, 31, 47, 51 shunt, 62 Feedback design nonlinear, 442 Feedback principle, 151 Feedback-sensitivity minimization, 503 Filter Kalman, 168 lagging, 94 lead, 103 linear, 83, 169 long-lag, 90 Wiener, 169 Filtering, 81, 88, 167 nonlinear, 168 Finite escape time, 159 Form Lur'e canonical, 276 Formula phase-area, 45 Function closed-loop transfer, 107 control, 150 describing, 2 ideal loop transfer, 46 Liapunov, 312,314 loop transfer, 1, 2 loss, 152 Lyapunov, 207, 236,407,463 open loop transfer, 107 sensitivity, 45 storage, 389, 392, 397 Functioning criterion, 116 Gain, 107 small loop, 289 Gain stability, 32 Gain theorem small loop, 283 Game differential, 113 nonzero-sum differential, 147 stochastic dynamic, 181 zero-sum differential, 147, 495 Geometric nonlinear control, 340 Geometric theory, 442 Geometry
518
differential, 342 sub-Riemannian, 342 Globally convergent adaptive control algorithm, 487 Grammian controllability, 147 Group manifold, 346 controllability of, 353 Hamilton-Jacobi equation, 113, 149 Hamilton-Jacobi theory, 113 Hamilton-Jacobi-Bellman equation, 113 Hamilton-Jacobi-Isaacs equation, 114 Hamiltonian, 154 Hamiltonian system, 129, 130 Hankel matrix, 240 High-pass, 73 Ideal cutoff characteristic, 46 Ideal loop transfer function, 46 Identification recursive, 457 Identification method equation error, 468 Impulse-response matrix, 247 Index performance, 152 stability, 40 Indistinguishable strongly, 450 Innovation approach, 168 Innovation sequence, 81 Input, 243 Input -output stability, 285 Input-to-state stability, 389 Instability theorem, 318 Integral curve, 370 Integral submanifold, 446 Interconnected system, 403 Invariance condition, 321 controlled, 321 Invariance principle, 309 Investigation (probing) risk, 181, 186 Irreducible, 239 Irreducible realization, 242, 249 Kalman filter, 168 Kalman- Yakubovich-Popov Lemma, 198,233 Lagging filter, 94 Lead filter, 103 Least square model, 427 Least squares recursive, 490 Lemma Kalman-Yakubovich-Popov, 198, 233 positive-real, 198, 233 Liapunov function, 312, 314 Lie bracket, 363
Index
Lie theory, 342 Limit point positive, 312 Limit set positive, 312 Linear boundness, 488 Linear filter, 83 Linear filtering, 169 Linear matrix inequalities-LMS, 233 Linear optimalcontrol, 143 Local controllability, 364 Locally controllable, 444 Locally observable, 448 Locally weaklycontrollable, 444, 448 Locally weaklyminimal,454 Long-lagfilter, 90 Loop gain small, 289 Loop gain theorem small, 283 Loop shaping,2 Loop transfer.function, 1, 2 Loss function, 152 Lossless dissipative dynamicsystem, 402 Low-pass, 73 LQG (Linear-Quadratic-Gaussian), 147 LQG design,495 LQR (Linear-Quadratic-Regulator), 147 Lur'e canonicalform, 276 Lur'e method,236 Lyapunov methodof, 160 Lyapunov function, 207, 236, 407, 463 Manifold differentiable, 363 group, 346 Margin amplitude, 45 phase, 45 Matrix Hankel, 240 impulse-response, 247 transfer-function, 249 transition, 150 Matrix Riccati equation, 149 Maximumprinciple, 124, 128, 130 Memoryless nonlinearity, 299 Method Caratheodory, 113 equationerror identification, 468 root locus, 107, 109 Wiener-Hopf,82 Method of Lur'e, 236 Method of successive approximation, 123 Minimal locally weakly, 454 Minimalrealization, 396 Minimal sensitivity, 515 Minimumphase, 45
Minimumvariance control,423, 426 Model least square,427 Model predictive control, 124 Model reduction, 240 Model referencecontrol adaptive, 485 Motion Brownian, 92 Multipleloop root locus, 111 Negative feedback, 31 Neutralproblem, 182 Noise white, 169 Nominalperformance problem,496 Non-linearity sector,296 Non-minimum phase, 45, 107 Non-smooth analysis, 114 Nonanticipatory,244 Noninteracting control, 321 Nonlinearcontrol geometric, 340 Nonlinearcontroltheory, 364 Nonlinearcontrollability, 367, 441, 443 Nonlineardamping, 424 Nonlinearfeedbackdesign,442 Nonlinearfiltering, 168 Nonlinearobservability, 442, 443 Nonlinearsystem, 199,454 Nonlinearity memoryless, 299 Nonminimum phase system,437 Nonzero-sum differential game, 147 Normalization error,486 Nyquistcriterion, 197, 283 Nyquistplot, 111 Nyquiststabilitydiagram,57 Observability, 147,250, 356 nonlinear, 442, 443 Observable completely, 251 locally, 448 uniformlycompletely, 158 weakly, 448 Observable realization, 358 Open loop transferfunction, 107 Operatortheorem positive,283 Optimalcontrol, 149 Hoo,124 linear, 143 stochastic, 181 Optimalpolicy, 116 Optimalregulation, 127 Optimality, 121 Optimization
519
H2,82 Optimumprogramming, 221 Orthogonal projection, 169 Output, 150,243 Outputdecoupling, 329 Output feedback, 148
Passivity, 233, 292 Passivity theorem,2 Performance index, 152 Performance problem nominal,496 Performance robustness, 496 Persistency of excitation, 310 Phase, 47, 49 minimum, 45 non-minimum, 45, 107 Phase margin,45 Phase shift, 52 Phase space, 245 Phase system nonminimum, 437 Phase-areaformula, 45 Plant, 150 Plant uncertainty attenuation, 499 Plot Bode, 46 Nyquist, 111 Policy, 116 optimal, 116 Pontryaginmaximum principle, 124 Popov condition, 301 Popovcriterion, 198,414 Positivefeedback, 31 Positivelimit point, 312 Positivelimit set, 312 Positiveoperatortheorem,283 Positive-real Lemma, 198, 233 Prediction, 81, 88, 167, 169 Predictive control model, 124 Principle argument, 2 feedback, 151 invariance, 309 maximum, 124, 128, 130 Pontryaginmaximum, 124 separation, 182 Principleof optimality, 117 Probe investigation risk, 181 Probing, 181 Problem neutral, 182 nominalperformance, 496 regulator, 149 Programming dynamic, 115 optimum, 221 Projection
Index
orthogonal, 169 Projection algorithm, 490 Qualitative control theory, 46 Rate dissipation, 403 Reachability, 364 Reachable, 156, 398 Realization, 248, 395 irreducible, 242, 249 minimal, 396 observable, 358 Realization theory, 240 Recursive identification, 457 Recursive least squares, 490 Recursive stochastic algorithm, 459 Reduction model, 240 sensitivity, 497 Reference control adaptive model, 485 Regeneration, 25 Regulation optimal, 127 Regulator self-tuning, 423, 425, 458, 471 Regulator problem, 149 Relation Bode, 46 duality, 252 Required supply, 389 Resolvent, 267 Riccati differential equation, 147, 159 Riccati equation, 148 Risk action, 181, 186 investigation (probing), 181, 186 RMS-error approach, 82 Robustness performance, 496 stability, 496 Root locus multiple loop, 111 single loop, 110 Root locus method, 107, 109 Sampling, 278 Second method of Lyapunov, 160, 197 Sector non-linearity, 296 Sector theorem conic, 283 Self-tuning regulator, 423, 425, 458, 471 Sensitivity, 511 minimal, 515 Sensitivity function, 45 Sensitivity reduction, 497 Separation principle, 182 Sequence innovation, 81 Servomechanism, 81
Set positive limit, 312 Shooting algorithm, 219 Shunt feedback amplifier, 62 Singing, 1, 47 Single loop root locus, 110 Single-loop system, 107 Small gain theorem, 2 Small loop gain, 289 theorem, 283 Smoothing, 81 Solution viscosity, 113 Space coset, 359 extended, 283 phase, 245 state, 243 Space system state, 239 Spectral factorization, 81 Spectrum factorization, 86 Spirule, 109 Stability absolute, 199 conditional, 1 gain, 32 input-output, 285 input-to-state, 389 Stability in the large, 197, 309 Stability index, 40 Stability robustness, 496 Stable, 407 asymptotically absolutely, 201 exponential asymptotically, 161 uniformly asymptotically, 161 State, 150 equilibrium, 150 State feedback, 148 State space, 243 State space system, 239 State transition, 173 State variable, 115 Statistics sufficient, 182 Stoepest ascent, 219, 221 Stochastic adaptive control, 182 Stochastic algorithm recursive, 459 Stochastic approximation algorithm, 466 Stochastic dynamic game, 181 Stochastic dynamic team, 181 Stochastic optimal control, 181 Storage available, 389, 397 Storage function, 389, 392, 397 Strong accessibility, 381 Strongly indistinguishable, 450 Structure theorem canonical, 254 Sub-Riemannian geometry, 342
520
Submanifold integral, 446 Subspace controllability, 321, 325 controllable, 323 Sufficient statistics, 182 Supply required, 389 Swapping error, 485 System dissipative, 391 dissipative dynamical, 389 dynamical, 243 Hamiltonian, 129, 130 interconnected, 403 lossless dissipative dynamic, 402 nonlinear, 199, 454 nonminimum phase, 437 single-loop, 107 state space, 239 Team stochastic dynamic, 181 Theorem canonical structure, 254 circle, 296, 300 conic sector, 283 duality, 151 instability, 318 passivity, 2 positive operator, 283 small gain, 2 small loop gain, 283 Theory averaging, 457 duality, 151 ergodic, 92 geometric, 442 Hamilton-Jacobi, 113 Lio, 342 nonlinear control, 364 qualitative control, 46 realization, 240 Wiener-Kolmogorov, 167 Topological equivalence, 246 Transfer function closed-loop, 107 open loop, 107 Transfer-function matrix, 249 Transition state, 173 Transition matrix, 150 Uncertainty attenuation plant, 499 Uniform boundness, 488 Uniformly asymptotically stable, 161 Uniformly completely controllable, 156 Uniformly completely observable, 158
Index
Variable state, 115 Variance control minimum,423, 426 Viscositysolution, 113 Weaklycontrollable,444
locally,444, 448 Weaklyminimal locally, 454 Weaklyobservable, 448 Weierstrass criterion, 128 White noise, 169 Wiener filter, 169 Wiener-Hopfdesign, 495
521
Wiener-Hopfequation, 81, 167, 175 Wiener-Hopfmethod, 82 Wiener-Kolmogorov theory, 167 Zero dynamics,322 Zero-sumdifferential game, 147, 495
About the Editor
Tamer Basar received the B.S.E.E. from Robert College, Istanbul, Turkey in 1969 and the M.S., M.Phil., and Ph.D. degrees in engineering and applied science from Yale University during 1970-1972. After stints at HarvardUniversity, Marmara Research Institute (Gebze, Turkey), and Bogazici University (Istanbul), he joined the University of Illinois at Urbana-Champaign (UIUC) in 1981, where he is currently the Fredric G. and Elizabeth H. Nearing Professor of Electrical and Computer Engineering and Director of the Decision and Control Laboratory. Dr.Basarhas authoredor coauthoredover 150journalarticles andbookchapters,andalsonumerousconference publications in the general areas of optimal,robust,and adaptive control,largescale and decentralized systems and control, dynamic games, stochastic control, estimation theory, stochastic processes, information theory, and mathematical economics. He is coauthor of Dynamic Noncooperative Game Theory (Academic Press, 1982;secondedition 1995; the latest editionin the SIAMSeries in Classics in Applied Mathematics, 1999) and H'
Control and Related Minimax Design Problems (Birkhauser,
1991; second edition 1995); he has also edited or coedited severalvolumesoncontrolanddynamicgames.Hiscurrentresearch interests are robust nonlinear and adaptive control, control of communication networks, risk-sensitive estimationand control, and robust identification. Dr. Basar has played activeroles in many scientific organizationsand,in particular, IEEEandIFAC (International Federation of Automatic Control). Currently, he is thepresidentof the IEEE ControlSystemsSociety, the deputyeditor-in-chief of the IFAC journal Automatica, the managing editorof the Annals of the International Society of DynamicGames, a member of the IEEE Publication Board, and member of editorial boards of various journals. A member of the National Academy of Engineering and a Fellow of IEEE, some recent awards and recognitions Dr. Basar has received are the Medal of Science of Turkey (1993), Distinguished MemberAward (1993) and Axelby OutstandingPaper Award (1995) of the IEEE ControlSystems Society, and NearingDistinguished Professorship at UIDC (1998).
523
