CIRCUITS SYSTEMSAND SIGNAL PROCESSING
VOL. I8, NO. 3, 1999, P'P. 241-267
LINEAR SYSTEMS IN A SATURATED MODE AND CONVERGENCE AS GAIN BECOMES LARGE OF ASYMPTOTICALLY STABLE EQUILIBRIUM POINTS OF NEURAL NETS* B r u c e D. C a l v e r t I
Abstract. We study solutions of the "linear system in a saturated mode" (M)
x' c T x + c - OID, X .
We show that a trajectory is in a constant face of the cube D ~ on some interval (0, d]. We answer a question about comparing the two systems: (M) and (H)
Cu'= Tv+c-R-lu,
v=GO~u).
As ~. --+ oc, limits of v corresponding to asymptotically stable equilibrium points of (H) are asymptotically stable equilibrium points of (M), and the converse is also tree. We study the assumptions to see which are required and which may be weakened.
1. Introduction In 1984 Hopfield [5] considered neural nets modeled by the ordinary differential equation (ODE) (H), in components Ciu I = ~
Tijvj + ci - u i / R i , J vi = g i ( X u i ) , 1 < i < n ,
(1) (2)
where gi is strictly increasing and g i ( x ) --+ -4-1 as x - + • In 1989 Li, Michel, and Porod [7] introduced the systems they called "linear systems in a saturated mode" and in particular the system o f interest (M), mentioned in the abstract and defined in Section 2 on preliminaries. * Received November 17, 1998; revised December 2, 1998. iDepartment of Mathematics,Universityof Auckland,PrivateBag 92019, Auckland,New Zealand. E-mail: calvert~math, auckland, ac. nz
242
CALVERT
The first purpose of this paper is to use the monotone operator theory of [4] and [10] to help provide a setting for the concepts of the authors of [7]. This gives the existence of solutions of (M). We give regularity results on the solution of (M) being in some face on an interval of time. These give the existence of solutions of (M) on [0, c~) independently of the monotone operator theory. It was seen in [7] how (M) was simpler than (H) but quite strongly related. The connections were pointed out in Remark 3.5, Remark 4.7, and Example 6.3 of [7]. In Remark 4.7 it was hypothesized that there was a 1-to- 1 correspondence between the sets of asymptotically stable equilibrium points for the two systems (H) and (M) via the energy functionals. The second purpose of this paper is to show this hypothesis to be correct, and to investigate the apparently stringent conditions required for it to hold. In 1993 and 1995 Vidyasagar [12], [14] analyzed the equilibrium points o f ( H ) as )~ --~ ~ , allowing T to be a nonlinear mapping. He also studied their asymptotic stability. We use these results of Vidyasagar. We note the relevance, to mean field annealing mentioned in Watta and Hassoun [16]. More recently, Vidyasagar has developed these ideas further in [13] and [15] and considered applications. Abe and Gee [2], Abe [1], Liu and Michel [8], and Perfetti [11] have all been concerned with linear systems in a saturated mode.
2. Preliminaries We recall some of the notation of [7]. Let D n = [ - 1 , 1] n. Let T be a real n x n matrix, i.e., T ~ L ( R n, R) ans let c 6 R, replacing the symbol I from [7]. Let ID, (x) = 0 if x ~ D n and be e~ if x r D n. We recall from [4] the following. Let OID n denote the subgradient of I v n, i.e,, if w ~ IRn, then w E O I o , (x) iff x ~ D n and for all y ~ D n we have the inner product ( w , x - y ) > 0. We describe w as being an outer normal to D n at x. The system (M) is defined by (M)
(3)
x ' E r x + c - OID, x .
This may be referred to as a linear system in a saturated mode. It is a special case of (14) in Section 2.1. We define a solution to be a Lipschitz continuous function satisfying this a.e. In Section 2.1 an existence and uniqueness theory is given. Another one follows from Section 3.1. We now define the systems ( L H ) and ( L M ) . For i = 1. . . . . n let gi : R -+ ( - 1 , 1) be C 1 with g i ( x ) ~ 4-1 as x --+ • and having a C 1 inverse. Define G : Nn _+ Rn by (G (x))i = gi (xi) for x 6 R n and all i. Let C/ 6 (0, c~) for each i, and define C : IRn --+ IRn by C ( x ) i = C i x i for x E ]~n and all i. Likewise let Ri E (0, c~) for each i give R : ]Rn --~ ]Rn. Let (H) be the equations (1) and (2) indexed by the parameter ~ 6 (0, e~). In vector form, (H)
Cu' = Tv + cv = G()~u).
R-lu
,
(4) (5)
LINEAR SYSTEMSIN A SATURATEDMODE 243
We can write this in terms of the variable v ~ ( - 1 , 1) n as the system (LH): (LH)
v' = H ( v ) ( T v + c - S ( v ) ) ,
(6)
where S = )~-IR-IG-t
and H ( v ) = )~C -1
[( G - i f ( v ) ]-1 E L(IR n, IRn)
for v 6 ( - 1 , 1) n, with ( G - 1 ) ' ( v ) being the derivative of G - i at v. We could also write this in terms of the variable t7 = Lu. We define ( L M ) as (LM)
v' = T v + c - S ( v ) .
(7)
To make explicit a fixed ), we may denote these by (LM,z), etc. We will use the following two assumptions of [7], labeled 4.1 and 4.2, in Section 4. A s s u m p t i o n 4.1 of [7]. (1) T is symmetric, (2) Any principal submatrix is nonsingular. Let A = { - 1, 0, 1}'. For ~ 6 A, let C ( ~ ) = {x ~ R n : ]xi[ < 1 if ~i : 0,
Xi :
~ if ~i # 0} .
For now take ~ with at least one component zero and at least one nonzero. Choose m, and cr ~ Symm(n) with ~o(i) = 0 iff 1 < i < m. We say ~ 6 Am. Write Ta,a = [Tcr(i),cr(j)]l<_i,j< m
(8)
Tb,b = [Ta(i),tr(j)]m
(9)
Za,b = [Za(i),o'(j)]l
(10)
"
(11)
The letters a and b replace 1 and I I used in [7]. For r/ 6 R n we set r/a = [rhr(i)] l<_i<_m' and so on. Note that we may use the preceding decomposition even if ~ has all components 0, i.e., m is n, so Ta,a becomes T, or if m is zero, Tb, b becomes T. Under Assumption 4.1, for 0 < m < n and ~ ~ Am, define x~ by
(x )o =-r;-2 (ro,bb+co) (X~)b = ~b 9
For m = n we define x~ = - T - lc, and for m = O, we define x~ = ~.
244
CALVERT
We use the notation x 9 y to denote the componentwise product of two elements x and y of R k, i,e., (x 9 Y)i = xiYi for each i ~ {1. . . . . k}. Write ( x , y ) for the standard inner product. We use {x, y) for the space spanned by the vectors x and y. We denote the line segment {Lx + (1 - L)y : )~ 6 [0, 1]} by [x, Y]. We write rain(x) for x 6 R k to mean the minimum of all k components xi ofx. Define r~, for ~ ~ A, ~ r 0, to be min((Tx~ + C)b * ~b). We write {el : 1 < i < k} for the usual basis in R k. We denote the closure and interior of a subset X by cl(X)and int(X). Assumption 4.2 of [7]. Assumption 4.1 (2) holds and for 0 < m _< n, and ~ ~ Am, I(x~)a(i)i 7~ 1 for all i < m .
In Remark 4.7 of [7], the question is posed as to the relation between the asymptotically stable equilibrium points of (M) and (Lt4) as L -+ e~. The researchers suggest using the energy functions defined as E M ( x ) = - - ~1( x , T x ) - (x, c) + lDn(X )
e x ( x ) = - ~ (t x ,
(1.2)
n
r x ) - (x, c) + (;~)-~ ~_. e ? ~
fox, gfl
.
(13)
i=1
Remark. The systems ( L M ) and (LH) have the same asymptotically stable equilibrium points, as noted in Remark 3.5 of [7]. This follows from Lyapunov's stability theorem, see, e.g., [3], using Ex.
2.1. Solutions o f (M).
We can resolve the existence and the uniqueness problems of (M) by requiring a solution a.e, (except of a set of measure zero) with a Lipschitz requirement on the solution. We use the theory of semigroups of type co, following [10], as follows. Let B : D n --+ N n have Lipschitz constant co. The system (M) will be a particular case of (M-n) (for M-nonlinear) as defined as (M-n)
x ' C B x - OIo~x .
(14)
We define a solution to be Lipschitz with (M-n) holding a.e. We talk of the solution u starting at u0 if u(0) = uo. We recall that a function A from IRn to subsets of •n is said to be M(co) if for all x and A x ' ~ A x , and for all y and A y ' c A y , ( A x ' - A y ' , x - y ) > - c o Ilx - y]t 2 9
(t5)
Let D ( A ) , for the domain of A, denote [x : A ( x ) r We regard A as its graph, and call A maximal M(co) if it cannot be properly included in another M(co) function. We write A ~ for the element of minimum norm in A x .
LINEAR SYSTEMS IN A SATURATEDMODE
245
We note that B + OlD, is maximal M(w), essentially from Corollary 2.6 of [4]. We use the following existence and uniqueness result, Theorem 3.1 of [4], which was developed for o~ = 0. The case o) > 0 follows from [10]. T h e o r e m 1. Let A be maximal M(co) in a real Hilbert space H. For each uo c D ( A ) there is a unique u : [0, ~ ) -+ H such that (1) u(t) E D ( A ) f o r a l l t
> O,
(2) u & locally Lipschitz on [0, cx~), and exp(-wt)
d-~t t <_ [[A~
a.e. (t),
(3) u'(t) + A u ( t ) ~ 0 a.e. (t), and
(4) u(0) = uo. Furthermore,
(5) u has a right derivative,
d+u
-dt and t ~
A~
+ A~
= 0 forall t ,
is continuous on the right,
(6) the function t ~-+ ]lA~
e x p ( - w t ) is decreasing, and 2T du exists and is continuous at continuity points o f l[A ~u ( t ) II, and
(7)
if u and u* are solutions o f ( l ) through (4), then ] l u ( t ) - u*(t) H < e x p ( w t ) I l u ( o ) - u*(O)ll f o r all t ~ [0, e~).
It seems helpful to define Ba(u) for u ~ D n as follows. For each i, (Bau)i = (Bu)i if - 1 < ui < 1, (Bau)i = min((Bu)i, 0) if ui = 1, and (Bu)i = m a x ( ( B u ) i , 0) if ui = - 1 . Then equation (M-n) states that x ' ( t ) = Bax(t) 9
Consequently equation (M) states that x' (t) = ( T + C)aX(t) ,
where T + c is the mapping x ~-~ T ( x ) + c.
(16)
246 CALVERT Corollary 1. Let B : D n --~ ]~n have Lipschitz constant a~. For uo E D n there is a unique u : [0, ~ ) -~ D n such that (1) u is Lipschitz on [0, c~), u'(t) = Bau(t) a.e. (t), and
(2) u(0) = u0. Furthermore,
(3) exp(-wt)
< [lBauoH a.e. (t),
(4) u has a right derivative, d+u
and t ~
= Bau(t) for all t, dt Bau(t) is continuous on the right,
(5) the function t ~
[[Bau(t)H exp(-wt) is decreasing, and ~tt exists and is continuous at continuity points of IInau ( t ) II,
(6) if u and u* are solutions of (1) through (4), then l l u ( t ) - u*Ct)l I < exp(wt)]lu(O)- u*
Proof We let A = - B + 0Io~, which we noted is maximal M(w). Note that D ( A ) = Dno For any x ~ D ( A ) we have - A ~ = Ba(x). Because {Bay : v D n } is bounded, the locally Lipschitz solution is Lipschitz. Q
3. Regularity of u 3. I. Regularity on the right.
Let n ~ {1, 2 . . . . }. Let u : [0, c~) -+ D n be the solution of (M), as opposed to (M-n), starting at uo ~ D n. We show in Theorem 2 that there is ~ ~ A and d > 0 such that u(t) ~ C(~) for all t ~ (0, d]. L e m m a 1. Let uo ~ R n, n >__1, and (Uo)n = 1. Let c ~ R n and T c L(R n, Nn). Write P1 f o r the orthogonal projection with nullspace (en). Let y be the solution
of y' = T y + c,
y(O) = uo o
(17)
Let u be the solution of u' = P I ( T u + c),
u(O) = uo .
~18)
LINEAR SYSTEMS IN A SATURATEDMODE
247
Suppose that Yn is strictly increasing on some interval [0, d], d > O. There is an integer k > O, and F > O, G > O, ak > O, and d > 0 such that on (0, d], ( T y ( t ) + c)n = aict k + ' "
,
(19)
Ilu(t) - y(t)II < Gt Ic+l,
(20)
and (Tu(t) +C)n > F t k 9
(21)
R e m a r k We can put the conclusion another way. Let K = {x : Xn < 1}. Then the solution of u'6Tu+c-OIx, u(O)=uo (22) has u(t)n = 1 on some [0, d], d > 0. Also the preceding inequalities hold. P r o o f of L e m m a L
For some k >_ 0 we have, by analyticity, y'n(t) = akt k + . . .
with ak > 0. Hence on some (0, d] we have y'n(t) > (aic/2)t k
(23)
and also y~ (t ) < (2aic)tic, giving yn(t)-
l < 2 aic tic+1. k+l
(24)
With notation corresponding to ~ = en (and a the identity), write Xa = (xl . . . . . xn-1), Xb = Xn, and let Xa = {x : xn = 0}. For Ta,a see (8), etc. We define a map H taking C([0, d], Xa) to itself, d to be chosen. Let Xa C([0, d], Xa). For all t, let H(xa)(t) = (UO)a -t-
fo
(Ta,aXa(S) + Ta,bl -t- ca)ds 9
Define t?
{Xa e C([O,d],Xa) : IlXa(t)- ya(t)fl < Gt Ic+l for all t e [0, d]] .
(25) We claim that given G, H maps B to itself if d is small. Let Xa ~ B. For t c [0, d],
Ifor
!tHxa(t) - ya(t)ll --- [
-
=
(Ta,aXa(S) + Ta,bl) - (Ta,aya(s) + Ta,bYb(S))ds
fFra,all
Ic+I + lira bll 2aic
sic+ 1 ds ( b y ( 2 4 ) , ( 2 5 ) )
k+I 2aic ~ t lc+2 !1Ta,a It G + IITa,b II ~ I k + 2
< Gt Ic+x ( i f d is small).
'
248
CALVERT
Hence the solution u of (18) satisfies [lUa(t) - ya(t)[I < Gt k+l on some [0, d],
d > 0.
(26)
This and (24) give (20). We now show that (Tu(t) + c)b >_ F t k on [0, d]: ( r u ( t ) + C)b = Tb,aUa(t) q- Tb,bl q- Cb = Tb,aya(t) + Tb,bUb(t) + Cb -t- Tb,a(Ua(t) -- ya(t)) + Tb,b(1 -- yb(t))
>
-Ilrb,oll ot k+l
IITb, ll 2aktk+l k+l
-
> Ft k for some F > 0 if d is small.
..B
T h e o r e m 2. Let n ~ {1, 2 , . . . }. Let u :[0, co) ---> D n be a soIutionof(M). Then there are ~ ~ A a n d d > 0 such that u(t) ~ C ( ~ ) f o r all t ~ (0, dl. R e m a r k , The proof does not assume the existence of a solution (M) and yields this existence without appeal to the theory of Section 2.1. P r o o f L e t u 0 = u(0) ~ C ( ~ ) , w h e r e ~ ~ Am. I f m = n t h e n ~ = 0, and u(t) ~ C(0) on some [0, d], d > 0, by continuity. Suppose that 0 _< m < n. By renaming, x = (0 . . . . . 0, 1 . . . . . 1) with n - m ones and m zeros. Let x ~ be the solution of (x~
= T x 0 + c,
x~
= uo.
(27)
Either x~ ~ D n on some [d, 0], d > 0, or, after renaming coordinates, there are k(0) E {0, 1. . . . }, F > 0, G > 0, and d > 0 such that on [0, d],
(rx~
+ c) >_ vt
,
(28)
n
and and
,Tx~
)
< G t k(~ for all i ~ { m + l
. . . . . n}.
(29)
i 9
0
t
These inequalities hold because we consider the power series for each (x}) (t) = bit h(i) + . . . and take k(0) to be one of the smallest h(i) for which bi > 0. Suppose the latter case is true, i.e., (28) and (29) hold. For each j e {1. . . . . . n}, let Pj be the orthogonal projection in 1Rn with nullspace ( e n + l - j , . . . , e,~}. Take x 1 to be the solution of ( x l f = P I ( T x 1 + c), xl(0) =- uo 9 (30) By Lemma 1, there are F > 0, G > 0, and d > 0 such that on [0, d], (x ~ - x~
< Gt k(~
(31)
and
(rxl(t) + c),, >__F? (~ .
(32)
LINEAR SYSTEMS IN ASATURATED MODE 249
By (29) and (31) for i 6 {m + 1 . . . . . n},
(Tx1(t) + c)i < Ti (xl - x~ (t) + (Tx~
+ c)i
< Gt k(~
(33)
for s o m e G > 0, d > 0, and all t 6 [0, d]. Either x 1(t) 6 D n on s o m e [0, d], d > 0, which happens automatically if m = n - I, or after renaming, we take k(1) ~ {0, 1 . . . } , F > 0, G > 0, and d > 0 such that on [0, d],
(Txl(t) + C)n_l > Ft k(1),
(34)
and
Txl(t) + c] >_ Gt k(1) for all i 6 {m + 1 / i
n - 1}
(35)
By (33) with i = n - 1, and (34), k(1) > k(0). S u p p o s e that p is such that 2 < p < n - m and for all q < p , we do not have x q (t) ~ D n on any [0, d], d > 0, where
Pq (Tx q + e ) ,
(xq)1=
xq(O)= uo.
S u p p o s e instead that for some F > 0, G > 0, d > 0, and nondecreasing
(36)
k(j) for
j<_q, (Txq(t) + C)n_j > Vt k(j) for all j ~ {0 . . . . . q},
(37)
and
(Txq(t)
+
C)i < Gt k(q) for all i ~ {m + ] . . . . . n - q} ,
for all t 6 [0, d]. We define
(38)
xP by
(xP) ' = Pp(Tx p +c),
xP(O) = uo.
EitherxP(t) ~ D n on some [0, d], d > 0, o r b y L e m m a 1, there are F > 0, G > 0, and d > 0 such that on [0, d],
(xP
Xp-l) (t) < Gt k(p-1)+l
(39)
(TxP(t) + c)n_(p_l) > Ft k(e-1) .
(40)
--
B y (37), and (39) there are F > 0 and d > 0 such that for all j < p - 1,
> Ft k(j) - Gt k(p-1)+l (F from (37)) > Ft k(j) because k(j) < k ( p - 1 ) . F o r / 6 { m + 1. . . . . n - p +
t},
<_ Gt k(p-1)
by (38), (39)) .
250
CALVERT
Either xP(t) ~ D n on some [0, d], d > 0, or else we may take k(p) so that after renaming,
( T x P ( t ) + C)n_ p :> Ftk(P) ( T x P ( t ) + c)i < Gt k(p) for all i 6 {m + 1. . . . . n - p } . This gives k(p) > k ( p - 1). If p = n - m, then xP(t) ~ D n on some [0, d], d > 0. Hence for some p c {0. . . . . n - m}, xP(t) E O n on some [0, d], d > Oi By analyticity, each xe(t)i is either less than 1 on some (0, d] or else equal to i on some (0, d], d > 0. Consequently there exists ~ E A with xP(t) ~ C(~) on some (0, d], d > 0. Also x p is the solution of (M) on [0, d]: 5 R e m a r k . If u is a solution of (M), then there is a finite or countable set B C ]~, 0 6 B, such that for each b c B there is a C(~) containing u(t) for all t 6 (b, c), where c 6 (B f) (b, c~)) tO {oo} is such that (b, c) contains no etement o f B. For n < 3 we see in Subsection 3 2 that we can say more.
3.2. Regularity on the left. L e t n 6 { 1 , 2 , 3 } . L e t u : [0, co) -+ D n be a solution of (M). We show in Theorem 3 that for to > 0 there are ~ ~ A and d < 0 such that u(t) ~ C(~) for all t 6 [to + d, to), We break the proof up into preliminary parts.
Question: Does this result hold for all n? Proposition 1. L e t n c {1, 2}. Let u : [b, c~) ~ D n be a solution of(M), where b < O. T h e r e a r e ~ ~ A a n d d < O s u c h t h a t u ( t ) ~ C ( ~ ) f o r a l l t c [d, 0). Proof. If uo is in the interior of D n, then so is u(t) on [d, O) for d small by continuity. Suppose that u(0) = uo is the boundary. We may suppose by renaming that no component of uo is equal to - 1. Suppose that Tuo + e = 0. Writing v(t) = u(t) - uo,
d d t Ilvl12 = 2(u - u0, u')~, = 2 ((u - uo)a, (Tu + C)a)~m = 2 (va, Tav)~m > - 2 j[TJ1110112 . Therefore jlo(t)ji exp(llTII t) is increasing, and hence u(t) = uo on [b, 0], which
gives the result in this case. Thus we will suppose that Tuo + c ~ O. Let n = 1. We could derive a contradiction by supposing that u(t) is neither in C(0) nor in C(1) on any [d, 0). More simply, assume that u0 = 1 and T u o + c ~ Or Hence Tuo + c > 0 because u(t) --+ 1 as t --+ 0: If u(d) = I for some d < 0,
LINEAR SYSTEMS IN A SATURATED MODE
251
then u(t) = 1 on [d, 0]. Otherwise u(t) < 1 on [b, 0), and u(t) ~ C(O) on some
[d, 0). Let n = 2. (A) Let uo 6 C((1, 0)). Note that (Tuo + c)l > O, because u(t) -+ uo. (1) Suppose that (Tuo + c)1 > 0. Either u(t) ~ C((0, 0)) for all small t < 0, or u(d)l = 1 for some small d < 0, giving u(t) ~ C((1, 0)) for all small t < 0. (2) Suppose that (Tuo + c) 1 = 0. Then by renaming, suppose that (Tuo + c)2 > 0. We suppose that (Tu + c)2 > 0 for u within E1 ofuo, and for t 6 [b, 0], u(t) is within 61 ofuo. (a) Suppose that (Tu + c)l > 0 on {uo - ke2 : k > 0}. Then there is a solution in B(uo, 61) of v(t)l=l,
v~=(Tv+c)2,
v(O)=uo
on some [bl, 0], bl < 0, which is a solution of (M). For b2 small, v(bi)2 < u(t)2 < (uo)2 for t 6 (b2, 0). Suppose that u(d)a = 1 for some d E (b2, 0). Then by uniqueness, u(t) = v(t) E C((1, 0)) on [d, 0). Otherwise u(t)l < 1 on (b2, 0). (b) Suppose that (Tu + c)1 < 0 on { u o - ke2 : k > 0}, Then (Tu + c)1 < 0 on K ( 6 ) = {u : lUl - 11 < 6 ( ( u 0 ) 2 - u2)}
for E > 0, small. We cannot have ul(d) = 1 for any d 6 (b, 0) because then u(t) ~ K(E) for t < d near d. Thus u(t) 6 C((0, 0)) on (b, 0). (B) Let u0 E C((1, 1)). Note that (Tuo + c)l > 0 and (Tuo + c) 2 > 0 and they are not both 0. (1) Let both be > 0. Now we have the following solutions: (a) v(t) = (1, 1) for all t > 0, (b) w(t)l = 1 for all t > 0, w(0)z < 1, w(T1)2 = 1, (c) x(t)2 = 1 for all t > 0, x(0)l < 1, x(T2)l = 1. Suppose that u(t)l > x(0)l and u(t)2 > w(0)2 on [b, 0]. If u(d) = uo for some d < 0, then u(t) = uo on [d, 0]. Otherwise if u(d)l = 1 for some d < 0 then u(t) ~ C((1, 0)) on [d, 0). Otherwise if u(d)2 = 1 for some d < 0, then u(t) ~ C((O, 1)) on [d, 0). Otherwise u(t) ~ C((0, 0)) on [b, 0). (2) Let just one be 0, say (Tuo + c)z > 0 and (Tuo + C)l = 0. The proof of (A)(2) holds if we can show that if u(d)z = 1 for d < 0, and small, then u(d) = (l, 1). B u t i f u ( d ) 2 = 1, d < 1 small, and u(d)l < 1, then u(t)2 = 1 on [d, 0]. But then (Tu0 + c) 1 = 0 implies that u (t) 1 converges exponentially to 1, contradicting u (0) 1 = 1. []
252
CALVERT
T h e o r e m 3. Let n ~ {I, 2, 3}. Let u : [b, oo) -+ D n be a solution of(M), where b < O. Thereare~ ~ A a n d d < Osuchthatu(t) ~ C ( ~ ) f o r a l l t ~ [d, 0).
Proof By Proposition 1 we may take n = 3. Write uo for u(0). We may assume that (U0)l = 1. Suppose that u(t)l = 1 for t < 0 near 0. Then we are done by Proposition 1. (A) Let uo 6 C((1, 0, 0)). By making b small we assume that lu(t)2[ < 1 and ]u(t)3J < 1 on [b, 0]. (1) (Tuo + c)1 > 0. Either u(t) ~ C((0, 0, 0)) for all small t, or u(d)l = 1 for some d < 0 such that (Tu(t) + c)1 > 0 for all t ~ [d, 0]. In the latter case, we are done by Proposition 1. (2) (Tuo + C)l = 0. Note that u is differentiable at 0. (a) (Tu + c)1 = 0 on C((1, 0, 0)). We proceed as in (1). (b) (Tu + c ) 1 = 0 on a line u o + (s C u o + (e2, e3). Suppose that {e, m } is an orthonormal basis of (e2, e3) and (Tu + c)1 > 0 if u 6 {uo + (s + k m : k>0}.
1. (Tuo + c, m) < 0. Then for t ~ [b, 0), if b < 0 is small, we have (u(t) - uo, m) > 0 on [b, 0), and so if u(d)l = 1, then u(t)l = 1 on [d, 0), because if e < 0, u(e) = 1, and u(t)l < 1 on a nonempty interval (e, f ) , then the fact that u'(t)l > 0 for t > e near e gives a contradiction.
2. (Tuo + c, m) > 0. Then for t c [b, 0), if b < 0 is small, we have (u(t) - u0, m) < 0 on [b, 0). Hence u(t)l < 1 on (b, 0), for otherwise u(d)l = 1 for some smallest d, contradicting u](t) < 0 for t < d, t near d.
3. (Tuo + c, m) = 0. We may assume that (Tuo + c, e) > O, noting that Tuo+c#O. a. (Tu + c, m) < 0 on {uo - ke : k > 0}. Then this holds on an open cone K(~) with vertex at u0, containing {u0 - ks : k 9 0}. Now for t < 0, and small, because u is differentiable at 0, u(t) ~ K(e), so that (Tu (t)+c, m) < 0 and (u (t), m) is strictly decreasing on [d, 0] if d < 0 is small. Suppose that u(f)~ = 1 for some f ~ [d, 0). As in 1. we have a contradiction if u leaves C((1, 0, 0)) on If, 0). Otherwise u(t) ~ C((0, 0, 0)) on [d, 0).
h. (Tu + c, m) 9 0 on {uo - kg : k 9 0}. Then this holds on an open cone K(E) with vertex at uo. Then (u(t), m) is strictly increasing on [d, 0] if d < 0 is small. Suppose that u ( f ) l = 1 for some f ~ [d, 0). This gives a contradiction as in 2. above.
LINEAR SYSTEMS IN A SATURATEDMODE
253
c. ( T u + c, m) = 0 on {uo - kg 9 k > 0}. Hence (T/, m) = 0. (i)
Supposethatu(d)l = 1, ( u ( d ) - u o , m) > 0, f o r s o m e d < 0. Suppose that
w' = (0, ( T w + r
( T w + c)3),
w(d) = u(d) .
Writing we(t) = ( w ( t ) - uo, g.) and win(t) = (w(t) - u o , m),
w ~ ( t ) = ( T w ( t ) + c, m) = ( T ( w ( t ) - uo), m) = (we(t)Tg. + w m ( t ) T m , m) = Wm(t)(Tm, m) . Hence Wm (t) is always positive. Therefore ( T w ( t ) + c)1 > 0 and w is a solution of(M). Hence u(t) = w(t) when lwz(t)l < I and ]w3(t)l < 1. Consequently w = u on [d, 0], contradicting Wm (0) r O. (ii) Suppose u(d)1 = 1, (u(d) - uo, m) < 0, for s o m e d < 0. We obtain a contradiction as in 2. (iii) Suppose that u(d)l = 1, (u(d) - uo, m) = 0, for some d < 0. Then on [u(d), uo], the line segment between u(d) and uo, we have Tu + c 6 (e), and so there is a solution v of (M) starting at u(d) in uo + (e), and by uniqueness, u(t) ~ uo + (g.) on
[d, 0]. (B) Let uo E C((1,0, 1)). Suppose that lu2(t)l < 1 on [b, 0]. (1) (Tuo + c)1 > 0 and (Tuo + c)3 > 0. Note that this is similar to Proposition I(B)(1). Suppose that (Tu (t) + c ) 1 > 0 and ( T u ( t ) + c)3 > 0 on [b, 0]. If u(d)3 = 1, for some d c [b, 0), then u(t)3 = 1 on [d, 0], and the result follows from the case n = 2. Otherwise if u(d) c C((1, 0, 0)) for some d ~ [b, 0), then u(t)a = 1 on [d, 0], and again the result follows from the case n = 2. Otherwise u(t) ~ C((O, O, 0))on [b, 0). (2) (Tuo + c)1 = 0 and (Tuo + c)3 > 0 (or vice versa). If u(d)3 = 1, for some small d c [b, 0) then u(t)3 = 1 on [d, 0], and the result follows from the case n = 2. Otherwise on [d, 0], for d < 0 small, we have u3(t) strictly increasing. The result follows by the case (A). This may be seen by replacing D 3 by K = {x : Ix1[ < 1} and noting that
u'(t) ~ Tu(t) + c - Olxu a.e. on [d, 0 ] . (3) (Tuo + C)l = (Tuo + c)3 = 0. We may suppose that (Tuo + c)2 > O.
254
CALVERT
(a) Suppose that (Tu + c)3 > 0 on {u0 - ke2 : k > 0}. Hence this holds on an open cone K(E) with vertex uo, containing {u0 - ke2 : k > 0}. Note that u(t) ~ K(E) on [d, 0), for d < 0 and small, by differenfiability. We proceed as in (B)(2).
(b) (Tu + c)3
< 0 on {uo - kE2 : k > 0}. Hence this holds on an open cone K(r with vertex uo containing {u~ - k e z : k > 0}. Because u(t) e K(r on [d, 0) for d < 0 and small, this contradicts u 3 (d) < 1 and u3 (0) = 1.
(c)
By symmetry we need not consider (Tuo + c)I > 0 or (Tuo + c)1 < 0 on {uo - ke2 : k > 0}, and hence we assume that (Tu + C)l = 0 and (Tu + c)3 = 0 on {u0 - ke2 : k > 0}. Write P for the nearest point projection on u0 + (e2). Let v(t) = u(t) Pu(t); then d__l iiv(t)l[ 2 = (v(t), Tu(t) + c - O[D3U ) dt 2 > (v(t), Tv(t)) , and so Ilv(t)ll exp(Kt) is increasing for some K. Hence u(t) is in u0 + (ez) for all t c [d, 0), or u(t) is never in uo + (ez). Because u(0) uo + (e2), we have u(t) ~ C((1, 0, 1)) on [d, 0].
(C) Let uo = (I, 1, 1). We may have at least two of {(Tuo + c)i " 1 < i < 3} that are strictly positive, or just one. (1) (Tuo + c)2 > 0 and (Tuo + e)3 > 0. We proceed as in (B)(2) above. If u(d)3 = 1, for some small d e Eb, 0), then u(t)3 = 1 on [d, 0], and the result follows from the case n = 2. The same is true if u(d)2 = 1, for some small d c [b, 0). Otherwise on [d, 0], for d < 0 small, we have u(t)3 and u(t)2 strictly increasing. The result follows by (A). This may be seen by replacing D 3 by K = {x : Ixl[ < 1}. (2) (Tuo + c)2 = 0 and (Tuo + c)3 > 0. As in (1), if u(d)3 = 1, for some small d ~ [b, 0), then u (03 = 1 on [d, 0] by uniqueness, and the result follows from the case n = 2. Otherwise on [d; 0], for d < 0 small, we have u3(t) strictly increasing. The result follows by (B), This may be seen by replacing D 3 by K = {x : Ixzl <_ 1 and Ix1[ < ! }. []
3.3. Regularity.
T h e o r e m 4. Let n r {1, 2, 3}, Let u : [0, ~ ) --~ D'* be a solution of(M). There is an increasing sequence tk --~ ~ , tl = O, or a finite sequence with first term 0 and last term c~, such that for all k there is a ~ such that u(t) e C ( ~ ) f o r all t E (tk, tk+l).
LINEAR SYSTEMS IN A SATURATEDMODE
255
Proof. The proof follows by the results on regularity on the left and on the right. []
E x a m p l e 1. There exist n < 3, T, and c such that a solution of (M) is not eventually in any C(~) and is nondifferentiable at infinitely many tn. We give (a) a periodic example in R 2 and (b) a nonperiodic example in R 3. (a) Let n = 2, c = 0, and
where/z 6 (0, 1). Note that ifx2 = - 1 , then (Tx)2 = Xl - / z . Hence a trajectory leaves x2 = - 1 at (/z, - 1 ) and forms a spiral r = e m until it hits Xl = 1. Then it continues vertically to (1,/z). The orbit is invariant under rotation by zr/4. (b) Let n = 3 and let Q3 be the positive octant. Shift the origin to consider
u ~ ~ Tu
-
OIQ3U,
where T =
--e + 2m
--1/-v/3-- m
1/~/-3-m
- e + 2m
-1/4'3-
m
1/V~-
1/q~-
m '~
-1/4"3-mJ
m
- e + 2m
/
with e > 0, and a small m > 0. The same behavior holds for a solution of
u r ~ Tu - T ( - 1 , - 1 , - 1 )
-
OID3U
.
Note that T = Tr + T m + Te, where Te = - e l , I is the identity, T m = 3 m P , P is the orthogonal projection with kernel ((1, 1, 1)), and e trr is rotation around the axis ((1, 1, 1)) by the angle t. "In and Tm commute, and d r = etrretr,,e ire. Writing S(t) for the semigroup generated by r - OIQ3, note that if S(s)uo ~ int(Q 3) for all s c (0, t), then S(t)uo = etTuo. Let us look at the plane xl + x2 + x3 = 1 to see the behavior of S(t) in projective space, this plane being invariant under d rr and e trm. Let p0 = ((1 - m)/2, (1 + m/2, 0). ( r x ) 3 < 0 on the line segment [el, p0], and ( r x ) 3 > 0 on [p0, ez]. Let rl be the projection from 0 onto xl + x2 + x3 = 0. Then 1-IS(t)pO = e t rr e t rm pO while in int(Q 3), and this rotation by the angle t and multiplication by e 3rnt with respect to the new origin (1, 1, 1)/3. Suppose that (e q Tretl T,, p0) 1 = 0 with tl the smallest positive solution. Note t w-~ S(t)pO is not differentiable at tl because (T (etlrretlrmpO))l < O. Then rlS(t)pO 6 {x : xl = 0} for t 6 [tl, t2], where t2 is the smallest positive solution of l'IS(t2)pO = (0, (1 - m)/2, (1 + m)/2). The trajectory FIS(t)pO is invariant under rotation by 27r/3 around ((1, 1, 1)), and we let t6 be the period of US(t), dependent on m.
256
CALVERT On the interval [tl, t2] we have (T-OIo))
~
(~ u2
=
u3
( -e+2m \ 1/.v/3 - m
~
t::l)
-!/~/5-m'~ - e -i- 2m
j
.
Hence S(t)u is approximately rotation by t/-v/3 in (e2, e3) and multiplication by e -et. Now as m ~ O, S(t6)pO --+ e-2JrepO. Hence if m is small, then S(t6)pO = otp0 with c~ ~ (0, 1). Thus we see how a trajectory spirals down to 0. In the next example we see that Theorem 2 need not hold if T is replaced by a general Lipschitz nonlinear operator. E x a m p l e 2. There exists a Lipschitz continuous B on D 2 and uo for which the solution to (M-n) starting at uo is not differentiable at tn "~ 0. Define B1 (x, y) = 1 for all (x, y). For n = 1, 2 . . . . . and x ~ [ 2 -n, 2-n+l], let B2(x, y) = (2 -1~ - x ) (2-n(1 + E) - x)(2 -n+l - x), where e > 0 is small enough that 2-n(l+x(E)) Bz(x, y) dx = 0
f2
--n
with 0 < K(~) < 1. Let Be(x, y) = B 2 ( - x , y) for all (x, y). Note that the solution of (M-n) starting at (0, 1) satisfies u(t)2 = 1 iff t 6 [2-n(1 + K ( e ) ) , 2 - n + l ]
9
for some n. R e m a r k . Theorem 2 does hold if T is replaced by any analytic function, because the solutions are analytic by [3]. We now relate our work to [7], and recall the definition of a solution o f ( M ) from [71. Definition 4.1. of [7]. Let ~ 6 Am, 0 < m < n, with a as in the preceding section. Consider a C 1 function x : (t, t + 3) ~ C(~) to be a solution of (M) if it satisfies x'a = Ta,aXa -~ Ta,b~b + Ca (41) and
(TbJa + rb,b~b + cb) * ~b >--0
(42)
on (t, t + a). The second inequality does not apply if m = n, and the first does not apply if m = 0. R e m a r k . Note that x : (t, t + 3) --+ C(~) satisfies equations (41) and (42) iff equation (3) holds.
LINEAR SYSTEMSIN A SATURATED MODE 257
Definition 4.2. of [7]. For xo c D n, a continuous function x(t) : [0, A) --+ D n is said to be a solution of (M) starting at x0 if x(0) = x0 and there are countably many disjoint open intervals (t, t + 3) such that the closure of their union is [0, &] and x restricted to each (t, t + 8) is a solution as in Definition 4.1. We consider the following two examples to show that although Theorem 2 determines existence, there are issues about obtaining uniqueness under these definitions. E x a m p l e 3. There exist, when n = 1, T = 0, and c = 0, two Lipschitz solutions of (M) starting at u0 = 0 under Definition 4.2. This shows that one needs to include in Definition 4.2 that U(ti, ti + 8i) has measure A. Let E1 be the open interval of length 1/4 centered at the midpoint of [0, 1]. Let E2 be the union of the two open intervals with total length 1/8, each centered at the midpoints of the two intervals of [0, I ] \ El. Let E 3 be the union of the four open intervals with total length 1/16, each centered at the midpoints of the four intervals [0, 1] \ E1 \ E2, etc. Let S = [0, 1] \ U~=l El. Note that S has measure 1/2. Let xl (t) = fo Xs for t ~ [0, 1], where Xs is the characteristic function. Let x2(t) = 0 for t ~ [0, 1]. Now U~=l Ei is dense in [0, 1], and both Xl and x2 are solutions o f x ~ = 0 on each El. E x a m p l e 4. There exist, when n = 1, T = 0, and c = 0, two Lipschitz solutions of (M) starting at uo = 0 under Definition 4.2, although [..J(ti, ti + 8i) has measure A. Lack of absolute continuity is the problem. Take Xl to be the Cantor function and x2 to be zero again on [0, 1]. These functions are both solutions o f x ' = 0 on each open interval of the complement of the Cantor set. Unlike Example 3, we have x' = 0 a.e. on [0, 1]. However, solutions of (M-n) satisfy Definition 4.2, by the following proposition. Proposition 2. Given u : [0, A] ~ D n continuous, there are countably many disjoint open intervals (t, t + 8) such that the closure of their union is [0, A] and x restricted to each (t, t + 3) has an image in some C(~). Proof. Work down the dimension as follows. For ~ 6 An, i.e., ~ = 0, let U(~) = u - 1 C ( ~ ) and Un = U(~). For j = 0 to n - 1, given U(~) for ~ 6 A n - j and Un-j, we let U@) = (t • cl (Un-j): u(t) E C@)) for ~ ~ An_j_ 1. Then let Un-j-1 = U~an_j_~ U(~). The closure of the union of the U(~)equals [0, A]. If t C [0, A], let u(t) 6 C(~), x ~ Am. If t ~ cl(Um+l), then t E U(~). Otherwise t 6 cI(U07)) for some 0 ~ Am+l. Also, each U(~) is a countable union of open intervals. []
258 CALVERT We note next that the solutions to (M-n) need not satisfy a version of Definition 4.2 with the union of all the [ai, bi] being [0, A].
Example 5. There exists a Lipschitz continuous B on D 2 and a solution u(t), t 6 [0, 1], to (M-n) starting at uo = (0, 1) for which there does not exist a countable set of intervals (ai, hi) on which u(t) belongs to a constant face C(~), for which the union of [ai, bi] is [0, 1]. Take B1 (x, y) = 1, and for x in an open interval(a, b) giving the Cantor set, we take d Bz(x, y) = , ' ~ x ((x - a ) 2 ( x - b ) 2 ) , while for x in the Cantor set, Bz(x, y) = O. For t ~ (a, b) we have u2(t) = 1 - (x - a)Z(x - b) 2, and for t in the Cantor set, uz(t) = 1.
4. Analysis of convergence We start by addressing the question of Remark 4.7 of [7], using all their assumptions, as well as Assumption A of Vidyasagar used in [ 12] and [ 14] on the functions gi.
Assumption A of [12], [14]. For each i, the function gi satisfies lira ~.g~(;~) = 0.
(43)
).--* i o o
The following theorem has been virtually proved by Vidyasagar, and we proceed by referring to [12] and [14], noting that more direct proofs may be given in some parts. The results we refer to are not written out here because they are long and contain different notation. The =* part of the proof may be achieved more simply by using the function Ez for the existence, but Vidyasagar's results apply to the more general case of T not being a gradient mapping, let alone linear.
Theorem 5. Consider the systems (M) and (L u) under Assumptions 4. i, 4.2, and A. Let f) ~ D n. The point fJ is an asymptotically stable equilibrium point o f ( M ) r there exists an asymptotically stable equilibrium point v x of (L H, x) for L large, with v ~ --~ f) as )~ ~ c~. Proof. We separate the cases: (a) fi 6 ( - 1 , 1)n, (b) ~ c {-1, 1}n, and (c) neither (a) nor (b) is true. (a) fi c ( - 1, I) n. Proposition 2.3 of [14] implies that fi is an equilibrium point of (M), i.e., T~+c=0
LINEAR SYSTEMSIN A SATURATED MODE
259
or f ( 0 ) = b in the notation of [14], iff there exists an equilibrium point v ~ of ( L H , z ) for )~ large, with v ~ --+ ~7as L --+ cx~. (Proposition 2.3 of [14] works with a set S consisting of equilibrium points of (LH,z(j)) for a countable set of )if j).) The required hypothesis that b be a regular value of f holds by Assumption 4.1. Proposition 4.3 of [ 12] shows that 0 is asymptotically stable iff v z is asymptotically stable. More directly, we work in v space rather than in t7 space, remembering that ti = Xu. The eigenvalues of the derivative of v ~-~ c § T v - ~.- 1R - 1G - 1 at v z, i.e., of T - ) - I R-1 (G-1)~(v;~), approach those of T. (b) 0 ~ { - 1 , 1}n. Assuming that TO + c has no component zero, Proposition 2.4 o f [14] implies that 0 is an equilibrium point of (M), i.e., (TO+c).O
>O,
iff there exists an equilibrium point v ~ of (LH, z) for X large, with v ~ -~ 0 as )~ -+ ~ . =~ Suppose that 0 is an asymptotically stable equilibrium point for (M). Then by Assumption 4.2, Lemma 4.2 of [7] shows TO + c has no component 0, giving the existence of v x -~ 0 as above. We note that Lemma 4.2 should require that x~ E D n. By Proposition 5.2 of [ 12], v ~ is an asymptotically stable equilibrium point for ~. large. Suppose that v x is an asymptotically stable equilibrium point and v x --~ 0. Renaming, we may suppose that 0i = 1 for all i, and TO + c _> 0. Then by Assumption 4.2, Lemma 4.2 of [7] shows that TO + c has no component 0. Suppose that h > 0 and min(TO + I) > h, so min(Tv + I ) > h for v ~ D n near 0, giving ( T v + c, O - v) > h IIv - 011el _>
(h/,/h-)
IIv - 0lie= 9
(44)
Suppose that v is a solution of (M), near 0; then v'(t) = (Tv(t)
+ c - OID,,v(t)) ~
implies that d d t IIv(t) - 0tl 2 = 2 ( ( T v ( t ) + c - 3 I D . v ( t ) ) ~ v ( t ) -- O) = 2 ( T v ( t ) + c, v(t) - f))
< - 2 (h/~/n-)
tlv(t)
-
Oil
9
This gives IIv(t - ~1I < fly(0) - 01I - 2 ( h / ~ - )
t
while v(t) # 0, but near 0. Hence v ( 0 = 0 for t _> IIv(0) - 011 vz-ff/2h. (c) W e h a v e ~ = (ga, ~b)withdimensionm > 1 a n d n - m > 1,respectively. Here the a and b correspond to ~ given by 0 ~ C(~).
260
CALVERT
=V Letting f be an asymptotically stable equilibrium point of (M), Assumption 4.1 shows that c is a regular value of -Ta,a and Assumption 4.2 shows that (TfJ + C)b has all components nonzero. Under the conditions, Proposition 2.5 of [14] shows that there exists an equilibrium point v x of (Ln,x) for ~. large, with v x --+ ~ as ~. -+ ec. We show that v x is an asymptotically stable equilibrium point. Assume that fb has all components equal to 1. Let B z be the derivative of v ~ - T v - c + Z-lR-1G-l(v) at v~:
B~.=
(Taa
Ta,b']_l_).,! ( R a l (Gal)' (v~a) J
0
Now Assumption A gives
0
)
R;'
g7 (y)t g-~l (1' ()
(y) ~ oo as y
--+ 1. But
c + rv )' = ~.-1R-Ia-I (v ~') ,
(45)
so there is a k > 0 such that ()~-1R-1G-1 (v ~))b has all components > k for large )~. These two facts show that given M 6 N, for )~ large, and any Xb,
There is 8 > 0 such that, for 3. large, because and Ta,a is negative definite,
(VZa)i are bounded
(B~a,aXa, xa) >_~ [IXaI[2 Then the inequality -- (Xa,
2ab < Ea2 +
away from +1,
.
(47)
E - l b 2 gives a K > 0 such that for all
Za,bXb) -- (Xb, Tb,aXa)
> --3/2 tlx.II 2 - g []Xb[I2 .
(Xa, xb), (48)
These last three equations show that B z is positive definite for ~. large. <= Suppose that there exists an asymptotically stable equilibrium point v ~ of (L/c,z) for ). large, with v x --+ ~ as )~ ---> oo. Assume that fib has all components equal to 1. By (45), because Va ~ --+ Va,
,,-'R;' giving
(I + rfOa
o,
= O. Also
>_o for L large because @ --+ vb. By (45), point of (M).
(TfJ + C)b > O. Thus
f is an equilibrium
By Assumption 4.2 and L e m m a 4.2 of [7], all components of (Tf + C)b are > 0. Because v z is an asymptotically stable equilibrium point, B x is positive semidefinite. Hence BXa,a is also positive semidefinite. Because the term )~-1 e a 1 ( G a l ) ' (i)a~) .__). 0, Ta, a is negative semidefinite. By Assumption 4.1(2),
LINEAR SYSTEMS IN A SATURATED MODE
Ta,a is
negative definite. Thus fi is an asymptotically stable equilibrium (M). In fact the calculation in (b) shows that if u(t) is a solution starting near fi 6 C(~), then u(t) hits C(~) in finite time. After that, u(t) stays and converges exponentially to ~. In more detail, writing A for IIv(t)a B for Ilv(t)b - Obl[, we find that there are K, M , / z , El, and ~2 :> 0, such dB
<-K dt -
if A < e ~
and 0 < B
261
point of from u0 in C(~) Va 11and that
<~2
and dA 2 -
-
dt
<-lzA 2 + MBA .
[]
The following material preceding Theorem 8 investigates the roles that Assumptions 4.1, 4.2, and A play in Theorem 5. E x a m p l e 6. If Assumption 4.1(1) does not hold, i.e., T is a nonsymmetric matrix, then ~ may be an asymptotically stable equilibrium point of (M) and (LM,x) but an unstable equilibrium point of (L H,x). We require the other assumptions, 4.1 (2), 4.2, and A, to hold. In R 2 let
( 00)1 (o.4 01) 1.1
Let C ~
0.5
.
0
The eigenvalues of T have negative real parts, but those of C - 1 T have positive real parts. Let gl and g2 be the identity near 0, R = I, and c = 0, and take ~ be 0 c IR2, an asymptotically stable equilibrium point of (M). It is also an asymptotically stable equilibrium point of (LM,x) for )~ large. Now 0 is an equilibrium point of (LH,x),andthederivativeofv ~ H(v)(Tv+c-S(v))atOis)~C-l(r-)~-aR-1). This, divided by ~., has eigenvalues near those of C - 1 T for L large, and so 0 is an unstable equilibrium point of (L H,X). E x a m p l e 7. We may, if Assumption 4.2 does not hold, have v ~ --r fi, where v ~ is an asymptotically stable equilibrium point of (L~/,z) and (LM,z), but ~ is an unstable equilibrium point of (M). The other assumptions, 4.1 and A, are required to hold. This gives a counterexample to [ 14], Proposition 5.1. Let n = 2, R = I , C = I, cl = 1 - r and c2 = 1 + E, both gi(x) -= g ( x ) = t - 1/~/x-for x large, and T~
,
--1
--E
with E > 0 and small. Let 0 = (1, 1). Now ~ is an equilibrium point, but c + T(~) = (0, 0) so that Assumption 4.2 fails. Now for x ~ ( - 1 , 1), c + T ( x , 1) =
262
CALVERT
(E(X -- 1), 1 -- X). Consequently the semigroup q~t given by (M) maps (x, I) to (y, 1) with y < x if t > 0, making fi unstable. We find an equilibrium point of (Ln, x), say (Vl, v2) = v ;~, near fi: Because g - l ( v ) = 1/(1 - v) 2 we solve
((1 -
02)
--
~(1
-
Vl))(1
--
01) 2 ~-
1/~.
((t - vl) + ~(1 - v2))(1 - v2) 2 = 1 / k . Substituting a = 1 - vl, b = 1 - v2, eliminating b, and substituting z = a3k gives
We take a solution z = z(E) 6 (1, 2) if ~ is small. Then a = (z/X) 1/3 -+ 0 as Z --+ o0, and b = (z -1 + E) a ---> 0 also. Hence v x --+ 0. By Proposition 5.2 of [12], v x is an asymptotically stable equilibrium point of (LH.x), hence of (LM,z), for large L.
E x a m p l e 8. We may have the implication =~ of Theorem 5 failing without Assumption A. Assumptions 4.1 and 4.2 are required to hold. Let n = 1 and c = 0. Take T, C, and R to be the identity, and fi = t. Note that (Tfi + c)b > 0, and fi is an asymptotically stable equilibrium point of (M). Suppose that g : R ~ ( - 1 , 1) is a C 1 diffeomorphism, and increasing. For n a n integer, let v n be the solution of T v n + c - n - l g - l g -1 (v n) = O,
which converges to t as n ----> ~ . Note that v n is strictly increasing for n large. Consider the derivative of the preceding mapping at v n, i.e.,
1--n-i (g-a)'(vn) . Change g-~ (if necessary) near v n, but leave g - I (v n) the same, so that this derivative is positive, to make v n an unstable equilibrium point. We now show the relationship of Assumption A to convexity.
Proposition 3,
Suppose that g : L~ -+ I~ is strictly increasing and C l, and g ( x ) --> 1 as x -+ r Then
(a) - g is convex on an interval [T, o~)
(b) x g l ( x ) ---> O as x ---> cx~, but not conversely.
LINEhR SYSTEMSIN A SATURATED MODE
Proof. T>0.
It is easier to consider the function f ( x )
263
= 1 - g ( x ) and assume that
(a) =~ (b). Let f be convex and let A ( x ) = f ( x ) - x f ~ ( x ) . Then A ( x ) is decreasing, because for x < z, A(x) - A(z) = f(x) - xf'(x) - f(z) + zf'(z) > xf'(x) - xf'(x)
>_ O.
Then suppose, to get a contradiction, that x f ' ( x ) 7# O. Hence A ( x ) 7# O, and hence we have b > 0 with A ( x ) >_ 2b, giving - x f ' ( x ) >__ b for large x. Then f (xo) - f (x) >__b log(x / x o ) , contradicting f (x) > 0 for all x. (b) 7~ (a). Consider 2 f(x) = - + X
sin(x) X2
We see that f is strictly decreasing on (2, e~) to 0. Also x f ~ ( x ) --~ O. But we check that f " ( x ) takes on positive and negative values in any interval [T, co), so that f is not convex there. [] E x a m p l e 9. We may, without Assumption 4.1(1), have v z an asymptotically stable equilibrium point of (LM,z) and (LH,z) converging to ~5and yet ~ need not be asymptotically stable. The other assumptions, 4.1(2), 4.2, and A, are assumed to hold. Let n = 2, c = 0, let T be rotation by re/4, R and C the identity, gi(O) = O, and g~ (0) = 1. Then take v z = 0 as an equilibrium point of v'(t) = T v + c -
~.-1G-lv .
With fix I12 as the Lyapunov function V ( x ) we have d
/
\
27 and 0 is an asymptotically stable equilibrium point of ( L M , D by Lyapunov's stability theorem. Using g~ (0) = 1 we check that the eigenvalues of the derivative of u T v --r c - ),.- 1 R - 1 G - 1 u at 0 are in the open left-half plane. Therefore 0 is an
asymptotically stable equilibrium point of (L n,x). Now v z ~ of (M).
fi = 0 and yet 0 is not an asymptotically stable equilibrium point
We now consider Assumption 4.1 (2). It cannot be changed without changing Assumption 4.2, which assumes it. We present the conclusion of L e m m a 4.2 of [7] as an alternative, calling it Assumption B.
264 CALVERT Assumption B. Let T be symmetric, as in Assumption 4.1(1). Suppose that ifx is an equilibrium point of (M), i.e., ( T x + C)a = O and ( T x + C)b * ~b > 0, where x 6 C(~), then min ( ( T x + C)b * ~b) > O. Theorem 6. Consider (M) and ( L t4) under Assumptions A and B, and tet ~ c D ~. The conclusion of Theorem 5 holds, i.e., the point ?; is an asymptotically stable equilibrium point of(M) r there exists an asymptotically stable equilibrium point v ;~ of(L14,z)for)~ large, with v ~ -+ f; as L -+ o0. Proof. Let 0 ~ C(~), ~ ~ Am. ::~ If fi r { - 1, 1}n is asymptotically stable, Ta,a is negative definite, and thus Assumption 4.1(2) holds for this particular submatrix. The result follows by the proof of Theorem 5. r As in Theorem 5 we find that fi is an equilibrium point of (M), and by Assumption B, min((Tfi + C)b * ~b) > 0. As in Theorem 5, Ta,a is negative semidefinite, and the result follows if we can show that Ta,a is nonsingular. Suppose not; take Za ~ 0 with Za,aZa -=- 0, and if z = (Za, 0), multiplying z by a scalar, assume that ~ + z ~ D n and (~ + Z)~Ck) = 4-1 for some k < m. Now ~ + z is an equilibrium point of (M). However, T(fJ + z) + c)~(k) = 0, and with the new ~, a and b corresponding to 0 + z we have min ((T(~ + z) + e)b * ~b) = 0, contradicting Assumption B. [] Example 10. Assumption B can hold without Assumption 4.1(2). Let n = 1, T = 0 , a n d c = 1. We now consider the ::~ part of Theorem 5 without linearity of T. Theorem 7, Let f) E C(~). Suppose that T is C 1 on a neighborhood of D n. Suppose that (T(f)) + c) a = O, and T'(f))a,a has its eigenvalues in the open lefthalf plane. Suppose that min ((Tfi + C)b * ~O) > O. Suppose that Assumption A holds. Then there exists Eo such that for all ~ c (0, E0] there exists 3% such that for all L >_ LE there is a unique asymptotically stable equilibrium point v ~ of v' = T(v) + c - S(v) within E of ~. If either ~ ~ { - 1, 1}n or T is a gradient, then v ~ is an asymptotically stable equilibrium point of Cu r = T v + c -
R-~u ,
v = G()~u) .
(49)
We omit the proof because it overlaps Proposition 2.5 of [14]. We show that the condition that Tt(f))a,a has eigenvalues in the open !es half plane, i.e., a nonlinear version of Assumption 4.1(2), used in Theorem 7, is necessary. This shows that Proposition 6.1 of [12] had to be changed to give Proposition 2.5 of [14]. Note that (0, 1)n in the work of Vidyasagar corresponds to ( - 1 , 1)n in the work of Li, Michel; and Porod.
LINEAR SYSTEMS IN A SATURATEDMODE
265
E x a m p l e 11, L e t n = 2, c = 0, and take gi(x) = g(x) = 1 - 1/x f o r x large, with g odd and equal to the identity near 0. Take R i = 1. Define
T(Xl,X2) = ( x 2 - 1
- (g-l(xl))2
,1
for xl near 0. The point fi = (0, 1) satisfies T'(v)a,a = 0 and T'(fi)/,,b > 0. However we claim that there is no equilibrium point v z of (49) with second component near 1, for )~ large. To derive a contradiction, let (Vl, v2) be such an equilibrium point. Then v2 - 1 -
g-l(vl)
= ~.-lg-l(vl) , 1 ----) ~ - l g - l ( v 2 ) .
Letting x = g - 1 (Vl) gives the quadratic X 2 + ~-1 x _.1_)~-1 = 0 . This has no real roots for )~ large. Under the circumstances of Theorem 6 or 7, we wish to describe the behavior of v z as L varies. T h e o r e m 8. Under the conditions of Theorem 7, for )~ large, if ~) ~ ( - 1, 1)n, then d
z
- T: (vX)] - 1 ) ~ - 2 R - 1 G - 1 w
The derivative a-~v z # O, and v k # v u if )~ # #, with both large. Proof. Let v ~ be an equilibrium point, so that v z = GRL (Tv ~ + c). I f L is large, then v z is near fi and hence (T (v z) + C)b r 0. Suppose that v z = vU, with both and/z large. Then (z ( r v . + c) = 0 and hence )~ = / z . To obtain the derivative of v 2, we use the implicit function theorem on
F()~, v) = c + Tv - )~-I R - 1 G - ~ v . Suppose that X 0"0, v~ = 0. g is C 1, and DzF()~, v) = T:(v)-)~ -1R -1 (G-1):(v). Now D2F 0~0, v ~ is an isomorphism for ~0 large, and v ~ near ft. Hence there are E1 and E2 such that for )~ 6 B ()~0, el) there is a unique v ~ 6 B (v ~ ~2) with F ()~, v ~) = 0, and the map )~ w-> v x is C 1, with d d - - ~ ( v Z ) = - [ D 2 F @ , v Z ) ] - 1 D 1 F @ , v x)
r
[]
266
CALVERT Question: W h e n does (v ~ - f)) / IIvz - f)ll converges as L ~
c~?
T h e f o l l o w i n g small result says something about the direction o f v z -- ~3.
P r o p o s i t i o n 4. Under the conditions o f Theorem 7, suppose that T(v)a(1) > T(v)~r(2) > . ~ .
> T@)cr(n)
f o r some c~ E S y m ( n ) . Let gi = g and Ri = R f o r all i. t f v ~ --+ f) as )~ --~ co, we have
P r o o f . For ~. large, T (vx)~r(i) > T
, etc.
B e c a u s e g is strictly increasing,
g R ) ~ ( c + T (v~')),~(1)> g R L ( c + T (vX))~r(2),
etc.
Q
Acknowledgment I thank C. M a r i n o v for his valuable contributions.
References [1] S. Abe, Convergence acceleration of the Hopfield neural network by optimizing integration step sizes, IEEE Trans. Systems Man Cybernet. -- Part B: Cybernet., 26, 194-201, 1996. [2] S. Abe and A. Gee, Global convergence of the Hopfield neural network with nonzero diagonal elements, IEEE Trans. Circuits Systems -- II: Analog Digital Signal Process., 42, 39-45, 1995. [3] V. I. Arnold, Ordinary Differential Equations, MIT Press, Cambridge, MA, 1973. [4] H. Brezis, Operateurs Maximaux Monotones et Semi-groupes de Contractions dans les Espaces de Hilbert, North-Holland, Amsterdam, and American Elsevier, New York, 1973. [5] J.J. Hopfield, Neurons with graded response have collective computational properties like those of two state neurons, Proc. Nat. Acad. Sci. USA, 81, 3088-3092, 1984. [6] J. H. Li, A. N. Michel, and W. Porod, Qualitative analysis and synthesis of a class of neural networks, IEEE Trans. Circuits Systems, 36, 976-986, 1988. [7] J.H. Li, A. N. Michel, and W. Porod, Analysis and synthesis of a class of neural networks: Linear systems operating on a closed hypercube, IEEE Trans. Circuits Systems, 36, 1405-1442, 1989. [8l D. Liu and A. Michel, Asymptotic stability of systems operating on a closed hypercube, Systems Control Lett., 19, 281-285, 1992. [9] A. Michel, J. Si, and G. Yen, Analysis and synthesis of a class of discrete-time neural networks described on hypercubes, IEEE Trans. Neural Networks. 2.32-46, 1991.
LINEAR SYSTEMSIN A SATURATEDMODE 267 [10] A. Pazy, Semi-gropus of nonlinear contractions in Hilbert space, in Problems in Nonlinear Analysis, ed. Prodi, Cremonese, CIME Varenna, 1971. [11] R. Perfetti, On the op-amp based circuit design of cellular neural networks, lnternat. J. Circuit TheoryAppl., 22, 425-430, 1994. [12] M. Vidyasagar, Location and stability of the high gain equilibria of nonlinear neural networks, IEEE Trans. Neural Networks, 4, 660-671, 1993. [13] M. Vidyasagar, Discrete optimization using analog neural networks with discontinuous dynamics, in International Conference on Automation, Robotics, and Computer Vision, Singapore, 1994. [14] M. Vidyasagar, Minimum seeking properties of analog neural networks with mulfilinear objective functions, IEEE Trans. Automat. Control, 40, 1359-1375, 1995. [15] M. Vidyasagar, Solution of difficult combinatorial optimization problems using analog neural networks with discontinuous dynamics, in International Conference on Automation, Robotics, Control and Computer Vision, Singapore, 1996. [16] P. B. Watta and M. H. Hassoun, A coupled gradient network approach for static and temporal mixed integer optimization, IEEE Trans. Neural Networks, 7, 578-593, 1996.