"Applied Science, Faculty of"@en . "Electrical and Computer Engineering, Department of"@en . "DSpace"@en . "UBCV"@en . "Masak, Mart"@en . "2011-08-22T19:26:59Z"@en . "1968"@en . "Doctor of Philosophy - PhD"@en . "University of British Columbia"@en . "The objective of this thesis is to investigate decomposition and its applicability to the theory of optimal control. The work begins with a representation of the structure of the optimal control problem in terms of directed graphs. This representation exposes a strong connectedness property leading to fundamental difficulties which are central in limiting the class of control problems to which decomposition can successfully be applied.\r\nComputational problems of optimal control are then considered, and decomposition is found to provide a framework within which to analyse numerical methods suitable for parallel processing. A number of such methods are shown and a numerical example is used to illustrate the viability of one of these.\r\nIn the second part of the thesis, the optimal control law synthesis problem is discussed together with an inverse problem. The latter concerns the requirement of a second-level co-ordinator in a hierarchical structure. A multi-level controller is then suggested for a class of systems. The effect of this controller structure is to provide a performance very close to the optimal while maintaining adequate sub-optimal control in case of a breakdown of the second-level co-ordinator. The structure is justified on the basis of the second variation theory of the calculus of variations.\r\nFinally, a new computational technique founded on the geometrical concepts of optimal control theory is introduced. This results in replacing the unstable co-state variables associated with Pontryagin's maximum principle with a set of bounded variables. The facility in the choice of initial iterates makes the method promising."@en . "https://circle.library.ubc.ca/rest/handle/2429/36811?expand=metadata"@en . "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 ............\u00C2\u00AB..\u00C2\u00BB.>.\u00C2\u00BB* <>.... Head of Department ..., \u00E2\u0080\u00A2 \u00C2\u00AB. 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 \u00C2\u00A3Ac^'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\u00C2\u00BB3 ) . Example 4.1 . .\u00E2\u0080\u009E 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 \u00C2\u00A3 =\u00E2\u0080\u00A2 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 \u00C2\u00AB 2 . . . . . . 0 . . . . . . . . 55 3\u00C2\u00AB5 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 \u00E2\u0080\u00A2' 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,-' \u00C2\u00A3 = . 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, \u00C2\u00A3 ~ 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 \u00E2\u0080\u00A2 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 \u00C2\u00A3 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 \u00C2\u00AB 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 \u00C2\u00A3 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 \u00E2\u0080\u00A2 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 \u00C2\u00A315} \u00E2\u0080\u00A2 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 \u00C2\u00BB 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\u00C2\u00AB z \u00C2\u00AB 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 = -\u00C2\u00A3( 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 \u00C2\u00A9screak-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 \u00E2\u0080\u009E _ 2 , 4- IT- 2 4- 9 C v v 4- n 2 a - ir2 o subject to J = | 5 + y + 2 \u00C2\u00A3 xy + u^ + v 2 )dt \u00C2\u00B1 = -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 + \u00C2\u00A3y + 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 \u00C2\u00A3 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 \u00C2\u00A3 , 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 \u00C2\u00A3 = 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) + \u00C2\u00A3x + 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 \u00C2\u00A3 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 \u00C2\u00A3l(y-z) 2 + x 2 + u 2 + v 2 + w2 } + p(f(x) + \u00C2\u00A3y + u) + q(g(y) + cx + v) + r ( - z + w) = p v = q w - r x - \u00E2\u0080\u0094 P - t q bx \"\ (y-z) - \u00C2\u00A3P - \u00E2\u0080\u0094 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 \u00C2\u00AB 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*.. and f-\u00C2\u00BB- , 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) = 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 \u00E2\u0080\u0094 \u00C2\u00BB - 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) = \u00C2\u00B0< 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 \u00C2\u00BB 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 * + \u00C2\u00A3, 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\u00E2\u0080\u009E.,x + a y* + p. + \u00E2\u0080\u0094 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 \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 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 \u00C2\u00BB 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 \u00C2\u00A3l ^ are closed\u00E2\u0080\u00A2convex regions of m^ -space N \u00C2\u00A3 n = n n. ^ 1 i = l , 2 , . . . N 1=1 1 1 N \u00C2\u00A3 m, = m m, > 1 \u00E2\u0080\u00A2 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 \u00C2\u00A3 = 1, Define P( \u00C2\u00A3> ) = 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( \u00C2\u00A3 ). 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 \u00C2\u00A3 . 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 \u00C2\u00A3. = 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 \u00C2\u00A3 . 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( \u00C2\u00A3 ). 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), \u00C2\u00A3 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 \u00C2\u00A3 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( \u00C2\u00A3^) can be computed. This process i s then repeated for succes-s i v e l y Increasing values of the parameter \u00C2\u00A3 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 \u00C2\u00A3 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(\u00C2\u00A3 ) has been obtained. Then, for -an i n i t i a l i t e r a t e for P ( \u00C2\u00A3 n + 1 ) , instead of Sol( \u00C2\u00A3 ), the f o l -lowing can be used: I n i t i a l Iterate = So.l(\u00C2\u00A3 n) + e n ) . ( \u00C2\u00A3 n + 1 --.&n) bSol( \u00C2\u00A3 n ) This naturally requires the computation of , d \u00C2\u00A3 which can be approximated by d S o l ( \u00C2\u00A3 n ) ~ S o l ( e , n + in,) - S o l ( e . n ) bz, &\u00C2\u00A3 where Se i s a very small change i n \u00C2\u00A3 . 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 Q , \u00C2\u00A3 ) i s a symbolic representation of the mapping * E 1 \u00E2\u0080\u0094* E n , P 0 \u00C2\u00A3 E 1 1 i e \u00C2\u00A3 e 1 and p(T) \u00C2\u00A3 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 ne n) +

Assume that the correct p D n which w i l l n u l l p(T) at \u00C2\u00A3 = \u00C2\u00A3 n i s known, i . e c + \u00C2\u00A3 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(\u00C2\u00A3 ) as t h e composi t e v e c t o r f u n c t i o n S o l ( \u00C2\u00A3- ) ov e r t h e i n t e r v a l t \u00C2\u00A3 [ 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 \u00C2\u00BB 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 ) ) = \u00C2\u00A3 Lhl ( S o l(\u00C2\u00B0)) - x i ( S o l ( O ) ) p,_0J J = l \u00C2\u00B0 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 \u00C2\u00A3 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 \u00C2\u00A3 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 ) \u00C2\u00BB i n c r e a s e \u00C2\u00A3 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 \u00C2\u00A3 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 \u00C2\u00A3 = 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 \u00E2\u0080\u0094 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 + \u00C2\u00A3-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 + \u00C2\u00A3 2 x 1 x ^ + 10 s a t ( p 2 / 1 0 ) x 2 ( 0 ) = -5 x 3 \" - x^ - \u00C2\u00A3 3 x 2 x 1 + 10 s a t ( p ^ / 1 0 ) x 3 ( 0 ) = 1 p l = 10 x1 + pj^- \u00C2\u00A3 ( 2 x ^ p 2 - 3x 2 p^) Pi ( D = 0 P 2 = 10 x 2 + p 2 - \u00C2\u00A3 ( X 3 P 1 - 3x 1 p^) P 2 ( l ) = 0 *3 = 10 x 3 4- p 3 - \u00C2\u00A3 ( 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 \u00C2\u00A3. 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 \u00C2\u00A3. = 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 \u00C2\u00A3 = 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 \u00C2\u00A3 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 , \u00C2\u00A3 =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 \u00C2\u00A9 STANDARD PARAMETRIC TRAJECTORY METHOD & STANDARD METHOD WITH LINEAR INTERPOLATION \u00E2\u0080\u00A2 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 \u00C2\u00A3S\u00C2\u00BB 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 \u00E2\u0080\u00A2 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 \u00E2\u0080\u00A2166 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 \u00C2\u00A3\u00E2\u0080\u00A2 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 \u00E2\u0080\u0094 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 \u00E2\u0080\u00A2+ 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\u00C2\u00AB2 . 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 \u00E2\u0080\u00A2 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\u00C2\u00AB1 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 \u00C2\u00AB 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 ) \u00C2\u00BB 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\u00C2\u00B0} \u00C2\u00BB 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 = \u00C2\u00A3 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=\u00C2\u00B0\u00C2\u00B0 , 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 ) = \u00C2\u00B0 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 \u00E2\u0080\u00A2 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 \u00C2\u00BB t h e n K n = K 2 2 \u00C2\u00BB a n d i f n^ = n 2 , t h e n CxD A01 ' t A\u00E2\u0080\u009E \u00E2\u0080\u009Et 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 \u00E2\u0080\u00A2assumed 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 \u00E2\u0080\u00A2 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 \u00E2\u0080\u00A2 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] \u00C2\u00BB 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 \u00E2\u0080\u0094 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 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 \u00C2\u00A3 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 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 \u00C2\u00A3 = . 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 ,'\u00C2\u00B0 J A ~ J o p t \u00C2\u00A3 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\u00C2\u00BB03 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 \u00C2\u00A3 , 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(\u00C2\u00B0) = x i 0 h = - a i y i + u i + \u00C2\u00A3 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 , \u00C2\u00A3. 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 \u00E2\u0080\u00A2 JC - J \u00C2\u00B0 P t J A \" J o ^ J A - J o ^ Jopt \u00C2\u00B0/o Jopt \u00C2\u00B0/o J - Jopt .5 \u00E2\u0080\u00A2 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 \u00E2\u0080\u00A2 378 5.727 2.5 2.5 . 2.5 2.5 466.018 466.295 467.846 .059 .392 6.644 - .5 - .5 r~ - \u00E2\u0080\u00A2 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 \u00C2\u00B0 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 \u00E2\u0080\u00A2 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 \u00E2\u0082\u00AC.= .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\ \u00E2\u0080\u00A2 \"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 \"\u00E2\u0080\u00A2X n \u00E2\u0080\u00A2 t o n. n where and 6x' f, 6x xxx f * f < \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 . 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 \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 ^* 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 <\u00C2\u00A3x 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 \u00C2\u00BB 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 = \u00C2\u00A3 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 ( \u00C2\u00AB - (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 \u00E2\u0084\u00A2 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 \u00E2\u0080\u0094 , 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^ \u00C2\u00BB 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 \u00C2\u00B0 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 \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 \u00E2\u0080\u00A2 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 \u00C2\u00A3 ( 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 \" \u00E2\u0080\u00A2 D \u00C2\u00AB 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 = \u00E2\u0080\u0094 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 \u00E2\u0080\u00A2 u s i n g D.5\u00C2\u00BB d /J_v\ = v - x & = f o x f x * J. o r v - v p = a.f - f x ' v D.9 p \u00E2\u0080\u00A2 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 - \u00E2\u0080\u0094 ( ( 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 - \u00C2\u00A3>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 \u00E2\u0080\u00A2 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\u00C2\u00A7(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 + \u00E2\u0080\u0094 ' xp + \u00E2\u0080\u0094 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\u00C2\u00B1 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 = \u00E2\u0080\u0094 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 ) ) . \u00C2\u00AB v 1 2 ( 0 ) +\u00E2\u0080\u00A2 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 \u00C2\u00A7>(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 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 \u00E2\u0080\u00A2 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 \u00E2\u0080\u00A2 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). "@en . "Thesis/Dissertation"@en . "10.14288/1.0104602"@en . "eng"@en . "Electrical and Computer Engineering"@en . "Vancouver : University of British Columbia Library"@en . "University of British Columbia"@en . "For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use."@en . "Graduate"@en . "Decomposition and optimal control theory"@en . "Text"@en . "http://hdl.handle.net/2429/36811"@en .