UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Decomposition and optimal control theory Masak, Mart 1968

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
UBC_1968_A1 M38.pdf [ 5.64MB ]
Metadata
JSON: 1.0104602.json
JSON-LD: 1.0104602+ld.json
RDF/XML (Pretty): 1.0104602.xml
RDF/JSON: 1.0104602+rdf.json
Turtle: 1.0104602+rdf-turtle.txt
N-Triples: 1.0104602+rdf-ntriples.txt
Original Record: 1.0104602 +original-record.json
Full Text
1.0104602.txt
Citation
1.0104602.ris

Full Text

DECOMPOSITION AND OPTIMAL CONTROL THEORY by MART MA3AK B.A.Sc, University oi Toronto, 1963 M.A.SCo, University of Toronto, 1964 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in the Department of E l e c t r i c a l Engineering We accept t h i s thesis as conforming to the required standard Research Supervisor *.*. Members of Committee ............«..».>.»* <>.... Head of Department ..., • «. Members of the Department of E l e c t r i c a l Engineering THE UNIVERSITY OF BRITISH COLUMBIA July, 1968 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r an advanced deg ree a t the U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r ee t h a t t he L i b r a r y s h a l l make i t f r ee1y . a v a i 1 a b 1 e f o r r e f e r e n c e and S tudy . | f u r t h e r a g r ee t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y pu rpo se s may be g r a n t e d by the Head o f my Department o r by h lis r e p r e s e n t a t i v e s . It i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l no t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Department o f £Ac^'cgJ ^ncp^^r;^ The U n i v e r s i t y o f B r i t i s h Co lumb ia Vancouve r 8, Canada Date l u l ^ . -2> t vqt,ft ABSTRACT The o b j e c t i v e of t h i s t h e s i s i s t o i n v e s t i g a t e d e c o m p o s i t i o n and i t s a p p l i c a b i l i t y t o t h e t h e o r y of o p t i m a l c o n t r o l . The work b e g i n s w i t h a r e p r e s e n t a t i o n o f t h e s t r u c t u r e of t h e o p t i m a l c o n t r o l problem i n terms of d i r e c t e d g r a p h s . T h i s r e p r e s e n t a t i o n exposes a s t r o n g c o n n e c t e d n e s s p r o p e r t y l e a d i n g t o f u n d a m e n t a l d i f f i c u l  t i e s which a r e c e n t r a l i n l i m i t i n g t h e c l a s s of c o n t r o l problems t o which d e c o m p o s i t i o n can s u c c e s s f u l l y be app l i e d . C o m p u t a t i o n a l problems of o p t i m a l c o n t r o l a r e t h e n c o n s i d e r e d , and d e c o m p o s i t i o n i s found t o p r o v i d e a framework w i t h i n which t o a n a l y s e n u m e r i c a l methods s u i t a b l e f o r p a r a l l e l p r o c e s s i n g . A number of such methods a r e shown and a n u m e r i c a l example i s used t o i l l u s t r a t e t h e v i a b i l i t y of one of t h e s e . I n t h e second p a r t of t h e t h e s i s , t h e o p t i m a l con t r o l l a w s y n t h e s i s problem i s d i s c u s s e d t o g e t h e r w i t h an i n v e r s e problem. The l a t t e r c o n c e r n s t h e r e q u i r e m e n t o f a s e c o n d - l e v e l c o - o r d i n a t o r i n a h i e r a r c h i c a l s t r u c t u r e 0 A m u l t i - l e v e l c o n t r o l l e r i s t h e n suggested f o r a c l a s s o f systems,, The e f f e c t o f t h i s c o n t r o l l e r s t r u c t u r e i s t o p r o v i d e a performance v e r y c l o s e t o the o p t i m a l w h i l e m a i n t a i n i n g adequate s u b - o p t i m a l c o n t r o l i n case of a breakdown of t h e s e c o n d - l e v e l c o - o r d i n a t o r . The s t r u c t u r e i s j u s t i f i e d on the b a s i s of the second v a r i a t i o n t h e o r y of the c a l c u l u s of v a r i a t i o n s . F i n a l l y , a new c o m p u t a t i o n a l t e c h n i q u e founded on t h e g e o m e t r i c a l c o n c e p t s of o p t i m a l , c o n t r o l t h e o r y i s i n  t r o d u c e d . T h i s r e s u l t s i n r e p l a c i n g t h e u n s t a b l e c o - s t a t e v a r i a b l e s a s s o c i a t e d w i t h P o n t r y a g i n ' s maximum p r i n c i p l e w i t h a s e t of bounded v a r i a b l e s . The f a c i l i t y i n t h e c h o i c e of i n i t i a l i t e r a t e s makes the method p r o m i s i n g . i v TABLE OF CONTENTS Page LIST OF TABLES v i LIST OF ILLUSTRATIONS v i i ACKNOWLEDGEMENT v . l i l 1. INTRODUCTION 1 2. BACKGROUND TO DECOMPOSITION AND OPTIMIZATION PROBLEMS 4 2.1 Systems Theory ..4 2.2 O p t i m a l D y n a m i c a l System 7 2.3 D i g r a p h Theory and t h e O p t i m a l Dynamical System 10 2.4 D e c o m p o s i t i o n 16 3. DECOMPOSITION AND COMPUTATIONAL-ALGORITHMS . 21 3.1 P a r a l l e l i s m i n C o m p u t a t i o n a l A l g o r i t h m s 23 3.2 G e n e r a l i z e d P i c a r d A l g o r i t h m 26 3.3 D e c o m p o s i t i o n A l g o r i t h m Based on D u a l i t y 28 3.4 D e c o m p o s i t i o n U s i n g P e n a l t y F u n c t i o n s .......... 33 3.5 P a r a m e t r i c T r a j e c t o r y Method (PART I ) 38 3.6 P a r a m e t r i c T r a j e c t o r y Method (PART I I ) 45 N u m e r i c a l Example 48 3.7 D i o o u s s i o n and C o n c l u s i o n 57 4. DECOMPOSITION AND MULTILEVEL CONTROL SYSTEMS 63 4.1 H i e r a r c h i c a l S t r u c t u r e 64 4.2 An I n v e r s e Problem 67 4.3 L o c a l S t a t e E s t i m a t i o n 73 4.4 A M u l t i - l e v e l C o n t r o l l e r Based on t h e Second V a r i a t i o n 77 Example 4.1 91 Example 4.2 92 4.5 C o n c l u s i o n 100 V Page 5. DISCUSSION AND CONCLUSION 101 Appendix A : N o t a t i o n 10^ Appendix B : M u l t i - P r o c e s s i n g Computers .106 Appendix C : S c a l a r Example 1 0 9 Appendix D : Tangent P l a n e Method 11^ REFERENCES 127 LIST OF TABLES T a b l e Page o 3.1 A Comparison of Computation Times w i t h D i f  f e r e n t M o d i f i c a t i o n s o f the P a r a m e t r i c T r a  j e c t o r y Method, Example 3*2, ( a l l t i m e s quoted i n seconds) . . . o . o o . o o . . . . o . . . o . . . . . . 51 3.2 T o t a l Number of I t e r a t i o n s t o O b t a i n S o l u  t i o n , Example 3.2 60 4.1 T r a j e c t o r i e s from D i f f e r e n t I n i t i a l C o n d i t i o n s w i t h e = . 8 , as i n F i g u r e 4 . 1 , .Example 4 . 1 . . 94 4 .2 E f f e c t of D i f f e r e n t V a l u e s of c , U s i n g I n i  t i a l C o n d i t i o n s ( 3»3 ) . Example 4.1 . .„ 94 4.3 E f f e c t o f D i f f e r e n t I n i t i a l C o n d i t i o n s on Example 4 . 2 , w i t h e = .5 , T = 2 96 4 . 4 E f f e c t of D i f f e r e n t V a l u e s of t h e Parameter e i n Example 4 . 2 , U s i n g I n i t i a l C o n d i  t i o n s ( -2 , 2, - 2 , 2) and T = 2 . . . . 97 C. l E f f e c t of b on t h e R a t i o A J / A J f o r t h e S c a l a r P r o b l e m , w i t h a = - 1 0 . . . . . . . . . . . 0 . . 112 D, l A Comparison of t h e Number of I t e r a t i o n s R e q u i r e d f o r Convergence U s i n g S t a n d a r d and Tangent P l a n e Methods . . o . 124 v i i LIST OF ILLUSTRATIONS F i g u r e Page 3.1 T r a j e c t o r y i n the I n i t i a l C o - s t a t e Space, Example 3.2 42 3.2 O p t i m a l S t a t e T r a j e c t o r i e s , Example 3 . 2 , w i t h £ =• 1 53 3 . 3 O p t i m a l C o - s t a t e T r a j e c t o r i e s , Example 3 . 2 i w i t h e = 1 .. 0.. 5^ 3.4 Comparison of Computation Times w i t h D i f f e r e n t M o d i f i c a t i o n s of the P a r a m e t r i c T r a j e c t o r y Method, Example 3 « 2 . . . . . . 0 . . . . . . . . 55 3«5 Comparison of Computation Times, as i n F i g u r e 3.4, w i t h P a r a l l e l M o d i f i c a t i o n s Times D i v i d e d by f a c t o r 3 •' 56 4.1 Proposed H i e r a r c h i c a l S t r u c t u r e f o r C o n t r o l l e r 89 4 .2 T r a j e c t o r i e s i n S t a t e Space R e s u l t i n g from D i f f e r e n t C o n t r o l Laws, Example 4.1,-' £ = . 8 . . 93 4 .3 S t a t e T r a j e c t o r i e s R e s u l t i n g from D i f f e r e n t C o n t r o l Laws, Example 4.2, £ ~ 0 5 , T = 2 . . . 98 C. l A Comparison of N o r m a l i z e d Performance Func- t l o n a l s i n S c a l a r Example ................... 113 D. l A Comparison of t h e Regions of Convergence f o r th e S t a n d a r d Method and t h e Tangent P l a n e Met hod 125 D.2 O p t i m a l T r a j e c t o r i e s f o r p . and v .... 126 v i i i ACKNOWLEDGEMENT I t i s my p l e a s u r e t o acknowledge t h e c o n t r i b u t i o n s of a number of people towards t h i s r e s e a r c h 0 In p a r t i c u l a r , I wish t o e x p r e s s my g r a t i t u d e t o P r o f e s s o r E. V.Bohn f o r h i s a s s i s t a n c e and c o n t i n u e d encouragement, and t o Dr. A.G. Longmuir f o r s t i m u l a t i n g d i s c u s s i o n s and c r i t i c i s m s , , The o r i g i n a l m o t i v a t i o n f o r t h i s t h e s i s i s t o a l a r g e e x t e n t due t o P r o f e s s o r s Ed.Gerecke and M.Mesarovic a t t h e Swiss F e d e r a l I n s t i t u t e of T e c h n o l o g y 0 S p e c i a l t h a n k s a r e g i v e n t o my. w i f e , K a t r e - A n n , w i t h o u t whose c o n f i d e n c e t h e p r e p a r a t i o n f o r t h i s t h e s i s would have been c o n s i d e r a b l y more d i f f i c u l t . T h i s r e s e a r c h was su p p o r t e d by a N a t i o n a l Research C o u n c i l S t u d e n t s h i p , 1965-1968, f o r which I am d e e p l y i n d e b t e d . 1 1. INTRODUCTION The o b j e c t i v e o f t h i s t h e s i s i s to s tudy the a p p l i  c a b i l i t y o f the d e c o m p o s i t i o n concept to o p t i m a l c o n t r o l p r o b l e m s . The r e q u i r e m e n t f o r d e c o m p o s i t i o n a r i s e s from the n e c e s s i t y t o u n d e r s t a n d and c o n t r o l i n c r e a s i n g l y complex systems b o t h i n i n d u s t r y and s o c i e t y i n g e n e r a l . These p r o  blems a r e so l a r g e t h a t t h e y cannot be h a n d l e d by the c l a s  s i c a l s c a l a r i n p u t - o u t p u t a n a l y s i s ; n e i t h e r do they b e l o n g i n the c a t e g o r y o f " d i s o r g a n i z e d c o m p l e x i t y " as do those s t u d i e d i n thermodynamics , f o r w h i c h s t a t i s t i c a l methods a r e a d e q u a t e . T h i s m i d d l e ground o f s o - c a l l e d o r g a n i z e d complex i t y r e q u i r e s the development o f new and p o s s i b l y s p e c i a l t e c h n i q u e s f o r e x p l o i t i n g the system s t r u c t u r e . These r e a l l y l a r g e p r o b l e m s , because they do c o n t a i n s u b s y s t e m s , a r e bound t o have a s t r u c t u r e t h a t can be u t i l i z e d t o a d v a n t a g e . Decomposing, o r b r e a k i n g down a problem i n t o i t s c o n  s t i t u e n t p a r t s , has l o n g been r e c o g n i z e d as a n a t u r a l a p p r o a c h t o c o m p l e x i t y , and numerous w o r k s , [ i j t o [6] , f rom many r e s e a r c h a r e a s have been d e v o t e d t o d i f f e r e n t a s p e c t s o f d e c o m p o s i t i o n , w i t h v a r y i n g degrees o f s u c c e s s . A l t h o u g h a -few works such as [5] and [6] , and o t h e r s to be d i s c u s s e d s u b s e q u e n t l y , have at tempted t o a p p l y t h i s concept to t h e dynamic o p t i m i z a t i o n p r o b l e m , no u n q u a l i f i e d b r e a k t h r o u g h s 2 can be c l a i m e d . T h i s t h e s i s b e g i n s by d e f i n i n g the s t r u c t u r e of an op t i m i z a t i o n problem and r e p r e s e n t i n g t h i s s t r u c t u r e by means of d i r e c t e d graphs. A l t h o u g h no s i g n i f i c a n t q u a n t i t a t i v e con c l u s i o n s a r i s e from t h i s approach, i t does o f f e r a u n i f i e d framework w i t h i n which t o c o n s i d e r d e c o m p o s i t i o n problems. The t h e s i s t h e n branches i n t o two r e l a t e d s t u d i e s , one con cerned w i t h t h e c o m p u t a t i o n a l problem of o p t i m a l c o n t r o l , and t h e o t h e r i n v o l v i n g the o p t i m a l feedback c o n t r o l l a w s y n t h e s i s problem. I t i s argued t h a t t h e f o r m e r b e n e f i t s from d e c o m p o s i t i o n because new, a t t r a c t i v e a l g o r i t h m s , s u i t  a b l e f o r m u l t i - p r o c e s s i n g computers, a r i s e as p r a c t i c a l pos s i b i l i t i e s . The s y n t h e s i s problem b e n e f i t s , s i n c e decom p o s i t i o n i s t h e n a t u r a l f i r s t s t e p i n o b t a i n i n g a h i e r a r c h i  c a l c o n t r o l l e r s t r u c t u r e , and t h i s s t r u c t u r e i s d e s i r a b l e from many e n g i n e e r i n g c o n s i d e r a t i o n s . " fundamental improvements i n c o n t r o l are r e a l l y improve ments i n communicating i n f o r m a t i o n w i t h i n an o r g a n i z a t i o n Or mechanism." When c o n f r o n t e d w i t h t h e problem of c o n t r o l  l i n g a complex system, a c e n t r a l i n t e g r a t e d c o n t r o l l e r can v e r y w e l l become a b o t t l e neck f o r t h e i n f o r m a t i o n f l o w . D e c o m p o s i t i o n , because i t o f f e r s t h e p o s s i b i l i t y of decen t r a l i z e d c o n t r o l , has the p o t e n t i a l of overcoming t h i s b o t - John Vcn Neumann has been quoted as s a y i n g t h a t 7 t i e - neck, t h e r e b y i m p r o v i n g t h e I n f o r m a t i o n f l o w s i g n i  f i c a n t l y . 2. BACKGROUND TO DECOMPOSITION AND OPTIMIZATION PROBLEMS I n t r o d u c t i o n T h i s p a r t of the t h e s i s p r o v i d e s some d e f i n i t i o n s as w e l l as b a s i c background m a t e r i a l to be u s e d i n the s u b s e  quent s e c t i o n s . Terms not d e f i n e d h e r e , s u c h as a d j o i n t v a r i a b l e s , s t r o n g connectedness and so f o r t h , a r e assumed t o have w e l l d e f i n e d meanings i n the c u r r e n t l i t e r a t u r e . The Maximum P r i n c i p l e of P o n t r y a g i n i s s t a t e d , but p r o o f s a r e r e f e r e n c e d , and the a s s u m p t i o n i s made t h a t the r e a d e r has f a m i l i a r i t y w i t h t h e c u r r e n t s t a t e of o p t i m a l c o n t r o l t h e o r y . The problem of d e c o m p o s i t i o n and system s t r u c t u r e Is most r e a d i l y s t u d i e d w i t h the a i d o f the t h e o r y of d i  r e c t e d g r a p h s , and one s e c t i o n i s t h e r e f o r e d e v o t e d t o the r e l e v a n c e o f t h i s t h e o r y t o the s t r u c t u r e of o p t i m a l c o n t r o l p r o b l e m s . F i n a l l y , t h i s t h e o r y i s used t o l i m i t the c l a s s of problems f o r which d e c o m p o s i t i o n i s r e a d i l y a p p l i c a b l e . 2.1 Systems T h e o r y The t h e o r y of systems i s a m a t h e m a t i c a l t h e o r y , d e a l  i n g w i t h a b s t r a c t e n t i t i e s or m a t h e m a t i c a l models . In t h i s c o n t e x t , the term o b j e c t , o r synonomously subsystem i s t a k e n t o mean a f i n i t e s e t of v a r i a b l e s t o g e t h e r w i t h a s e t of r e l a t i o n s between them. The term system r e f e r s to a c o l l e c t i o n of o b j e c t s u n i t e d by some form of m a t h e m a t i c a l -5 l y well-defined i n t e r a c t i o n or interdependence. By apply ing cause-effect r e l a t i o n s h i p s , the set of variables charac t e r i z i n g an object i may be partitioned into two non-inter secting sets, v , known as the subsystem input, and y^, the system output. In thi s thesis, i t i s assumed that the set of re l a t i o n s between v^ and , the input-output descrip t i o n , can be expressed In the form of an ordinary, f i r s t - order, vector d i f f e r e n t i a l equation, = ^ ( y i . V x ^ ) 2.1 and at some time t Q , i t i s assumed that y^ i s availa b l e f o r measurement, so that y ^ o ) = y 0 i 2.2 Furthermore, i t i s assumed that the interactions which unite the c o l l e c t i o n of objects to form the system be ex pressible by a vector algebraic equation of the form g(y,v) = 0 2.3 wher y and v are the composite vectors formed from the vec tors y^ and Vj^ as 1 ranges over a l l the objects comprising the system. Equations 2.1, 2.2, and 2.3 are s u f f i c i e n t to provide a complete mathematical des c r i p t i o n of the system dynamics. In f a c t , some redundancy i s bound to exist, since many sub systems have outputs which form part of the input of some other subsystem. In this thesis as well as i n almost a l l control system l i t e r a t u r e , these redundancies are eliminated 6 by e x p l i c i t l y solving for some of the variables i n equa t i o n 2.3 • The re s u l t of t h i s i s a new smaller set of i n  put-output variables, called x and u, which are intercon nected by the dynamical equation x = f(x,u) 2.4 while equation 2.3 has been eliminated completely. It i s now assumed that the remaining system inputs, u, are a l l control inputs i n the sense that, within c e r t a i n p r a c t i c a l l i m i t a t i o n s , these vectors may be chosen at w i l l by the system designer. This precludes the p o s s i b i l i t y of noise inputs, but t h i s i s j u s t i f i e d by the following argu ment. In the case of the computational algorithm, the ob je c t i v e i s to calculate the i d e a l behaviour of the system under no imperfections such as noise or c o n t r o l l e r l i m i t a  tions. This i d e a l i s then used e i t h e r d i r e c t l y i n c o n t r o l  l e r synthesis, or i n d i r e c t l y , as a measure of the perfor mance of some r e a l i s t i c , implementable control law. In the case, of t h * synthesis procedure f o r on-line c o n t r o l l e r s , a control law i s obtained whose sole purpose i s to correct f o r noise inputs to the system. Unless these uncontrolled disturbances are highly predictable, there i s no e f f e c t i v e way to compensate fo r them i n the generation of the feed back control law, and they are therefore ignored. It i s further noted that the foregoing discussion ? makes no mention of the concept Of the state of the system. In the f i r s t place, no purpose Is served by entering Into a long discussion of this concept here, when so many excellent references such as [8] and [ 9 ] treat t h i s i n d e t a i l . More s i g n i f i c a n t l y , the assumption i s made that there exists a unique minimal state description of the system, which i s i d e n t i c a l to the afore-mentioned input-output description of the system. The reason for t h i s somewhat r e s t r i c t i v e assumption i s that with decomposition, the emphasis i s on the system s t r u c t u r a l properties as manifested at the input- output l e v e l . As with s t a b i l i t y properties, these structu r a l properties are not preserved with a r b i t r a r y transfor mations of state, and at present, no r e s t r i c t i o n s on these transformations are avail a b l e which do imply these preser vations. Henceforth i n t h i s thesis, the terms output and state s h a l l be employed interchangeably, keeping i n mind the above assumption. 2.2 The Optimal Dynamical System The optimization problem to be studied i n th i s thesis i s now defined. Given a dynamical system whose motion i s described by the equation x = f (x,u), 2A x(0) = x 0 determine the vector u £ fl which w i l l minimize the functional J = j h(x,u) dt 2.5 o subject to M(x(t f)) = 0 2.6 where Q Is some convex s e t , M ( . ) i s a v e c t o r v a l u e d t e r m i n a l c o n d i t i o n , h ( . , . ) i s a s c a l a r v a l u e d , p o s i t i v e s e m i - d e f i n i t e f u n c t i o n . The H a m l l t o n i a n f o r the problem i s d e f i n e d as H ( x , p , u ) = - h ( x , u ) + p ( f ( x , u ) 2 .7 The Maximum P r i n c i p l e o f P o n t r y a g i n s t a t e s t h a t i f the c o n t r o l u= u # i s o p t i m a l , t h e n c o r r e s p o n d i n g t o u * and the g e n e r a t e d o p t i m a l t r a j e c t o r y x"*, t h e r e e x i s t s an a d j o i n t v e c t o r p * , such t h a t x* = V H ( x * , p * , u * ) 2.8 P p * =-V H ( x * , p * f u * ) 2 .9 x p * ( t j « M ( x * ( t f ) ) = 0 2 .10 H ( x * , p * , u * ) > H(x?p?u) f o r a l l u e & , and a l l t , 0 ^ t ^ t f . 2 .11 T h i s r e s u l t i s p r o v e d i n d e t a i l i n [ lo] , w h i l e [ l l} and £ l 2 j s e r v e as u s e f u l r e f e r e n c e s and g i v e examples of how t h i s i s u s e d . E q u a t i o n s 2.8 t o 2 .11 d e f i n e a t w o - p o i n t boundary v a l u e p r o b l e m , h e n c e f o r t h r e f e r r e d t o as the TPBVP. E q u a t i o n 2 .11 p r o v i d e s an a l g e b r a i c r e l a t i o n s h i p between t h e v a r i a b l e s x, u and p , and w i t h t h e use o f the I m p l i  c i t f u n c t i o n theorem, i f t h e problem i s n o n - s i n g u l a r Ci3^ , u can be e x p r e s s e d as a f u n c t i o n of x and p . T h e r e f o r e , t h e s e e q u a t i o n s a r e s u f f i c i e n t f o r g e n e r a t i n g the o p t i m a l t r a j e c t o r y x ( t ) , and the o p t i m a l c o n t r o l u ( t ) , and these w i l l presumably be u n i q u e i f the problem i s w e l l d e f i n e d . / 9 The d i f f i c u l t y arises because the mixed boundary conditions do not allow r e a d i l y obtainable solutions. To quote Letov [l4j : "... the famous two-point boundary value problem stands as a fo r t r e s s that has been attacked time a f t e r time, but never conquered. ... (I am) not so bold as to claim that success i s close at hand i n many applications of v a r i a  t i o n a l techniques which are both rigorous and legitimate..." This obstacle has sent many to search f o r other optimization techniques, the most notable of which has been dynamic programming. However, none has been found that i s r e a l l y as useful i n general as the maximum principle,and • therefore, t h i s thesis w i l l consider optimal control problems only from t h i s viewpoint. Consequently, i n the subsequent sections, the dynamical system defined by the necessary conditions of the maximum p r i n c i p l e w i l l be studied extensively, and t h i s system, governed by equations 2.8 to 2.11 w i l l be referred to as the Optimal Dynamical System, or the ODS f o r short. By the term generating system for the ODS i s meant the o r i g i n a l dyna mical system defined by equation 2.4, where no st i p u l a t i o n s are made regarding performance functlonals. As w i l l become evident shortly, i t i s important to d i f f e r e n t i a t e between these two systems. The structure of the system i s now defined as the network of couplings between the objects which constitute the system. Clearly, the structure of the ODS i s p o t e n t i a l l y much more complex than the structure of the generating system. Therefore a successful decomposition technique must u t i l i z e a l l the information not only of the genera t i n g system structure, but also that of the ODS, In which the generating system i s embedded. The l o g i c a l t o o l f or studying system structure i s the branch of topology known as the theory of directed graphs £15} • The objective of applying t h i s theory to the study of the ODS i s to j u s t i f y the use of a l i m i t e d class of systems l n the subsequent sections dealing with decomposition. 2.3 Digraph Theory and the Optimal Dynamical System The subsequent discussion of the theory of directed graphs w i l l employ terminology i d e n t i c a l to that of r e f e  rence (l5} , Harary et al.A directed graph, henceforth referred to as a digraph, consists of two sets,the set of points and the set of l i n e s , each l i n e having associated with i t a d i r e c t i o n . To obtain the digraph of an ODS, a l l the variables x , p , and u * are considered as points. The l i n e s f or the digraph are obtained as follows. Since each of the components of x and p i s generated by a d i f f e r e n  t i a l equation, the l i n e s converging to a point w i l l be defined by the variables on the ri g h t hand side of the respective d i f f e r e n t i a l equation. For example, i f the * In the next section, some others are also included. d i f f e r e n t i a l e q u a t i o n g e n e r a t i n g i s g i v e n by p^ = f ( x 2 , x^, p ^ t h e n t o the node a s s o c i a t e d w i t h p^ w i l l come d i r e c t e d l i n e s f rom t h e nodes a s s o c i a t e d w i t h x 2 » x^, and p^ . I f f ( . ) were t o i n c l u d e p^ , l o g i c a l l y a s e l f - l o o p would be r e q u i r e d , but s i n c e t h e s e do not f u r t h e r the u n d e r s t a n d i n g o f the r e l a t i o n s h i p s between t h e v a r i a b l e s , t h e y w i l l be o m i t t e d . F o r each component o f u , t h e r e i s a r e l a t i o n s h i p r e q u i r i n g t h a t H be a maximum, and c o n s e q u e n t l y , the e x p l i c i t s o l u t i o n o f t h i s r e l a t i o n s h i p f o r t h e p a r t i c u l a r u component p r o v i d e s an a l g e b r a i c e q u a t i o n w h i c h i s used a n a l o g o u s l y t o o b t a i n t h e l i n e s o f the g r a p h . The d i g r a p h f o r the e n t i r e ODS t h e n c o n s i s t s o f t h e t o t a l i t y o f s u c h p o i n t s and l i n e s . I t i s noted t h a t the d i g r a p h t h u s o b t a i n e d i s I n many ways s i m i l a r t o a s t a n  d a r d b l o c k d i a g r a m . However, b l o c k diagrams a l r e a d y have a s s o c i a t e d w i t h them c o n c e p t s o f t r a n s f e r f u n c t i o n s and l i n e a r i t y , w h i l e t h e d i g r a p h i s much more g e n e r a l . The g e n e r a t i o n o f an ODS d i g r a p h i s now I l l u s t r a t e d w i t h some examples . Example 2.1 F i n d t h e f u n c t i o n s u and v w h i c h w i l l m i n i m i z e the f u n c t i o n a l T J = | J ( x 2 + y 2 + u 2 + v 2 ) d t ' 0 12 s u b j e c t t o x = - x + lOxy + u x(0) = x o y = x + v y(0) = y Q |u|$ U I v I ^ V The Hamiltonlan Is H = - | ( x 2 + y 2 + u 2 + v 2 )' + p(-x + lOxy + u ) + q( x .+ v ) Thus, the ODS w i l l be of the form x = - x + lOxy + u x(0) = x Q y = x + v y(0) = y Q u = U sat(p/U) v = V sat(q/V) p = x + p - lOyp - q p(T) = 0 q = y - lOxp q(T) = 0 where j 1 z > 1 sat(z) = < z -1« z « 1 cl z < -1 and the digraph w i l l be as follows: I t i s observed that t h i s digraph i s strongly connected. 13 Example 2.2 Choose u and v to minimize the functional T J = s J ( y 2 + u + v 2 ) dt o subject to x = -x 3 + u x (0)=x Q x(T) = 0 y = -y + v y (0)=y Q y(T) = 0 Thus H = -£( y 2 + u 2 + v 2 ) + p(-x 3 + u) + q(-y + v) If the digraph for t h i s ODS i s drawn according to the preceding rules, i t i s found to be t o t a l l y disconnected, and th i s of course Implies that two independent optimization problems are being considered. However, these problems are not en t i r e l y independent, since they are connected through the parameter T and the requirement that both subsystems reach the o r i g i n at the same time. This interconnection i s indicated l n the above graph by means of the dotted l i n e s . 14 Thus, the o v e r a l l graph remains connected, but not strongly connected as i n the previous example. Example 2.3 Again, f i n d u and v to minimize T J = | J ( x 2 + y 2 + Z 2 + u 2 + V 2 )dt O subject to x = -xz + u y = -yz + v z = -z Application of the maximum p r i n c i p l e y i e l d s u = p v = q p = x + pz q = y + qz f = p x + q y + r + z The basic digraph for th i s ODS has a source and a sink, 15 and Is, therefore , again not strongly connected. A look at the generating system reveals i t to be uncontrollable. In f a c t , i t i s easy to show that a necessary condition for the c o n t r o l l a b i l i t y of the generating system i s that the basic, digraph of the ODS, composed of x , p and u , have no sources or sinks. It i s further noted , however, that the optimization problem fo r t h i s example i s well-defined and has a unique solution. The foregoing examples i l l u s t r a t e how the structure of an ODS can be represented i n terms of a digraph. I t i s e v i  dent that some transformations of state variables can pro foundly a f f e c t the i n t e r n a l structure and hence the digraph of the system. However, because these transformations leave the input-output description of the system invariant, and be cause the synthesis i s concerned mainly with t h i s description and i t s associated structure, the o r i g i n a l r e s t r i c t i o n to t h i s unique description of the system i s j u s t i f i e d . The basic shortcoming of digraphs i s the lack of capacity or values on the l i n e s , and t h i s prohibits quantitative state ments regarding the system structure. This shortcoming can not be overcome i n the case of systems with n o n l i n e a r l t i e s and therefore, only q u a l i t a t i v e conclusions can be drawn. The next section describes how these q u a l i t a t i v e conclusions are employed to effect ODS decomposition. 16 2.4 Decomposition The Oxford dictionary defines decomposition ©screak ing down into i t s constituent parts." The objective of t h i s section i s to i d e n t i f y constituent parts of an ODS, and then, with the aid of digraph theory, attempt conceptually to break the optimization problem into smaller sub-problems. As w i l l become evident shortly, the natural constituent parts of an ODS do not necessarily coincide with the sub systems which make up the generating system. In order to i l l u s t r a t e decomposition, consider the following example. Example 2 .4 Find u and v which w i l l minimize the functional T „ _ 2 , 4- IT- 2 4- 9 C v v 4- n 2 a - ir2 o subject to J = | 5 + y + 2 £ xy + u^ + v 2 )dt ± = -5x + ey + u x(0) = x Q y = -7y + y 3 - 3&x + v y(0) = y The maximum p r i n c i p l e y i e l d s u = p v = q where p = x + £y + 5p + 3&q p(T) = 0 q = y + ex - ep + 7q - 3y 2q q(T) = 0 The digraph f o r t h i s ODS i s o 1? It i s noted that although the generator systems for examples 2.1 and 2.4 are d i f f e r e n t , the ODS's have i d e n t i c a l struc tures. I t i s evident that the digraph has a high degree of connectivity, and because the l i n e s have no capacities asso ciated with them, the job of i s o l a t i n g constituent parts on the digraph i s d i f f i c u l t . However, i f i t i s known that £ represents a small quantity, and since a l l the l i n e s crossing the dotted l i n e are weighted by £ , then It would appear that the obvious choice f o r the ODS constituent parts would consist of (x,u,p) and (y,v,q) .Both of these constituent parts are strongly connected, and with £ = 0 , define meaningful optimization problems. This l a t t e r underlines the f a c t that t h i s writer has f a i l e d to f i n d any problem i n which i t i s useful to consider an output variable and i t s associated adjoint variable i n d i f f e r e n t constituent parts. This tends to corroborate the hypothesis that i f an o p t i  mization problem lends I t s e l f to successful decomposition, i t must be b u i l t up from a number of interconnected o p t i  mization problems, each of which can be made meaningful when considered alone. Now, of course, the concepts of decomposition can be applied just as well to the generating system as to the ODS, and i n f a c t , t h i s i s done i n papers dealing with m u l t i - l e v e l systems, aggregated systems and so f o r t h . There i s no harm i n t h i s , p r o v i d e d one i s not c o n c e r n e d w i t h a s p e c i f i c o p t i m i z a t i o n problem. The f o l l o w i n g somewhat s i m p l e - minded example u n d e r l i n e s t h e d i f f e r e n c e s between decomposing t h e g e n e r a t i n g system and the ODS . Example 2 . 5 C o n s i d e r a g e n e r a t i n g system w i t h t h e dynamics x = f ( x ) + c y + u y = g(y) + £x + v z = -z '+ w w h i c h g i v e s as a d i g r a p h R -N R - " - - \ v J V -J I f t h e o b j e c t i v e o f d e c o m p o s i t i o n were t o choose two subsystems w h i c h had t h e l e a s t amount of i n t e r a c t i o n b e t  ween them, t h e n the o b v i o u s c h o i c e , c o n s i d e r i n g o n l y t h e g e n e r a t i n g system, would be as I n d i c a t e d by t h e d o t t e d l i n e s above. However, i f t h e problem were t o f i n d , as w e l l , t h e f u n c t i o n s u, v and w such t h a t , s u b j e c t t o t h e above d y n a m i c a l c o n s t r a i n t s , t h e f o l l o w i n g f u n c t i o n a l was m i n i  mized : 19 J then H and u where P q r and the ODS digraph would be as follows: I f the o r i g i n a l objective i n decomposition i s retained and i f £ i s smaller than ^ ,the natural decomposition appears as shown. In s t r i v i n g for decomposition, i t i s evident that the objectives of decomposition d i f f e r somewhat between the com putational problem, and the on-line synthesis problem. However l n both problems the f i r s t step i s to group sets of input T o o 2 2 o a- S ii(y-z) + xc + u + v + w^  } dt = -s £l(y-z) 2 + x 2 + u 2 + v 2 + w2 } + p(f(x) + £y + u) + q(g(y) + cx + v) + r ( - z + w) = p v = q w - r x - — P - t q bx "\ (y-z) - £P - — q z>y &g = - ^ ( y-z) + r and output variables to be considered as sub-systems. Be cause r e l a t i v e l y few res u l t s are available for the synthesis problem i n general, the usefulness of the digraph to th i s problem i s li m i t e d , except perhaps i n the negative sense, that i f the digraph Is strongly connected to a high degree of connectedness, and i f i t appears that the connections have strong influences, then i t may be wiser to sythesize an Integrated, c e n t r a l i z e d c o n t r o l l e r . Also, for thi s reason, the h i e r a r c h i c a l synthesis problem i n part 4 i s r e s t r i c t e d to a spe c i a l class of systems, whose digraph i s rather t r i v i a l . The objective of decomposition with computational problems w i l l be discussed further i n part 3 , but here i t su f f i c e s to say that one of the goals i s multi-processing. However, because the digraph of an ODS Is i n general stron gly connected, the standard TPBVP i s Incompatible with multi-processing. The i d e a l structure f o r thi s i s a num ber of p a r a l l e l paths, but since that i s an u n r e a l i s t i c goal, then weak connectedness i s acceptable. In fact, the next part of the thesis w i l l cover a number of techniques which reduce to adding more nodes to the ODS digraph and then restructuring i t from the undesirable strongly con nected configuration to a more desirable , weakly connec ted, sink-source configuration. 3 . DECOMPOSITION AND COMPUTATIONAL ALGORITHMS . I n t r o d u c t i o n A major segment of o p t i m a l c o n t r o l t h e o r y concerns t h e n u m e r i c a l c o m p u t a t i o n of t h e f u n c t i o n r e p r e s e n t i n g t h ODS t r a j e c t o r y , and t h i s f u n c t i o n i s r e q u i r e d t o a h i g h degree of a c c u r a c y i n o f f - l i n e o p t i m a l g u i d a n c e problems. T h i s emphasis on a c c u r a c y may be c o n t r a s t e d w i t h t h e on l i n e c o n t r o l problems, t r e a t e d In p a r t 4 , w h e r e i n t h e paramount c o n s i d e r a t i o n i s t h e c o m p u t a t i o n t i m e . Neverthe l e s s , i n g u i d a n c e problems o f any c o m p l e x i t y , t h e compu t a t i o n t i m e a c q u i r e s t h e second most i m p o r t a n t p o s i t i o n , s i n c e i t u l t i m a t e l y d e t e r m i n e s t h e p r a c t i c a l f e a s i b i l i t y o f a p a r t i c u l a r s o l u t i o n . T h e r e f o r e , i n t h i s s e c t i o n , de c o m p o s i t i o n i s c o n s i d e r e d n o t o n l y as an a t t r a c t i v e pos s i b i l i t y f o r s i m p l i f y i n g t h e n u m e r i c a l p r o c e d u r e s , but as a means o f a c h i e v i n g g r e a t e r c o m p u t a t i o n a l speed. The o b j e c t i v e , t h e n , i s t o s u b - d i v i d e t h e o r i g i n a l c o m p u t a t i o n a l problem i n t o s m a l l e r , and h o p e f u l l y s i m p l e r sub-problems, p r e f e r a b l y chosen i n such a way t h a t each can be s o l v e d r e l a t i v e l y i n d e p e n d e n t l y o f o t h e r s . F o r example, dynamic programming o f f e r s what might be termed t e m p o r a l d e c o m p o s i t i o n , i n t h a t a t each s t a g e ( i n t i m e ) , t h e s o l u t i o n o f a s i m p l e problem i s r e q u i r e d . C l o s e l y c o n n e c t e d w i t h dynamic.programming i s t h e t e c h n i q u e , hope l e s s l y complex f o r d y n a m i c a l systems, f o r o p t i m i z i n g a system with cascaded structure, as described by Fan et a l j l Although these achieve the goal of simplifying the numeri c a l procedures, they are impractical because of excessive computer memory requirements. I f memory i s extended to i n  clude tapes, then of course, computation time becomes im p r a c t i c a l . Naturally, no decomposition scheme i s acceptable i f the time required to sequentially solve the set of sub- problems exceeds the solution time of the o r i g i n a l integra ted problem, assuming that some algorithm exists for doing so. In f a c t , the primary reason f o r considering decompo s i t i o n i s the p o s s i b i l i t y of discovering situations where the smaller sub-problems can be solved simultaneously,the reby o f f e r i n g a p o t e n t i a l l y s i g n i f i c a n t decrease i n t o t a l computation time, i f suitable multi-processing computers are av a i l a b l e . Consequently, t h i s part of the thesis be gins with a b r i e f discussion of the nature of par a l l e l i s m i n numerical algorithms. Then, some algorithms which pos sess an inherent high degree of pa r a l l e l i s m are described and an attempt i s made to define the s t r u c t u r a l properties of the control problems which would allow e f f i c i e n t use of this p a r a l l e l ism. 3.1 P a r a l l e l i s m i n Computational Algorithms When formulating a sequential numerical algorithm, one does not f e e l obliged to consider many r e s t r i c t i o n s a r i s i n g from the fact that a computer, w i l l eventually pro cess the algorithm. In the case of par a l l e l i s m , t h i s s i  tuation i s reversed, and because such a variety of multi processing machinery i s possible, there i s a strong temp t a t i o n to t a i l o r algorithms to s p e c i f i c computer config urations. This tendency i s undesirable i f one wishes to achieve any generality with the proposed algorithm. Consequently, the discussion of proposed and actual multi-processing hardware has been relegated to Appendix B, while some universal aspects of para l l e l i s m , indepen dent of hardware, are considered here. P a r a l l e l i s m can be c l a s s i f i e d into four l e v e l s . The lowest occurs at the b i t l e v e l , and consists of p a r a l l e l l o g i c and arithmetic hardware incorporated into most present-day high-speed computers. This l e v e l w i l l not be considered any further i n t h i s thesis. The next l e v e l i n  volves p a r a l l e l i s m of i n d i v i d u a l i n s t r u c t i o n s , and might be considered as the d i g i t a l counterpart of an analogue computer, i n that a l l instructions which can be perfor med simultaneously w i l l be. Although t h i s concept may become fe a s i b l e i n the future, present day hardware and s o f t - w a r e l i m i t a t i o n s p r e c l u d e t h i s from p r a c t i c a l c o n  s i d e r a t i o n s , except i n v e r y l i m i t e d f o r m , such a s " n - s t e p look-ahead ' , ' i n c o r p o r a t e d i n some l a r g e , modern computers . The t h i r d l e v e l , which w i l l be emphasized s u b s e q u e n  t l y , i s p a r a l l e l i s m among s u b - r o u t i n e s , or groups of I n s t r u c t i o n s , a l l a s s o c i a t e d w i t h a s i n g l e , o v e r a l l p r o  b l e m . I t i s assumed t h a t the programmer i n s e r t s FORK and JOIN [I?] , [ l8 l i n s t r u c t i o n s i n t o the program, thereby e s  t a b l i s h i n g the p o s s i b l e e x t e n t o f the s u b r o u t i n e p a r a l l e  l i s m . On e n c o u n t e r i n g the FORK i n s t r u c t i o n , t h e e x e c u t i v e program a l l o c a t e s f r e e p r o c e s s o r s to t h e d e s i g n a t e d p a r a l  l e l s t r e a m s , but i f the number o f s t reams exceeds the num b e r o f f r e e p r o c e s s o r s , some streams w i l l be executed s e q u e n t i a l l y . I t i s a p p a r e n t , t h e r e f o r e , t h a t f o r an e f f i  c i e n t m u l t i - p r o c e s s i n g computer , the e x e c u t i v e program must be h i g h l y e l a b o r a t e . F u r t h e r m o r e , i n o r d e r to make e f f i c i e n t use o f t h i s p a r a l l e l c a p a b i l i t y , the s u b r o u t i n e s must be chosen so t h a t the e x e c u t i v e program t ime r e q u i r e d per s u b - r o u t i n e i s s m a l l i n c o m p a r i s o n t o the s u b - r o u t i n e r u n n i n g t i m e . The h i g h e s t l e v e l o f p a r a l l e l i s m i s t h a t between i n d e pendent programs. K u l t l - p r o c e s s o r s u t i l i z i n g t h i s r a t h e r t r i v i a l form of p a r a l l e l i s m a r e w e l l on t h e i r way to com m e r c i a l r e a l i t y , and a g a i n , t h i s form w i l l not be d i s c u s  sed any f u r t h e r . The w i d t h of the c o m p u t a t i o n f r o n t at any g i v e n t i m e , c o n s i d e r i n g p a r a l l e l i s m of type 3 , i s d e f i n e d as the num ber o f p a r a l l e l streams emanating from the l a s t FORK i n s  t r u c t i o n which have not y e t been combined by a J O I N . I t i s e v i d e n t t h a t i n d e v e l o p i n g a l g o r i t h m s , t h e r e Is n o t h i n g t o be g a i n e d by making the w i d t h o f the c o m p u t a t i o n f r o n t exceed t h e t o t a l number of p r o c e s s i n g elements i n the com p u t e r . When d e a l i n g w i t h o p t i m a l c o n t r o l p r o b l e m s , by f a r the g r e a t e s t p r o p o r t i o n of t ime i s consumed i n r e p e a t e d i n t e g r a t i o n s of d i f f e r e n t i a l e q u a t i o n s . I n f a c t , s i n c e u s u a l l y 2n e q u a t i o n s must be i n t e g r a t e d , where n i s t h e d i m e n s i o n of the s t a t e space of the s y s t e m , t h e r e a r i s e s t h e p o s s i b i l i t y of u s i n g 2n (or more) p r o c e s  s i n g elements i n p a r a l l e l t o o b t a i n each i n t e g r a t i o n s t e p . However, because of the r e l a t i v e l y few o p e r a t i o n s i n v o l  ved i n each s t e p , t h i s a p p r o a c h must be r e j e c t e d as the e x e c u t l v e / s u b - r o u t i n e t ime r a t i o p r o b a b l y becomes e x c e s  s i v e . M o r e o v e r , i f n Is l a r g e , t h i s a p p r o a c h would r e  q u i r e a n o n - c o n v e n t i o n a l computer , as d e s c r i b e d i n A p  p e n d i x B . An a l t e r n a t i v e i s to choose groups of e q u a t i o n s , and i n t e g r a t e these groups i n p a r a l l e l , u s i n g f o r I n t e r a c t i o n s some a p p r o p r i a t e i t e r a t i o n i n f o r m a t i o n . S i n c e t h i s a p p r o a c h i s I t e r a t i v e , i t would appear t h a t i f N groups are c h o  sen t o be i n t e g r a t e d i n p a r a l l e l , s i g n i f i c a n t g a i n s In 26 c o m p u t a t i o n speed c o u l d be a c h i e v e d o n l y i f t h e r e q u i r e d number of i t e r a t i v e i n t e g r a t i o n s were l e s s t h a n N . How e v e r , as w i l l be shown, t h i s r e q u i r e m e n t can be r e l a x e d somewhat, s i n c e t h e s e i n t e g r a t i o n i t e r a t i o n s can be com b i n e d e f f e c t i v e l y w i t h t h o s e a r i s i n g from t h e TPBVP . These b r i e f comments on p a r a l l e l i s m i n a l g o r i t h m s end t h i s d i s c u s s i o n , and some s p e c i f i c c a s e s of o p t i m a l c o n t r o l problem co m p u t a t i o n a r e next c o n s i d e r e d i n o r d e r t o i l l u s t r a t e t h e p o t e n t i a l of m u l t i - p r o c e s s i n g . 3 .2 G e n e r a l i z e d P l c a r d A l g o r i t h m As a l r e a d y mentioned, the well-known c l a s s i c a l met hod of d e c o u p l i n g a set of e q u a t i o n s i s t o employ i t e r a  t i o n . Thus, i n s t e a d of s o l v i n g t h e a c t u a l e q u a t i o n s , one s o l v e s a d i f f e r e n t s e t , dependent on a p r e v i o u s i t e r a t i o n . I n t h e case of the ODS , a v e r y o b v i o u s d e c o u p l i n g and i t e r a t i o n scheme, based on a g e n e r a l i z a t i o n of t h e P i c a r d i t e r a t i o n f o r d i f f e r e n t i a l equations; i m m e d i a t e l y a r i s e s . T h i s w i l l be i l l u s t r a t e d w i t h t h e f o l l o w i n g example. Example 3 « 1 Assume t h a t the a p p l i c a t i o n of t h e maximum p r i n c i p l e t o some o p t i m i z a t i o n problem has g i v e n r i s e t o t h e f o l  l o w i n g TPBVP : x = f-^x.y.u) x ( 0 ) = x Q y = f 2 ( x , y , v ) y(0) = y Q u = u(x,p) v = v(y,q) p. = Bi U . p . q ) ' p(T) = 0 q = g 2 ( y . p . q ) q(T) = 0 This TPBVP i s reformulated as k = f 1(x,y^,u) x(0) = x 0 y = f 2(x*,y,v) y(0) = y Q u = u(x,p) v = v(y,q) P = g^x.p.q*) P(T) = 0 q = g2(y.p*.<i) <i(T) = 0 whre x* f y*, p* and q* are functions obtained at a pre vious i t e r a t i o n . Naturally, i t i s assumed that some st a r  t i n g i t e r a t e can somehow be chosen. The digraph f o r t h i s second system i s therefore a source-sink configuration as i l l u s t r a t e d : This approach provides both a weakly connected ODS structure, and a p a r a l l e l i s m of type 3 with a computa ti o n front width acceptable to conventional multi-pro cessing computers. Furthermore, l n p r i n c i p l e , there are no r e s t r i c t i o n s on the a p p l i c a b i l i t y of the method, and non l i n e a r as well as l i n e a r problems can be handled. However, severe d i f f i c u l t i e s can be encountered i n choosing good i n  i t i a l i t e r a t e s , and consequently, a simple-minded a p p l i  cation of the method may lead to unsatisfactory rates of convergence, as reported by Takahara [19] . Another objec t i o n against the method i s that being a generalized Plcard algorithm, i t also has a c h a r a c t e r i s t i c slow rate of con vergence i n comparison to Newton-Raphson algorithms. Never theless, l a t e r i n t h i s section, i t w i l l be shown that by introducing a number of modifications, the method has im portant p r a c t i c a l s i g n i f i c a n c e f o r some classes of prob lems. Before this,. however, some other approaches, some what more elegant t h e o r e t i c a l l y , though of l i t t l e Import as p r a c t i c a l computation schemes, w i l l be considered. 3 * 3 Decomposition Algorithm Based on Duality Probably the best known and rather aesthetic algorithm concerned with decomposition and optimal control theory i s that derived by J.D.Pearson [20] [21] , based on duality and the Legendre transformation of the calculus of v a r i a  tions [ 2 2 ]. Of a l l the techniques considered i n t h i s t h esis, t h i s one bears the closest resemblance to the Decomposi t i o n P r i n c i p l e for Linear Programs, as discussed i n Dantzig and Wolfe [ 3 ] . Although t h i s l a t t e r p r i n c i p l e has enjoyed some degree of success, there does not appear to be any way of extending i t to optimization problems with dyna mical constraints, as considered here. The technique of Pearson, though s i m i l a r , has wider a p p l i c a b i l i t y but Is also a f a r weaker numerical algorithm. For the sake of complete ness and for purposes of comparing the resultant digraph structure with the other algorithms, Pearson's technique i s Included here. For i l l u s t r a t i v e purposes, consider the optimization problem of fi n d i n g u and v which minimize T J = I 5 ( x 2 + y 2 + u 2 + v 2 )dt 3.1 o subject to x = a11x + a 1 2 y + u x(0) = 3.2 y = a 2 1 x + a 2 2 y + v y(0) = ja 3-3 x e Q 1 y £ Q2 where and Q 2 are closed, bounded, convex sets. That i s , the problem concerns a l i n e a r system with a quad r a t i c performance functional, and, very importantly, boun ded state variables. By introducing y = r 3.4 x = s 3.5 the dynamical constraints can be re-written as x = a ^ x + a ^ 2 r + u 3.6 y = a 2 j s +' a 2 2 y + v 3.7 The o r i g i n a l problem can then be reformulated as 30 f i n d i n g the minimum of J , s u b j e c t to c o n s t r a i n t s 3.4 t o 3.7 . F o r m i n g the L a g r a n g i a n , 1 X 2 o p L(x , y , u , v f p l f p 2 , s f r,X , t * ) = liHx2 +• y + u 2 + v ) + Pi (x - a ^ x - a 1 2 r - u) . + p 2 (y - a 2 i s - a 2 2 y - v) + M y - r ) + ^ ( x - s) } d t t h e problem r e q u i r e s t h e e x t r e m i z a t i o n of L s u b j e c t t o x (0) = « , and y (0 ) = p , X j S e Q j , y , r e Q 2 . Now L c o n v e n i e n t l y b r e a k s up i n t o two p a r t s , L = L 1 ( x , u , p 1 , r , X , ^ ) + L 2 ( y , v , p 2 , s , X , f * ) where L l = S I s ( x 2 + u 2 ) + p 1 (x - a 1 1 x - a 1 2 r - U ) + ( X J A - Xr)]dx o T 2 2 L 2 = J { _ § ( y + v ) + p 2 (y - a 2 i s - a 2 2 y - v ) + ( y X - ^s)]d-c o C o n d i t i o n s which r e q u i r e L t o be a t an e x t r e - mum a l s o r e q u i r e t h a t b o t h and be a t an extremum. T h i s r e q u i r e m e n t l e a d s t o t h e c o n c l u s i o n t h a t t h e r e e x i s t two s u b - p r o b l e m s , s i m i l a r i n form to the o r i g i n a l , w h i c h , when s o l v e d , l e a d t o t h e s o l u t i o n of the o r i g i n a l . T h u s , f o r a g i v e n X and , b o t h L 1 and can be e x t r e m l z e d as L * = L*( X , p.) L * = Lg( X , ) T h e n , u s i n g the w e l l - e s t a b l i s h e d s a d d l e p o i n t arguments i n Banach space,[23} , i t f o l l o w s t h a t L * = max [ L|( X , ) + Lg( X , ^  ) 31 I t Is noted that i n the case of the sub-system ext- remizations, s and r are treated as sub-system controls, while X and -^ are arbit r a r y functions.. Thus, for example, the f i r s t subsystem problem i s , given >. and f-»- , mi nimize with respect to u and r , T J1 = h \ l ( x 2 + u 2) + 2(^x _ x r ) } d t o subject to k = &ux + a 1 2 r + u x(0) = <x x £ Qj^  , r e Q 2 The ODS generated by th i s sub-problem i s x = a ^ x + a 1 2 r + u x(0) = °^  P X= x - a n p x + ^ P 1(T)= 0 u = P! r = r ( p l t X) where the equation for r i s obtained by maximizatition of the sub-system Hamlltonian with respect to r , subject to the condition that r be i n Q 2 . The digraph f o r this entire system again has the desirable property, namely two strongly connected subgraphs, connected together weak l y , as shown i n the following diagram: Therefore, i d e a l l y , the extrema of the two sub-systems are obtained as functions of X and ^ , and the sum then maximized. However, since X and are elements of a function space, such e x p l i c i t functional representations are impossible to obtain i n practice. Realizing t h i s , Pear son has suggested a h i l l - c l i m b i n g scheme, where one begins with some a r b i t r a r y * and (-»• , obtains L| and L* , and proceeds h i l l - c l i m b i n g i n the conventional manner. While t h i s suggestion i s v a l i d , i t i s very questionable whether the method w i l l ever be a t t r a c t i v e computationally, since each step i n the h i l l climb requires the solution of v a r i a t i o n a l problems, and h i l l - c l i m b i n g techniques are not noted f o r t h e i r f a s t convergence. The other major objection to this theory Is that i t i s v a l i d only for l i n e a r systems with quadratic performance c r i t e r i a , since the duality theorem has only been estab l i s h e d f o r the case of b i l i n e a r functionals on a Banach space, subject to l i n e a r constraints. Furthermore, as this problem has the very a t t r a c t i v e solution formulated by Kalman, the p r a c t i c a l usefulness of t h i s dual theory i s questionable. I t i s not known whether the theory can be extended to more general, problems. Also, before leaving t h i s technique, mention must be made of the bounded state variable requirement. In f a c t , this requirement i s not necessary, and when absent, some form of juggling, as i n reference \2k] , can sometimes solve 33 the problem. However, i t i s noted that, i n contrast to other methods, the boundedness requirement i s not merely an extension of the a p p l i c a b i l i t y of the theory, but r a t  her a constraint, which can sometimes, but not always be circumvented. 3.4 Decomposition Using Penalty Functions A decomposition scheme, based on penalty functions, has been suggested as another p o s s i b i l i t y . The method i s i l l u s t r a t e d f o r the same problem as i n the previous sub-sec t i o n , although t h i s does not imply a r e s t r i c t i o n to l i n e a r systems with quadratic/performance c r i t e r i a . The problem i s to minimize 3.1 subject to 3.2 and 3.3 . Again, 3.^ and 3«5 are introduced, and the dynamical constraints are rewritten as 3.6 and 3«? . Now the o r i g i n a l performance functional i s augmented using penalty functions i n the following manner: T JN = J + iIFrH<x-s*)2 +rL2<y-r*>2 + r ^ f r - y * ) 2 + ^ ( s - x * ) 2 ] dt o J 3.8 where the variables with the ast e r i s k s w i l l be consi dered as the respective previous i t e r a t e s . Thus, i f the i t  erative scheme were to converge, the penalty functions would approach zero, and J " N — » - J . It i s observed that i f con s t r a i n t s 3.4 and 3.5 are neglected, and i f fixed values are chosen f o r the vector fJ. , then minimization 3 4 of 3 . 8 with respect to u, v, r and s subject to con s t r a i n t s 3 . 6 and 3 - 7 consists of two independent pro blems. The ODS s h a l l be demonstrated only for one. That i s , f i n d u and r which minimize I t i s noted that t h i s method allows freedom i n the choice of p a r t i c u l a r penalty functions so as to Impose functional convexity i n both u and r , as opposed to the approach by Pearson, x^here, as mentioned, d i f f i c u l t i e s can a r i s e i f the problem i s not o r i g i n a l l y formulated with bounded state variables. Now, the ODS for t h i s sub-problem i s : J ! = L>2 + u2 +p,(x-s*)2 + fVr-y*) 2] dt o subject to x(0) = o< x a l l x + a 1 2 r + u x + |-\(x-s*) x(0) = °< P i P t(T)= 0 u = Pi r = y* + i ( a 1 2 P i ) The o v e r a l l system digraph i s : 1 S u b - fe^stem "2 I t i s evident that t h i s structure i s a combination of the two previous structures, and i t i s i n t e r e s t i n g to compare i t to the others. To begin with, i t appears that i n contrast to the generalized Picard method, th i s tech nique does not require an I n i t i a l p - vector to serve as a source. In addition, since a f t e r convergence, r and s should approach y and x respectively, i t might be somewhat easier to choose a s a t i s f a c t o r y I n i t i a l i t e r a t e . Consider now the r o l e of the JJ.- vector. From the calculus of va r i a t i o n s , I t Is known that the solution to the o r i g i n a l problem requires i n f i n i t e values for |^  . Also, substitutions show that i n f a c t the four components can not be independent, i f . the solution to the o r i g i n a l problem i s to be attained, but rather the following r e l  ationships should hold: m = These two considerations indicate that perhaps by s a t i s f y i n g the above relationships at some suitably large values of ^ ^ and rv 2 » a s o l u t i o n a r b i t r a r i l y near the optimum could be obtained. Since p.' represents a measure of the e f f e c t i v e coupling between the sub-systems, i t may be expected that for small values of , convergence can be obtained rather quickly, and then with these values f o r x and y as I n i t i a l i t e r a t e s , l a r g e r v a l u e s o f p. can be p r o g r e s s i v e l y c o n s i d e r e d u n t i l a p r a c t i c a l i n f i  n i t y i s o b t a i n e d . A l t h o u g h some s u c c e s s has I n f a c t been o b t a i n e d w i t h a s l i g h t m o d i f i c a t i o n o f t h i s a p p r o a c h , t h e f o l l o w i n g argument s h o u l d demonstrate the weaknesses of o f t h e method i n t h e g e n e r a l c a s e . A l t h o u g h i n t h e n u m e r i c a l c o m p u t a t i o n , t h e e q u a t i o n s r e p r e s e n t i n g t h e ODS as a l r e a d y shown, would be used, t h e f o l l o w i n g e q u a t i o n s i l l u s t r a t e from an a l t e r n a t i v e v i e w  p o i n t what i s a c t u a l l y b e i n g computed. A f t e r some s u b s t i  t u t i o n , i t i s f o u n d t h a t the*TPBVP t o be s o l v e d i s x = a n x + a 1 2 ( y * + £, a 1 2 P j _ ) + Px x(0) = p l = x + r i ( x - s * ) ~ a l l p l P X ( T ) = 0 y = & 2 1 ( x * + | j a 2 1 P 2 ) + a 2 2 y + p 2 y(0) = (3 p 2 = y + r 2 ^ y " r * } " a22 p2 P 2 ( T ) = 0 But s i n c e r * and s* a r e o b t a i n e d from p r e v i o u s i t e r a t e s w h i c h a r e denoted by d o u b l e s u p e r s c r i p t s t h e TPBVP can be r e - w r i t t e n as x = a ^ x + a 1 2 ( y * + ^ 3 a 1 2 p l ^ + p l x(0)= <* P l = x + ^ ( x - [ x * * + ^a 2 1p2]") - a n P l P l( T ) = 0 y = a 2 1 ( x * + ^ a 2 1 p 2 ) + a 2 2 y + p 2 y(0)= (3 P 2= y + r - 2 ( y - [ y * * + j i 3 a l 2 p f l ) - a 2 2 P 2 P 2(T)=0 U s i n g j-k = J A ^ , | - L 2 = p. ^ , t h e s e e q u a t i o n s r e  duce t o : x ( o ) = << P 1(T) = 0 y(o) = (3 P 2(T) = 0 These equations, being an alternate representation of the algorithm, i l l u s t r a t e the d i f f i c u l t i e s i n the a p p l i  cation of t h i s technique. For small values of JU. , the terms with the J J . ' S i n the denominator can cause trouble, while f o r large values, the terms f^^(x-x**) and f* 2(y-y**) make the system extremely s e n s i t i v e , and computational errors very d i f f i c u l t to control. Before leaving t h i s section, i t should be pointed out that the penalty functions employed here for i l l u s t r a t i v e purposes are probably the simplest possible. Other more complex alternatives might be considered, the only res t r i c t i o n being that they r e t a i n the convexity properties previously mentioned. However, because of the li m i t e d success that other researchers have had with penalty func t i o n approaches i n other applications, i t i s f e l t that the chances for success with t h i s approach are not very high. = a„.,x + a y* + p. + — a 1 9 p. 11 12 1 F-i l d 1 Pi = y = P2 = x - a 1 1 p 1 - a 2 1 p | + ^ ( x - x * * ) ! 2 a 2 1 x * + a 2 2 y + P 2 + ^ * Z 1 V Z y - a 1 2 p * - a 2 2 p 2 + ^ 2 ( y - y * * ) 3.5 Parametric Trajectory Method (PART I ) In the previous sub-sections, three d i f f e r e n t compu t a t i o n a l algorithms have been discussed, and with each, d i f f i c u l t i e s i n t h e i r a p p l i c a t i o n have been pointed out. The f i r s t method, the generalized Picard algorithm, i s now reconsidered along with the introduction of some major modifications. This modified method, for reasons which w i l l become evident shortly, has been c a l l e d the Parametric Trajectory Method. The primary drawback with the generalized Picard method concerns the d i f f i c u l t i e s i n s e l e c t i n g convergent i n i t i a l i t e r a t e s . A class of optimization problems i s now defined for which a basic technique f o r circumventing t h i s d i f f i c u l t y can be obtained. Basic Problem: Consider the optimization problem of determining the control u which w i l l minimize the functional tf N • • J = S S [ g , ( x , f u . ) -:- eh. (x,u)j dt 0 1=1 1 1 1 . subject to the dynamical constraints * i = f i ( x 1 » u 1 ) + e l 1 ( x , u ) x, (0) = x, l xo i = 1,2,...N t f either free or f i x e d , x i(t f.) either free or fixed 39 where x^ i s an n^ - vector, the system output u^ i s an m^  - vector, the system control, or input x i s the composite n - vector, consisting of a l l x i u i s the composite m - vector, consisting of a l l u^ g^ and h^ are scalar functions f^ and 1 ^ are n^ - vector functions £l ^ are closed•convex regions of m^  -space N £ n = n n. ^ 1 i = l , 2 , . . . N 1=1 1 1 N £ m, = m m, > 1 • i = 1.2...N 1=1 1 x 6 i s the scalar decoupling parameter, and with no loss of generality, i t can be s t i p u l a t e d that the solution to the problem i s required at £ = 1, Define P( £> ) = The foregoing optimization problem as a function of the decoupling parameter Sol( & ) = The solution, as described by the functions u(t) and x(t) as well as p ( t ) , the adjoint composite variable, of the problem P( £ ). 40 W i th t h e s e d e f i n i t i o n s , t h e range of t h e a p p l i c a b i  l i t y o f t h e P a r a m e t r i c T r a j e c t o r y Method can be s t a t e d . R e s t r i c t i o n on B a s i c Problem; S o l ( e ) e x i s t s and i s unique t h r o u g h o u t the c l o s e d i n  t e r v a l [ 0 , l ] o f t h e parameter £ . An a l l encompassing statement o f n e c e s s a r y and s u f  f i c i e n t c o n d i t i o n s r e q u i r e d t o meet t h i s r e s t r i c t i o n , even i f t h a t were p o s s i b l e , i s beyond the range o f t h i s t h e s i s , and t h e i n t e r e s t e d r e a d e r I s r e f e r r e d t o a c u r r e n t s u r v e y a r t i c l e [ l2] where t h i s q u e s t i o n i s c o n s i d e r e d I n d e t a i l , and where a f u r t h e r l i s t o f r e f e r e n c e s i s p r o v i d e d . I t might be noted t h a t i n most p r a c t i c a l problems, i f t h e math e m a t i c a l m o d e l i n g has been done c o r r e c t l y , t h e s e g e n e r a l q u e s t i o n s r a r e l y a r i s e . However, i n t h i s p a r t i c u l a r c a s e , the problem o f e x i s t e n c e and u n i q u e n e s s i s not u n i m p o r t a n t , e s p e c i a l l y a t £. = 0, s i n c e P(0) i s i n r e a l i t y N comple t e l y I s o l a t e d sub-problems, and many systems problems l o s e t h e i r meaning when decoupled and t a k e n out o f t h e i r systems c o n t e x t . T h i s r e s t r i c t i o n , t h e r e f o r e , p r o v i d e s an i l  l u s t r a t i o n o f t h e h y p o t h e s i s made i n p a r t 2 o f the t h e  s i s , t h a t problems s u s c e p t i b l e t o d e c o m p o s i t i o n c o n s i s t o f m e a n i n g f u l i n t e r c o n n e c t e d sub-problems. R e g a r d l e s s o f whether t h e f o r e g o i n g r e s t r i c t i o n i s s a t i s f i e d o r n o t , C u l l u m [25j has shown t h a t under r e l a t i  v e l y m i l d c o n d i t i o n s , S o l ( t ) i s c o n t i n u o u s i n £ . The standard. Parametric Trajectory Method i s a mod i f i c a t i o n of the generalized Picard algorithm, based on the foregoing r e s t r i c t i o n and the continuity of Sol( £ ). Because P(0) consists of N independent sub-problems, i t i s anticipated that Sol(O) can be obtained more quickly and/or with considerably less e f f o r t than S o l ( l ) . * Having obtained Sol(O), £ i s increased by a factor to and Sol(O) i s used as an i n i t i a l Iterate at the new £ value. With &t s u f f i c i e n t l y small, this i n i t i a l i t e r a t e i s within the ( f i n i t e ) region of convergence, and Sol( £^) can be computed. This process i s then repeated for succes s i v e l y Increasing values of the parameter £ u n t i l 1 i s reached. Throughout t h i s process, z generates a discrete trajectory i n the soluti o n space, and this gives r i s e to the name of the algorithm. Figure 3.1, based on Example 3.2 to be discussed shortly, i l l u s t r a t e s one of these t r a j e c t o r i e s i n the i n i t i a l co-state space. I f the step s i z e l n £ i s taken to be too large, the previous solution no longer serves as a s a t i s f a c t o r y i n i t i a l i t e r a t e , and the next step does not converge. One can therefore imagine a hypothetical region of convergence around each solution point, as shovm i n Figure 3.1, and i f this region does not overlap the next solution point, smaller steps i n E. are required. * In fa c t , P(0) i s i d e a l l y suited for p a r a l l e l processing. h2 Figure 3 '1 Trajectory i n the i n i t i a l co-state space, Example "}.2 . The work of Cullum [25] ensures that i f r&ls chosen small enough, convergence i s obtained, but i t gives no information as to how small i n fact should be i n order to have a p r a c t i c a l computational algorithm. Unfortunately, as i n h i l l - c l i m b i n g methods, only computational experi ence serves as a guide f o r t h i s choice. However, i n order to increase the optimal step s i z e , the following modifica tions, using l i n e a r i n t e r p o l a t i o n , can be employed. Assume that Sol(£ ) has been obtained. Then, for -an i n i t i a l i t e r a t e for P ( £ n + 1 ) , instead of Sol( £ ), the f o l  lowing can be used: I n i t i a l Iterate = So.l(£ n) + e n ) . ( £ n + 1 --.&n) bSol( £ n ) This naturally requires the computation of , d £ which can be approximated by d S o l ( £ n ) ~ S o l ( e , n + in,) - S o l ( e . n ) bz, &£ where Se i s a very small change i n £ . Sol( e, + & t ) i s therefore obtainable i n at most two i t e r a t i o n s . If the problem i s being solved using a Newton-Raphson i t e r a t i o n i n the i n i t i a l adjoint variable space to n u l l the f i n a l adjoint variables, the following equivalent approach might be considered. Since the i n i t i a l state va ri a b l e s remain constant, the f i n a l adjoint variables can be written as P(T) = <?( P o,eO where ^ > ( p Q , £ ) i s a symbolic representation of the mapping * E 1 —* E n , P 0 £ E 1 1 i e £ e 1 and p(T) £ if1 , and p Q i s the i n i t i a l adjoint variable. Using Frechet derivatives, t h i s operator can be expanded up to f i r s t order terms <?(P 0,eJ = 6>(P 0 ne n) +<P P o l n(Po- PoA + <?e,U*n+I -«n> Assume that the correct p D n which w i l l n u l l p(T) at £ = £ n i s known, i . e c <P(P 0 . e n ) = o Then the l i n e a r approximation to p D which w i l l null. p(T) with 5 = Z-n+i i s given by Po = Po -OPp I i ^ n V ^ n n " ^ ) n+1 n o Since the operator ((P I ^ i s estimated (using d i f •Pb ferences) at each value of £ , t h i s interp.oration scheme re quires only the add i t i o n a l c a l c u l a t i o n of , which i s obtained i n one integration sweep. The decision whether to use a standard Parametric Trajectory Method or the l i n e a r i n t e r p o l a t i o n modification i s again d i f f i c u l t . While the i n t e r p o l a t i o n promises a larger e f f e c t i v e step size &£ , t h i r i s at the expense of a d d i t i o n a l computation. As demonstrated in the example at the end of the next section, the i n t e r p o l a t i o n did i n fact r e s u l t in a decrease i n the o v e r a l l computation time, but t h i s decrease was not s i g n i f i c a n t . However, as expected, the optimum step size was increased, and to a value which was hot only non-optimum fo r the standard method, but which did not even provide a convergent i t e r  ation f o r the standard method. 3.6 Parametric Trajectory Method (PART I I ) In the previous section, the Parametric Trajectory Method was introduced as a technique for circumventing the d i f f i c u l t i e s of choosing the i n i t i a l iterate with the generalized Picard algorithm. Although the method accom plished this task admirably, i t also eliminated the parallelism inherent in the algorithm, since neither the standard nor the interpolation modification is suited to multi-processing computers. In fact, i t is easy to show that the digraph for the standard Parametric Trajec tory Method, except at £- = 0, is strongly connected. A further modification is now proposed which retains the fa c i l i t y for the choice of the i n i t i a l i-terate, while at the same time being f u l l y applicable to multi-processing com puters . Because of the decoupled nature of P(0), Sol(0) can be obtained on a multi-processing computer. However, In order to compute Sol( each sub-system must have information about the Interaction functions, and this . requirement eliminates the usefulness of multi-processing. But, i f instead of the current interaction information, a l l sub-systems were to use available solutions at the previous £.-value, parallelism would be retained. Nat urally, the solution obtained thus at £ = £^ vrould then not be Sol( £-.,), but rather some approximation, whose quality would depend on how close the previous £ -value solution was to Sol( £^), and how closely the sub-systems are coupled. The original basic problem, sta ted on page 38 , is used to Illustrate these Ideas. The Hamlltonian for this problem is N N , H = - [ Z ( g * (x, ,u, ) +£h,(x,u)3] + S P 1 t f i ( x i , u 1 ) + 1=1 1=1 £ 1 1 ( X , U ) ] where Assuming that the fixed time, free end point problem is under consideration, the terminal conditions on p^ are: Pi(t f) = 0 Maximization of the Hamiltonian results in N N Hu< = " g i " e 2 ) + f ' p. + t Z l l / u i 1 u i j = 1 Ju i U i 1 j=i J U i and i t is assumed that this set of equations can be solved for u^. as u i = u i i ^ x i ' p i ^ + £ ^ i 2 ( x , p ) Substituting this expression for u^ in the state and adjoint equations provides the standard TPBVP: = fj.(x l f [ u i 1 ( x 1 , p 1 ) + £ui (x,p)]> + £ l i(x lu(x,p)) x i ( 0 ) = x p^tp = 0 h7 I f t h i s TPBVP were b e i n g s o l v e d by means of q u a s i  l i n e a r i z a t i o n [z6\, i t would be s u f f i c i e n t t o c o n s i d e r Sol(£ ) as t h e composi t e v e c t o r f u n c t i o n S o l ( £- ) ov e r t h e i n t e r v a l t £ [ 0 , t^] . I n o r d e r t o o b t a i n S o l ( O ) , because t h e problem i s d e c o u p l e d , N s m a l l e r TPBVP*s can be s o l v e d i n p a r a l l e l . Then, i n o r d e r t o r e t a i n p a r a l l e l i s m , and assuming f o r example, t h a t . 2 5 i s chosen as a s t e p s i z e i n ^  , i n s t e a d o f s o l v i n g f o r S o l ( . 2 5 ) , t h e f o l l o w i n g TPBVP i s s o l v e d : x i = f l < x i ' t u i 1 ( x i » P i ) + . 2 5 u l 2 ( S o l ( 0 ) ) ] ) + . 2 5 ^ ( 5 0 1 ( 0 ) ) ^ = gj_ - P i + . 25P(Sol (0 ) ) X i ( 0 ) = x, Pi ( t j ) = o where N r , T P ( S o l ( 0 ) ) = £ Lhl ( S o l(°)) - x i ( S o l ( O ) ) p,_0J J = l ° xi J x i U I f S o l ( O ) does not d i f f e r a p p r e c i a b l y from S o l ( . 2 5 ) , o r i f t h e £ terms have weak e f f e c t s , t h e s o l u t i o n t o t h i s p roblem, c a l l e d A p p r o x ( . 2 5 ) , does n o t d i f f e r a p p r e c i a b l y from S o l ( . 2 5 ) . At t h i s p o i n t , two p o s s i b i l i t i e s a r i s e . F i r s t , assuming t h a t A p p r o x ( . 2 5 ) i s a b e t t e r a p p r o x i m a t i o n t o Sol ( . 2 5 ) t h a n was S o l ( O ) , t h e above TPBVP can a g a i n be s o l v e d , but u s i n g i n s t e a d o f S o l ( O ) , Approx ( .25) . T h i s p r o c e s s , r e f e r r e d t o as P i c a r d c y c l i n g , c o u l d be c o n t i n u e d u n t i l Approx ( ,25) converges t o S o l ( . 2 5 ) . Then £ can be i n c r e a s e d t o . 50 , and t h e p r o c e s s r e p e a t e d w i t h Sol ( . 2 5 ) i n s t e a d of S o l ( O ) as i n t e r a c t i o n s . The second p o s s i b i l i t y i s t o assume t h a t t h e f i r s t Approx ( ,25 ) i s a s u f f i c i e n t l y good a p p r o x i m a t i o n t o S o l ( . 2 5 ) » i n c r e a s e £ t o .50 i m m e d i a t e l y , and s o l v e t h e new TPBVP w i t h Approx ( .25 ) i n t h e i n t e r a c t i o n p o s i t i o n . The p r o c e s s i s t h e n r e p e a t e d w i t h s u c c e s s i v e s t e p s i n £ and i f t h e e r r o r b u i l d - u p has n o t been extreme, P i c a r d c y c l i n g can t h e n be employed a t £ = 1 , t o o b t a i n S o l ( l ) . I t w i l l be shown i n t h e f o l l o w i n g n u m e r i c a l example t h a t t h i s p r o c e d u r e can r e s u l t i n a f a i r l y s u c c e s s f u l c o m p u t a t i o n a l a l g o r i t h m . Example J.2 I n o r d e r t o i l l u s t r a t e t h e f o r e g o i n g t h e o r y , a s a t e l  l i t e a n g u l a r v e l o c i t y c o n t r o l system I s c o n s i d e r e d . I n t h i s c a s e , i t i s assumed t h a t t h e r e a r e t h r e e i n d e p e n  dent c o n t r o l s a v a i l a b l e f o r s t a b i l i z i n g t h e t h r e e angu l a r v e l o c i t i e s , and c o n s e q u e n t l y , the problem i s t r e a t e d as a c o l l e c t i o n o f t h r e e sub-systems, c o u p l e d t o g e t h e r by t h e p r o d u c t s o f i n e r t i a terms. The problem i s t o choose u i n o r d e r t o m i n i m i z e t h e f u n c t i o n a l J = i- I — 2 --(.-1.0-x-i-+u|) -dt 0 1=1 s u b j e c t to the c o n s t r a i n t x = - x^ + e X 2 X 3 + u l x 1 (0 ) = 5 x 2 = - x 2 + £-2x^x-j + u 2 x 2 (0) =-5 xy= - x 3 - e ' 3 x 2 x 1 + u ^ x^(0) = 1 l u ^ 4 10 , i = 1, 2, 3 x ^ l ) a r e f r e e . W i t h t h e a i d of t h e Maximum P r i n c i p l e , t h i s o p t i m i  z a t i o n problem can be c o n v e r t e d to the f o l l o w i n g TP3VP: x l = - x 1 + fcXgX^ + 1 0 s a t ( p 1 / 1 0 ) x x ( 0 ) = 5 x 2 = - x 2 + £ 2 x 1 x ^ + 10 s a t ( p 2 / 1 0 ) x 2 ( 0 ) = -5 x 3 " - x^ - £ 3 x 2 x 1 + 10 s a t ( p ^ / 1 0 ) x 3 ( 0 ) = 1 p l = 10 x1 + pj^- £ ( 2 x ^ p 2 - 3x 2 p^) Pi ( D = 0 P 2 = 10 x 2 + p 2 - £ ( X 3 P 1 - 3x 1 p^) P 2 ( l ) = 0 *3 = 10 x 3 4- p 3 - £ ( x 2 p 1 + 2 x 1 ? 2 ) P 3 ( l ) = 0 where (y i f l y l ^ 1 1 i f y 1 -1 i f y ^ - 1 The parameter £. has been Included e x p l i c i t l y , but i t i s assumed that the o r i g i n a l problem requires a sol u t i o n with £. = 1 . C l e a r l y , the problem f a l l s i n to the basic category for the parametric trajectory method, since i t Is evident that a unique solution exists f o r a l l values of s i n the closed i n t e r v a l \0 , l\ . However, because of the d i s c o n t i n u i t i e s i n the r i g h t hand side of the equations, the e f f i c i e n t method of q u a s i - l i n e a r i z a t i o n i s inapplicable, and, therefore, a technique based on a Newton-Raphson algorithm on zeroing the f i n a l p - vector with the choice of the i n i t i a l p - vector was employed to ob t a i n the solution. The solutions were obtained \\sing- a l l the d i f  ferent modifications of the parametric trajectory method, and a comparison of the computer times i s provided i n Table 3.1 . These computer times r e f e r to the actual computation time with an IBM 7 0 4 4 com puter, and do not include compiling or assembly of the program. These times are rather s e n s i t i v e to factors such as the norms determining the conver gence of an i t e r a t i v e algorithm, and consequently, these numbers are to be considered as a confirmation of anticipated trends rather than as useful quanti t a t i v e data. A S t e p S i z e B No. o f Steps c D E F 1.0 1 no 51.2 142 . 0 123.6 conv .5 2 51.4 63.5 1 2 4 . 8 105.5 .33 3 62.7 99.6 1 4 1 . 4 83.3 .25 4 77.7 106.5 170.7 81 .2 .20 5 84 .3 123.2 - 85.8 .166 6 - - - 84 .9 . 1 4 3 7 - - - 89.3 T a b l e 3.1 : A comparison o f c o m p u t a t i o n t i m e s w i t h d i f f e r e n t m o d i f i c a t i o n s o f t h e P a r a m e t r i c T r a j e c t o r y Method, Example 3.2 , a l l t i m e s quoted i n seconds. Column A : S t e p s i z e i n parameter ^ . Column B: Number o f s t e p s i n p a r a m e t r i c t r a j e c t o r y . Column C : S t a n d a r d P a r a m e t r i c T r a j e c t o r y Method. Column D : S t a n d a r d Method w i t h L i n e a r i n t e r p o l a t i o n . Column E : P a r a l l e l m o d i f i c a t i o n , P i c a r d c y c l i n g a t each e s t e p . Column F : P a r a l l e l m o d i f i c a t i o n , P i c a r d c y c l i n g a t ^ = 1 . 52 F i g u r e 3 .2 and 3 . 3 i l l u s t r a t e the o p t i m a l t r a  j e c t o r i e s and the Lagrange m u l t i p l i e r s , r e s p e c t i v e l y , a t £ = 1 , w h i l e F i g u r e 3 . 4 d e p i c t s g r a p h i c a l l y the v a r i o u s c o m p u t a t i o n t i m e s . Here, the optimum s t e p s i z e s a re c l e a r l y e v i d e n t . In f a c t , t h e s e o c c u r r a t h e r l o g i c a l l y , i n t h a t the optimum s t e p s i z e s f o r the two s t a n d a r d t e c h n i q u e s t e n d t o be g r e a t e r t h a n t h o s e f o r t h e p a r a l l e l m o d i f i c a t i o n s . F o r the s t a n d a r d meth ods, as e x p e c t e d , t h e l i n e a r i n t e r p o l a t i o n i n c r e a s e s t h e optimum s t e p s i z e , and i n t h i s example, t h e o v e r a l l com p u t a t i o n time i s a l s o s l i g h t l y d e c r e a s e d . I n t h e case of p a r a l l e l methods, t h e s m a l l e s t optimum s t e p s i z e , as ex p e c t e d , was o b t a i n e d w i t h t h e t e r m i n a l c y c l i n g m o d i f i c a t i o n , and t h i s o c c u r r e d a t e = . 2 5 . U s i n g P i c a r d c y c l i n g a t each £ s t e p tended t o consume t o o much t i m e , and s i n c e t h e t e r m i n a l c y c l i n g was c a p a b l e of p r o d u c i n g convergence, t h i s m o d i f i c a t i o n seemed h i g h l y p r e f e r a b l e when c o m p u t a t i o n t i m e s were t a k e n i n t o c o n s i d e r a t i o n . I n comparing t h e o v e r a l l c o m p u t a t i o n t i m e s f o r t h e d i f f e r e n t methods, i t s h o u l d be mentioned t h a t a l l t i m e s were o b t a i n e d u s i n g a s t a n d a r d s e q u e n t i a l g e n e r a l purpose computer. I f a m u l t i - p r o c e s s i n g computer w i t h a t l e a s t t h r e e p r o c e s s o r s were a v a i l a b l e , and i f t h e e x e c u t i v e program d i d not use a s i g n i f i c a n t p r o p o r t i o n of t h e o v e r  a l l c o m p u t a t i o n t i m e , t h e n i t i s r e a s o n a b l e t o assume t h a t the p a r a l l e l m o d i f i c a t i o n s s h o u l d have t h e i r c o m p u t a t i o n 53 F i g u r e 3 .2 : O p t i m a l S t a t e T r a j e c t o r i e s , Example 3 .2 , &=1 54 F i g u r e 3.3 : O p t i m a l C o - s t a t e T r a j e c t o r i e s , Example 3.2 , £ =1 . COMPUTER TIME (SECONDS) 180\ 170 160 150 140 130 120 110[ 100 90 eo[ 70 60 sot 40 301 20 10 55 FIGURE 3-4 COMPARISON OF COMPUTATION TIMES WITH DIFFERENT MODIFICATIONS OF THE PARAMETRIC TRAJECTORY METHOD, EXAMPLE 3-2 © STANDARD PARAMETRIC TRAJECTORY METHOD & STANDARD METHOD WITH LINEAR INTERPOLATION • PARALLEL MODIFICATION, PICARD CYCLING AT E=1 ONLY # PARALLEL MODIFICATION, PICARD CYCLINC AT EACH e STEP _1 l_ 7 2 3 4 5 6 7 8 No OF STEPS 1-0 -5 -333 -25 -2 -166 -143 SIZE OF STEP -J £S» 56 COMPUTER TIME (SECONDS) 150- 140 130 120 110 100 90 60[ 70 50h 50 40 30 20 10 FIGURE 3-5 COMPARISON OF COMPUTATION TIMES, AS IN FIGURE 3 4, WITH PARALLEL MODIFICATIONS TIMES DIVIDED BY FACTOR 3 o STANDARD METHOD & STANDARD WITH LINEAR INTERPOLATION • PARALLEL WITH TERMINAL CYCLING 8 PARALLEL WITH CYCLING AT EVERY STOP 1 2 3 4 5 10 -8 -33 -25 2 6 7 8 No OF STEPS •166 143 SIZE OF STEP t i m e s c u t be a f a c t o r n e a r l y e q u a l t o t h r e e . T a k i n g t h i s t i m e d i v i s i o n f a c t o r t o be t h e i d e a l , three", "the!""hew com p u t a t i o n t i m e s a r e p l o t t e d i n F i g u r e J.5 . C l e a r l y , t h e r e l a t i v e m e r i t s o f t h e d i f f e r e n t methods t a k e on new p e r  s p e c t i v e . The s h o r t e s t c o m p u t a t i o n time i s now o b t a i n e d by t h e p a r a l l e l method w i t h t e r m i n a l P i c a r d c y c l i n g , and even t h e l e s s e f f i c i e n t method o f c y c l i n g a t each £• s t e p p r o v i d e s a l o w e r optimum c o m p u t a t i o n t i m e t h a n t h e s t a n  d a r d methods. Indeed, i t s h o u l d be p o i n t e d out t h a t t h i s p a r t i c u l a r example by no means r e p r e s e n t s a system w i t h weak c o u p l i n g , and i t i s s a f e t o assume t h a t i f t h i s were t h e c a s e , t h e improvements o f f e r e d by t h e p a r a l l e l methods would be even more s i g n i f i c a n t . F u r t h e r m o r e , as w i l l be shown by t h e a n a l y s i s i n t h e n e x t s e c t i o n , g r e a t e r impro vements i n computing t i m e s can a l s o be e x p e c t e d i f systems o f h i g h e r o r d e r a r e c o n s i d e r e d . 3.7 D i s c u s s i o n and C o n c l u s i o n I n t h e p r e v i o u s f i v e s e c t i o n s , v a r i o u s methods com p a t i b l e w i t h t h e s u b r o u t i n e t y p e o f p a r a l l e l i s m have been c o n s i d e r e d . The t h e o r y of d i r e c t e d g r a p h s , a l t h o u g h o f l i t t l e p r a c t i c a l computing s i g n i f i c a n c e h e r e , has been s u g g e s t e d as an u n d e r l y i n g and u n i f y i n g c oncept i l l u s t r a  t i n g t h e r e - s t r u c t u r i n g o f t h e d i f f e r e n t a l g o r i t h m s f o r use w i t h m u l t i - p r o c e s s i n g computers. A l l t h e methods d e s c r i b e d , except t h e s t a n d a r d p a r a m e t r i c t r a j e c t o r y method which i s not s u i t a b l e f o r — m u l t i - p r o c e s s i n g , - e s s e n t l a l i - y - a c h i e v e - t h e i r - p a r a - l l - e l - i - s m a t t h e expense of i n t e r - s u b s y s t e m i t e r a t i o n . I n o r d e r t o make t h e s e s t a t e m e n t s c o n c r e t e , t h e f o l l o w i n g e l a b o r a t i o n i s p r e s e n t e d . Assume t h a t a Newton-Raphson a l g o r i t h m r e  q u i r i n g i n t e g r a t i o n sweeps i s employed, and suppose the system under c o n s i d e r a t i o n c o n s i s t s o f N sub-systems, each r e p r e s e n t e d on t h e a v e r a g e , by n d i f f e r e n t i a l equa t i o n s . L e t I j ^ r e p r e s e n t t h e number of i t e r a t i o n s r e q u i  r e d t o s o l v e t h e o p t i m i z a t i o n problem u s i n g some i n t e g r a t e d f o rm of t h e a l g o r i t h m , and s i n c e [_( N n ) + N n ] e q u a t i o n s a r e t o be i n t e g r a t e d p e r i t e r a t i o n , t h e t o t a l s e q u e n t i a l s o l u t i o n t i m e , T^ , assuming a s i n g l e i n t e g r a t i o n o f one e q u a t i o n r e q u i r e s t ^ s e c o n d s , i s T A = (Nn) (Nn + 1 ) l 1 t i On t h e o t h e r hand, i f a m u l t i - p r o c e s s i n g computer i s a v a i l a b l e , assiime i t t a k e s I p i t e r a t i o n s t o o b t a i n a s o - l u t i o n u s i n g a p a r a l l e l a l g o r i t h m . S i n c e o n l y j n + n 3 e q u a t i o n s a r e t o be i n t e g r a t e d ( s e q u e n t i a l l y ) per i t e r a  t i o n , and assuming t seconds a r e r e q u i r e d f o r t h e i n t e  g r a t i o n of one e q u a t i o n , t h e t o t a l m u l t i - p r o c e s s i n g s o l u  t i o n t i m e , Tp , would be T p = n ( n + D l p t p The r a t i o o f t h e s e i s _Ip ( n + D = ' 3 . 9 N(Nn •+ 1 ) 1 ^ 59 I n t o t has been i n c o r p o r a t e d t h e f a c t t h a t t h e exe c u t i v e program i n a murti-pYocessor"'wourd""ta"ke'"-some-t--but h o p e f u l l y s m a l l , f r a c t i o n o f t h e t o t a l computing t i m e . Thus, t p can be r e p r e s e n t e d as t p = tj_( 1 + K ), where K s h o u l d be a s m a l l p o s i t i v e number. A l s o i t i s c l e a r t h a t I p would be s i g n i f i c a n t l y l a r g e r t h a n 1^ , s i n c e not o n l y a r e sub- problems b e i n g s o l v e d i t e r a t l v e l y , b u t t h e s e sub-problems must be i t e r a t l v e l y c o - o r d i n a t e d . I f i t i s assumed t h a t t p = t ^ , and n i s l a r g e , t h e n t h e above f o r m u l a can be a p p r o x i m a t e d by S i n c e t h e s u c c e s s f u l use o f a p a r a l l e l a l g o r i t h m r e q u i r e s a much more p o w e r f u l computer,, a t l e a s t i n terms of t h e number of c e n t r a l p r o c e s s i n g u n i t s , t h e n i t might be argued t h a t i n o r d e r t o have a s u c c e s s f u l a l g o r t h m , t h e N t i m e s as p o w e r f u l computer s h o u l d produce an N - f o l d d e c r e a s e i n t h e o v e r a l l c o m p u t a t i o n t i m e . I n t h a t c a s e , t h e r a t i o I / I ^ needs t o be l e s s t h a n , o r e q u a l t o N . As a m a t t e r o f i n t e r e s t , t h e number o f i t e r a t i o n s u s i n g t h e p a r a l l e l m o d i f i c a t i o n of t h e p a r a m e t r i c t r a j e c t o r y method w i t h t e r m i n a l P i c a r d c y c l i n g and t h e number wi t h t h e s t a n  d a r d p a r a m e t r i c t r a j e c t o r y method a r e shown i n T a b l e 3«2 . From t h i s T a b l e , t h e r a t i o o f t h e o p t i m a l number of i t e r a  t i o n s i s 44/13 o r 3.4 . Thus i t i s seen t h a t f o r t h i s P 3.10 - - A c ' - - S t a n d a r d ..Method - -.-....Parallel w i t h T e r m i n a l C y c l i n g ; 1. OO - .5 13 55 • 33 1? 45 .25 20 44 .20 22 46 T a b l e 3.2 : T o t a l number of i t e r a t i o n s t o o b t a i n s o l u t i o n , Example 3.2 . example, t h i s t e c h n i q u e p l a c e s t h e c o m p u t a t i o n a l p r o c e s s i n t h e r e g i o n o f d i m i n i s h i n g r e t u r n s , i n t h a t t r i p l i n g t h e number o f c e n t r a l p r o c e s s o r s does not c u t t h e o v e r a l l c o m p u t a t i o n t i m e by a f a c t o r o f t h r e e . N e v e r t h e l e s s , t h e f a c t remains t h a t t h e t o t a l c o m p u t a t i o n can be d e c r e a s e d . W i t h t h i s i t e r a t i o n r a t i o , t h e use o f e q u a t i o n 3*9 ( a l o n g w i t h t h e a s s u m p t i o n t h a t t p = t ^ ) would i n d i c a t e a t h e o  r e t i c a l c o m p u t a t i o n t i m e r a t i o o f T p (1+1) 44 T 1 3(3+1) 13 On t h e o t h e r hand, t h e a c t u a l optimum T^ f o r t h e s t a n d a r d method from T a b l e 3«1 i s 51.4 seconds, and the optimum Tp f o r t h e t e r m i n a l c y c l i n g m o d i f i c a t i o n , i f a m u l t i  p r o c e s s o r were a v a i l a b l e , would be 2 ? . l seconds. Thus, t h e a c t u a l r a t i o would be 61 i n d i c a t i n g t h a t t h i s a n a l y s i s p r o v i d e s c o m p u t a t i o n time r a t i o s o f t h e r i g h t o r d e r o f magnitude. The fundamental d i f f i c u l t i e s a s s o c i a t e d w i t h any op t i m i z a t i o n problem a r e c e n t e r e d on the r a t e s o f convergen c e , e r r o r p r o p a g a t i o n and s u i t a b l e s t e p s i z e , e i t h e r i n i n  t e g r a t i o n o r l n some s e a r c h p r o c e d u r e . The p a r a l l e l p r o c e s  s i n g t e c h n i q u e s d i s c u s s e d i n t h i s s e c t i o n c o n v e r t the l a r g e i n t e g r a t e d c o m p u t a t i o n a l problems i n t o groups o f s m a l l e r and, h o p e f u l l y , more manageable sub-problems. Even s o , t h e s e sub-problems employ s t a t e and c o - s t a t e v a r i a b l e s and t h e l a t  t e r a r e n o t o r i o u s f o r c a u s i n g c o m p u t a t i o n a l i n s t a b i l i t y and a s s o c i a t e d problems o f e r r o r p r o p a g a t i o n . I n an attempt t o overcome t h i s d i f f i c u l t y , a method has been dev e l o p e d w h i c h r e p l a c e s t h e c o - s t a t e v e c t o r s w i t h a s e t o f bounded v e c t o r s . A d e s c r i p t i o n i s i n c l u d e d i n Appendix D. Such a t e c h n i q u e c o u l d t h e n be used b o t h as an a l t e r n a t i v e a p p r o a c h t o the sub-problem c o m p u t a t i o n and as a j u s t i f i c a t i o n f o r decompo s i n g t h e system i n t o f e w e r but l a r g e r sub-systems. These remarks c o n c l u d e the p a r t o f the t h e s i s on com p u t a t i o n a l t e c h n i q u e s , and t h e nex t p a r t i s concerned w i t h t h e s y n t h e s i s o f o n - l i n e c o n t r o l l e r s . The d i f f e r e n c e b e t  ween t h e s e p a r t s stems m a i n l y from t h e time a v a i l a b l e f o r p e r f o r m i n g c o m p u t a t i o n s , and t h e f a c t t h a t o n - l i n e c o n t r o l  l e r s have s t r i n g e n t t ime r e q u i r e m e n t s p l a c e s a n o t h e r s e v e r e c o n s t r a i n t on the o v e r a l l problem. C o n s e q u e n t l y , w h i l e de-c o m p o s i t i o n a p p l i e d t o the c o m p u t a t i o n a l problem p r o v i d e d r e s u l t s o f some g e n e r a l i t y , s u c c e s s w i t h o n - l i n e c o n t r o l l e r s , as w i l l be shown p r e s e n t l y , can be c l a i m e d o n l y f o r a spe c i a l c l a s s o f systems. 63 4. DECOMPOSITION AND MULTILEVEL CONTROL SYSTEMS I n t r o d u c t i o n T h i s s e c t i o n c o n c e r n s t h e s y n t h e s i s of o n - l i n e c o n t r o l  l e r s f o r t h e o p t i m a l c o n t r o l problem, and emphasis i s p l a c e d on the development of a h i e r a r c h i c a l c o n t r o l l e r s t r u c t u r e . I t i s e v i d e n t t h a t the s t a n d a r d o p t i m i z a t i o n problem f o r  m ulated i n terms of a s c a l a r o p t i m i z a t i o n f u n c t i o n a l p u t s no a p r i o r i r e q u i r e m e n t s on t h e s t r u c t u r e of t h e c o n t r o l  l e r , and t h e r e f o r e , the added c o m p l e x i t y of t h e h i e r a r c h i c a l s t r u c t u r e must be j u s t i f i e d by e n g i n e e r i n g c o n s i d e r a t i o n s . These i n c l x i d e f a c t o r s such as i n c r e a s e d r e l i a b i l i t y and ease of maintenance, a d a p t a b i l i t y t o f u t u r e system e x p a n s i o n and r e o r g a n i z a t i o n , s p a t i a l s e p a r a t i o n of sub-systems and t h e consequent problem of d a t a communication. Indeed, by t h e use of w e i g h t i n g f a c t o r s , i t i s c o n c e p t u a l l y p o s s i b l e t o i n c o r  p o r a t e t h e s e c o n s i d e r a t i o n s i n a s c a l a r performance f u n c t i o n a l , but i n p r a c t i c e t h e p o s s i b i l i t i e s f o r d o i n g so appear remote. On t h e o t h e r hand, d e f i n i n g v e c t o r v a l u e d performance c r i  t e r i a i s of no a v a i l , s i n c e no u s e f u l t h e o r y e x i s t s f o r t r e a t i n g such problems. N e v e r t h e l e s s , the h i e r a r c h i c a l con t r o l l e r s h o u l d be i n v e s t i g a t e d , s i n c e such s t r u c t u r e s have e v o l v e d as r e g u l a t o r s and c o n t r o l systems i n complex b i  o l o g i c a l , s o c i o l o g i c a l and i n d u s t r i a l s y s t e m s 0 6h 4 o l H i e r a r c h i c a l S t r u c t u r e In most o n - l i n e c o n t r o l s i t u a t i o n s , the time c o n s t a n t s a s s o c i a t e d w i t h the system are s u f f i c i e n t l y s m a l l so t h a t any p o s s i b i l i t y of a p p r o a c h i n g the problem w i t h t h e v i e w of r e p e a t e d l y s o l v i n g t w o - p o i n t boundary problems u s i n g some i t e r a t i v e a l g o r i t h m must be r u l e d out as i m p r a c t i c a l . R a t h e r , an a l g e b r a i c r e l a t i o n s h i p mapping t h e c u r r e n t s t a t e v e c t o r i n t o t h e c o n t r o l v e c t o r i s r e q u i r e d , and t h i s i n t u r n r e q u i r e s the e l i m i n a t i o n of t h e a d j o i n t system. I n some i n s t a n c e s , such as the N o r m - i n v a r i a n t system and the l i n e a r r e g u l a t o r , [ l l ] , t h i s e l i m i n a t i o n can be a c  co m p l i s h e d a n a l y t i c a l l y o Other a t t e m p t s [2?] , [28] , have been made t o a c h i e v e t h i s n u m e r i c a l l y , but w i t h systems w i t h any degree of c o m p l e x i t y , t h i s approach be comes i m p r a c t i c a l . A t h i r d a l t e r n a t i v e i s t o s o l v e some d i f f e r e n t but j u d i c i o u s l y chosen problem,the s o l u t i o n o f which: i u easy- t o o b t a i n , implement the c o n t r o l l aw from t h i s problem t o t h e o r i g i n a l , end t h e n compensate f o r t h e f a c t t h a t i t i s a d i f f e r e n t problem. T h i s has been a t  tempted by F r i e d l a n d [29] , but the a p p l i c a b i l i t y of h i s method re m a i n s t o be demonstrated,, A s i m i l a r approach i s examined and a p p l i e d t o a s p e c i a l c l a s s of problems i n a subsequent s e c t i o n . I t i s assumed t h a t the s e t of system o u t p u t s and con t r o l s has been p a r t i t i o n e d i n t o a s e t of d i s j o i n t s u b s e t s 65 i n such a manner t h a t each s u b s e t c o n t a i n s a t l e a s t one ou t p u t and one i n p u t o r c o n t r o l . T h i s a s s u m p t i o n r e s t r i c t s t h e c l a s s of systems s t u d i e d and i s c l o s e l y l i n k e d w i t h t h e b a s i c r e s t r i c t i o n i n P a r t 3 of t h e t h e s i s and t h e h y p o t h e s i s on page 17. I f t h e system posesses some s u i t a b l e s p a t i a l p r o p e r t i e s , t h e n t h i s p a r t i t i o n i n g and assignment i s o b v i o u s . F o r example, i f t h e system c o n s i s t s of a l o n g s t r i n g of moving v e h i c l e s , each s u b s e t might c o n s i s t o f t h e p o s i t i o n , v e l o c i t y and con t r o l o f one v e h i c l e . I t i s f u r t h e r assumed t h a t t h e sub system c o n t r o l l e r can measure o n l y t h e ou t p u t of i t s sub system and a p p l y a c o n t r o l o n l y t o t h e sub-system. I n t h e ca s e o f a l i n e a r g e n e r a t i n g system of t h e form x = Ax + Bu t h i s means t h a t B i s b l o c k d i a g o n a l , and c o n s e q u e n t l y , t h e i ' t h component o f u a f f e c t s t h e j ' t h component o f x o n l y t h r o u g h t h e c o u p l i n g i n t h e m a t r i x A . The s t r u c  t u r e o f t h e system, assuming o n l y two sub-systems f o r i l  l u s t r a t i o n , i s t h e n as shown: Sub- C c o i r o U e r No. I Ne. 2 Now, w h i l e t h e g o a l i s s t i l l t he o p t i m a l c o n t r o l as s t a t e d i n t h e o p t i m i z a t i o n problem i n p a r t 2, i t I s c l e a r t h a t because o f t h e s t r o n g connectedness p r o p e r t y o f t h e O D S , t h e achievement of t h i s g o a l w i l l be j e o p a r  d i z e d w i t h t h e above s t r u c t u r e . T h i s I s a consequence of the f a c t t h a t each c o n t r o l must be, i n g e n e r a l , a f u n c t i o n o f a l l t h e system o u t p u t s . I f t h e s t r u c t u r e i s augmented by t h e a d d i t i o n of a " s e c o n d - l e v e l " , w h i c h r e c e i v e s com m u n i c a t i o n s from each o f t h e sub-system c o n t r o l l e r s and i n some sen s e , c o o r d i n a t e s t h e s u b - s y s t e m s , t h e n op t i m a l c o n t r o l i s a g a i n f e a s i b l e . Central i CovrV<-c!\ Ms. 2 >^ """H ' The t h r e e approaches t o o n - l i n e c o n t r o l p r e v i o u s l y mentioned a r e now examined w i t h a v i e w o f i n c o r p o r a t i n g such a s e c o n d - l e v e l c o o r d i n a t o r . I n t h e f i r s t two c a s e s , i t becomes a p p a r e n t t h a t t h e r o l e of t h e s e c o n d - l e v e l I s r e d u c e d t o t h a t o f an i n f o r m a t i o n d i s t r i b u t i o n c e n t r e , s i n c e t h e l o c a l c o n t r o l l e r s a r e p r o v i d e d w i t h complete t r a n s f o r m a t i o n l a w s , and r e q u i r e o n l y t h e m i s s i n g s t a t e i n f o r m a t i o n f o r o p t i m a l c o n t r o l i m p l e m e n t a t i o n . 6? I n t h e case o f t h e t h i r d a p p r o a c h , what i s e n v i s i o n e d i s an a c t i v e s e c o n d - l e v e l w h i c h , upon o b t a i n i n g s t a t e i n  f o r m a t i o n , performs e i t h e r some c a l c u l a t i o n s , s i m u l a t i o n as i n 4 . 4 , o r some m a x i m i z a t i o n , as i n t h e d u a l decompo s i t i o n method d i s c u s s e d i n P a r t 3 « To g e n e r a l i z e , a l l t h r e e approaches l e a d t o a s i m i l a r h i e r a r c h i c a l s t r u c t u r e , but i n t h e f i r s t two, t h e r o l e o f th e second l e v e l i s r e d u c e d t o t h e t r a n s m i s s i o n o f d a t a , w h i l e i n t h e t h i r d , some i n f o r m a t i o n p r o c e s s i n g i s a c t u a l  l y p erformed. The advantages o f t h i s s t r u c t u r e d e c l i n e when t h e p r o c e s s i n g c a p a b i l i t y r e q u i r e d of t h e c o o r d i n a t i n g second l e v e l b e g i n s t o approach t h e c a p a b i l i t y o f a s i n g l e i n t e g r a  t e d c o n t r o l l e r , i n which c a s e , t h e a d d i t i o n a l e n g i n e e r i n g c o n s i d e r a t i o n s mentioned i n t h e i n t r o d u c t i o n l o s e t h e i r r e  l e v a n c e . 4.2 An I n v e r s e Problem B e f o r e p u r s u i n g t h i s l i n e o f tho u g h t any f u r t h e r , i t i s i m p o r t a n t t o i n q u i r e i n t o t h e f o l l o w i n g i n v e r s e problem: Under what c o n d i t i o n s i s t h e s e c o n d - l e v e l c e n t r a l c o o r d i  n a t o r n o t r e q u i r e d ? Or t o s t a t e i t i n a d i f f e r e n t manner, under what c o n d i t i o n s can t h e g e n e r a t i n g system be p a r t i t i  oned i n such a way t h a t t h e i ' t h s u b s e t of t h e c o n t r o l v a  r i a b l e s r e q u i r e s o n l y t h e i ' t h s u b s e t o f t h e o u t p u t v a r i a b l e s i n o r d e r t o g e n e r a t e t h e o p t i m a l c o n t r o l ? M a t h e m a t i c a l l y , t h i s i n v e r s e problem can be f o r m u l a t e d 68 w i t h i n t h e framework of t h e f o l l o w i n g o p t i m i z a t i o n p r o  blem: G i v e n a d y n a m i c a l system x = f ( x , u ) f i n d u which w i l l m i n i m i z e t h e f u n c t i o n a l T J = J g(x,u) d t o where x i s t h e ou t p u t n - v e c t o r , u i s t h e c o n t r o l m-vector. Under what c o n d i t i o n s i s i t p o s s i b l e t o w r i t e t h e o p t i m a l c o n t r o l l a w, u * = u ( x ) , as u^* = u^(x^) , Ug*^ ^ ( x g ) » where x 1*2 , x^ i s an n ^ - v e c t o r , x 2 i s an n 2 - v e c t o r , n^ + n 2 = n , and where u , u^ i s an m^-v e c t o r , u 2 i s an m 2 - v e c t o r , + m^  = m ? I n faci;, t h i s I n v e r s e problem can a g a i n be d i v i d e d i n t o two c a s e s . The f i r s t c o n c e r n s t h e s t a n d a r d c a s e , w h e r e i n u^* = u^Cx^) i s r e s t r i c t e d t o be an a l g e b r a i c mapping o f p a r t o f t h e s t a t e space i n t o p a r t o f t h e c o n t r o l space. The second a l l o w s t h i s mapping t o i n c l u d e d i f f e r e n  t i a l e q u a t i o n s . T h i s second c a s e , i n v o l v i n g l o c a l s t a t e e s t i m a t i o n , i s c o n s i d e r e d i n s e c t i o n 4.3 . A p r e l i m i  n a r y r e p o r t o f t h e f i r s t problem appeared i n ^3°} » a n d - h e r e , some o f t h e s e r e s u l t s a r e r e c a l l e d , and some f u r t h e r o b s e r v a t i o n s p r e s e n t e d . A most useful s u f f i c i e n t condition which ensures that a second l e v e l coordinator i s not required Is a v a i l a b l e i n the case of no coupling boundary conditions or control or state constraints, and t h i s demands that the Hamlltonlan of the optimization problem be decomposable in t o a sum of sub-Hamiltonians. For example, i n the problem stated on the previous page, the Hamlltonlan i s i H(x,p,u) = - g(x,u) + p f(x,u) Therefore, i f H can be re-written as 2 H = £ H (x ,p , u ) 1=1 1 1 1 1 and If there are no non-decomposable boundary constraints such as G ( x ( t f ) ) = 0 where G ( x ( t f ) ) = i G 1 ( x 1 ( t f ) ) } 1 = 1,2 or s i m i l a r constraints connecting the control variables, then the optimal control can be written i n terms of alge braic mappings as u A * = u 1 ( x 1 ) , i = 1,2 A p r a c t i c a l example of where such a control i s used i s i n the design of a i r c r a f t , where, under s u f f i c i e n t l y small disturbances about a steady state condition, the Hamlltonlan can be decoupled i n t h i s manner. Consequently, 70 a d e c o u p l e d o p t i m a l c o n t r o l system i n a u t o p i l o t s i s not o n l y f e a s i b l e , but s t a n d a r d p r a c t i c e . U n f o r t u n a t e l y , as shown l n [36] , t h i s s u f f i c i e n t c on d i t i o n i s n o t n e c e s s a r y , and i t would be d e s i r a b l e t o have some s i m p l e n e c e s s a r y and s u f f i c i e n t c o n d i t i o n s . However, even i f t h e c l a s s o f o p t i m i z a t i o n problems i s r e s t r i c t e d t o t h o s e w i t h l i n e a r dynamics and q u a d r a t i c performance c r i t e r i a , t o t h e b e s t of t h i s w r i t e r ' s knowledge, no en t i r e l y s a t i s f a c t o r y c r i t e r i a have been o b t a i n e d . C o n s i d e r t h e f o l o w i n g o p t i m i z a t i o n problem: M i n i m i z e T J = I S (x'Q x + u'R u) d t 4.1 o s u b j e c t t o x = Ax + Bu 4.2 The case o f B=I, R=I, T=°° , and dlm(u) = dim(x) , was c o n s i d e r e d i n [30] . Here i t i s assumed t h a t B anc". R a r e b l o c k d i a  g o n a l , Q i s symmetric, and e q u a t i o n 4.2 can be w r i t  t e n as x l = A l l x l + A 1 2 x 2 + B l l u l x 2 = A 2 1 x l * A 2 2 x 2 + B 2 2 u 2 where dimCs^) = n , + n 2 = n dim(u ) = , m..+ m2 = m and m i s not n e c e s s a r i l y e q u a l t o n . -1 ' T h e r e f o r e , BR B i s b l o c k d i a g o n a l , and i t can be r e p r e s e n t e d as BR" 1 B ' = C = C l l 0 C 2 2 o T h i s problem g i v e s r i s e t o t h e f o l l o w i n g TPBVP: x l = A l l x l + A 1 2 X 2 + C l l P l x l ( 0 ) = x l X 2 = A 2 1 x l + A 2 2 X 2 + C 2 2 P 2 X 2 ( 0 ) = X 2 C h = % l x l + ^ 1 2 X 2 - A n ' P i - A 2 i P 2 P X ( T ) = 0 P2 = Q 1 2 X 1 + Q 2 2 X 2 " A 1 2 , p l ~ A 2 2 P 2 P 2 ( T ) = ° T h i s has a s o l u t i o n p l = K l l x l + K 1 2 X 2 P 2 = K 1 2 x l + K 2 2 X 2 K 1 X ( T ) = 0 , K 1 2 ( T ) = 0 , K 2 2 ( T ) = 0 where t h e K's s a t i s f y t h e w e l l known m a t r i x R i c c a t i equa t i o n s . S i n c e B l l u l = c l l P l and B 2 2 U 2 = ^ 2 2 P 2 t h e I n v e r s e problem r e q u i r e s t h a t K 1 2 = 0 T h i s , i n t u r n , r e q u i r e s t h a t t he R i c c a t l m a t r i c e s K ^ j s a t i s f y t h e f o l l o w i n g e q u a t i o n s : *11 = " K 11 A 11 - A l l ' K l l ~ K 11 C 11 K 11 + Q H K 2 2 = - K 2 2 A 2 2 ~ A 2 2 ' K 2 2 " K 2 2 C 2 2 K 2 2 + Q 2 2 k A K U A 1 2 + A 2 1 ' K 2 2 = Q 1 2 4 . 5 I n t h e case o f m^  = n^ = 1 , i t i s p o s s i b l e t o use e q u a t i o n s 4.3 and 4.4 t o e l i m i n a t e t h e K's from e q u a t i o n 4.5 e n t i r e l y , t h e r e b y o b t a i n i n g a n e c e s s a r y r e l a t i o n s h i p among t h e A*s , Q's , and C's . I n t h e g e n e r a l c a s e , t h i s does n o t appear t o be f e a s i b l e , but some u s e f u l i n f o r m a t i o n can s t i l l be e x t r a c t e d from equa t i o n s 4.3 , 4.4 , and 4.5 . 1. I n ca s e A]_ 2= A 2 j _ = 0 , o n l y Q^ 2 = 0 w i l l s a t i s f y 4.5 • T h i s , o f c o u r s e , i s t h e case c o v e r e d by t h e f o r e g o i n g s u f f i c i e n c y c o n d i t i o n . 2. I f Q 1 2 = 0 , K U A 1 2 = - A 2 1 ' K 2 2 . 3. I f T = o o , A U = A 2 2 , Q U = Q 2 2 , Q 1 2 = 0 , C l l = C 2 2 » t h e n K n = K 2 2 » a n d i f n^ = n 2 , t h e n CxD A01 ' t A„ „t 0 A 21 " A 1 ? K l l = ~ J e Qi2 e d t o F u r t h e r m o r e , B e l l m a n [31] shows t h a t i n t h i s c a s e , a necessary and s u f f i c i e n t condition that at least some matrix w i l l s a t i s f y 4.5 i s that where \ ^ and ^ j are the c h a r a c t e r i s t i c roots of A 1 2 a n d respectively. Clearly, equation 4.5 severely l i m i t s the admissibl systems, e s p e c i a l l y when s e n s i t i v i t y considerations are included. The smallest change i n A i j w i l l mean that equation 4.5 i s no longer s a t i s f i e d , and therefore, the c o n t r o l l e r structure with no second l e v e l i s no longer capable of achieving the optimal control. Although these conclusions have been drawn only f o r l i n e a r systems with quadratic performance c r i t e r i a , i t i s expected that the severity of the requirement w i l l carry over to other optimization problems^ since many non-linear systems approach l i n e a r behaviour near the o r i g i n . 4.3 Local State Estimation . In the previous section, the inverse problem was con sidered wherein the control law mapping the state vector into the control vector was r e s t r i c t e d to be algebraic. In t h i s section, t h i s r e s t r i c t i o n i s l i f t e d and the pro blem i s thereby transformed into one of obse r v a b i l i t y . Assuming that the l o c a l c o n t r o l l e r has a true optimum feed back control law av a i l a b l e , but lacks only information 74 about t h e o t h e r s t a t e s of the system, i s i t s t i l l p o s s i b l e t o c i r c u m v e n t t h e r e q u i r e m e n t f o r a s e c o n d - l e v e l c o o r d i n a t o r by s y n t h e s i z i n g l o c a l e s t i m a t o r s , w h i c h , by m e asuring th e l o c a l s t a t e v a r i a b l e s , can p r o v i d e a s a t i s f a c t o r y a p p r o x  i m a t i o n t o t h e e n t i r e s t a t e v e c t o r ? I f t h i s were i n d e e d p o s s i b l e , t h e n t h e c o s t o f the added c o m p l e x i t y o f t h e l o  c a l c o n t r o l l e r s c o u l d be weighed a g a i n s t t h e c o s t of an o v e r a l l d a t a t r a n s m i s s i o n n e t w o r k , o r even an i n t e g r a t e d , c e n t r a l i z e d c o n t r o l l e r . As i n t h e p r e v i o u s s e c t i o n , i t i s •assumed t h a t t h e s t a t e and c o n t r o l o f t h e o v e r a l l system have been p a r t i t i o n e d as x = x l u = \u and a f e e d b a c k c o n t r o l l a w o f t h e form U i * = U l ( x l ' x 2 ) is a v a i l a b l e t o t h e i ' t h l o c a l c o n t r o l l e r . However, t h i s c o n t r o l can not be implemented because, say X g , i s unknown. C l e a r l y , t h e problem of s t a t e e s t i m a t i o n i s t h e n r e d u c e d t o a problem of o b s e r v a b i l i t y . However, because no t h e o r y o f o b s e r v a b i l i t y e x i s t s f o r n o n - l i n e a r systems, o n l y l i n e a r systems w i l l be c o n s i d e r e d , and i n t h i s r e s t r i c t e d c a s e , t h e t h e o r y o r i g i n a l l y d e v e l o p e d by Kalman [32J and ex tended by L u enberger [*33j . [3^3 t o t n e n o i s e - f r e e s i t  u a t i o n i s a p p l i c a b l e h e r e . 75 The d y n a m i c a l g e n e r a t i n g system t o be c o n s i d e r e d i s x l = A l l x l + A 1 2 x 2 + B l u l X 2 = A 2 1 x l + A 2 2 X 2 + B 2 U 2 where t h e o u t p u t s a r e Y1 = C 1 x 1 ?Z = C 2 X 2 U s i n g some i n f i n i t e t i m e , q u a d r a t i c performance c r i t e r i o n , i t i s known t h a t • u l = K l l x l + K 1 2 x 2 u 2 = K 1 2 x l + K 2 2 x 2 where, a g a i n , t h e K*s s a t i s f y a p p r o p r i a t e R i c c a t l equa t i o n s . The problem, t h e n , f o r t h e i ' t h sub-system i s t o ge n e r a t e u^ u s i n g o n l y t h e i n f o r m a t i o n i n i t s measure ment y^ . U s i n g t h e n o t a t i o n t h a t (A,C) i s o b s e r v a b l e i f t h e system x = Ax + Bu • y = Cx i s o b s e r v a b l e , t h e n t h e f o l l o w i n g r e s u l t s due t o Luen b e r g e r I341 can be s t a t e d : 1. L e t t i n g A = { A 1 J } , t h e f o r e g o i n g i n v e r s e problem i s u n s o l v a b l e i f ( A . C ^ ) i s u n o b s e r v a b l e , i = 1, 2 . 2. F o r each ( A , C ) t h a t i s o b s e r v a b l e , ( v - l ) ' t h o r d e r o b s e r v e r s can be c o n s t r u c t e d , where v i s t h e i n d e x o f o b s e r v a b i l i t y , such t h a t each row of u^ can be g e n e r a t e d u s i n g t h e o u t p u t of t h i s o b s e r v e r i n l i n e a r c o m b i n a t i o n w i t h y^ ^ . T h e r e f o r e , i n t h e case where o b s e r v e r s can be c o n s t r u c  t e d , an e s t i m a t e f o r t h e e n t i r e s t a t e v e c t o r i s o b t a i n e d . I n t h e case of an e r r o r a r i s i n g from a d i s c r e p a n c y i n i n  i t i a l c o n d i t i o n s , t h i s e r r o r can be made t o d i m i n i s h a r b i  t r a r i l y q u i c k l y , l i m i t e d o n l y by t h e f a c t t h a t t o o f a s t a re s p o n s e would make t h e system e x t r e m e l y s e n s i t i v e t o any n o i s e i n t h e o u t p u t measurements. The q u e s t i o n o f t h e s e c o n d - l e v e l would t h e r e f o r e be s e t t l e d , a t l e a s t f o r l i n e a r systems, i f t h e p a r t i c u l a r o b s e r v a b i l i t y c o n d i t i o n s r e q u i r e d were a common o c c u r r e n c e . U n f o r t u n a t e l y , l n t h e e x p e r i e n c e o f t h i s w r i t e r , t h e s e con d i t i o n s have n ot been met by systems o f any c o m p l e x i t y . F o r example, l n t h e problem o f a s t r i n g of moving v e h i c l e s , , a l l o w i n g each v e h i c l e t o measure i t s own p o s i t i o n and v e l o c i t y a l o n g w i t h , p e r h a p s , t h o s e o f t h e p r e c e d i n g v e h i c l e , i s s t i l l n o t n e a r l y enough t o s a t i s f y t h e o b s e r  v a b i l i t y r e q u i r e m e n t s . 77 O t h e r approaches t o s t a t e e s t i m a t i o n , based on game t h e o r y o r M a r k o v i a n models, have been s u g g e s t e d , but f o r one r e a s o n o r a n o t h e r , no s a t i s f a c t o r y s t a t e e s t i m a t i o n based on l o c a l measurements a l o n e appears f e a s i b l e . I t must t h e r e f o r e be c o n c l u d e d t h a t i n most p r a c t i c a l p r o  blems, any hope o f a c h i e v i n g l o c a l s t a t e e s t i m a t i o n i s n e g l i g i b l e , and i n o r d e r t o implement the o p t i m a l f e e d  back c o n t r o l l a w, a second l e v e l must be e s t a b l i s h e d . 4.4 A M u l t i - l e v e l C o n t r o l l e r Based on t h e Second V a r i a t i o n I n t h i s s e c t i o n , t h e h i e r a r c h i c a l c o n t r o l l e r s t r u c  t u r e i s s y n t h e s i z e d f o r a c l a s s o f o p t i m i z a t i o n problems. T h i s c l a s s o f problems c o n t a i n s systems so l a r g e and com p l e x t h a t o b t a i n i n g an a n a l y t i c a l e x p r e s s i o n f o r t h e f e e d  back c o n t r o l law i n t h e form u* = u ( x ) i s i m p o s s i b l e . And, f o r t h e m a j o r i t y o f t h e systems c o n s i d e r e d , even f u n c t i o n a l a p p r o x i m a t i o n s as suggested i n [ 2 7 l a n d [ 2 8 ] a r e c o m p l e t e l y I m p r a c t i c a l . Thus, not even an e x p e n s i v e communications n e t  work can overcome t h e sub-system c o o r d i n a t i o n problem. I n  s t e a d , an a c t i v e s e c o n d - l e v e l c o o r d i n a t o r i s proposed w h i c h w i l l r e c e i v e i n f o r m a t i o n from t h e lox^er l e v e l c o n t r o l l e r s , p e r  form f u n c t i o n a l o p e r a t i o n s on t h i s i n f o r m a t i o n , and t h e n p r o  v i d e l o w e r l e v e l s some u s e f u l c o o r d i n a t i o n d a t a . W ith t h e a i d o f t h i s d a t a , t h e l o w e r l e v e l c o n t r o l l e r s can t h e n Improve t h e i r c o n t r o l l a w s , t h e r e b y o b t a i n i n g a good ap p r o x i m a t i o n t o t h e optimum. N a t u r a l l y , much o f t h e con t r o l c a l c u l a t i o n i s done by. t h e l o c a l c o n t r o l l e r s , and t h e s e c o n d - l e v e l c o o r d i n a t o r i s t h e r e f o r e , r e l a t i v e l y s i m  p l e i n comparison t o a c e n t r a l i n t e g r a t e d c o n t r o l l e r . The d e c o m p o s i t i o n t e c h n i q u e based on d u a l i t y (see P a r t 3) was d eveloped t o o p e r a t e on t h e s e p r i n c i p l e s , and P e a r s o n has c l a i m e d i t to be a w o r k a b l e a l t e r n a t i v e [24] . However, i t w i l l s u f f i c e t o say t h a t e xcept i n e x t r e m e l y s i m p l e c a s e s o f s c a l a r , l i n e a r systems w i t h q u a d r a t i c p e r  formance c r i t e r i a , any p o s s i b i l i t y o f o n - l i n e a p p l i c a t i o n o f t h i s method appears o p t i m i s t i c . T h i s becomes immediate l y e v i d e n t when the method i s a p p l i e d t o any problem of s i g n i f i c a n c e , s i n c e , i n e f f e c t , t h e r e s u l t i n g s e c o n d - l e  v e l c o o r d i n a t i o n problems t u r n out t o be v a r i a t i o n a l p r o  blems o f g r e a t e r d i f f i c u l t y t h a n the o r i g i n a l l y s t a t e d , i n  t e g r a t e d problem. T h e r e f o r e , t h e c o m p l e x i t y o f t h e second- l e v e l c o o r d i n a t o r , even i f one were f e a s i b l e , would exceed t h e c o m p l e x i t y of a c e n t r a l , i n t e g r a t e d c o n t r o l l e r , and t h e g a i n s o f d e c o m p o s i t i o n and h i e r a r c h y would be l o s t . That a s u c c e s s f u l a p p r o x i m a t i o n t e c h n i q u e can be d e v e l o p e d from t h i s t h e o r y has y e t t o be demonstrated. One o f t h e s t a n d a r d approaches w h i c h might l e a d t o a m u l t i - l e v e l c o n t r o l l e r s t r u c t u r e i s t h e w e l l known n e i g h  borhood c o n t r o l l e r , t r e a t e d i n d e t a i l by K e l l e y | 36] , and by B r e a k w e l l , Speyer and B r y s o n [37] » and t h e r e appears no p o i n t i n f u r t h e r e l a b o r a t i o n h e r e , except t o say t h a t i n g e n e r a l , t h e l i n e a r i z e d system remains coup l e d , and one i s l e f t w i t h one h i g h l e v e l ( n o m i n a l t r a  j e c t o r y ) c o n t r o l l e r , and one low l e v e l ( l i n e a r r e g u l a  t o r ) c o n t r o l l e r . I t has t h e f u r t h e r u n f o r t u n a t e p r o  p e r t y t h a t the l i n e a r r e g i o n i s v e r y s m a l l and minor p e r t u r b a t i o n s tend t o throw th e system so f a r from t h e n o m i n a l t h a t t r u e o p t i m a l i t y i s l o s t u n l e s s new n o m i n a l t r a j e c t o r i e s can be c a l c u l a t e d r a p i d l y . The c o n t r o l l e r d e v e l o p e d here can be f u l l y under st o o d u s i n g o n l y two sub-systems, and e x t e n s i o n t o N sub-systems i s r o u t i n e . The n o t a t i o n used here i s de f i n e d i n Appendix A. C o n s i d e r t h e problem o f d e t e r m i n i n g t h e c o n t r o l v e c t o r Uj_, 1=1,2 , w h i c h w i l l m i n i m i z e t h e f u n c t i o n a l 2 T s u b j e c t t o t h e c o n s t r a i n t x i = A i x l + s f i ^ t X g ) + B i u i ^'7 x j L (0) = x i o , 1 = 1 , 2 Here, i t i s assumed t h a t the f u n c t i o n t f ^ (x-^ , X g ) i s s m a l l i n some sen s e , as d i s c u s s e d l a t e r , so t h a t the system c o n s i s t s p r i m a r i l y o f two l i n e a r systems, c o u p l e d together weakly. Also, any small subsystem n o n - l i n e a r i t i e s have been lumped into the functions. With the aid of the Maximum P r i n c i p l e , the optimal control law can be written as \x1 = Rj^  Bi'C-KiXi + hi) where and h^ are governed by — 1 Ki = - Ai'Ki - KiAi + KiBiRi Bi'Ki - Qj_ 4.8 Ki(T) = 0 hi = -(A x - B i R ^ B i ' K i ) ' h i + C K i f i - 2 , e 22 f * (-K <x -j + h *) 4.9 j=l i J hj_(T) = 0. This control law immediately suggests a h i e r a r c h i c a l -1 • c o n t r o l l e r structure, l n that the -Ri ^ K ^ X i term i n the control lav? acts as a l o c a l feedback control, while -1 • the Ri Bi hi term plays the r o l e of the coordination function. As £ goes to zero, h^ becomes vanishingly small, and no coordination i s required, while, as £ gets large, the i n t e r a c t i o n term begins to dominate the dyna mics, and consequently, the l i n e a r system-quadratic per formance functional control law becomes i n s i g n i f i c a n t l n comparison to the coordination function. 81 As t h e c o n t r o l law s t a n d s , no a p p r o x i m a t i o n s have been made. On t h e o t h e r hand, s i n c e t h e i n t e g r a t i o n of 4.9 r e q u i r e s t h e v e c t o r x , t h e p r e s e n t form o f f e r s m erely an a l t e r n a t e , n o n - t r i v i a l , two p o i n t boundary v a l u e p r o b  lem.* However, t h e a t t r a c t i v e n e s s o f t h i s f o r m u l a t i o n becomes more e v i d e n t when systems w i t h " s m a l l " i n t e r a c t i o n s a r e c o n s i d e r e d . W r i t i n g t h e c o n t r o l law as 4.10 4.11 4.12 t h e n i n t h e case o f weak i n t e r a c t i o n s , t h e u. term would A i d ominate t h e c o n t r o l w h i l e t h e term p l a y s t h e r o l e o f a secondary improvement.,Of c o u r s e , under t h e s t a t e d c o n d i t i o n s , t h e u. can be implemented e x a c t l y by t h e A i l o c a l c o n t r o l l e r s . I t i s s u g g e s t e d t h e r e f o r e , t h a t t h e u-g^ term, vrtiich i s d i f f i c u l t t o implement e x a c t l y , be approx imated. Because o f t h e secondary n a t u r e of t h i s term, t h i s a p p r o x i m a t i o n need n o t be p a r t i c u l a r i l y good. Thus, i n s t e a d o f u s i n g 4.12 i n 4.10 , u B i i s chosen t o be * I n f a c t , l i m i t e d c o m p u t a t i o n a l e x p e r i e n c e has shown no p a r t i c u l a r advantages w i t h t h i s f o r m u l a t i o n . where u, = u. + u R i o p t A i B i u A i = ~ R i l B i , K i x i u f i = R ^ B 'h where 82 4. 13 h i = - ( A 1 - B i R i 3 i K i } ' h i + £ K 1 f i ( x ' : " ) - 4 . 14 h ^ T ) . ^ 0 I n 4 . 1 4 , x" i s t a k e n t o be some s u i t a b l e , a p r i o r i e s t i m a t e o f t h e s t a t e t r a j e c t o r y . A n a t u r a l c h o i c e f o r x' would be x * ( t ) = U ( t ) x, 4.15 where U = ( A - B R ^ B ' K ) - U , U (0 ) = I 4.16 Here, and i n t h e subsequent development, t h e n o n - s u b s c r i p  te d v a r i a b l e s and m a t r i c e s a r e t a k e n t o mean t h e co m p o s i t e v a l u e s , made up o f t h e s u b s c r i p t e d v a r l b l e s . F o r example, A l l 0 A = \ 0 '22 The f o l l o w i n g d e f i n i t i o n s a r e now employed. The Approximate C o n t r o l Law, u , i s t a k e n t o be U A = R^B'Kx 4.1? and t h e v a l u e o f t h e performance f u n c t i o n a l J a r i s i n g from t h e use of t h i s c o n t r o l l aw i s d e f i n e d t o be J" A 83 The Compensated C o n t r o l Law , u c , i n d i c a t i n g t h a t some compensation f o r t h e c o u p l i n g and t h e n o n - l i n e a r i t i e s has been made, i s t a k e n t o be u c = - R-l-B'Kx + R-^-B'h* 4 . 1 8 and t h e v a l u e f o r t h e c o r r e s p o n d i n g f u n c t i o n a l J i s d e f i n e d as J c The O p t i m a l C o n t r o l Law , u o p t , i s d e f i n e d as u o p t = ~ R ~ 1 B ' K X + R ~ 1 B , h > 4 . 1 9 w i t h t h e c o r r e s p o n d i n g performance f u n c t i o n a l J o p t N a t u r a l l y , t h e c o m p l e x i t y o f t h e c o n t r o l l e r f o r i m p l e  m e n t i n g t h e s e t h r e e c o n t r o l laws p r o g r e s s i v e l y i n c r e a s e s from 4 . 1 7 t o 4 . 1 9 , and i t i s i m p o r t a n t t o s t u d y t h e im provements l n J , i f any, w h i c h a r e t o be e x p e c t e d by u s i n g t h e more complex c o n t r o l l a w s . I d e a l l y , i t i s d e s i r e d t o ob t a i n a n a l y t i c e x p r e s s i o n s f o r t h e f u n c t i o n a l s J ^ , J ^ , , and J o p t , and t h e n compare t h e v a l u e s o f t h e s e f o r d i f f e r e n t c o u p l i n g f u n c t i o n s and £ s . However, t h e problem i s t o o complex t o a l l o w such a c o u r s e of a c t i o n , and t h e r e f o r e t h r e e a l t e r n a t i v e s a r e c o n s i d e r e d . The f i r s t o f t h e s e i n v o l v e s o b t a i n i n g , f o r a r a t h e r t r i v i a l problem, a p p r o x i m a t e a n a l y t i c e x p r e s s i o n s f o r t h e J ' s , and t h i s development i s r e l e g a t e d t o Appendix - C. The second, which i s t r e a t e d a t t h e end of t h i s s e c t i o n , i n -84 v o l v e s n u m e r i c a l s i m u l a t i o n of d i f f e r e n t systems t o i l  l u s t r a t e t h e e f f e c t s of t h e s e c o n t r o l laws on t h e p e r f o r  mance f u n c t i o n a l s . The t h i r d i s a development based on t h e second v a r i a t i o n approach o f t h e c a l c u l u s of v a r i a t i o n s t o s u p p o r t t h e a s s e r t i o n t h a t J c i s l e s s t h a n J A under n o r  mal c i r c u m s t a n c e s , and i s p r e s e n t e d h e r e . A p p l i c a t i o n o f t h e c o n t r o l law u A of e q u a t i o n 4.17 t o t h e system 4.7 r e s u l t s i n t h e s t a t e t r a j e c t o r y x A and th e performance f u n c t i o n a l J" A . A v a r i a t i o n i n u A , c a l l e d <Su , r e s u l t s i n a v a r i a t i o n of t h e s t a t e t r a j e c t o r y , <Sx , about x A , and i n a v a r i a t i o n o f t h e performance f u n c  t i o n a l , S J , about J A . E x p a n s i o n o f 4.7 about t h i s n o m i n a l t r a j e c t o r y , r e t a i n i n g terms up t o t h e second o r d e r , y i e l d s t h e f o l l o w i n g d i f f e r e n t i a l r e l a t i o n s h i p between £x and &u : « hx = (A + £ f x ( x A ) )Sx + BSu + «\ 4.20 6x(0) = 0 where t h e n o t a t i o n and t h e second o r d e r term *\ i s de f i n e d i n Appendix A . A l s o , t h e v a r i a t i o n , <$J , expanded up t o second o r d e r terms becomes T , , T 6 J = $(x AQ6x + u A R $ u ) d t + § $ (6x *Q&x + Su R$u) d t 4.21 o o On s u b s t i t u t i n g c o n t r o l laxv 4.17 and i n t e g r a t i n g the ti m e d e r i v a t i v e term, t h i s e x p r e s s i o n can be r e - w r i t t e n as T T S J - ( f 'K + x%AKfx)hx d t + | J ( 6 X ' Q S X + ou'fiou + o o t £ xAKV-j ) d t 4 . 2 2 S i n c e J i s not t h e minimum v a l u e of J , t h e r e e x i s t s some Su such t h a t &J < 0 . I n f a c t , a new o p t i m i z a t i o n problem of d e t e r m i n i n g t h e c o n t r o l 6 u which w i l l m i n i  mize 4 . 2 2 , s u b j e c t t o the c o n s t r a i n t 4 , 2 0 , can be posed. Thus, an a u x i l i a r y H a m i l t o n i a n i s d e f i n e d as H A = - e ( f *K + x A K f x ) i x - i Ux'QSx + S U ' R S U + ex^K^) + q'([A + e f x ] 6 x + BSu •+ 4.23 where q = QSx - (A •+ £f + I-AI) 'q + £ (Kf + f^Kx. + A K x A ) 4.24 q(T) = 0 and TV » t h e second o r d e r term i n &x, i s d e f i n e d i n Appendix A . A p p l i c a t i o n of t h e Maximum P r i n c i p l e t o t h i s a u x i  l i a r y problem r e s u l t s i n c -1 » 6u = R B q 4 . 2 5 and t h e TPBVP a r i s i n g from e q u a t i o n s 4 . 2 0 , 4.24 and 4 . 2 5 has as a s o l u t i o n q = - L 6"x + 3? 4 . 2 6 where L = - L( A + £ f x ) -- ( A + £ f x ) ' L + LGL - Q 4 . 2 ? I = - ( A + £ f x - CL + | ( L ^ - 2 A [ - L S x + ) + t ( K f + f x K x A + A K x A ) 4 . 2 8 C = BR ' V , L ( T ) = 0 , .$ (T) = 0 . 4 . 2 9 I t i s a p p r o p r i a t e to d e f i n e the m a t r i x M = K - L 4 . 3 0 and by d i r e c t s u b s t i t u t i o n , u s i n g 4 . 8 and 4 . 2 7 1 i t i s seen t h a t M = - (A + £ f x - C K ) ' M - M(A + £ f x - CK) - MCM + £. ( K f x + f x K ) 4 . 3 1 M(T) = 0 Then the e q u a t i o n f o r $ can be r e - w r i t t e n as $ = - ( A + £ f x - CK + C M ) ' l + e(Kf + f x K x A ) + L [ ( K - MW + zA{K-n)6x - 2 A 5 '+ 2A.KX.] 4 . 3 2 2 » A 5(T) = 0 The optimum c o n t r o l v a r i a t i o n t h e r e f o r e becomes <Su = R"^B' [ (M-K)^x + $] 4 . 3 3 8? and t h e n , i f i n s t e a d o f the c o n t r o l law , the law u s = u A + U = R ^ B ' f - K x A + (M-K)6x + = R ~ 1 B ' [ - K ( X A + Sx) •+ Mix + § ] 4 .34 were used, a performance f u n c t i o n a l , J s , would r e s u l t w h i c h would be l e s s t h a n J A , i f e x p a n s i o n s up t o t h e second o r d e r terms p r o v i d e a s u f f i c i e n t l y good a p p r o x i m a  t i o n t o the o r i g i n a l problem. I t i s Important t o note t h a t i f g i s d e f i n e d as g = Mix + 5 4 .35 t h e n the e q u a t i o n g o v e r n i n g g i s found t o have a s t r u c  t u r e i d e n t i c a l t o e q u a t i o n s 4.9 and 4 . 1 4 , namely, g = - (A - CK)'g + £Kf(x A) - e f x ( x A ) ( - K x A + g) 4.36 g(T) = 0 And t h e e q u a t i o n f o r U3 , n o t i n g the s i m i l a r i t y t o 4 . 1 8 and 4 . 1 9 , i s u s = R" 1B ' ( - K x s + g ) 4 .37 where Xg i s the s t a t e t r a j e c t o r y r e s u l t i n g from the c o n t r o l u y . The e f f e c t i v e n e s s o f the c o n t r o l law 4 .37 i s de pendent on how c l o s e l y the o r i g i n a l system can be a p p r o x i  mated by second o r d e r e x p a n s i o n s . I f t h e s e a p p r o x i m a t i o n s 88 a r e good, and t h i s i s t o be e x p e c t e d w i t h normal dyna m i c a l systems, then u g i s a c o n t r o l law c l o s e t o t h e optimum, and t h e r e f o r e Jg <• J" A . S i n c e h i s an ap- • p r o x i r a a t i o n t o g , th e n under normal c i r c u m s t a n c e s , i t i s a l s o e x p e c t e d t h a t t h e c o n t r o l law u^ w i l l p r o v i d e J S * J C J A The c o n t r o l l e r s t r u c t u r e e n v i s a g e d i s t h e n as shown i n f i g u r e 4.1 . Each c o n t r o l l e r c o n t i n u o u s l y measures i t s l o c a l s t a t e v a r i a b l e , and a t t i m e z e r o , t r a n s m i t s t h i s v a l u e t o t h e c o o r d i n a t o r . The l a t t e r , a f t e r o b t a i n i n g x(0) , g e n e r a t e s and s t o r e s h/ by means of one i n t e g r a  t i o n sweep of 4.14 i n c o n j u n c t i o n w i t h equation. 4.15 • Then, t h r o u g h o u t t h e t i m e i n t e r v a l [0 , T] , i t s u p p l i e s h c o n t i n u o u s l y t o t h e sub-system c o n t r o l l e r s which combine t h i s w i t h t h e i r l o c a l f e edback c o n t r o l law , - K^x^ , t o form u^ . N a t u r a l l y , i n an o n - l i n e s i t u a  t i o n , t h i s p r o c e s s would be c a r r i e d out on a sampled b a s i s , s a m p l i n g p e r i o d b e i n g T seconds. I f t h e sub-system t r a n s i e n t s were s u f f i c i e n t l y s l o w , i t might even be f e a s i b l e t o implement c o n t r o l law u s , 4.37 . However, t h i s would r e q u i r e t h e c o o r d i n a t o r t o make two i n t e g r a t i o n sweeps, a f o r w a r d sweep t o g e n e r a t e x^ , and t h e n a backward sweep t o o b t a i n g . B e f o r e p r o c e e d i n g t o t h e n u m e r i c a l examples, t h e s p e c i a l CENTRAL CO-ORDINATOR F i g u r e 4.1: Proposed H i e r a r c h i c a l S t r u c t u r e f o r C o n t r o l l e r 9 0 case of l i n e a r c o u p l i n g w i l l be c o n s i d e r e d . I f the coup l i n g f u n c t i o n , f ( x ) , can be r e p r e s e n t e d t o a s a t i s f a c  t o r y degree of a c c u r a c y by t h e form f ( x ) = F ( t ) x 4 . 3 8 t h e n /r| = 0 , and A. = 0 , and t h e e q u a t i o n s f o r M and 3? r e d u c e t o k = - ( A + E F - C K ) ' M - M( A + fc F - C K ) - MCM + e ( K F + F ' K ) 4 . 3 9 k = - ( A + eF - CK + CM)'$. + e ( K F + F * K ) x 4.40 Moreover, t h e e q u a t i o n f o r g becomes g = - ( A + eF - cK)'g +. £ ( K F + F ' K ) X A 4.4l g(T) = 0 Because of t h e l i n e a r i t y o f t h e s e e q u a t i o n s , i t becomes f e a s i b l e t o w r i t e the e x p l i c i t s o l u t i o n f o r g as T g ( t ) = [fcY(t) J Z ( s ) { K ( s ) F ( s ) + P(s) ,K(.s)}Z(s)ds" l x t J 0 4.42 where Y = - ( A + £ F ( t ) - C K ( t ) )' Y Y(0) = 1 Z = ( A + € F ( t ) - C K ( t ) ) Z Z ( 0 ) = I 91 o r g ( t ) = X ( t ) x Q vrhere X ( t ) i s t h e m a t r i x i n t h e b r a c k e t s i n e q u a t i o n 4.42 . Thus, by s t o r i n g o r h a v i n g a v a i l a b l e , the m a t r i x X ( t ) , t h e c o o r d i n a t o r can s u p p l y t h e l o w e r l e v e l c o n t r o l l e r s t h e f u n  c t i o n g ( t ) w i t h no i n t e g r a t i o n sweeps n e c e s s a r y , and i n t h i s c a s e , t h e c o n t r o l law u 3 i s r e a d i l y Implemented. Some n u m e r i c a l examples a r e c o n s i d e r e d n e x t . Example 4.1 The f i r s t example co n c e r n s two, c o u p l e d , f i r s t - o r d e r s y stems, each w i t h a s c a l a r c o n t r o l i n p u t . The low o r d e r o f t h e system t e n d s t o b e l i e t h e c o m p l e x i t y o f i t s beha v i o u r , e s p e c i a l l y i n r e g i o n s o f t h e s t a t e . s p a c e where t h e n o n - l i n e a r c o u p l i n g e f f e c t s a r e not i n s i g n i f i c a n t . I n f a c t , t h e u n c o n t r o l l e d system i s h i g h l y u n s t a b l e i n most r e g i o n s o f t h e s t a t e space. The o p t i m i z a t i o n problem c o n s i s t s o f d e t e r m i n i n g con t r o l s and u 2 w h i c h m i n i m i z e the f u n c t i o n a l T 2 2 2 2 J = | \ (100x 1 + 1 0 0 x 2 + n± + u 2 ) d t o s u b j e c t t o x^ = - x i + + zx^x^ , x^CO) = X 1 Q 2 x 2 = ~ 2 x 2 + u 2 + x^ Z , x 2 ( 0 ) = x 2 92 The o p t i m a l s o l u t i o n s f o r d i f f e r e n t i n i t i a l con d i t i o n s and e v a l u e s were o b t a i n e d u s i n g t h e R i c c a t l t r a n s f o r m a t i o n i n c o n j u n c t i o n w i t h the g e n e r a l i z e d Newton-Raphson a l g o r i t h m , as d e s c r i b e d i n [38"}. F i g u r e 4.2 shows p l o t s of t y p i c a l t r a j e c t o r i e s , s t a r t i n g a t d i f f e r e n t i n i t i a l p o i n t s i n t h e s t a t e space, and u s i n g t h e t h r e e d i f f e r e n t c o n t r o l l a w s , u A , u^ and u 0 p ^ • Because of t h e near symmetry of t h e system about t h e v a r i a b l e x 2 , o n l y t h e r i g h t h a l f p l a n e I s shown. T a b l e 4 .1 g i v e s v a l u e s o f J a s s o c i a t e d w i t h t h e s e t r a j e c t o r i e s . T a b l e 4.2 i l l u s t r a t e s t h e e f f e c t of d i f f e r e n t v a l u e s o f £. , t h e i n i t i a l c o n d i t i o n b e i n g h e l d f i x e d a t (3»3)» a p o i n t i n a p a r t i c u l a r l y u n s t a b l e r e g i o n o f the s t a t e space. Indeed, a s l i g h t i n c r e a s e i n £. above .9 a t t h i s s t a r t i n g p o i n t i s s u f f i c i e n t t o a l l o w t h e system t o escape i f o n l y t h e a p p r o x i m a t e c o n t r o l law, u^ , i s used w i t h no compensation. Example 4.2 The second example c o n c e r n s t h e o p t i m a l r e g u l a t i o n o f two second o r d e r o s c i l l a t o r s which a r e c o u p l e d by c r o s s - p r o d u c t terms. A problem of t h i s t y p e c o u l d a r i s e , f o r example, i n f l i g h t v e h i c l e s , where t h e e f f e c t s of the p r o d u c t s o f i n e r t i a a r e not n e g l i g i b l e , and where i t may be d e s i r e a b l e t o compensate f o r t h e s e e f f e c t s i n some op t i m a l manner. I x2 F i g u r e 4.2 T r a j e c t o r i e s i n State Space R e s u l t i n g from D i f f e r e n t C o n t r o l Laws. Example 4.1. £ = -8. I n i t i a l Cond i t i o n s x l o > X 2 D J o p t J A % J C - J o p t J o p t % J A - J o p t I J o p t o . i , 3 . 0 7 4 . 0 1 7 4 . 0 1 7 4 . 0 4 0 . 0 . 0 4 1 3 . 0 , 3 . 0 2 5 2 . 1 5 26M.73 408.91 4 . 9 9 6 2 . 2 3 . 0 , 0.3 82 . 5 4 82.<4 82 . 6 7 0 . . 157 3 . 0 , - 3 . 0 1 0 2 . 8 7 104 . 0 6 1 0 7 . 4 4 1.157 4 C 4 4 3 0 . 1 , - 3 . 0 7 3 . 8 1 7 3 . 8 1 73.82 0 . . 0 1 4 T a b l e 4 . 1 : T r a j e c t o r i e s from d i f f e r e n t I n i t i a l con d i t i o n s w i t h £ = . 8 , as i n F i g u r e 4 . 2 , Example 4 . 1 0 J o p t J A % J C ~ J o p t ,'° J A ~ J o p t £ J o p t J o p t .1 1 6 5 . 5 5 1 6 5 . 7 8 1 6 6 . 2 9 .14 > 5 . 3 168 . 1 6 189»03 1 9 5 . 6 8 . 5 0 4 . 0 0 . 5 2 1 2 . 7 0 214 . 9 2 2 4 1 . 6 7 1.0 1 3 . 6 0 .7 2 3 8 0 6 8 245 . 5 6 3 2 6 . 6 5 2 . 9 . 3 6 . 9 0 . 9 265o92 288 . 4 5 5 9 4 . 6 0 8 . 5 1 1 2 3 . 6 T a b l e 4 . 2 : E f f e c t of d i f f e r e n t v a l u e s of £ , u s i n g i n i t i a l c o n d i t i o n s ( 3 , 3 ) , Example 4.1. The problem i s t o d e t e r m i n e and u 2 which w i l l m i n i m i z e T 2 J = h i Z ( q i X i 2 + p i y i 2 + ) d t o 1=1 s u b j e c t t o x i = y i xi(°) = x i 0 h = - a i y i + u i + £ f ' y i ( 0 ) = y i 0 where f = y^y^ The parameters used i n t h e n u m e r i c a l example were as f o l l o w s : ^1 = q2 = 1 0 0  P l = P 2 = 1 and T , £. and t h e I n i t i a l c o n d i t i o n s were v a r i e d . The o p t i m a l t r a j e c t o r i e s i n t h i s case were o b t a i n e d u s i n g a s t a n d a r d p a r a m e t r i c t r a j e c t o r y method a l o n g w i t h t h e u n m o d i f i e d Newton-Raphson a l g o r i t h m i n f u n c t i o n space T a b l e s 4.3 and 4.4 p r o v i d e a comparison of performance f u n c t i o n a l s u s i n g t h e t h r e e d i f f e r e n t c o n t r o l laws f o r v a r i o u s v a l u e s of T , g. and i n i t i a l c o n d i t i o n s . F i g u r e 4.3 shows t y p i c a l s t a t e t r a j e c t o r i e s w i t h t h e s e c o n t r o l l a w s . Jopt J p . J A • JC - J ° P t J A " J o ^ J A - J o ^ Jopt °/o Jopt °/o J - Jopt .5 • s .5 .5 17.684 17.703 17.706 .107 .124 1.159 1.0 1.0 1.0 1.0 71.440 71.511 71.609 .099 .237 2.394 1.5 1.5 1.5 1.5 162.758 162.894 163-309 .084 .339 4.036 2.0 2.0 2.0 2.0 293-559 293-753 294.707 .066 • 378 5.727 2.5 2.5 . 2.5 2.5 466.018 466.295 467.846 .059 .392 6.644 - .5 - .5 r~ - • D - .5 17.504 17.517 17.573 .074 .394 5-324 -1.0 -1.0 -1.0 -1.0 70.016 70.036 70.060 .029 .063 2.172 -1.5 -1.5 -1.5 -1.5 158.054 158.244 164.893 .120 4.327 36.058 -2.0 -2.0 -2.0 -2.0 282.703 284.421 313.995 .608 11.069 18.206 -2.5 -2.5 -2.5 -2.5 . 445.457 450.546 542.373 1.142 21.757 19.052 TABLE 4.3: The E f f e c t of D i f f e r e n t I n i t i a l C o n d i t i o n s on Example 4.2, w i t h e = .5, T = 2 97 E J o p t J c J A J C " J o p t % J A _ J o p t J A " J o p t J ° p t J o p t J c " J o p t .0 1 2 1 . 1 2 2 1 2 1 . 1 2 2 1 2 1 . 1 2 2 .0 .0 .1.0 .2 1 2 1 . 9 7 9 122.044 124.649 . 0 5 3 1 .697 3 2 . 0 1 9 . 4 1 2 5 . 5 0 5 1 2 5 . 5 7 1 142.153 . 0 53 1 3 . 2 6 5 2 5 0 . 2 8 3 . 6 131.208 1 3 3 . 1 5 7 2 0 7 . 5 7 4 1 . 485 5 8 . 2 0 2 39.139 • 8 1 3 8 . 5 0 7 1 6 9 . 0 6 2 7 2 7 . 0 6 8 2 2 . 0 6 0 424 . 932 1 9 . 2 6 3 T a b l e 4 . 4 : E f f e c t of d i f f e r e n t v a l u e s of the parameter e i n Example 4 . 2 , u s i n g i n i t i a l c o n d i t i o n s ( - 2 , 2 , - 2 , 2 ) and T = 2 . D i s c u s s i o n o f Examples The f i r s t p o i n t t o note i s t h a t i n every case con s i d e r e d , t h e compensated c o n t r o l lav; improved t h e system performance as measured by t h e performance f u n c t i o n a l s . T h i s r e s u l t i s i n agreement w i t h t h e s c a l a r problem t r e a  t e d i n Appendix C , and might have been e x p e c t e d from the f o r e g o i n g second v a r i a t i o n t h e o r y . I t i s a l s o n o t e d t h a t d i f f e r e n t p o r t i o n s of t h e s t a t e space p r o v i d e v e r y d i f f e r e n t performance c r i t e r i a and t h i s d i f f e r e n c e i s r e f l e c t e d l n t h e comparison o f t h e v a r i o u s c o n t r o l l a w s . A l s o , i t was a n t i c i p a t e d t h a t t h e p e r c e n t a g e impro vement of t h e compensated c o n t r o l l aw o v e r t h e a p p r o x i  mate c o n t r o l law would n o t c o n t i n u e i n d e f i n i t e l y w i t h i n c r e a s i n g v a l u e s o f t , and t h i s f a c t i s borne out by column 7 o f T a b l e 4.4 , where t h e maximum p e r c e n t a g e improvement o c c u r s a t €.= .5 . T h i s tendency i s a g a i n v e r i f i e d by t h e s c a l a r example. On t h e whole, t h e compensated c o n t r o l l aw p r o v i d e s a performance v e r y c l o s e t o t h a t o f t h e optimum, and s i n c e t h e i m p l e m e n t a t i o n o f t h i s c o n t r o l lav; i s v e r y much s i m p l e r t h a n t h a t of t h e o p t i m a l , i t s h o u l d be s e r i o u s l y c o n s i d e r e d . N a t u r a l l y , t h e i m p l e m e n t a t i o n of t h e a p p r o x i m a t e c o n t r o l l aw i s even s i m p l e r s t i l l , b u t i t i s q u e s t i o n a b l e whether t h e r e s u l t a n t performance d e g r a d a t i o n i s a c c e p t a b l e . 100 4.5 C o n c l u s l o n The p r e c e d i n g s e c t i o n s have c o n s i d e r e d t h e o p t i m a l c o n t r o l s y n t h e s i s problem f o r a c l a s s of d y n a m i c a l systems. T h i s c l a s s c o n s i s t s of systems composed of a number of sub-systems, p r e f e r a b l y weakly i n t e r a c t i n g . I t was f i r s t a r g ued t h a t , a l t h o u g h e n g i n e e r i n g c o n s i d e r a t i o n s may f a  v o r a c o m p l e t e l y d e c e n t r a l i z e d c o n t r o l , the r e s t r i c t i o n s a r i s i n g from the i n v e r s e problem i n v e s t i g a t i o n n e c e s s i t a t e t h e use o f c o n t r o l l e r c o o r d i n a t i o n . A c c o r d i n g l y , a h i e r  a r c h i c a l c o n t r o l l e r s t r u c t u r e was s y n t h e s i z e d , and nume r i c a l examples i n d i c a t e t h a t such a c o n t r o l l e r i s worth c o n s i d e r i n g as an a l t e r n a t i v e t o an i n t e g r a t e d , c e n t r a l i z e d c o n t r o l l e r . Among the d e s i r e a b l e c h a r a c t e r i s t i c s of t h i s c o n t r o l l e r a r e ease o f c o n t r o l i m p l e m e n t a t i o n and s a t i s  f a c t o r y b e h a v i o u r i n a poor i n t e r sub-system communica t i o n environment. I n h e r e n t i n t h e h i e r a r c h i c a l s t r u c t u r e i s t h e p r o p e r t y t h a t i f t h e c e n t r a l c o o r d i n a t o r f a i l s , t h e l o c a l c o n t r o l l e r s r e m a i n o p e r a t i n g , and t h e system c o n t i n u e s t o f u n c t i o n a l t h o u g h f u r t h e r from the optimum. 101 5. DISCUSSION AND CONCLUSION The t h e s i s began w i t h a statement o f t h e g e n e r a l o p t i m i z a t i o n problem under c o n s i d e r a t i o n , and by means of the Maximum P r i n c i p l e , t h i s problem was re d u c e d t o d e t e r m i n i n g t h e t r a j e c t o r y of t h e o p t i m a l d y n a m i c a l s y s  tem. The s t r u c t u r e o f t h i s system was then r e p r e s e n t e d by d i r e c t e d g r a p h s , which i n t u r n ' p r o v i d e d a b a s i c frame work from which t o s t u d y d i f f e r e n t a s p e c t s of decomposi t i o n . D e c o m p o s i t i o n was n e x t c o n s i d e r e d both f o r the com p u t a t i o n a l problem as w e l l as f o r t h e s y n t h e s i s problem. I n t h e f o r m e r , t h e fundamental c o n t r i b u t i o n o f decomposi t i o n was t o su g g e s t methods of p a r a l l e l p r o c e s s i n g , w h i l e i n t h e l a t t e r , d e c o m p o s i t i o n was found t o be t h e f i r s t s t e p i n s y n t h e s i z i n g , a h i e r a r c h i c a l s t r u c t u r e f o r t h e op t i m a l feedback c o n t r o l l e r . The one f a c t o r w h i c h d e t r a c t s from t h e p r a c t i c a l use f u l n e s s o f t h e s e s t u d i e s i s t h e scope o f t h e problem t h a t has been c o n s i d e r e d . F o r t h e sake o f m a t h e m a t i c a l c o n v e n i  ence, t h e o p t i m i z a t i o n problem was s t a t e d as t h e e x t r e m i - z a t i o n of a s c a l a r f u n c t i o n a l s u b j e c t t o d i f f e r e n t i a l con s t r a i n t s . U n f o r t u n a t e l y , i n p r a c t i c a l s i t u a t i o n s , i t appears e x t r e m e l y d i f f i c u l t t o d e f i n e a s c a l a r f u n c t i o n a l , w h i c h , when e x t r e m i z e d , g u a r a n t e e s a d e s i r e a b l e c o n t r o l system w i t h s a t i s f a c t o r y performance. That a h i e r a r c h i c a l s t r u c t u r e i s sought i n t h e s y n t h e s i s r e f l e c t s t h e f a c t t h a t c o n s i d e r a t i o n s o t h e r than t h e e x t r e m i z a t i o n of a s c a l a r f u n c t i o n a l a r e i n e v i d e n c e . However, t h e i d e a t h a t t h e s e o t h e r c o n s i d e r a t i o n s may d e f i n e o t h e r f u n c t i o n a l s , and t h a t t h e s e may be combined t o form a v e c t o r p e r f o r  mance c r i t e r i a i s not i m p o s s i b l e , but u n l i k e l y . I n t h e f i r s t p l a c e , t h e s e c o n s i d e r a t i o n s , w h i c h may I n v o l v e ease o f maintenance and r e a d i l y i m p l e m e n t a b l e redundancy, do not l e n d t h e m s e l v e s t o q u a n t i t a t i v e m a t h e m a t i c a l e x p r e s  s i o n s . S e c o n d l y , even i f t h e y d i d , t h e v e c t o r v a l u e d o p t i m i z a t i o n problem would be of much g r e a t e r c o m p l e x i t y , and i t s u s e f u l n e s s would be q u e s t i o n a b l e . Another c o n c l u s i o n w h i c h a r i s e s from t h e t h e s i s i s t h a t t h e s t r u c t u r e o f t h e system c o n t r o l l e r i s h i g h l y de pendent on n o t o n l y t h e performance c r i t e r i o n but t h e p r o blem s t a t e m e n t . I t was shown i n P a r t 2 how two u n c o u p l e d g e n e r a t i n g systems become c l o s e l y c o u p l e d by e i t h e r t h e performance f u n c t i o n a l , o r t h e boundary c o n d i t i o n s r e q u i  r i n g b o t h t o r e a c h t h e o r i g i n , i n a c e r t a i n t i m e . I n p r o  blems where a f i x e d performance f u n c t i o n a l i s d e f i n e d , and i t i s w i t h o u t a doubt, t h e one r e q u i r e d t o be o p t i m i  zed, t h e n o f c o u r s e t h e r e i s no a l t e r n a t i v e . However, i f as i n most s y n t h e s i s problems, a performance f u n c t i o n a l i chosen merely on t h e b a s i s of p r o v i d i n g a s y s t e m a t i c p r o  c e d ure f o r o b t a i n i n g t h e c o n t r o l lav;, then a g r e a t d e a l o f thought s h o u l d be g i v e n t o whether a d i f f e r e n t c h o i c e f o r t h i s f u n c t i o n a l might r e s u l t i n a f a r s i m p l e r c o n t r o l  l e r s t r u c t u r e , w h i l e g i v i n g a l m o s t t h e same system beha- v i our. I n c o n c l u s i o n , t h e m o d e r a t e l y w e l l known p r i n c i p l e l n systems e n g i n e e r i n g might be c o n s i d e r e d \_39\ • "Do not t r y t o o h a r d t o o p t i m i z e the s m a l l p i e c e s of a t i g h t l y i n  t e r r e l a t e d system because i t w i l l c o s t you more t h a n you g a i n e d when you put t h e p a r t s t o g e t h e r . " . On t h e o t h e r hand, t h e r e s u l t s of t h i s t h e s i s i n d i c a t e t h a t i f t h e system un de r c o n s i d e r a t i o n i s not " t i g h t l y i n t e r r e l a t e d " , t h e n s i g  n i f i c a n t g a i n s can be a n t i c i p a t e d by d e c o m p o s i t i o n and de c e n t r a l i z e d o p t i m i z a t i o n . Appendix A : N o t a t i o n Throughout the t h e s i s , t h e f o l l o w i n g n o t a t i o n has been employed. f 1 f l l x l l x 2 . . f- f f n = ( I n "•X n • t o n. n where and 6x' f, 6x xxx f * f < • • . f * l x l x l l x l x 2 l x l x n Lxx i x n x l i x n x 2 • • • ^* A -x nx n F u r t h e r m o r e , JV - l A ^ - \ z nx x ^} U t 1 = 1 x ^ j i Note t h a t _/\! ^ A-105 Using t h i s notation, the expression for &(s ) , d( 6x) where s i s any vector independent of <£x becomes fr(s'/^) o(6x) 1 k=l K j=i K x i X l J f n n ") 1 Z s k ( H f k 6x.)i ^ k=l K 1=1 Kxj_x, J J 2- J 2 A ! s Also, with t h i s notation, the following expressions can be used : f(x + Sx) = f(x) + f x*(x)6x + h"\ f x ( x + &x) = f x ( x ) + JV Appendix B : M u l t i - P r o c e s s i n g Computers The o b j e c t i v e of t h i s a p p e ndix i s t o p r e s e n t a b r i e f g e n e r a l d e s c r i p t i o n o f t h e p r e s e n t s t a t u s of m u l t i - p r o  c e s s i n g computers. F o r a more d e t a i l e d s t u d y o f t h i s sub j e c t , a l i s t of r e f e r e n c e s i s i n c l u d e d , and f o r su r v e y mended. The machines t o be c o n s i d e r e d a r e c l a s s i f i e d i n  t o two c a t e g o r i e s , here r e f e r r e d t o as t h e c o n v e n t i o n a l and t h e u n c o n v e n t i o n a l . I n t h e former c a t e g o r y b e l o n g a dozen c e n t r a l p r o c e s s o r s p l u s a s i m i l a r number o f ad d i t i o n a l p e r i p h e r a l d a t a c h a n n e l . c o n t r o l u n i t s and which r e p r e s e n t t y p i c a l p r e s e n t day computer hardware. The l a t t e r c a t e g o r y i n c l u d e s machines such as SOLOMON I I | 4 l l , w i t h a 16 by 16 a r r a y of p r o c e s s i n g e l e m e n t s . The u n c o n v e n t i o n a l machines, though an e x c i t i n g de velopment, a r e s t i l l f a c e d w i t h a number o f not e n t i r e l y u n r e l a t e d problems. One co n c e r n s memory a l l o c a t i o n , and how much l o c a l memory t o p r o v i d e f o r i n d i v i d u a l p r o c e s  s i n g elements. A n o t h e r i n v o l v e s t h e d e s i g n of a f l e x i b l e d a t a d i s t r i b u t i o n network between p r o c e s s i n g elements and th e c e n t r a l c o n t r o l u n i t w hich w i l l n o t be overwhelmed by hardware c o m p l e x i t y . I n t h e case o f SOLOMON I I , each p r o  c e s s i n g element i s p r o v i d e d w i t h a l o c a l memory not exce e d i n g one thousand words o f 24 b i t s , w h i l e t h e c e n t r a l p u r p o s e s , a r e p a r t i c u l a r ! l y recom- machlnes such as t h e IBM 9020 program memory, a l s o r e l a t i v e l y s m a l l , i s used f o r system i n s t r u c t i o n s as w e l l as a c t i n g as an o v e r f l o w f o r t h e l o  c a l memories. A v e r y d i f f i c u l t t a s k r e m a i n i n g i s t o deve l o p s o f t w a r e which a c h i e v e s s a t i s f a c t o r y hardware u t i l i  z a t i o n f a c t o r s . T h i s t y p e of machine h o l d s g r e a t promise f o r t h e s o l u t i o n o f p a r t i a l d i f f e r e n t i a l e q u a t i o n s , as i n  d i c a t e d by some r e c e n t p u b l i c a t i o n s , and consequen t l y , i n t h e c o n t e x t o f o p t i m a l c o n t r o l t h e o r y , t h e ques t i o n o f e x p l i c i t s o l u t i o n s of B e l l m a n ' s p a r t i a l d i f f e r  e n t i a l e q u a t i o n i s a g a i n r a i s e d . The c o n v e n t i o n a l machines a r e u s u a l l y d e s i g n e d so t h a t each of t h e p r o c e s s i n g e l e m e n t s , h a v i n g v e r y l i t t l e o r no l o c a l memory, has d i r e c t a c c e s s t o t h e c e n t r a l me mory, w h i c h , as i n t h e case o f IBM 9020, i s a v a i l a b l e i n 32 K word modules. Because no s i n g l e major element i s c r i t i c a l t o t h e o p e r a t i o n of t h e system, i t can be p r o  grammed t o work i n one extreme as a s i n g l e p r o c e s s o r s e  q u e n t i a l i.'-achlne u s i n g t h e e n t i r e memory, o r i n t h e o t h e r extreme as a number o f independent s m a l l e r computers. Thus, each p r o c e s s o r has a v a s t and y e t v a r i a b l e memory a t i t s d i s p o s a l . However, most complex problems would p r o b a b l y have a degree o f p a r a l l e l i s m f a r i n excess of t h a t p r o v i d e d by a c o n v e n t i o n a l m u l t i - p r o c e s s o r computer, and iyet ex pandi n g t h e number o f p r o c e s s o r s w i t h t h i s c o n f i g u r a t i o n becomes i m p r a c t i c a l . The p r i m a r y l i m i t a t i o n seems t o be s t o r a g e i n t e r f e r e n c e , or more th a n one p r o c e s s o r w i s h i n g a c c e s s t o t h e same memory module, as d e s c r i b e d i n r e f  erence A l s o , a l t h o u g h s o f t w a r e d e s i g n f o r t h e con v e n t i o n a l m u l t i - p r o c e s s i n g computer seems e a s i e r t h a n f o r a n o n - c o n v e n t i o n a l machine, h i g h e f f i c i e n c y w i l l a l m o s t c e r t a i n l y r e q u i r e a c o m b i n a t i o n of m u l t i - p r o g r a m m i n g as w e l l as m u l t i - p r o c e s s i n g , and because m u l t i - p r o g r a m  ming even on a s e q u e n t i a l machine i s a n o n - t r i v i a l t a s k , a g r e a t d e a l of work remains t o be done. Appendix C : S c a l a r Example As an a d d i t i o n t o t h e development i n P a r t 4, S e c t i o n 4 , t h i s a ppendix i n c l u d e s t h e d e r i v a t i o n of a p p r o x i m a t e a n a l y t i c e x p r e s s i o n s f o r t h e v a l u e of t h e performance f u n c t i o n a l i n t h e case where th e d y n a m i c a l c o n s t r a i n t i s r e p r e s e n t e d by a s c a l a r , l i n e a r d i f f e r e n t i a l e q u a t i o n , and t h e performance f u n c t i o n a l i s q u a d r a t i c . A l t h o u g h I n t h i s c a s e , d e c o m p o s i t i o n i s not p o s s i b l e , i t i s f e l t t h a t t h e c h a r a c t e r i s t i c s of t h e t h r e e c o n t r o l l a w s , 4.17 » 4.18 and 4.19 v i l l i be i l l u s t r a t e d . The problem i s t o choose u t o m i n i m i z e t h e f u n c t i o n a l T J = h $ (Qx 2 + u 2 ) d t o s u b j e c t t o x = ax + bx + u x ( 0 ) = x 0 On t h e a s s u m p t i o n t h a t T i s l a r g e , t h e o p t i m a l feedback c o n t r o l lav; 4.19 i s known t o be u o p t = - N x where M 2 - 2 ( a + b)M - Q = 0 o r M = ( a + b) + ( ( a + b ) 2 + Q ) ^ W i t h t h i s c o n t r o l l aw, t h e o p t i m a l t r a j e c t o r y i s governed by the e q u a t i o n x = ( a + b - M)x L e t t i n g c< = - ( ( a +"b) 2 + Q t h e n t h e o p t i m a l t r a j e c t o r y can be w r i t t e n as x o p t = e x o and J o p t = £ M x o 2 However, suppose t h a t b i s not a v a i l a b l e f o r ac c u r a t e measurement, and t h e a p p r o x i m a t e c o n t r o l law, 4, u A = - Kx i s used i n s t e a d , where K 2 - 2aK - Q = 0 or K = a + ( a 2 + Q ) 2 Then t h e system t r a j e c t o r y i s governed by t h e e q u a t i o n x A = ( a + b - K )X_A and by l e t t i n g (3 = (b - ( a 2 + Q )* ) t h i s t r a j e c t o r y i s g i v e n by ft XA= 6 X C L e t t i n g A.J = J A - J ( t o f i r s t o r d e r terms ^ A opt i t i s found t h a t A J bK ( « - (a ) x Q 2 p (oc + p. ) o r A J A _ bK ( cx - p ) J o p t H P ( * + P ) On the o t h e r hand, t h e compensated c o n t r o l law, 4.18 , i s g i v e n by u c = - Kx + h" where K i s t h e same as above, and h i s t h e s o l u t i o n o f t h e e q u a t i o n h* = - ( a - K ) h * + bKx* - b ( - K x * + h*) = - >^ h* + 2bKx'"" h*(T) = 0 . v . C h o o s i n g x t o s a t i s f y t h e e q u a t i o n x = ( a - K ) x x*(0) = x Q , 2 1 l e t t i n g X = - ( a* + Q ) ? and assuming t h a t T i s l a r g e , t h e f u n c t i o n h" i s found t o be h * ( t ) = 2 b K x Q e ^ t / ( p> + "S ) The t r a j e c t o r y x c a r i s i n g from t h e use of t h e con t r o l u^ i s t h e n a p p r o x i m a t e d by X C and l e t t i n g ^ J C = J C ™ J o p t i s found t o be o^? T-r 2K IT 1 X(t+P) -2Kb These expressions were calculated for a range of values of a , b and Q , and a t y p i c a l r e s u l t i s shown i n Figure C.l . In T a b l e d are l i s t e d numerical values for A J C / & J A for d i f f e r e n t values of b . I t i s found that for every case, this r a t i o remains less than 1 , ind i c a t i n g that for the r e l a t i v e l y wide range of values covered, the compensated control law always performed better than the approximate. A J C A J G b , Q=100 — , Q=10 A J A -10 .3^2 .985 - 8 . 2 1 8 .659 - 6 . 122 .388 - /(. .053 . 1 8 0 - 2 .013 . 0 4 7 0 .000 .000 2 .012 .051 4 . 0 4 4 .207 / . 0 8 8 .465 8 . 134 .775 10 .170 I .979 Table C.l Effect of b on the r a t i o A J c / A J for the scalar problem , with a = - 10 1 1 4 Appendix D : Tangent Pla n e Method The o p t i m a l d y n a m i c a l system as d e s c r i b e d i n p a r t s 2 and 3 o f the t h e s i s i s d e f i n e d by t h e s t a t e , c o n t r o l and t h e c o - s t a t e v a r i a b l e s o f t h e problem. As i s w e l l known, t h e s e c o - s t a t e v a r i a b l e s a r e alm o s t always governed by u n s t a b l e e q u a t i o n s and, c o n s e q u e n t l y , t h e n u m e r i c a l d i f f i c u l t i e s a s  s o c i a t e d w i t h e r r o r p r o p a g a t i o n when t h e two p o i n t bounda r y v a l u e problem i s b e i n g s o l v e d a r e n o t o r i o u s . The purpo se o f t h i s a p p e n d i x i s t o i n t r o d u c e a new s e t o f v a r i a b l e s r e l a t e d t o t h e c o - s t a t e v a r i a b l e s , w h i c h p o s s e s s a p p e a l i n g boundedness p r o p e r t i e s . The development o f t h i s t e c h n i q u e i s based on t h e geo m e t r i c a l c o n c e p t s o f o p t i m a l c o n t r o l t h e o r y as d e s c r i b e d by Leitmann [45] , and B l a q u i e r e and Leitmann [46^ » a r K* ^ n e n o t a t i o n s u b s e q u e n t l y employed i s i d e n t i c a l t o t h a t o f chap t e r 1 i n r e f e r e n c e [45] . C o n s i d e r t h e o p t i m i z a t i o n problem o f m i n i m i z i n g t h e f u n c t i o n a l V = f f (x,u) d t t ° s u b j e c t t o t h e c o n s t r a i n t x = f ( x , u ) . and 1f'(x(t 1 )) = 0 . 11 T h i s I s e q u i v a l e n t t o m i n i m i z i n g x ^ t ^ ) , s u b j e c t to x Q = f 0(x,u) x = f (x,u) ^ ( x ^ ) ) = 0 . As i n [45] , t h e l i m i t i n g s u r f a c e i n t h e (n+1)-space i s denoted by 2> , and t h e n - d i m e n s i o n a l t a n g e n t p l a n e t o 2 a t t h e p o i n t x * ( t ) i s denoted by T 2 ( x * ( t ) ) . P r o v i d e d t h e i n i t i a l c o n d i t i o n s a r e s u i t a b l y chosen, any ( n + l ) - v e c t o r i n t h i s t a n g e n t p l a n e , denoted by ^ , i s governed by n'l = f x ' f ^ where t h e a s t e r i s k i n d i c a t e s t h a t t h e d e r i v a t i v e m a t r i x x >xi o X 2 • • • f**-'x n n. _ *xi "x 2 n>V.. i s c a l c u l a t e d a t the optimum t r a j e c t o r y . D e f i n i n g t h e v e c t o r A t o s a t i s f y t X = - f x * x T h e r e f o r e , "X^ = c o n s t a n t , and i f t h e i n i t i a l A i s chosen as o r t h o g o n a l t o T £ ( x ( t ) ) , t h e n X remains o r t h o g o n a l t h r o u g h o u t the e n t i r e t r a j e c t o r y . u S i n c e i t can be shown [45] t h a t X i s a l s o o r t h o g o n a l t o i t f o l l o w s t h a t f n f o f * l i e s e n t i r e l y i n t h e p l a n e T z ( x * ( t ) ) . 116 I f l w J / x * ( t ) , j = l , . . . . n r e p r e s e n t s a t i m e - v a r y i n g ortho-normal s e t o f n ( n + 1 ) - v e c t o r s spanning T z (x' ( t ) ) , t h e n f o can be r e p r e s e n t e d as n Z} a o 0 w where because o f o r t h o - n o r m a l i t y , a. L e t a = a l a n V/ =/wi 1 w^2 ... w ^ \ w n w n ... w n n T h e r e f o r e , D . l and D.2 can be w r i t t e n as fo = w Q a f * - W a a = f c w Q + W f D.l = ^ f o " + w < 3 f " • D « 2 K 1 \ ' n C o m b i n a t i o n o f t h e s e e q u a t i o n s y i e l d s = w D' ( f Q " w c + tf'fv ) and t h i s can be r e - w r i t t e n as f ~ : (WwQ) f (1 - w Q W Q ) D.3 D e f i n e = 1 - w o w o v = Ww o E q u a t i o n D.3 t h e n becomes f = — f o r # v i o p T h i s i s m e r e l y a r e s t a t e m e n t o f t h e f a c t t h a t t h e H a m i l t o n i a n f o r a non-autonomous system a t t h e o p t i m a l t r a j e c t o r y i s z e r o . F u r t h e r m o r e , s i n c e t h e s t a n d a r d Ha m i l t o n i a n i s d e f i n e d as H = - f c + p'f , i t f o l l o w s t h a t P - f . D.5 where t h e r o l e o f p i s t o a c t as a s c a l i n g f a c t o r . The p r i m a r y advantage o f t h i s new s e t o f v a r i a b l e s o v e r t h e c o - s t a t e v a r i a b l e s , p , a r i s e s from t h e boundedness p r o  p e r t i e s . Because o f o r t h o - n o r m a l i t y , w 0w 0' + w'w = I n , where I n denotes an n by n i d e n t i t y m a t r i x . T h e r e f o r e , w o ' ( w o w o ' + w ' w ) w o = w o ' w o o r (1 - (3 ) 2 + v'v = (1 - p>) v'v = p(l - p ) D.6 o r t S i n c e v v > 0 t h e n 0 < | i < 1 D.7 11.8 Moreover, D.5 i m p l i e s t h a t max v 1 v = max p (1 - p ) = \ D. 8 W i t h the a i d o f e q u a t i o n s D.5 and D.6 , t h e d i f  f e r e n t i a l e q u a t i o n s g o v e r n i n g v and p can be d e r i v e d . S i n c e P = f o x " f x ' p • u s i n g D.5» d /J_v\ = v - x & = f o x f x * J. o r v - v p = a.f - f x ' v D.9 p • T h e r e f o r e , v'v - i v ' v p = p v ' f 0 x - v ' f x ! v w h i c h , w i t h t h e a i d o f D.6, can be reduced t o 1 d - — ( ( 3 ( 1 - ( 3 ) ) - ( l - B ) B = i p ' f 0 x - v ' f x , v 2 d t p = 2 p v ' ( - f Q x o r ft ( i v * Q v + f x ' v ) W r i t i n g the H a m l l t o n l a n as H = - f Q + v' f , D.10 t h e e q u a t i o n f o r p becomes p = 2 | i v * H x D . l l C o n s e q u e n t l y , e q u a t i o n D.9 can be used t o o b t a i n v = (2 v' H x) v - £>H X D.12 The t r a n s v e r s a l i t y c o n d i t i o n s r e q u i r e t h a t 1 v f = K y D . 1 3 where K i s some p o s i t i v e c o n s t a n t , and the s u b s c r i p t f denotes t e r m i n a l v a l u e s . E q u a t i o n D.12 can be w r i t t e n as fz - f v f = K 2 ^ * X f , w h i c h , w i t h the a i d o f i d e n t i t y D.6 y i e l d s 1 Pf = 1 + K 2 ^ ' }f D-1^ x f X f C o n s e q u e n t l y , K v f = ^ D.15 1 + K ^ x ^ ^ X f With the a i d o f the s c a l i n g f a c t o r p and t h e v e c t o r v , t h e maximum p r i n c i p l e t o g e t h e r w i t h t h e t r a n s v e r s a l i t y c o n d i t i o n s D . l4 and D.15 can be used t o g e n e r a t e a new TPBVP c o n s i s t i n g o f t h e s t a t e e q u a t i o n s and e q u a t i o n s D . l l and D.12 . The r e q u i r e m e n t t h a t H as d e f i n e d i n e q u a t i o n D.10 be a maximum w i t h r e s p e c t t o t h e c o n t r o l v a r i a b l e u i s s u f f i c i e n t t o p r o v i d e c o n d i t i o n s under w h i c h the c o n t r o l v a r i a b l e can be r e p l a c e d by a f u n c t i o n o f x , v and |9 . T h i s method i s i l l u s t r a t e d on a s i m p l e second o r d e r system i n o r d e r t o demonstrate i t s a p p l i c a t i o n . The problem i s t o d r i v e t h e system x l = x 2 x 2 = u from i t s i n i t i a l s t a t e x 1 = 0 , x? = -3 t o t h e c i r c l e $ ( x ( l ) ) = x ^ l ) 2 +. x 2 ( l ) 2 - 1 = 0 so t h a t \ 2 j = I ] r d t i s m i n i m i z e d . 120 The s t a n d a r d approach i s t o d e f i n e the H a m i l t o n i a n as H = - j u 2 + P l x 2 + P 2 U whe re P i = 0 P 2 = ~ P i • The maximum p r i n c i p l e t h e n y i e l d s u = p 2 w h i c h , when s u b s t i t u t e d , g i v e s H as H = | p 2 2 + p x x 2 m The f a c t t h a t H(0) = 0 p r o v i d e s a r e l a t i o n s h i p between P i ( 0 ) and p 2 ( 0 ) as P! (0)= - p 2 2 ( 0 ) . 1 2X2T0T A n u m e r i c a l a l g o r i t h m based on t h e g e n e r a l i z e d Newton- Raphson t e c h n i q u e s i m i l a r t o t h a t d e s c r i b e d on page 43 o f t h e t h e s i s i s employed t o d e t e r m i n e the unknown q u a n t i t y P 2(0) w h i c h w i l l n u l l the f u n c t i o n c§(x(l)). The p r e s e n t method b e g i n s by d e f i n i n g t h e H a m i l t o n i a n as ? v l v 2 , H = u + — ' xp + — u vrhere p = 2 p V ' H X = 2 V l v 2 v x = (2 v'H x) V l - p H X 1 = 2 Vj v ? 2 r 2 = (2 Y ' H x ) V 2 - p H = 2 v 2 Y t - v± A g a i n the maximum p r i n c i p l e y i e l d s v 2 u = — and, t h i s , when s u b s t i t u t e d i n t o H g i v e s 2 v 2 v 1 H = - i - ; + - 1 x 2 Thus, t h e H ( 0 ) = 0 c o n d i t i o n i m p l i e s t h a t v 2 2 ( 0 ) = - 2 p ( 0 ) v., (0) x 2 ( 0 ) Moreover, t h e i d e n t i t y 0 ( 1 - |3) - v'v w h i c h i s v a l i d f o r a l l t , p r o v i d e s t h e o t h e r m i s s i n g i n i  t i a l c o n d i t i o n as p(0) (1 - p ( 0 ) ) . « v 1 2 ( 0 ) +• v 2 2 ( 0 ) o r o r p ( 0 ) ( l - p ( 0 ) ) = V ! 2 ( 0 ) - 2 p ( C ) v 1 ( 0 ) x 2 ( 0 ) VjCO) = p ( 0 ) x 2 ( 0 ) ^ (0) + p ( 0 ) ( x 2 2 ( 0 ) - 1) and t h e r e f o r e , v 2 ( 0 ) = -2 p ( 0 ) x 2 ( 0 ) p ( 0)x 2 ( 0 ) + ^ p(0) + p 2 ( 0 ) ( x 2 ( 0 ) - l ) As b e f o r e , t h e problem i s reduced t o f i n d i n g t h e m i s s i n g s c a l a r q u a n t i t y p(0) such t h a t §>(x(l)) w i l l be n u l l e d . 122 T a b l e D.l p r o v i d e s a comparison o f t h e number o f i t  e r a t i o n s r e q u i r e d f o r convergence between t h e s t a n d a r d me thod and the t a n g e n t p l a n e method. These r e s u l t s a r e d i s  p l a y e d g r a p h i c a l l y i n F i g u r e D.l I n T a b l e D.l , 3 r e f e r s t o the q u a n t i t y P 2 ( O ) - p 2' f(o) P 2 * (0 ) and T r e f e r s t o ft(0) - B(0) T = J ; where p 2 (0) and |3(0) a r e t h e guessed i n i t i a l c o n d i t i  ons as t a b u l a t e d i n the f i r s t and f o u r t h column r e s p e c t i v e l y , P 2 * (0 ) and |i*(0) a r e the c o r r e c t i n i t i a l c o n d i t i o n s f o r s o l v i n g t h e problem, and t h e s e happen t o be 6. and .0137 t r e s p e c t i v e l y , f o r t h i s p a r t i c u l a r problem. These n o r m a l i z e d q u a n t i t i e s S and T a r e u s e f u l f o r comparing t h e ranges o f convergence o f t h e two methods, and a r e used as the com mon a b s c i s s a i n F i g u r e D.l . F i g u r e D.2 shows t h e o p t i m a l t r a j e c t o r i e s f o r ^ , v^ and v 2 As shown i n F i g u r e D.l , t h e range o f convergence f o r the t a n g e n t p l a n e method i s g r e a t e r t h a n t h a t f o r the s t a n  dard method. I n f a c t , t h i s d i f f e r e n c e i s even more notewor t h y when i t i s r e a l i z e d t h a t t h e "no convergence" c o n d i t i o n of the t a n g e n t p l a n e method a t T = - .5 o c c u r s v e r y c l o s e 123 t o one extreme of p . To s o l v e the problem, t h i s would not be a l o g i c a l i n i t i a l c o n d i t i o n w i t h w h i c h t o b e g i n the i t  e r a t i o n . T h e r e f o r e , the f a c t t h a t p i s known t o l i e between 0 and 1 s h o u l d be o f s i g n i f i c a n t a s s i s t a n c e i n c h o o s i n g I n i t i a l i t e r a t e s . The same can not be s a i d o f P2(0) w h i c h may l i e anywhere i n t h e range - o o <L p 2 ( 0 ) ^ o o . A s i d e from t h e f a c i l i t y o f c h o o s i n g i n i t i a l c o n d i t i o n s , t h e boundedness c o n d i t i o n s , D. 7 and D.8 , because t h e y a l  ways a p p l y , s h o u l d h o l d down t h e r a t e o f e r r o r p r o p a g a t i o n d u r i n g f o r w a r d i n t e g r a t i o n . The c o n t r o l v a r i a b l e i s t h e n c a l c u l a t e d by n o r m a l i z i n g the.' v - v e c t o r w i t h p , and b o t h of t h e s e would be a v a i l a b l e t o a good degree o f a c c u r a c y . I t s h o u l d be noted t h a t w i t h t h e tangent p l a n e method, each i t e r a t i o n r e q u i r e d the i n t e g r a t i o n o f (n+1) e q u a t i o n s as compared t o n e q u a t i o n s f o r t h e s t a n d a r d method, 3y u s i n g t h e i d e n t i t y D.6 , I t may be p o s s i b l e t o e l i m i n a t e the e q u a t i o n f o r p e n t i r e l y . I f such i s not the c a s e , t h e n t h i s drawback must be weighed a g a i n s t the o t h e r a d  vantages o f t h e method. 124 STANDARD METHOD TANGENT PLANS METHOD Guessed I n i t i a l C o n d i t i o n P 2 ( 0 ) 3 Number of i t e r a t i o n s f o r Convergence Guessed I n i t i a l C o n d i t i o n /3(0) T Number of i t e r a t i o n s f o r Convergence 18.0 2. n. c. .15 9.96 n. c. 12.0 1. n. c. .1 6.28 6 9.0 .5 n. c. .05 2.65 5 7.5 .25 8 .03 1.19 4 6.5 .083 4 .02 .46 4 6.0 0. 1 .0137 0. 1 5.5 -.083 4 .013 -.05 3 3.0 - .5 6 .01 - .27 3 0.0 -1.0 8 .008 -.416 4 -6 . -2.0 10 .007 -.49 5 -12. -3.0 11 .005 -.635 n.c. T a b l e D.l : A comparison o f t h e Number o f I t e r a t i o n s R e q u i r e d f o r Convergence U s i n g t h e S t a n d a r d and Tangent P l a n e Methods, (n.c. means no convergence) -e- S T M ^ A R D METHOD - © - i - 5 — T A N G E N T P L M M E . M E T H O D J 1 1 • i i i i .3 -2 -> 0 1 2 3 4 5 SJ T : M'/? Ai A L I Z E O 'N1T1AL CONbiTiohJ Corenari son. of the Regions of Convergence f o r the Standard Method and the Tangent P l a n e Method, 12? REFERENCES 1 . Kron, G. "Diakoptics, the piecewise sol u t i o n of large-scale systems" London, Macdonald (1963). 2 . R i t t e r , K. "A Decomposition Method for Structured Quadratic Programming Problems" Journal of Computer and System Sciences, Vol. 1, No. 3, Oct. 196?. 3 . Dantzig G. B. and Wolfe, P. "The Decomposition Algorithm f o r Linear Programming" Econometrica Vol. 29, No. 4, Oct. 1961. 4 . Mesarovic, M. D. "Self-Organizing Control Systems" IEEE Transactions on Applications and Industry, Sept. 1964. 5.. Kulikowski, R. "Optimum Control of Mul t i - dimensional and Multi-Level Systems" Advances i n Control Systems, Vol. 4, Ed. C, T. Leondes, Academic Press, New York (1966). 6 . Straszak, A. "Suboptimal Supervisory Control" i n Functional Analysis and Optimization edited by E. R. C a i a n i e l l o , Academic Press, New York 1966. 7 . Beckenbach, E. F. "Applied Combinatorial Mathematics" Wiley and Sons, New York (1964) p. 219 et seq. 8 . Zadeh, L. A. and Desoer, C. "Linear System Theory" McGraw H i l l , New York (1963). 9 . Balakrishnan, A. V. "Foundations.of the State- Space Theory of Continuous Systems" Journal of Computer and System Sciences Vol. 1, No. 1, Apr. 1967, pp. 91-116. 10 . Pontryagin, L. S. et a l . "Mathematical Theory of Optimal Processes" Wiley, New York, (1962). 1 2 8 11 . At h a n s , M. and F a l b , P. " O p t i m a l C o n t r o l " McGraw H i l l , New York, (1966). 12 . Ath a n s , M. " S t a t u s of O p t i m a l C o n t r o l Theory and A p p l i c a t i o n s f o r D e t e r m i n i s t i c Systems" IEEE T r a n s a c t i o n s on Au t o m a t i c C o n t r o l , V o l . AC-11, No. 3, J u l y 1966. 13 . K e l l y , H. J . , Kopp, R. E. and Moyer, H. G. " S i n g u l a r E x t r e m a l s " T o p i c s i n O p t i m i z a t i o n , ed. G. L e i t m a n n , Academic P r e s s , New York ( 1 9 6 ? ) . 1 4 . L e t o v , A. M. "The S y n t h e s i s of O p t i m a l R e g u l a t o r s " P r o c e e d i n g s o f t h e Second Congress IFAC, p. 2 4 9 , B u t t e r w o r t h s , London (1964). 15 . H a r a r y , F., Norman, R. Z. and C a r t w r i g h t , D. " S t r u c t u r a l Models; An I n t r o d u c t i o n t o Theory o f D i r e c t e d Graphs" W i l e y , New York (1965). 16 . Fan, L. T. and Chen, T. C. "The Co n t i n u o u s Maximum P r i n c i p l e , a s t u d y o f complex system O p t i m i z a t i o n " W i l e y , New York (1966). 17 . C r i t c h l o w , A. J . " G e n e r a l i z e d M u l t i - p r o c e s s i n g and MultI-programming Systems" 1963 F a l l J o i n t Computer C o n f e r e n c e , AFIPS Co n f e r e n c e P r o c e e d i n g s , V o l . 2 4 . Academic P r e s s , 1 8 . Conway, M. E. "A M u l t i - p r o c e s s o r System D e s i g n " 1963 F a l l J o i n t Computer Conference AFIPS C o n f e r e n c e P r o c e e d i n g s , V o l . 2 4 , Academic P r e s s . 19 . Pea r s o n , J . D. and Tak a h a r a , Y. "On t h e S y n t h e s i s o f a M u l t i - l e v e l S t r u c t u r e " Systems Re s e a r c h C e n t e r Report SRC 7O-A-65-25, CASE I n s t i t u t e o f Technology. 2 0 . P e a r s o n , J . D. " D u a l i t y and a D e c o m p o s i t i o n T e c h n i q u e " J o u r n a l SIAM on C o n t r o l , V o l . 4, pp. 164-172, Feb. 1966. 129 21 . P e a r s o n , J . 22 . Courant, R. D. " D e c o m p o s i t i o n , C o - o r d i n a t i o n and M u l t i - l e v e l Systems" IEEE T r a n s a c t i o n s on Systems S c i e n c e and C y b e r n e t i c s , V o l . SSC-2., Aug. 1 9 6 6 , pp. 3 6 - 4 0 . and H i l b e r t , M a t h e m a t i c a l pp. 233-238, D. "Methods of ' P h y s i c s , Volume I " I n t e r s c i e n c e ( 1 9 5 3 ) . 23 • H u r w i c z , L. and Uzawa, H. "A Note on L a g r a n g i a n S a d d l e P o i n t s " S t u d i e s i n L i n e a r and N o n - L i n e a r Programming, ed. Arrow, K. J . , H u r w i c z , L., and Uzawa, H. S t a n f o r d U n i v e r s i t y P r e s s ( 1 9 5 8 ) . 24 . P e a r s o n , J . D . "On C o n t r o l l i n g a S t r i n g of Moving V e h i c l e s " IEEE T r a n s a c t i o n s of A u t o m a t i c C o n t r o l , V o l . AC-12, No. 3, pp. 328-329, June 1967. 25 . C u l l u m , J . " P e r t u r b a t i o n s o f O p t i m a l C o n t r o l Problems" SIAM J o u r n a l on C o n t r o l , V o l . 4, 1966., No.3, PP. 4 7 3 - 4 8 ? . 26. M c G i l l , R. and Kenneth, P. " S o l u t i o n o f v a r i a t i o n  a l Problems by Means of a G e n e r a l i z e d Newton-Raphson O p e r a t o r " American I n s  t i t u t e of A e r o n a u t i c s and A s t r o n a u t i c s J . , V o l . 2, pp.l ?6 l -1766, October 1964 . 27 . Longmuir, A. G. and Bohn, E. V. "The S y n t h e s i s of S u b o p t i m a l Feedback C o n t r o l Laws" IEEE T r a n s a c t i o n s on A u t o m a t i c Control", V o l . AC-12, No. 6, Dec. 196?. 28 . S m i t h , F. W. "Design o f Q u a s i - O p t i m a l Minimum Time C o n t r o l l e r s " IEEE T r a n s a c t i o n s on A u t o m a t i c C o n t r o l , V o l . AC-11, No. 1 Feb. 1968. 29 . F r l e d l a n d , B.' "A T e c h n i q u e f o r Quasi-Optimum C o n t r o l " J o u r n a l o f B a s i c E n g i n e e r i n g , S e r i e s D, V o l . 88, No. 2, pp. 4 3 7 - 4 4 3 , June 1966. 130 30 . Masak, M. "An I n v e r s e Problem on D e c o u p l i n g O p t i m a l C o n t r o l Systems" IEEE T r a n s a c t i o n s on Au t o m a t i c C o n t r o l , V o l . AC-13, No. 1, Feb. 1968, p. 109. 31 . B e l l m a n , R. " I n t r o d u c t i o n t o M a t r i x A n a l y s i s " p. 231, McGraw H i l l , New York ( i960). 32 . Kalman, R. E. "A New Approach t o L i n e a r F i l t e r i n g and P r e d i c t i o n Problems" J o u r n a l o f B a s i c E n g i n e e r i n g , S e r i e s D, V o l . 82, I 9 6 0 . 33 . L u e n b e r g e r , D. G. "Observers f o r M u l t i v a r i a b l e Systems" IEEE T r a n s a c t i o n s on Au t o m a t i c C o n t r o l , V o l . AC-11, No. 2, A p r i l 1966. 34 . L u e n b e r g e r , D. G. " O b s e r v i n g t h e S t a t e of a L i n e a r System" IEEE T r a n s a c t i o n s on M i l i t a r y E l e c t r o n i c s , A p r i l 1964. V o l . MIL - 8 , No. 2. 35 . L e v l n e W. S. and Athans, M. "On t h e O p t i m a l E r r o r R e g u l a t i o n o f a S t r i n g o f Moving V e h i c l e s " IEEE T r a n s a c t i o n s on A u t o m a t i c C o n t r o l , V o l . AC-11, No. 3. J u l y 1966. 36 . K e l l e y , H. J . "An O p t i m a l Guidance A p p r o x i m a t i o n Theory" IEEE T r a n s a c t i o n s on Automatic C o n t r o l , V o l . AC -9, No. 4, Oct. 1964. 37 . B r e a k w e l l , J . V., Speyer, J . L. and B r y s o n , A. E, " O p t i m i z a t i o n and C o n t r o l of N o n - l i n e a r Systems U s i n g t h e Second V a r i a t i o n " SIAM J o u r n a l on C o n t r o l , V o l . 1, No. 2, 1963. 38 . S c h l e y , C. H. J r . and L e e , I . " O p t i m a l C o n t r o l Computation by t h e Newton-Raphson Method and t h e R i c c a t i T r a n s f o r m a t i o n " IEEE T r a n s a c t i o n s on A u t o m a t i c C o n t r o l , V o l . AC-12, No. 2, pp. 139-144, A p r i l 1967. 39 . Hamming, R. W. " N u m e r i c a l Methods f o r S c i e n t i s t s and E n g i n e e r s " p. 375, McGraw H i l l , New York (1962). 131 4o . 41 . ^3 • 44 . ^5 . 46 . Murtha, J.-C. " H i g h l y P a r a l l e l I n f o r m a t i o n P r o c e s s i n g Systems" i n Advances i n Computers, V o l . 7, ed. A l t , F. and R u b i n o f f , M., Academic P r e s s (1966). "Workshop S p a r t a n Barnum, A. A. and Knapp, M. A. (ed.) on Computer O r g a n i z a t i o n " Books (1963) a r t i c l e s by: 1) S l o t n i c k , D. L. et a l . 2) Comfort, W. T. 3) E s t r i n , G. e t a l . 42 . Lehman, M, IBM S t a f f "Survey o f Problems and P r e l i m i n a r y R e s u l t s C o n c e r n i n g P a r a l l e l P r o c e s s i n g and P a r a l l e l P r o c e s s o r s " P r o c e e d i n g s o f t h e IEES, V o l . 54, No. 12, pp. 1889- 1901, Dec. 1966. "An A p p l i c a t i o n O r i e n t e d M u l t i  p r o c e s s i n g System" IBM Systems J o u r n a l , V o l . 6, No. 2, 1967. C a r r o l l , A. B. and W e t h e r a l d , R. T, " A p p l i c a t i o n o f P a r a l l e l P r o c e s s i n g t o N u m e r i c a l Weather P r e d i c t i o n s " J o u r n a l f o r the A s s o c i a t i o n o f Computing M a c h i n e r y , V o l . 14, No. 3, J u l y 1967. L e i t m a n n , G. "An I n t r o d u c t i o n t o O p t i m a l C o n t r o l " McGraw H i l l , New York (1966). B l a q u i e r e , A. and Leitman n , G. "On the Geometry o f O p t i m a l P r o c e s s e s " i n O p t i m i z a t i o n T e c h n i q u e s , V o l . I I , ed. G. Leitman n , Academic P., New York (1967). 

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 25 19
France 7 0
United States 5 1
Japan 4 0
Canada 2 0
Australia 1 0
Azerbaijan 1 0
City Views Downloads
Beijing 22 0
Unknown 11 0
Tokyo 4 0
Ashburn 4 0
Shenzhen 3 19
Sydney 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0104602/manifest

Comment

Related Items