C.I NECESSARY CONDITIONS FOR A SOLUTION OF A NON-LINEAR PROGRAMMING PROBLEM by LINDA MAY LEE B . S c , U n i v e r s i t y of B r i t i s h Columbia, 1969 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n the Department of Mathematics We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA September, 1973 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 requirements f o r an advanced degree at the U n i v e r s i t y o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and study. I f u r t h e r agree 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 purposes may be granted by the Head o f my Department or by h i s r e p r e s e n t a t i v e s . I t i s understood t h a t c o p y i n g or p u b l i c a t i o n of 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 not be allowed without my w r i t t e n p e r m i s s i o n . Department o The U n i v e r s i t y o f B r i t i s h Columbia Vancouver 8, Canada Date - i i -ABSTRACT The conditions required for a s o l u t i o n of general non-linear programming problems of the form rain{f(x): x € X , g(x) ±0 , h(x) = 0} ; where f i s c a l l e d the objective f u n c t i o n , g the i n e q u a l i t y constraint and. h the equality c o n s t r a i n t , are presented i n t h i s t h e s i s . The following cases are studied: (1) X, a f i n i t e dimensional space; f , a r e a l valued function; and g and h f i n i t e dimensional vector functions. (2) X, an i n f i n i t e dimensional space; f , a r e a l valued function; and g and h either f i n i t e or i n f i n i t e dimensioanl vector functions. An a p p l i c a t i o n of t h i s type of problem to optimal control w i l l be given and the recent developments i n t h i s area w i l l be discussed. - i i i -TABLE OF CONTENTS Chapter 1. Preliminary M a t e r i a l 1.0 Introduction. • • • •. 1 1.1 D i f f e r e n t i a b i l i t y Concepts 2 1.2 Inverse and I m p l i c i t Function Theorems...... 5 Chapter 2. Optimization Problems i n F i n i t e Dimensional Spaces 2.0 Introduction. 12 2.1 Necessary Conditions 12 2.2 S u f f i c i e n t Conditions 24 Chapter 3. Optimization Problems i n Linear Spaces 3.0 Introduction. 26 3.1 General C r i t e r i a f o r Optimization by Linear Space Methods 26 3.1.1 Global Necessary Conditions ..26 3.1.2 Local Necessary Conditions ...29 3.1.3 Necessary Conditions f o r E q u a l i t y Constraints...... 33 3.2 Pshenichnyi's Approach.. ....36 3.3 Comparison of Pshenichnyi's Approach to Luenberger's 48 Chapter 4. A p p l i c a t i o n To Optimal Control 4.0 Introduction .51 4.1 Basic Necessary Conditions for Optimality 54 4.2 Example 57 Chapter 5. Developments • 59 Appendix 65 Bibliography. »67 - i v -ACKNOWLEDGEMENTS I am indebted to Dr. Rodrigo Restrepo f or suggesting the topic of the thesis and for h i s encouragement during the research of the t o p i c . My s p e c i a l thanks goes to Dr. U l r i c h Haussmann for allowing me a generous amount of h i s time and for h i s many constructive comments during the thesis preparation. - 1 -CHAPTER ONE; PRELIMINARY MATERIAL 1.0 Introduction During the l a s t decade, the.problem of optimization has attracted a l o t of a t t e n t i o n , since such problems a r i s e i n many f i e l d s ; f or example, i n automatic control theory, economics and even i n biology. Although optimization problems are not new i n mathematics, owing to the demands of economics and control theory and also owing to the appearance of the com-puter, an intensive and systematic i n v e s t i g a t i o n of such problems has only recently been s t a r t e d . The f i r s t category of problems was studied as early as 1925. This f i e l d i s c a l l e d Calculus of Variations and deals with problems of maxima and minima where d e f i n i t e i n t e g r a l s i n v o l v i n g one or more unknown functions are considered, subject to equality c o n s t r a i n t s . G. A. B l i s s and 0. Bolza did s i g n i f i c a n t work with t h i s type of problem. The next type of problem to be c l a s s i f i e d were l i n e a r programming problems; problems where the objective function and constraints are a l l l i n e a r . The theory for t h i s problem was widely developed by G. B. Dantzig and can be dated to 1948. By 1951, the Kuhn-Tucker theory was developed. This gives the necessary conditions for an extremum i n convex programming problems and, when i n d i f f e r e n t i a l form, formulates the necessary conditions for non-convex programming problems i n a f i n i t e dimensional space. In the decade f o l l o w i n g , the theory of optimal control was de-veloped. The basis of t h i s theory i s Pontryagin's Maximum P r i n c i p l e . This p r i n c i p l e permitted the,solution of various problems of mathematical and - 2 -applied nature and thus stimulated work i n mathematical programming. The embedding of optimal c o n t r o l theory into a general theory of necessary conditions was f i r s t c a r r i e d out by A. A. M i l y u t i n and A. Y. Dubovitski. They with H. Halkin and L. W. Neustadt have taken the present "modern" i n f i n i t e dimensional approach. This thesis presents the conditions required f o r a s o l u t i o n of general non-linear programming problems. The general problem i s of the form min{f(x): x £ X, gCx) < 0, hCx) = 0} ; f i s c a l l e d the objective function, g the i n e q u a l i t y constraint and h the equality constraint. In Chapter Two, the following assumptions are made: the space X on which f, g, and h are defined i s f i n i t e dimen-s i o n a l , f i s a real-valued function and g and h are f i n i t e dimensional vector functions. In Chapter Three, X i s assumed to be i n f i n i t e dimensional and f a fu n c t i o n a l defined on X . From here the problem breaks down to two d i s t i n c t problems depending on the dimension of the range of the constr-a i n t functions; that i s , f i n i t e or i n f i n i t e dimensional. Chapter Four gives a b r i e f introduction to optimal control problems and to t h e i r s o l u t i o n using mathematical programming r e s u l t s . Also an example i s given. F i n a l l y , Chapter Five discusses the. recent developments i n non-linear pro-gramming problems. The rest of t h i s f i r s t chapter deals with the tools required i n the l a t e r chapters. 1 . 1 D i f f e r e n t i a b i l i t y Concepts. Let X, Y be normed l i n e a r spaces and f be an operator defined - 3 -on a domain contained i n X and range contained i n Y . 1.1.1 D e f i n i t i o n The operator f : X .-> Y i s Gateaux d i f f e r e n t i a b l e at x i n X i f there e x i s t s an operator 6f(x;e) which i s l i n e a r ^ i n e for a l l e i n X and which s a t i s f i e s f ( x + Ae) - f(x) = X6f(x;e) + r ( x , A e ) where l i mte-UM2l = o for a l l e i n X . „ A A-K) 1.1.2 D e f i n i t i o n The operator f: X -* Y i s Frechet d i f f e r e n t i a b l e at x i n X i f there e x i s t s a continuous l i n e a r operator f C x ) : X -> Y s a t i s f y i n g f(x) - f(x) = f ( x ) ( x - x) + r(x;x - x) for a l l x i n X where the function r(x,z) i s such that lim ^ ^ > l ^ I = 0 . |z|^o P T The Frechet d e r i v a t i v e of f i s continuous at x i f given e > 0 there e x i s t s 6^-0 such that ||x - x|j < 6 implies ||f'Cx) - f ( x ) | | < e . If the d e r i v a t i v e of f i s continuous i n some open sphere S, f i s con-tinuously Frechet d i f f e r e n t i a b l e on S . Remark: If f'(x) i s a Frechet d i f f e r e n t i a l then i t i s also a Gateaux d i f f e r e n t i a l i . e . f(js)e = <5f(x,e) for a l l e i n X . But the converse i s not always true 1) In the usual d e f i n i t i o n of Gateau d i f f e r e n t i a b i l i t y , the l i n e a r i t y i s not assumed. - 4 — 1.1.2.1 Some Elementary Properties of Frgchet D e r i v a t i v e s . If follows from the d e f i n i t i o n that i f f and g are Fre*chet d i f f e r e n t i a b l e at x then af + gg i s Frechet d i f f e r e n t i a b l e at x and (af + (Bg)'(x) = af'tx) + gg'Gx) . The chain r u l e and an i n e q u a l i t y which replaces the Mean Value Theorem f o r the ordinary d i f f e r e n t i a b l e functions also.hold f o r Frechet d i f f e r e n t i a b l e f u n c t i o n . The proofs w i l l not be given here but may be found i n Luenberger [10]. The i n e q u a l i t y w i l l be stated here as i t w i l l be r e -ferenced l a t e r . Let f be Frechet d i f f e r e n t i a b l e on an open set X i n X . r o Let x be i n X and suppose that x + ah i s i n X for a l l a , o o 0 < a < 1 . Then || f (x + h) - f (x) 1 < ||b.| sup ||f'(x + ah) || . 0^a<l 1.1.3 D e f i n i t i o n . A f u n c t i o n a l f defined on a normed l i n e a r space X i s said to be q u a s i - d i f f e r e n t i a b l e at a point x i f there exists a convex weak - * closed set F(x) C X such that lim f (x + Xe) f (x) = f * c ^ f ( j r a U & ± n x x->oH ,+ A f*6.FCx) - 5 -1.2 Inverse arid I m p l i c i t Function Theorems This section deals with the major r e s u l t s from analysis under-l y i n g the l a t e r theorems i n optimization. The commonly known versions of the Inverse and I m p l i c i t Function Theorems f o r continuously d i f f e r e n t i a b l e functions i n Rn w i l l be stated. The reader i s referred to Rudiri [14] for proofs of these theorems. An I m p l i c i t Function Theorem generalized to functionals defined on l i n e a r spaces and an Inverse Function for Banach spaces w i l l be presented. We. follow the proofs i n [10] and [13]. 1.2.1 Inverse Function Theorem. Let f be a continuously d i f f e r e n t i a b l e mapping of an open set E of Rn into Rn where f ''(x) i s i n v e r t i b l e f o r some x i n E and where y = f(x) . Then (a) there e x i s t open sets U and V i n Rn where x i s i n U and y i s i n V and where f i s one to one on U and f(U) = V ; (b) i f g i s the inverse of f (which ex i s t s by (a)) defined i n V by g(f(x)) = x f o r a l l x i n U then g i s a continuously d i f f e r e n t i a b l e function on V . 1.2.2 I m p l i c i t Function Theorem. Let (x,y) be a vector of an open set E contained i n Rn + m and l e t f be a continuously d i f f e r e n t i a b l e n-dimensional vector function defined on E which s a t i s f i e s the following conditions: (1) f(x,y) = 0, (2) V f(x,y) i s non-singular; that i s , ; V^f(x,y)K = 0 implies K = 0 . - 6 -Then there i s a neighbourhood Z i n Rn of x, and an m-dimensional vector function e which i s continuously d i f f e r e n t i a b l e on Z such that (a) y = e (x) , (b) f(x,e(x)) = 0 for a l l x i n Z . 1.2.3 Generalized Inverse Function Theorem. Before the theorem can be s t a t e d , a d e f i n i t i o n i s required. 1.2.3.1 D e f i n i t i o n . Let f be a continuously Fre*chet d i f f e r e n t i a b l e mapping from an open set E i n a Banach space X into a Banach space Y . If x i n D i s such that f^ Cx) maps X onto Y , the point x i s said to be a regular point of the transformation f . 1.2.3.2 Theorem: Let x be a regular point of a continuously Frechet d i f f e r e n t i a b l e transformation f mapping the Banach space X into a Banach space Y . Then there i s a neighbourhood V of the point y = f Cx) and a constant K such that the equation f(x) = y has a,solution for every y i n V and the s o l u t i o n s a t i s f i e s ||x - x|| <_ K||y - y|| . Proof: Let L be the n u l l space of f'(x). Since L i s closed, the o r o ' quotient space X / L q i s a Banach space. If [x] denotes the class of elements equivalent to x ,modulo L q and i f A i s an operator on X / L Q defined by A[x] = f^ (x)x then A i s well-defined since equivalent elements x y i e l d i d e n t i c a l elements y i n Y .- A l s o , by d e f i n i t i o n , A i s l i n e a r , - 7 -continuous, one-to-one and onto and hence, by the Bounded Inverse Theorem [Appendix, Theorem 1 ] , A has a continuous l i n e a r inverse. Let y be an element of Y close to y and l e t g Q = 0, the zero element i n L^ . Now define the sequence of elements from X / L q and a corresponding sequence d"gn} with § n > a n element from L^ , r e c u r s i v e l y by L - L = A_ 1( y - f( x + g^ •-•)). . CD n n-1 n-1 As IIL - L , I] = i n f l|g - g ., || , s e l e c t g from the coset L such 11 n n-1" , T 1 1 6 6n - l " ' ° n n ^ a t | | g n - g n . 1 f l i 2 | | L n - L n _ 1 | Rewriting ( 1 ) , .-1. L n = A (y -H± + Bn_1)) + L n _ x ,. = A "'"(y - f ( x + g T) + A[g -]) by the d e f i n i t i o n of L .. \J \ ° n - l ° n - l n-1 and the properties of A , = A- 1( y " f ( x + g .) + f ( x ) g ..) by the d e f i n i t i o n of A J n-1 ° n - l and s i m i l a r l y , L = A 1( y ~ f (x + g _„) + f ( x ) g _ „ ) . Thus Define g = tg ± + (1 - t ) g n _ 2 and l e t F(x) = - A _ 1 ( f ( x ) - f'(x)x) . Applying the generalized mean value i n e q u a l i t y f o r Frechet d i f f e r e n t i a b l e functions (Section 1.1.2.1), t h i s implies ||F<* + g ^ ) " F(x + g n_ 2) || = ||g n_ 1 - g ^ s u p J l T f e + gfc) || . - 8 -Hence l L n " L n - l ' l - l A _ 1 H " g n - l ~ 8n-2" S U p Hf'<* + g t } " f'(*>H ' ( 2 ) 0< t<l By the s e l e c t i o n of and by the d e f i n i t i o n of , h±\\ - || 8 l - g j l 1 2||Ll - L j | =211^11 = 2f|A-1f| ||y - y|| . This implies for ||y - y|| small enough that ||g]_lj < "J r f 9 r some r > 0 and hence, i n t h i s p a r t i c u l a r case ||gtH = || t g ^ +: 0- ~ t) g Q || < r for 0 < t < 1 . By the cont i n u i t y of f " at x , for a given e > 0 there exists an r > 0 such that ||f'(x) - f "(x) || < e for j|x - x|| < r . There-fore (2) becomes: - L^ || < e||A "'"H ||g^ - gQ|| . By the s e l e c t i o n of > the preceding i n e q u a l i t y implies that ||g2 - g j | <_ 2\\h^ - I. || <_ 2e|[ A "*"|| || g^ - g£ Hence for s u f f i c i e n t l y small e , |g 2 " Sill 1 2| l gl " U ( 3 ) S i m i l a r l y i f flgj = || t g f c _ 1 + (1 - t)g k _ 2 | | < r , then I'gk " gk-lH l-lK-l " g k J ' ( 4 ) Moreover i f (4) holds f or a l l k <_ n , then IIgj - I I 8 l + ( g 2 - g_):+ ••• + ( g n - gn__>H I2|| g l|| < r , so that ||gt|| = ||tg n + (1 - t) g n _ 1 | | < r • Thu s by induction (4) holds for a l l k. Hence the sequence converges to an element g and correspondingly ~9 -the sequence {L^} converges to a coset L . Thus f (x + g) = y and ||g| < ^ g j < 4||A _ 1 || ||y. - y|| . F i n a l l y , by l e t t i n g K = 4||A''^|| , the theorem i s proved. 1 . 2 . 4 Generalized I m p l i c i t Function Theorem. Let x be a m-dimensional v e c t o r , l e t X € R and l e t f\ (A,x) for i = 1 , . ... , m be continuous r e a l valued functions which s a t i s f y the following conditions: (a) f ..(0,0) = 0 for i = 1 , m ; (b) f_j.(A,x) i s d i f f e r e n t i a b l e at X = 0, x = 0 ; (c) V-.f.CO.O) =0 f o r i = 1 , m A X (d) V xf(0,0) i s non-singular Then the system of equations f_^(A,x) = 0 has a s o l u t i o n for s u f f i c i e n t l y small X and there exists a s o l u t i o n x(A) with the property that o A Proof: Condition (b) i s equivalent to f(X,x) - f(0,0) - AV^fCO.O) - xV xfC0,0)|| < r c A 2 + j|x||2 ) CD z i n e q u a l i t y ( 1 ) becomes where ^* -> o as z -> 0 . Now applying conditions ( a ) , (s) , Cd) , the z: f(X,x) = (V xf(0,0))Cx) +rCX,x) C2) where ||r(A,x) || £ x(A 2 + ||x||2 ) . Gonsider the mapping g(X,-x) = x - (V f(0,0)) 1f(X,x) . Applying (2), t h i s becomes g(A,x) = - ( V ^ CO ,0)) _ 1 r (X ,x) and ||gCA,x)|| £ r ( A2 + ||x|2 )|| (V xf (0,0)) - 1|| . Without any loss of g e n e r a l i t y , the assumption that rCz) i s a non-decreasing function can be made since i f i t were not, r ( z ) can be replaced by wCz) = sup rCt) where 0<t<z w(z) > rCz) and thus W^ -*• 0 . Now set T(A) = i n f i x : K r ( A 2 + x 2 ) < x} (3) where K = || (? f(0,0)) 1|| . Since Kx(A 2 + A 2) < A f o r s u f f i c i e n t l y small X A , T (A) <_ A for a l l such A . By d e f i n i t i o n of infimum, f o r every such A , there ex i s t s a T (A) such that it (A) T CD £. t ( A ) + A and K r ( A2 + ( T * ( A ) ) 2 ) <_ x * ( A ) . By d e f i n i t i o n of x(A) , 2 - / 2 2 2 -T ( A ) - A < Kr(/A + (T(A) - A ) ) . Since r(z) i s a non-decreasing /2 2 function and since v A + w <_ A + w f o r A > 0 , w > 0 , th i s implies Kr( A2 + (x(A) - A2)2) £ Kr (A + ix(A) - A2 I) . Thus, x(A) - A2 < Kr"(A + |r(A) - A2|) . Further since x(A) < A f o r s u f f i c i e n t l y small A , Kr (A + |x(A) - A21) <_Kr(A + A) = Kr C2A) . Thus TCA) - A2 < KrC2A) or < 2 K * ( 2 D + A a n d s i n c e — A — Za • ^ + 0 as z * 0, -> 0 as X -* 0 . Thus T W -> 0 as A + 0 Z - A A - 11 -If ||x|| '< T*(X) then || gCX ,x) || < K r ( A 2 + ||x||2 ) < KrcA2 + ( T * ( X ) ) 2 ) < t*CA) . t h i s implies that the continuous l i n e a r map g(X,x) maps the b a l l ||x|| <_ T (x) in t o i t s e l f . Hence, by Brouwer's Fixed Point Theorem [Append-i x , Theorem 2], g(X,x) has a f i x e d point; that i s , there exists a point x(X) such that x(X) = g ( X , x ( X ) ) and ||x(X) || < x (X) . But the d e f i n i t i o n of g(X,x) implies f(X,x(X)) = 0 ; that i s the set of non-linear equations r consideratic ie s MU 0 unde onsideration has a s o l u t i o n . A l s o , since lk_i_ll< ^ } t h i s A A impl •> -> as X 0 CHAPTER TWO: OPTIMIZATION PROBLEMS IN FINITE DIMENSIONAL SPACES. 2.0 Introduction This chapter presents the necessary and s u f f i c i e n t s conditions for optimality when the objective function and constraints are f i n i t e dimensional. The mathematical programming problem to be studied here i s : M: min f ( x ) : x € X q , g(x) 1 0 , hCx) = 0 where f i s a f u n c t i o n a l , g i s an m-dimensional vector fun-c t i o n , h i s a k-dimensional vector f u n c t i o n , a l l defined on X , a subset of R° . o 2.1 Necessary Conditions. In the necessary optimality conditions, the d i f f e r e n t i a b i l i t y property of the functions play a c r u c i a l r o l e since t h i s i s used to l i n -earize the nonlinear programming problem. Lemma 2.1.1 Let X • be a convex set i n Rn with a non-empty i n t e r i o r : i n t X ^ , and l e t E be an open set i n Rn . Let f be an -^.-dimensional vector function and l e t h be a k-dimensional vector f u n c t i o n , both defined on some open set containing X q . Let x be an element from E , fCx) = 0 and h(x) = 0 . Let f be d i f f e r e n t i a b l e at x , l e t h be continuously d i f f e r e n t i a b l e i n an open set containing x and l e t Vh^(x) for j = 1, k be l i n e a r l y independent. I f the equations f(x) < 0 and hCx) = 0 have no s o l u t i o n x i n X r\ E then the equations - 13 -VfCx)(x - x) < 0 and Vh(x)(x - x) = 0 have no s o l u t i o n x i n i n t X o Proof: Case k > n : This case i s excluded because the assumption that Vh.Cx) , j = 1, k , i s l i n e a r l y independent implies that k i n . Case k == n : Since the l i n e a r independence of Vh '(x) , j = 1, ..., k , i s equivalent to the n o n - s i n g u l a r i t y v o f Vh(x) , Vf(x)(x - x) < 0 cannot hold because Vh(x)(x - x) = 0 implies that (x - x) = 0 . Thus neither the l i n e a r nor the nonlinear equations Vf(x)(x - x) < 0 can be solved. Case 3 0 < k < n : The proof for t h i s case follows from an i n d i r e c t attack because the way the lemma i s stated i s the way i t w i l l be a p p l i e d , not the way i t i s proved. Instead the proof shows that i f the equations Vf(x)(x - x) < 0 and VhCx)(x - x) = 0 have a s o l u t i o n x i n i n t X then the equations o fCx) < 0 and h(x) = 0 have a s o l u t i o n x i n X A E . o Let x i n i n t X q be. such that Vf Cx) (x --x) < 0 and Vh(x) (x - x) = 0 . For a l l x i n R l e t Cx^.x,,) form a p a r t i t i o n of n-k k - -x such that x^ i s i n R and x 2 i s i n R . Then Vh(x) = (V h(x) , Xl V h(x)) Since VhCx) i s non-singular, t h i s implies i n p a r t i c u l a r that X2 V hCx) i s non-singular. Thus, since hCx) = 0 , "and since V hCx) i s ^2 ^2 non-singular and h i s continuously d i f f e r e n t i a b l e i n an open set containing x , the I m p l i c i t Function Theorem [section 1.2.2] states that there e x i s t s n-k -an open set W i n R containing x^ and a k-dimensional d i f f e r e n t i a b l e - 14 " vector function e on W such that (a) x 2 = eCxD and (b) hCx^,e(xD) = 0 for a l l • x^ i n W . Since W i s open and since x. i s i n W , . there e x i s t s 6 > 0 1 o such that for a l l 6 < 5 , • (x- + S(x •-•x,-)) i s i n W . Thus, since e o 1 1 1 ' • i s d i f f e r e n t i a b l e at x^ i n W , t h i s implies that e(x, + - x n)) = e ( x j + 6ve(x-)(x - x j + o(6) f o r a l l 6 < 6 . (1) 1 i l l 1 1' O ' Since h i s d i f f e r e n t i a b l e at x and since hCx^,eCxD) = 0 . f o r a l l x i n W, by chain r u l e , V h(x) + V h(x)Ve(x..) = 0 and m u l t i p l y i n g ^2 by (x, - x ) t h i s becomes V h(x) (x - x ) + V h(x)Ve(x )(x - x ) = 0 . -L - i - ^2 But the assumption Vh(x)(x - x) = 0 i s equivalent to V h C x ) ^ - x.) + V h(x)(x 9 - x„) = 0 . Thus V h(x) (x 0 - x„) x ^ 1 1 x 2 I I x 2 2 I V : hCx)Ve(x,)(x n - x..) and the non-singularity of V K(x) implies x 2 . i i i x 2 (x 2 - x 2) = V e C x J C ^ - x j . (2); Using C2) and the f a c t that x 2 = eCxD , equation (1) becomes e C ^ + 5 0 ^ - x j ) = x 2 + <5(x2 - x 2) + o(6) f o r a l l 6 < 6 q . (3) Because x i s i n i n t (by assumption) and by d e f i n i t i o n of ^ A o (o) o(6) , there e x i s t s 6^ > 0 such that for a l l 8 < 6^, (x^,x 2 H j ~ - ) i s i n X . In p a r t i c u l a r 5, can be chosen such that 0 < 6, *<<5 . Since o r 1 1 o — * — — a o(6)~ x i s i n "7X and since " X i s convex, (1- 6)(x.,x 0) + 6(x-,x 0 -\ ~ - ) o o - J V / v i » 2 1' 2 . o i s i n X q for a l l 6 < 6^; that i s , (x^ + S(x - x^) , * 2 + 6(x 2 - x 2) + o(6)) _ 15 _ i s i n X q which by applying equation (3) i s . equivalent to (x^ + <S(x^ - x ^ ) , e(x, + S(x - x,))) • i s i n X f o r a l l 6 < 6. . Furthermore since x i s 1 1 1 o 1 i n E and since E i s open, there exists <$2 > 0 such that for a l l 6 < 6^, Cx^ + S(x^ - x ^ ) , eCx^ + 6 Cx^ - x^))) i s i n E . Hence, l e t t i n g 6^ = min{6 1,6 2} , Cx, + <5(x, - x j . - ^ i c . + 6(x '- x.))) i s i n X P\ E f o r a l l <5 < 6. . (4) 1 1 1 " ! 1 1 o 3 Since h(x^, e(x^)) = 0 for a l l x^ i n W , and since for a l l 6 < 6 Cx, + clCx, - x,-)) Is i n W and since 6„ < 6 0 < 6 4 then for o l 1 1 3 — 2 • o ' a l l 5 < 6 ., h ^ + S(x± - x±) , e(K± + 6 (2^---x^-))) = 0 . F i n a l l y , since f i s d i f f e r e n t i a b l e at x, t h i s implies the existence of <5. such that 6, < 6„ and such that for a l l 6 < 6, 4 4 o 4 f ^ + - X;L) , e(x;L + 6(x 1 - x^))) f f ( X ; L + 6( X ; L - x x) , x 2 + 6(x 2 - x 2) + o(5)) , by equation (3) , = f CCx 1,x 2) + 6 ( 3 ^ - X ; L , x 2 - x 2 + )) , = fCx) + elfVv f(x)(x. - x.) + V f(x)Cx 9 - x„) +r V f(x) ] + 0(6) x^ 1 1 x 2 2 / x 2 0 by the d i f f e r e n t i a b l i t y of f at x , = 6{VfCx)Cx - x)] + 7„ ftx)o(<5) + o(j5) since f(x) = 0 . x 2 But by assumption -Vf(x)(x.- x) < 0 which implies that there exists ^5 > 0 such that 6_ < <S, and such that 5 4 f C ^ + S(x± - x ^ , e(K± + 6 ( 2 ^ - x 1 ) ) ) < 0 for a l l 5 < <55 . - 16 -Hence, l e t t i n g 6 = min{6^,(5^} , for a l l 6 < <5 f + 6( X ; L - x ^ , e O ^ + 6 0 ^ - x 1 ) ) ) < 0 and h(x x + 6 ^ - x±) , e(x± + 5(i± - x^))) = 0 where (x.. + 6(x. - x.)) i s i n X H E . i l ± o Case 4 k = 0 : Suppose there e x i s t s x i n i n t X q s a t i s f y i n g Vf(x)(x - x) < 0 . Then i t must be shown that there exists x i n X q E s a t i s f y i n g f(x) < 0 Since x i s i n X /~\ E (by hypothesis) and since X q i s convex and E i s open, there e x i s t s <5 > 0 such that for a l l 8 < 6 < 1 , o o (x + <5(x - x ) ) ' i s i n X H E . By the d i f f e r e n t i a b i l i t y of f at x , there e x i s t s 6.. > 0 such that cL < <S and such that f or a l l 6 < cS, 1 1 o 1 f( x + S(x - x)) = fCx) + S[Vf (x)(x - x) + ^1^- ] , = S[Vf (x)(x - x) + ] since f(x) = 0 . o By the assumption Vf (x) (x - x) < 0 and by d e f i n i t i o n of o(<$) , there ex i s t s §2 > 0 such that 6^ < 6^ and such that for a l l 6 < 6^ , f (x + <5(x - x)) < 0 . 'Lemma 2.1.2 Let X , E, x and f be as given i n Lemma 2.1.1. Let h be o a k-dimensional vector function which i s continuously d i f f e r e n t i a b l e i n an open set containing x . If f(x) < 0 and h(x) = 0 have no solu t i o n i n - SL ' - k - - - / X Q n E then there e x i s t s p i n R , q i n R with p f- 0, (p,q) F 0 _ 17 _ satisfying [pVf (x) + qVhCx)]Cx - x ) >. 0 for a l l x in the closure of X Proof: o Case 1: Vh.Cx), j = 1, ... , k .linearly dependent. - k -This, implies that there exists q in R where q ^ 0 such that ' qVh(x) = 0 . Therefore for p = 0, [pVf(x) + qVhOOKx - x) = 0 for a l l x in the closure of X Case 2: VhjCx), j = 1, ..., k, l i n e a r l y independent. Since X i s convex, then i n t X i s convex. Let FCx) = Vf(x)(x - x) o o and HCx) = VhCx) Cx - x) . Define for each x i n i n t X q , the set SCx) = (Cy.z): y€ R£, z € Rk, y > FCx), z = H(x)} and l e t S = VJ S(x) . x i n t X o Observe that S i s convex since i f Cy^ >z-j_) a n C* ^2^2^ a r e ^ n ^ ' t n e n for 0 < X < 1 , Cl - X)yx + Xy2 > (I - A)FCx1) + XF(x2) , (1 - X)VfCx)Cxx - x) + XVf(x)(x2 - x) , = Vf(x)[Cl - X ) ( X l - x) + X(x 2 - x)] , and = F((l -X ) x x + Xx2) ; Cl - X)z± + \z± = (1 -. X)RCx1) + M(x2) , = (1 " ^)Vh(x) ( x 1 - x) + XVh(x) (x 2 - x) , - 1 8 -= Vh(x) [ ( 1 - A) ( X ; L - x) +.\A(x2 - x) ] , = H [ ( l - \)x1 + Ax 2] . Since f(x) < 0 and h(x) = 0 have no s o l u t i o n x i n X H E , by o J Lemma 2 . 1 . 1 , F(x) < 0 and H(x) = 0 have no so l u t i o n x i n i n t X o Z k This implies that ( 0 , 0 ) i s not i n S which i s i n R x R • Apply the separation theorem [Appendix, Theorem 3 ] f o r the convex sets S and Z k { ( 0 , 0 ) } . Then there e x i s t s p e R and q fc R where (p,q) ^ 0 such that for (u,v) i n S , pu + qv >_ 0 . . Note that p > 0 since each u.^ can be made as large as desired. Let e > 0 , u = FCx) + ee where e i s the a l l ones vector and v =,H(x) where x i s i n i n t X q . Then obviously (u,v) i s i n S(x) and hence i n S . Thus pu + qv = pF(x) + pee + pH(x) >^ 0 or equiv-a l e n t l y , pF(x) + qK(x) >_ - epe for a l l x i n i n t X Q . But since e > 0 i s chosen a r b i t r a r i l y , one must have pF(x) + qH(x) >_ 0 for a l l x i n i n t X Q . Hence: i-nf (pF(x) + qH(x)) > 0 . ( 1 ) x€int X o F i n a l l y , since [pVf(x) - qVhCx)](x - x) i s continuous i n x and i n f a c t l i n e a r , equation (1) holds for a l l x i n the closure of X Q . Theorem 2 . 1 . 3 Let X be a convex set i n R n with a non-empty i n t e r i o r : o i n t X . Let x be a so l u t i o n to the minimization problem M . Let f o - 19 " and g be d i f f e r e n t i a b l e at x and h be continuously d i f f e r e n t i a b l e i n an open set containing x . Then there exists V Q i n R , r i n R and s i n R such that (a) Cr QVf(x) + ieVg(x) + sVh(x))Cx - x) >_ 0 for a l l x i n the closure of X ; o (b) rg(x) = 0 ; jCc) CrQ,-f) > 0 ; (d) G0,r,s) i 0 . Proof: Let I = { i : g ± Cx) = 0} and J = { i : gAx) < 0} then I U J = {I, 2, m} and l e t m^ ., m^ denote the number of elements i n the set I and J r e s p e c t i v e l y so that m^ + nij = m . Since g i s de-fined on some open set containing X q and since g i s continuous at x , there e x i s t s <5 > 0 such that o E = {x: g < 0,||x - x|| < <5 } i s an open set i n Rn . J o If Lemma 2.1.2 can be a p p l i e d , the theorem i s proved. Let F be the mapping from Rn to R x where F(x) = [f(x) - f ( x ) , g I(x)] . Note that F(x) = (f (x) - f Cx) , gjCx)) = (0,0) and that F i s d i f f e r e n t i a b l e at x since f and g are. A l s o , since x i s i n X q and x i s i n E, x i s i n XQP\ E . Now, since x i s the s o l u t i o n to the minimization pro-blem, then the equations f (x) — f(x) •< 0 and h(x) = 0 have no so l u t i o n x i n X n E , or equivalently F Cx) < 0 and H(x) = 0 have no solu t i o n i n X- O E . Hence, by Lemma 2.1.2, there e x i s t s Cr ,r T) i n R x R » " 2 0 -s i n R.k with ( r ^ r ^ . ) >_ 0 , ( r o , r ^ , s ) / 0 . s a t i s f y i n g CC^.rJVFCx) + sVh(x))(x - ic) > 0 for a l l x i n the closure of X ,., and, by d e f i n i t i o n of F, t h i s implies that ( r Q V f Cx) + -r^Vg '(it) + sVh(x))(x - x) > 0 . By d e f i n i n g Xj = 0 and r = (r ^ r ^ . ) . i n R™, rg(ic) = r^Cx) + r^jCx) = 0 and rVgCx) = r Vg Cx) + r Vg Cx) = r Vg Cx) . Hence the theorem i s proved. i- JL J J J_ J-Remark: If the convexity requirement on X q i s replaced by the r e q u i r e -ment that X q be open then a stronger necessary optimality condition than condition Ca) i n the previous theorem i s obtained. This i s known as the Fritz-John Stationary Point Necessary Optimality Theorem. Theorem 2.1.4 Let X q be an open set i n R n . Let x be a (global) so l u t i o n of the minimization problem M or a l o c a l s o l u t i o n thereof; that i s fCic) = min{fCx): x £ X C\ B.Cx), gCx) < 0 , hCx) = 0} where B.(x) i s an o o — 0 open b a l l around x with radius 6 I Let f and g be d i f f e r e n t i a b l e at x and h be continuously d i f f e r e n t i a b l e i n an open set containing — — •*• m — lc x . Then there e x i s t s r i n R, r i n R ,. s i n R where o Crd,r,s) f 0 such that r Q V f ( x ) + rVg(ic) + sVh(x) = 0 , rg(ic) = 0 and ( r o , r ) >_ 0 . Proof: Let x be a global or l o c a l s o l u t i o n of the minimization problem. Then since X q i s open, there e x i s t s B^Cx) > an open b a l l around x with radius X such that B. (x) C B„(x)C X and such that A O O fCx) = min{fCx): x € B (ic) , g(x) <^0, h(x) = 0} . - .21 ~ Since B. Cx) i s convex and has a non-empty i n t e r i o r (x € B Cx)) , A A Theorem 2.1.3 can be.applied thus giving TQ i n R, r i n Rm , s i n Rk , Cr Q,r,s) f 0 where (r"0>-r) >_ 0 such that (r VfCx) + rVg(x) + sVh(x))(x - x) > 0 f o r a l l x i n B. Cx) CD o A and rg(x) = 0 . Since, for some p > 0, Cx - p[r QVfCx) + rVg(x) + sVh(x)]) i s i n B^Cx), then, by i n e q u a l i t y ( 1 ) » t h i s implies r Q V f ( x ) + rVgCx) + sVh(x) = 0 Remark: In the Fritz-John necessary optimality c r i t e r i a , there i s no guarantee that r ^ > 0 . I f ' r = 0 the necessary op t i m a l i t y c r i t e r i a does not say much about the minimization problem since the function f , i t s e l f , disappears; thus any other function could play i t s r o l e . I t i s possible to exclude such cases by introducing r e s t r i c t i o n s , known as con-s t r a i n t q u a l i f i c a t i o n s on the constraints g(x) <_ 0 and h (x) = 0 . There are many constraint q u a l i f i c a t i o n s , some.weaker than others but a l l giving the same r e s u l t , namely r Q > 0 . The one presented next gives a very elegant proof although i t s r e s t r i c t i o n s are not the weakest. Other con-' s t r a i n t q u a l i f i c a t i o n s can be found i n Mangasarian [11]. The mod i f l e d Arrow-Hurwicz-Uzawa Constraint Qualif icat i o n . Let X q be an open set i n Rn , l e t g and h be m-dimensional and k-dimensibnal vector functions on X q and l e t X ={{x: x 6 X Q , gCx) ±_ 0, hCx)'= 0} . The functions g and h are said to s a t i s f y the modified - 22 -Arrow-Hurwicz-Uzawa constraint q u a l i f i c a t i o n at x i n X i f Ca) g i s d i f f e r e n t i a b l e at x Cb) h i s continuously d i f f e r e n t i a b l e at x Cc) Vh^(.x) for i = 1, k are l i n e a r l y independent Cd) there e x i s t s a s o l u t i o n - z i n Rn . such that Vg^Cx)z > 0 and Vh(x)z = 0 where I = { i : g^Cx) = 0} . Mangasarian r e f e r s only to the r e s t r i c t i o n s . o n the constraints and not on the objec t i v e f u n c t i o n . A d i f f e r e n t approach where the constraint q u a l i f i c a t i o n s involve both the/objective function and the constraints has been developed by Geoffrion [6]v : This approach s i g n i f i c a n t l y weakens the hypothesis demanded by Mangasarian but i n t h i s chapter Mangasarian's approach w i l l be described. The following theorem i s known as the Kuhn-Tucker Stationary-point Necessary Optimality Theorem. Theorem 2.1.5 Let X q be an open set i n Rn and l e t x be a global s o l u t i o n of the minimization problem M or a l o c a l s o l u t i o n thereof. Let f and g be d i f f e r e n t i a b l e at x and let. h be continuously d i f f erentiable i n an open set containing x . Let g and h s a t i s f y the modified Arrow-Hurwicz-Uzawa constraint q u a l i f i c a t i o n at x . Then there e x i s t s u i n Rm, v i n Rk such that VfOO + uVg(x) + vVhCx) = 0, u > 0, and ugOO = 0 . Proof: Since X q , f , g, h and x s a t i s f y the assumptions of Theorem 2.1.4, t h i s implies that there e x i s t s r i n R, r i n Rm , - 23 -and s i n Rk where ( r Q , r , s ) ^ 0, Cr Q,r) > 0 such that rQVfCx) + rVg(x) + sVh(x) = 0 and. rg(x) = 0 . Note that i f TQ > 0 then by l e t t i n g u = r / r Q and v = s/r0 ' t n e theorem i s proved. Suppose r^ = 0 . Case 1: r = 0 . This implies that s ^ 0 and sVh(x) = 0 . Since h s a t i s f i e s the constraint q u a l i f i c a t i o n , Vh. '(x)' f o r i = 1, k are l i n e a r l y independent therefore i f sVhCx) = 0 then s = 0 which i s a c o n t r a d i c t i o n . Thus, i f r = 0 then r. > 0 . o Case 2: r f'0 . This implies that r > 0 . Let I = { i : g±Cx) = 0} and J = { i : g^G). < 0} . Then rg(x) = r^ gjCx) = 0 (1) and ?VgCx) + sVh(x) = r IVg I Cx) + r / g / x ) + iVh(x) = 0 . (2) By d e f i n i t i o n of I and J , equation (1) implies that r = 0 thus Tj. > 0 . Substituting t h i s into (2), t h i s implies that ?IVg ICx) + s"Vh(x) = 0 • (3) Since f and g s a t i s f y the modified Arrow-Hurwicz-Uzawa constraint q u a l i f i c a t i o n , then there e x i s t s z i n Rn such that - - - k Vg][(x)z > 0 and Vh(x)z = 0 . Thus, since r ]. > 0 for a l l s i n R , r IVg ] .Cx)z + sVh(x)z = (r ; [Vg I(x) + sVh(x))z > 0 contradicting equation (3). Therefore, for r / 0, r > 0 . o 2.2 -Sufficient Optimality Criteria. • Theorem 2.2.1 . Let X q be an open set in R N- and let f, g, h be, respec-tively, a numerical function, an m-dimensional vector function and a k-dimensional vector function, a l l defined on X . Let x be in X o o ' let f and g be convex and differentiable at. x and let h be a linear _ lc equality constraint. If there exists u in R and v in R such that (x,u,v) satisfy the following conditions: Ca) VfCx) + uVgCx) + vVhCx) = 0 , Cb) ugCx) = 0 , (c) gCx) < 0 , Cd) hCx) = 0 , (e) u > 0 , then x is a solution of the minimization problem M . Proof: Let X = {x: x € X q, gCx) ± 0, hCx) = 0} . Since h is a linear equality constraint, hCx) = Bx - d = 0 for a l l x in X where B is a k x n matrix and d is some constant vector in R . Then Bx = d can be substituted for hCx) = 0 and VhCx) = B . Since f is convex and differentiable at x , fCx) - fCx) 1 VfCx)Cx - x) for a l l x in X . CD - 25: -Condition Ca) implies that Vf(x) = - uVgCx) - vVhCx) or equivalently, Vf (x) Cx - x) = - uVgCx) Cx - x) - vVhCx) Cx - x) . C2) Since h(x) = 0, Bx = d, and by: the linearity of h , VKCx) Cx - x) = BCx - x) = 0 for a l l x in X . Also, since g is convex and differentiable at x , Vg(x) (x - x) ^gCx) - gCx) . But because u 0, gCx) f_ 0 and ugCx) = 0, for a l l x in X - uVgCx) Cx - x)>^ u"[ - gCx) + gCx) ] = - ug(x) >. 0 . Therefore equation (2) becomes: VfCx) Cx - x) >_ ^ ugCx) >_ 0 . Hence by inequality (1)» f Cx) - f Cx) >_ 0 for a l l x in X and since g(x) <_ 0 and h(x) = 0, x- is i n X . Thus x is the solution to M . Remark: The assumptions of this theorem, namely, the convexity of f and g and the linearity of the equality constraint, can be weakened somewhat since not a l l the properties of convex functions are needed. For example, f need only be.pseudo-convex at x ; that is i f f is d i f f e r -entiable at x in X and i f x is in X where VfCx)Cx - x) >_ 0, then f Cx)' >_.f (x) > g be quasi-convex at x , that is for x in X where g(x) <^ g(x) and where for, 0 < A < 1 , Cl - A)x +? Ax is in X , then gCCl - X)x + Ax) <^ gCx) ; and f i n a l l y the equality constraint hCx) = 0 need not be linear so long as h is differentiable, quasi-convex and quasi-concave at x . The proof is very similar to the previous proof and can be found in Mangasarian [11], - 26 -CHAPTER THREE: OPTIMIZATION PROBLEMS IN LINEAR SPACES 3.0 Introduction: In t h i s chapter, optimality c r i t e r i a are developed for mathematical programming problems where the objective f u n c t i o n a l and the constraints are defined on l i n e a r spaces. The f i r s t s e c tion deals with the necessary and s u f f i c i e n t conditions f o r the problem with constraints which are map-pings from a l i n e a r space into a normed space. The necessary c r i t e r i a are approached i n two ways: the global theory r e l y i n g on convexity and the l o c a l theory using d i f f e r e n t i a b i l i t y . A lso, necessary conditions f o r the case where only equality constraints are present i n the problem w i l l be developed. Section 3.2 deals with the necessary c r i t e r i a f o r a s l i g h t l y modified problem; namely, where the constraints are a c t u a l l y functionals defined on a l i n e a r space. F i n a l l y , i n Section 3.3, a comparison of the necessary, conditions for the two problems i s presented. 3.1 General C r i t e r i a f o r Optimization by Linear SpaCe Methods. This presentation follows Luenberger [10] 3.1.1 Global Necessary Conditions. The basic problem to be considered i n t h i s section i s : L^: min{f(x): x 6 X q, gCx) 1 8} where XQ i s a convex subset of a l i n e a r space X , f i s a convex f u n c t i o n a l on X q and g i s a convex mapping from X Q into a normed space Z which has a p o s i t i v e cone P . - 27 -Consider t h i s problem i n the space R x Z . I f u were the s o l u t i o n to t h i s problem then, by convexity, there would ex i s t s a hyper-plane which l i e s below f(x) for a l l x i n X q where gCx) 1 9 and which goes through the point (y Q,8) . This separating hyperplane cor-responds to the point ( l , z )• i n R x Z where y = i n f {f(x) + z* gCx)} . ° x€X o Theorem 3.1.1.1 Let X be a l i n e a r space and X a convex subset of X . Let r o Z be a normed l i n e a r space with p o s i t i v e cone P having a non-empty i n t e r i o r . Let f be a real-valued convex fu n c t i o n a l on X q and g a convex mapping from X to Z . Assume the existence of a point x^ i n X q for which gCx^) < 8 ;• that i s , g(x^) i s an i n t e r i o r point of N = - P . l e t y = i n f { f ( x ) : x € X , gGO < 0} and assume y i s o o — o * * * f i n i t e . Then there i s an element z i n Z , z > 8 such that o o — y = i n f { f Cx) + z gCx): x € X } . o o o Furthermore, i f the infimum i s achieved by an x i n X for which J o gCx) <. 8 then z Qg(x) = 0 . Proof: In the space W = R x z> define the following sets: l e t ACx) = {Cr»z): r >_ f Cx), z >_gCx)} for each x i n X ; l e t A = U A(x) 0 x^X o and l e t B = { ( r , z ) : r <_ y , z <_ 8} . Obviously CMo,8) i s i n B and, - 28 -since x^ i s i n X q , .the'point CfCx^)., gCxD) i s i n A . Since f and g are convex, the sets A, and B are convex and by d e f i n i t i o n of U q , A contains no i n t e r i o r points of B . A l s o , since N = - P has an i n t e r i o r p o i n t , by the d e f i n i t i o n of B i t contains an i n t e r i o r p o i n t . Thus by the separating hyperplane theorem, [Appendix, * * * Theorem 4] there e x i s t s a non-zero element w = (r ,z ) i n W such o o' o that * * r Q r ^ + Z Q Z ^ ±_ r 0 r 2 + Z 0 Z 2 ^ o r a 1 1 1 , Z1^ "'"n ^ a n t ^ ^ r2' Z2 ^ n ^ Since x^ — VQ and /.9 Cby d e f i n i t i o n of B), equation Cl) implies * * that r > 0 arid z > 0 . But suppose r = 0 then since w i s non-o — o — rr Q w Q * zero, Z q > 0. Since (y o,0) i s i n B , for r Q = 0 equation Cl) implies that Z Q Z ^ >_ 0 for a l l ^xi'z\} * n ^ . In p a r t i c u l a r for * CfCx^), gCxD) i n A , t h i s implies that z Qg(x^) >_ 0 . But t h i s contra-* d i e t s the f a c t that gCx,) < 0 and z > 0 . Therefore r. > 0 and ° 1 o o without loss of g e n e r a l i t y , take r = 1 . Now applying x^ = 1 and the fa c t that (U q,0) i s an element of B and i s a r b i t r a r i l y close to A , equation 1 then imples that it u = i n f { r + z z: (r,z) € A} ; o o = inf { f C x ) + z*gCx): x 6 X q} by defn. of A ; * < i n f ( f C x ) : x € X , gCx) < 9} since z > 0 and — o — o — considering only those x i n X q for which gCx) <_ 0 ; = u by d e f i n i t i o n of u o 3 o - 29 -Thus the f i r s t part of the theorem i s proved. Suppose there e x i s t s an x i n X q such that g(x) <_ 0 and — — ?t _ y Q = f(x) . Since by above, y^ . < fCx) + zQgCx) , t h i s implies — * _ * _ y < f Cx) because z > 9 , and g(x) < 6 . Thus z g Cx) = 0 . O — O — o v • — O Remarks; Ca) The theorem depends p a r t i a l l y on the convexity of the set A . The way the theorem i s s t a t e d , the convexity of A i s guaranteed by the convexity of f and g . As i n the f i n i t e dimensional study, t h i s may be somewhat weakened as A may be convex without f and g being convex. Cb) The assumption the existence, of an i n t e r i o r point of P, and the assumption that gCx^) < 9 for some x^ i n X q guarantee the existence of a n o n - v e r t i c a l separating hyperplane. Cc) Only convex constraints of the form gOO 1 9 have been considered. Linear equality c o n s t r a i n t s , h(x) = 9 , although equivalent to convex i n e q u a l i t i e s hCx) 9 and - hCx) ^_ 9 cannot be treated i n the same way as there never ex i s t s an x^ which simultaneously renders hCx1) <_ 9 and - hCx^ _< 9 . 3.1.2 Local Necessary Conditions The l o c a l theory of optimization p a r a l l e l s the theory for f i n i t e dimensions since generalizations of the concepts of d i f f e r e n t i a l s , grad-ients , and such to normed l i n e a r spaces are used. It also p a r a l l e l s the global case as the underlying p r i n c i p l e s are s u b s t a n t i a l l y the same: the separating hyperplane argument i s again used. - 30 -The basic problem here i s : L : min{f (x): x € X, g(x) <_ 0} where X i s a normed l i n e a r space,, f i s a real-valued f u n c t i o n a l on X and g i s a mapping from X into the normed space Z which has a p o s i t i v e cone P . Again, as i n the globa l case, an assumption must be included i n the theorem to guarantee the existence of a non-vertical hyperplane. The analog to the i n t e r i o r point condition i s the following d e f i n i t i o n of a regular point of an i n e q u a l i t y . Def i r i i t i o n 3.1.2.1 Let X and Z be normed l i n e a r spaces. Let P be a p o s i t i v e cone i n Z which has a non-empty i n t e r i o r . Let g be a mapping from X to Z which i s Gateaux d i f f e r e n t i a b l e at x i n X . The point x i s said to be a regular point of the i n e q u a l i t y g(x) <_ 6 i f g(x) < 8 and i f there e x i s t s an e i n X such that gCx) + <SgCx;e) < 6 . Theorem 3.1.2.2 Let X be a normed l i n e a r space and Z be a normed l i n e a r space with a p o s i t i v e cone P having a non-empty i n t e r i o r . Let f be a Gateaux d i f f e r e n t i a b l e real-valued f u n c t i o n a l on X and g be a Gateaux d i f f e r e n t i a b l e mapping from X to Z . Suppose x i s the s o l u t i o n to problem and x i s a regular point of the i n e q u a l t i y g(x) <_ 0 , then there e x i s t s a z i n Z such that o f'(x)e + z* 6g(x;e) = 0 for a l l e i n X & — and futhermore z g(x) = 0 . - 31 -Proof: For each e i n X define the set A(e) = {(r,z) e R X 'Z: r > f'(x)e,' z > g(x) + g'(x)e} and l e t A = U ACe). e€X Also define the set B = { ( r , z ) : r <_ 0, z <_ 0 } . Obviously A and B are convex, ( 0 , 6 ) i s i n A ( 0 ) , and B i s a cone with vertex at ( 0 , 0 ) . Hence ( 0 , 0 ) i s i n both A and B . A l s o , from the d e f i n i t i o n of B one may-observe that B contains an i n t e r i o r point since N = - P has an i n t e r -i o r p o i n t . In order to apply the Separating Hyperplane Theorem (Appendix, Theorem 4) i t must be shown that A contains no i n t e r i o r points of B . Suppose A does. Then there e x i s t s an e i n X such that 6f(x;e) < 0 and g(x) + 6g(x;e) < 0 . Consider the l a t t e r i n e q u a l i t y . This implies that there e x i s t s an open sphere of some r a d i u s , say . p, and center g(x)•'+ 6g(x;e) such that the sphere i s contained i n N . For 0 < a < 1, the point a(g(x) + Sg(x;e)) i s the center of an open sphere of radius ap contained i n N . Thus the point (1 - a)g(x) + a(g(x) + Sg(x;e)) = g(x) + a6*g(x;e) i s i n N . For f i x e d h since g i s Gateaux d i f f e r e n t i a b l e , |g(x + ah) - g(x) - aSg(x;e)| <_ o(a) , i t follows that for s u f f i c i e n t l y small a , g(x + ae) < 0 . S i m i l a r l y <5f (x;e) < 0 implies that f ( x + ae) <^ f(x) . This contradicts the optimality of x . Hence A contains no i n t e r i o r points of B . Thus, by the Separating Hyperplane Theorem, there i s a closed - 32 -hyperplane H separating the sets A and B ; that i s , there e x i s t s a non-zero element (r ,z ) i n R x Z such that o o A A r r „ + z z- < g < r r . + z z. o 2 o 2 — — o 1 o l for a l l (r^,z^) i n A and {v^z^) i n B . Since (0,9) i s i n both A and B , t h i s implies that 5 = 0 and that * r r . + z z. > 0 for a l l ( r i , z . ) i n A Cl) o 1 o 1 — • 1' r and * r r „ + z z_ < 0 for a l l Cr 0 , z 0 ) i n B • (2) o I o 2 — I I In order for equation C2) to hold, the d e f i n i t i o n of B implies that * * r >• 0 and z > 9 . Suppose r = 0 . Then since (r ,z ) i s a o — o — r r o o o * " * * non-zero element i n R x z » Z Q > 9 . Equation 1 implies that Z D Z ^ 0 f o r a l l (r^,z^) i n A ; i n p a r t i c u l a r , since by the d e f i n i t i o n of A , the point C6f(x;e), g(x) -I- <5g(x;e)) i s i n A for a l l e i n X, t h i s * - -implies that z Q(g(x) + <5g(x;e))>^ 0 . But there e x i s t s an e i n X such that g(x) + 6gCx;e) < 9 since x i s a regular point of the i n e q u a l i t y gCx) <_ 9 . Thus a contradiction i s reached since Z Q > 0 . Therefore r Q > 0 and without loss of g e n e r a l i t y , one can assume that r = 1 . Applying XQ = 1 and the fact that C<5f(x;e), g(x) + <5gCx;e)) i s i n A , for a l l e i n X, equation Cl) becomes 6fCx;e) + z*Cg(x) + <SgCx;,e)) > 0 for a l l e i n X . A _ In p a r t i c u l a r , since 9 i s i n X , t h i s implies that ZQgCx) >_ 0 . But A _ A _ A _ Z Q > .9 and g(x) £ 9 imply that zog'Cx) <_ 0 . Thus z og(x) = 0 . - 3 3 -F i n a l l y , by the l i n e a r i t y of Gateaux d i f f e r e n t i a l s with respect to e , 5f(x;e) + z . 6g(x|e)' = 0 . Remark With the r e g u l a r i t y condition on x , t h i s theorem cannot be extended to include equality constraints h(x) = 0 since there never exi s t s an e i n X such that h(x) + Sh(x;e) < 6 and - h(x) - 6h(x;e) < 0 . 3.1.3 Necessary Condition^ for Equality Constraints. For problems with equality constraints only, a necessary optim-a l i t y theorem by L u i s t e r n i c k as done i n Luenbe.rger [10] w i l l be presented here. References w i l l be made to the d e f i n i t i o n of a regular point of a transformation [Section 1.2.3J and to the Generalized Inverse Function Theorem [Section 1.2.4] . The basic problem i s {min f ( x ) : x (£. X, h(x) = 0} where X i s a Banach space, f i s a real-valued f u n c t i o n a l on X and h i s a mapping from X into a Banach space Z . Lemma 3.1.3.1 Let f achieve a l o c a l extremum subject to h(x) = 0 at the point x and assume that f and h are continuously Frechet d i f f e r e n t i a b l e i n an open set containing x and that x i s a regular point of the transformation h (see d e f i n i t i o n 1.2.3). Then f'(x)e = 0 for a l l e i n X s a t i s f y i n g h^Cx)^ = 0. - 34 -Proof: Assume that the l o c a l extremum i s a l o c a l minimum. Suppose there e x i s t s an e i n X such that f ' C x ) e ^ 0 and h ' C x)e = 0 . Define the mapping T: X->R)j Z such that T(x) = ( f C x ) , h(x)) then T i s continuously Frechet d i f f e r e n t i a b l e i n an open set containing x and T'(x) = ( f ( x ) , h ' C x ) ) . Since x i s a regular point of h , t h i s implies that h'(x) maps X onto Z; that i s , f or a l l z i n Z there exists a y i n X such that h ' C x)y = z . By the l i n e a r i t y of Frechet d i f f e r e n t i a l s , t h i s implies that h 'Cx)Cy + Ae) = h'(x)y and f ' C x ) ( y + Ae) = f'(x)y + A f ( x ) e - f or a l l A . For any t i n R , A can be chosen such that f ' C x ) C y + Ae) = t , and hence T'(x) i s an onto map from X to R x Z . Thus x i s a regular point of the transformation T . By the Generalized Inverse Function Theorem [Section 1.2.4], for any e > 0 there e x i s t s a vector x i n X and <5 > 0 with |x - x| < e such that T(x) = (f(x) - 6, 9) , contradicting the assumption that x i s a l o c a l minimum. Theorem 3.1.3.2 Let f , h and x be as i n the previous lemma. Then there A * — * — e x i s t s an element z i n Z such that f ' C x ) + z h 'Cx) = 9 . o o Proof: Lemma 3.1.3.1 implies that f'(x) i s orthogonal to the nullspace of the transformation h 'Cx) . By the d e f i n i t i o n of Frechet d i f f e r e n t i a l , h 'Cx) i s a bounded l i n e a r operator. Since h 'Cx) niaps X onto Z , a Banach space, t h i s implies that the range of the operator h 'Cx) i s closed. Thus, - 35 -by the property of bounded linear operators defined on Banach spaces — * (Appendix, Theorem 5), f C x ) is an element in the range of h'(x) . This implies the existence of z in Z such that f-(x) = - h'Cx)* z* , or an alternative notation f ( x ) •+ z* h'(x) = 0 . 3.1.4 Sufficient Conditions By the necessary conditions for optimality in problem L as seen in theorem 3.1.1.1, convexity and the existence of interior points guarantee the existence of a separating hyperplane. But these are too strong to impose for sufficiency since the appropriate hyperplane could exist in the absence of these conditions. Theorem 3.1.4.1 Let f be a real-valued functional defined on a subset X of o a linear space X . Let g be a mapping from X q into the normed space Z having a non-empty positive closed cone P . Suppose there exists an element z in Z , z > 0 and an element x in X such that o o — o f Cx) + z*g(x") 1 f Cx) + z*gCx) 1 f (x) + z*gCx) * * -for a l l x in X q, z >_ 0 in Z . Then x minimizes f Cx) subject to g Cx) < 0 with x in X . — o - 36 -Proof: & ic Since f ( x ) + z g(x) <_ f Gx)' + "Z g(x) for a l l z >_ 6 i n Z , it it — it it t h i s implies that z g(x) < z g(x) . If z.> 0 then Gz, + z ) > 0 — o 1 — 1 o — * * * _ * _ since z^ >_ 0 and thus Gz^ + z Q ) g ( x ) • <_ z QgGx) or equivalently z^g(x) <_ 0 for a l l z^ >_ 0 . Then, since N = - P i s a closed cone, * _ t h i s implies g(x) <_ 0 and thus, z QgGx) <_ 0 . Therefore, since it it it it it z g(x) <_ z^g(x) for a l l z >_ 0 i n Z , t h i s implies that z Qg(x) = 0 . Assume that x 1 i s i n X q and that g C x ^ <_ 0 . Therefore, since - * - * f (x) + Z QgCx) _< f (x) + z^gCx) f o r a l l x i n X q , t h i s implies that _ * * * _ f Gx) + z^gGx) <_ f GxD + z Qg(x^) . Since z^g(x) = 0 by the previous * part of t h i s proof and also since Z Q >_ 0 , g(x^) <_ 0 , t h i s implies that f ( x ) ^ f C x D . Therefore x minimizes fGx) subject to gCx) £0 and x i n X . o 3.2 Pshenichnyi's Approach The necessary c r i t e r i a f o r optimality derived i n t h i s section are f o r the following problem: P: min{fCx): x € X Q , gGx) <_ 0, h(x) =0} where X q i s some set i n the l i n e a r space X and f , g^ f o r i = 1, m and h f o r j = 1, k are functionals defined on X . This presentation follows Pshenichnyi 113]. The,major r e s u l t s are: 1) Theorem 3.2.2 i s the basic theorem of the s e c t i o n . I t ' s assumptions on X , f , h are the weakest given for t h i s type of problem. - 37 -The method of proof i s very s i m i l a r to the others i n that a separating plane argument i s used. 2) Theorem 3.2.4 r e s t r i c t s theorem 1 to the case where f and g are q u a s i - d i f f e r e n t i a b l e , h i s Gateaux d i f f e r e n t i a b l e at x and X i s a Banach Space. 3) Theorem 3.2.5 r e s t r i c t s theorem 1 to the case where f and e are convex and bounded, h i s l i n e a r and X i s a convex set i n the ° o Banach space X . Pshenichnyi's f i r s t theorem i s s i m i l a r i n statement to Mangas-aria n 's /Minimum P r i n c i p l e Necessary Optimality Theorem [Section 2.1.3] in"the f i n i t e dimensional case.. R e c a l l that Mangasarian's required assumptions on X q, f, g, h were: 1) X q i s a convex set i n R n with a non-empty i n t e r i o r . 2) f and g are d i f f e r e n t i a b l e at x . 3) h i s continuously d i f f e r e n t i a b l e ' i n an open set containing x . Pshenichnyi's basic assumptions are: 1) X i s a l i n e a r space, X q i s some set i n X . 2) there e x i s t s a convex cone K such that i f e i s i n K k then for A>> 0 s u f f i c i e n t l y small, x(A) = x + e + E r.CA)e. i s i n i = l 1 1 X where e. for i = 1, k are any vectors i n X and the functionals o 1 r.CX) r . s a t i s f y l i m — : = 0 . •X-0 x , , - n u g,(x(A)) " g(X> 3 ) l j J U f(x(A)) - f(x) £ F C e ) a n d l i m _ i ^ - < G ± ( e ) • A-s-0 A A->0 A - 38 -for i = 1, m where F and are convex functionals with respect to e . . h . ( x ( A ) ) - h.(x) 4) l i m -H.(e) where H. i s a l i n e a r func-A+0 A 1 1 t i o n a l . Observe that Pshenichnyi makes no convexity assumptions d i r e c t l y on X Q nor any d i f f e r e n t i a b i l i t y assumptions d i r e c t l y on f, . g and h . Thus h i s r e s u l t s are i n terms of F, G, > and H . Thelemma preceding theorem 3.1.2 proves that i n the case where H^, are l i n e a r l y independents, the separating plane argument can be applied i n Theorem 3.2.2 . Lemma 3.2.1 Let x be the s o l u t i o n to the minimization problem P where X ,• X, f, '.g and h s a t i s f y assumptions 1 through 4. Also, l e t E. , ...., H, - be l i n e a r l y independent.?;". Define I = {.i: g. (x) = 0}'. •, X tv 1 J = { i : g.Cx) ¥• 0} and l e t m , m denote the number of elements i n X X J each set. Then the convex h u l l of the set m , K = U ( C r , s , t ) € R X R X R : r - FCe), s = G (e), t = HCe)} e^K and the set M I k P = {'Cr,s,t) e R x R X R : r < 0, s < 0,. t = 0} have an empty i n t e r s e c t i o n . Proof: Suppose the i n t e r s e c t i o n were not empty. Then i t must be shown that the existence of an element i n the i n t e r s e c t i o n contradicts the - 39 -minimality of f(x) . Let ( r , s , t ) be an element i n coK A P . This implies that since (r>s,t) i s i n coK there e x i s t s Cr3 ,s3 , t3) i n K such that (r , s , t ) = Z X. ( r 3 , s 3 , t 3 ) where X. > 0 and Z X. = 1 . j J J j J Furthermore, since ( r3, s3, t3) are i n K then f o r some e3 i n K , r3 = F ( e3) , s3 = GjCe3) and t 3 = H(e J) . Let e° = Z A.e3 and observe that e° i s i n K since K i s convex and Z X. = 1 where X . > 0 . i 3 3 Therefore FCe°) <_ Z X. F(e 3) since F i s convex with respect to e , j 3 - Z X. r 3 , j J = r ; s i m i l a r l y G^Ce°) 1 s and, since H i s l i n e a r , H(e°) = t .. Thus FCe°) •< 0, Gj.Ce0) < 0 and HCe°) = 0 since ( r , s , t ) i s also i n P . Consider the set of equations k Tl)^(X,r^,r2, • • • ,r^) = h^Cx + Xe° + Z r.a 3) = 0 f o r i = 1, k where j = l 3 a3 are i n X and are chosen such that H.Ca ) = that i s 5.. = 0 i f i 4 i and 6.. = 1 i f i = i . Then by the Generalized i j i j I m p l i c i t Function Theorem [Section 1.2.5] the system of equations ijj. (X,r 1,.... ,r, ) = 0 for i = 1, . . . , k has a s o l u t i o n r . (X) for r±CA) i = 1, . . . , k where lim — - — = 0 . A->0 X _ _ k Consider the points x(A) = x + Ae° + E r . ( A ) a3 where .".A > 0 , 3=1 3 - 40 then since e° is in K , x(A) is in X^ . . Thus by definition of F f(xCX)) <_f(x) + XFCe°) + o(X) . but FCe°) < 0 implies that fCxCA)) < fCx) for sufficiently small A^ . Similarly by definition g±, g^xCX)) < g^x) + X^Ce 0) + oCX^ for i = 1, :..., m, thus implying g^ -CxCX)) <_ gjCx) + XjGj.Ce0) + oCAj.) . But gj-Cx) = 0 and G^(e°) < 0 . Thus for sufficiently small X , gjCxCX)) < 0 . Finally by construction of xCX) , hCx'CX)) = 0 for sufficiently small X . Therefore a contradiction to the assumption that x is the solution to P is obtained. Theorem 3.2.2 Assume 1 through 4 again. If x i s a s o l u t i o n to the minimization problem P then there exists r 6 R , r 6 Rm , s £ R k where Cr ,r,s) ^ 0 _ • _ _ o o such that r Q F ( e ) + r G(e) + sH(e) >_ 0 for a l l e i n K where ( r Q , r ) >_ 0 and rg(x) = 0 . Proof: Case 1: set (r o Case 2: lemma coKA P = <f> . Since coK and P are finite dimensional convex sets, they can be separated; that is, there exists a vector Cr,Sj.,t) in m T k R X R X R s u c h that r r + + >_ 0 >_ x^r + s ^ + t 2 t for a l l Cr^.s^jt^) in coK ,' thus for a l l point s in K , and for a l l ^c2>S2't2^ "*"n P ' This implies that rFCe) + Sj-Gj-Ce) + tHCe) > 0 for a l l e in K and also that ( r , i j ) >_ 0 since < 0 and < 0 . B y . l e t t i n g S j . = 0 and s = ( s ^ j S j ) , the theorem i s proved since ?F(e) + sG(e) + tH(e) >_ 0 f o r a l l e i n K with (r,s) > 0 and sg(x) = s^g^Cx) + Sjgj(x) = 0 since g-j-Cx) = 0 and s^. = 0 . Next, the p a r t i c u l a r i z a t i o n of Theorem 1 to the case where X i s a Banach space and f and g^ for i = 1, m are q u a s i - d i f f e r e n -t i a b l e w i l l be presented. R e c a l l that the c l a s s of a l l q u a s i - d i f f e r e n t i a b l e functions contains a l l Gateaux d i f f e r e n t i a b l e functionals and a l l convex f u n c t i o n a l s . It w i l l be shown that i f f and g^ also s a t i s f y a L i p s c h i t z condition then • fCx(X)) - f (x) _ „ * lxm r? =, -,.,sup r \e) A+0 A fVCx) and g ±(xIX)).- g.(x) A l i m = sup g (e) A+0 A g*€S.Cx) i . e . the q u a s i - d i f f e r e n t i a l s . The r e s u l t s of Theorem 3.2.4 are comparable to Luenberger's l o c a l case (Theorem 3.1.2.2) which i s i n terms of Gateaux d i f f e r e n t i a l s . Lemma 3.2.3 Let X be a Banach space. Assume the existence of K as i n assumption 2. Let f , g± for 1 = 1 , m be functionals defined on X which are q u a s i - d i f f e r e n t i a b l e and l e t h^" be such that f or - 42 -h.(x(A)) - h.(x) ^ A * i - 1, ...., k , lim • = h. (e) for some h. in X A+0 • 1 1 where x is the solution to the minimization problem V ~. If the sets FCx) and GJj*-) for i = 1,;..., m are bounded then i f A M _ * K _ A r sup f (e) + Z r. sup g (e) + Z s.h.Ce) > 0 °f*€FCx) 1-1 1g?t6;c5)i- 1 1=1 1 1 ~ I r for a l l e in K , it is necessary and sufficient that there exists * r - * r. -functionals f t F(x) and g± 6 G^x) for i = 1, m such that - *m_ *k_ * * r- f + Z r. g. + Z s. h. is in K 1=1 j=l J J Proof: The proof for sufficiency is obvious. A" A A — A _ A K * Let N = {x : x = r f + Z r. g. + Z s. h. wher 1-1. 1 1 j-1 3 3 e "f 6 F(x) and g± € G±Q) for i = 1, m} . Since F ( £ ) and ^(x) for i = 1, m are convex by definition, N is convex. Also since F(x) and G^(x) for i = 1, ..., m are, by definition, weak closed and bounded, F (x) and <3. (x) for i = 1, m are weak compact. These * * * in turn imply that N is weak closed and weak compact. Suppose there does not exist f in F(x) and g^ in ^.(x) * m * k * * for i = 1, m such that r f + Z r. g. + Z s. h. . is in K . O . .. 1 1 . .. J 1 l - l j=l J * * This says that K and N have an empty intersection, or equiyalently * * * * that K - N • does not contain the zero functional Since N is weak * * closed and.compact and since K is weak closed, this implies {Appendix; A A A A A Theorem 6] that K - N is weak closed. Also since N and K are - 43 -convex, K - N i s also convex. Thus K - N i s r e g u l a r l y convex [Appendix Theorem 7,]; that i s , f o r every functional X q not i n K - N there e x i s t s e i n X such that jit jit • ' it it "ft z (e) < x (e) - e for a l l ' z i n K - N , e > 0 . o Since the zero f u n c t i o n a l i s not i n K. - N , t h i s implies that it it it it it z (e) < - e < 0'., Thus y (e) - x (e) > e > 0 for a l l y i n K and * * * * * x i n N . This implies that y (e) i s bounded for a l l y i n K but since K i s a cone, mt y ( e) = 0 . Thus e i s i n K by prop-y l K* * * * e r t i e s . of conjugate cones and x Ce) < - e for a l l x i n N Since F(x) and G .Cx) are bounded, there e x i s t s e i n K 1 o where Ie - e I i s so small that ' o1 A M A K * |r I Ix. Ce - e ) I + E J r . I Ix Ce - e ) + E s J J h . Ce - e ) < e/4 1 o1 1 o o 1 . ' i1 1 o o 1 . , j J o 1 i = l . 3=1. for a l l x i n ' Cx) and x. i n 0 . Cx) f o r 1 = 1, ..., m . Then by supremum property A M A K A 0 < r sup f (e ) + E r . sup g. Ce ) + E s. h.Ce ) - ° f * ° i = l 1 g* 1 ° j= l 1 1 ° A • M * K A < r f Ce ) + E r . g.Ce ) + E s h Ce ) + e/4 - 0 ° i = i x 1 ° j = l 3 3 0 A M A K A < r f (e) + E r . g.Ce) + E s. h (e) + e/4 + e/4 - o . = 1 x x j = 1 j 3 = x*Ce)'+ e/2 - 44 -it it it it Thus, x (e) 2l - e/2 .contradicting x Ce) < - e for a l l x i n N and so necessity i s established. Theorem 3.2.4 Let f , g_^ for i = 1, ... , m and for j = 1, ... , k be functionals on a Banach space X . Let X be some set i n X . Assume r o the existence of K as i n assumption 2.: If f and g^ for i = 1 m s a t i s f y a L i p s c h i t z . c o n d i t i o n and are q u a s i - d i f f e r e n t i a b l e and i f h^ for j = 1, k s a t i s f y a L i p s c h i t z condition and has a Gateaux d i f f e r e n t i a l hj for j = 1, k, then i n order that x be a s o l u t i o n to the minimization problem P , i t i s necessary that there e x i s t s r Q i n R , r i n Rm and s i n R^ where ( r o , r , s ) ^ 0, and functionals< f i n — it ^ Cx) and g_^ i n G^Cx) for i = 1 m such that * m * k * * r f + E r . g.+ I s. h. £ K with Cr ,r) > 0 O . . . X X . . . X X v o — 1=1 i = l and futhermore r gCx) = 0 . Proof: I f i t can be shown that the given assumptions on f , g_^ for i = 1, m and f o r j = 1 , k imply that the conditions on f , e. and h. i n theorem 3.2.2 are s a t i s f i e d and that F Cx) and G': Cx) ° i j l for i.= 1, m ,are bounded, then by Lemma 3.2.3, this.theorem i s proved. Since f and g_^ f o r i = 1., .„..., m s a t i s f y the same conditions i t i s s u f f i c i e n t to consider ju s t f . Since - 45 -f C x ( A ) ) r f ( x ) = f(x(A)) - f ( x + A e ) ^ f ( x + A e ) - f(x) ^ a n d s i n c e > b y d e f i n i t i o n of x(A), f Cx(A)) - f (x + Ae) A < L E r.CA)e. i - l 1 1 because f s a t i s f i e s a L i p s c h i t z c o n d i t i o n , then taking l i m i t s , l i m f(x(A)) - f(x) = s u p ^ f * C e ) f o r a l l x ( a ) i n x s i n c e A-H-0 A f V ( x ) l i m L A-H-0 E r.CA)e. i = l 1 1 = 0 and by the q u a s i - d i f f e r e n t i a b i l i t y of f — f (X + A e ) - f ( x ) = s u p f * ( . e ) ^ T h u g b y s e t t i n g F(ey = s u p f * ^ ) l i m A-H-0 f*6F(x) fx6FCx) and s i m i l a r l y G.(e) = sup g.(e) for i = 1, . . ., m, t h i s implies 1 g*€GCx) 1 that F and for i = 1, m are convex with respect to e and assumption 3 required of f and g^ for i = 1, . .. , m i s more than met since equality has been established. F i n a l l y , since h^ for j = 1, k has a Gateaux d i f f e r e n t i a l * -hj at x for j = 1, k and since f o r j = 1, k s a t i s f y a L i p s c h i t z c o n d i t i o n , a s i m i l a r argument as used f or f and g^ for i = 1 m y i e l d s l i m A-H-0 h,(x(A)> - h (x) * * =h.(e) for a l l xCA) i n X A 3 Thus s e t t i n g H.Ce) = h.( e ) , H., by d e f i n i t i o n of Gateaux d i f f e r e n t i a l s J J 3 [Section 1.1.1] i s the required l i n e a r f u n c t i o n a l f o r assumption 4 . Suppose F(x) i s not bounded. This implies that f o r every n > 0 there e x i s t s e with le I = 1 and a fu n c t i o n a l f i n FCx) n 1 n1 n * such that f C e ) > n - e for some e > 0 . Since f i s a quasi-n n " — » d i f f e r e n t i a b l e f u n c t i o n a l , t h i s implies that fCx + Xe ) - fCx) = X sup f*Ce ) + oCX) n f *€ F(x) n > X f*Ce„) + oCX) — n n > X Cn - e) + oCX) . Since f also s a t i s f i e s a L i p s c h i t z c o n d i t i o n , ]fCx + ^ >^ n) ~ fCx)| <_LX , t h i s now implies LX >_ X(n - e) + oCX) . Thus L > n - e . But n can be chosen so large that n - e > L since L i s f i x e d . Thus, a contradiction i s reached. F i n a l l y , since the same argument holds f or G^Cx), i = 1, m, the theorem i s proved. The f i n a l theorem presented i n t h i s section i s a p a r t i c u l a r i z a t i o n of the problem P to the case where f and g^ f o r i = 1, m are convex bounded f u n c t i o n a l s , where h_. f o r j = 1, k are l i n e a r f u n c t i o n a l s , and X i s a convex set i n the Banach space X . This theorem o i s s i m i l a r to Luenberger's global case [3.1.1]. Theorem 3.2.5 Let f and g^ f o r i = 1, m be convex bounded functionals on a Banach space X . Let h^. for j = 1 , k be bounded l i n e a r functionals on X and l e t X be a convex set i n X . If x i s the o so l u t i o n to the minimization problem P , i t i s necessary that there - 47. -— ~~ xn. — lc ~~ ^ exists r Q in R , r in R and s in R with (r Q,r,s) ^ 0 such that r Q f Cx) + rg Cx) + shCx) > t Q f Cx) + rg Cx) + shCx) for a l l x in X where (r ,r) > 0 and moreover rgCx) = 0 . o o — f Proof: Let K = {e: e = ACx - x) for x in X Q, X f x, /.A >• 0} . Then K is a cone and i f e i s in K then x(X) .= x + Ae is in X o for small A since X is convex. Since f is a convex functional o i . f Cx + Ae) - f Cx) 9f Cx) ^ C F - , ^ C F ~ \ T j_ -r. / \ j r / - , \ lim — - — < f Cx + e) - f Cx) . Let FCe) = fCx + e) - f Cx) . A-H-0 S e _ .Then F i s a convex func t i o n a l with respect to e . S i m i l a r l y define G.Ce) f o r i = 1, .... m . Since h. i s a l i n e a r f u n c t i o n a l , x x h.(x + Ae) - h.(x) 3h.Cx) lim — — = —1 = h.Cx + e) - h.Cx) = H. Ce) . Thus A^+0 X 9e x x i by theorem 1, there exists r Q i n R , s i n R^ where Cr o >r,s) f 0 such that where r FCe) + rGCe) + sH'Ce) > 0 for: a l l e in K o — (r ,r) > 0 and r (x) = 0 ; o ' — S or e q u i v a l e n t l y r Q C f C x + e) - f C x ) ) + rCgCx + e) - gCx)) + sChCx + e) - h(x))- > 0 and by s e t t i n g e = x - X q f o r some x i n X Q , t h i s i m p l i e s r Q f ( x ) - rgCx) + shCx) >_ i Q f Cx) + r g(x) + shCx) f o r a l l x i n X Q . - 48 -3.3 Comparison of Pshenichnyi's Approach:to Luenberger's . In Luenberger's minimization problems there can be an i n f i n i t e number of constraints since the i n e q u a l i t y constraint g i s a mapping into Z , a normed l i n e a r space of any dimension, f i n i t e or i n f i n i t e and sim-i l a r l y the equality constraint h i s a mapping into Z , a Banach space of any dimension. Thus Pshenichnyi's problems are a c t u a l l y a p a r t i c u l a r -i z a t i o n of Luenberger's to a f i n i t e number of c o n s t r a i n t s . In t h i s case Pshenichnyi's r e s u l t s are better than Luenberger's since Pshenichnyi's assumptions are weaker. In t h i s s e c t i o n , a comparison of assumptions and r e s u l t s of Luenberger's.problem L r e s t r i c t e d to the case where the number of constraints i s f i n i t e , to Pshenichnyi's problem P w i l l be presented. Since, in1Luenberger's presentation, global and l o c a l eases with i n e q u a l i t y constraints and the case with equality constraints only are a l l handled separately, the comparison with Pshenichnyi's assumptions w i l l ' a l s o be handled separately but f i r s t observe that the problems L^, and can be deduced from P by s e t t i n g X q to be the whole space X . The choosing of X q from the l i n e a r space X i s a way of further q u a l i f y i n g a mathematical programming problem. For an example of where t h i s i s used r e f e r to Kushner's paper: Necessary Condition f o r Continuous Parameter Stochastic Optimal Problem [8J.; 3.3.1 Inequality Constraints — Local Case. F i r s t i t w i l l be.shown that Theorem 3.2.2 can be applied to derive Theorem 3.1.2.2. The set X and the cone K can both be defined - 49 -as X . The assumption of Gateaux d i f f e r e n t i a b i l i t y of f and g implies that assumption ( 3 ) (Theorem 3 . 2 . 2 ) holds with F and G being the Gateaux d i f f e r e n t i a l s . Hence from theorem 3 . 2 . 2 , there exists r € R , o r € Rm where Cr ,-r) f 0 such that r F ( e ) . + ?GCe) >_ 0 for a l l e • i n X where Cr Q,r) >_.0 and such that rg(x) = 0 . Now, i f the condition that x be a regular point of the. i n e q u a l i t y constraint i s assumed i n Theorem 3 . 2 . 2 t h i s would imply the existence of e i n X such that g(x) + 6gCx;e) < 6 and g(x) < 0 . But Theorem 3.2.2 says that rg(x) = 0 , Cr o,r) >_ 0 , Cr o,r) ^ 0 and r^fCxje) + r5g(x;e) > 0 for a l l .e i n X . If r = 0 t h i s then implies o r ir6g(x;e) >_ 0 for a l l e i n X . ( 1 ) If e i s as given i n the r e g u l a r i t y c o n d i t i o n , then r(g(x) + <5gCx;e)) < 0 since r > 0 . But rg(x) = 0 hence r<5g(x;e) < 0 contradicting Cl) • Thus r ^ 0 and, without loss of g e n e r a l i t y , r Q can be taken as 1 . Hence with the regular point assumption added, theorem 3.2.2 says FCe) + rG(e) >_ 0 for a l l e i n X . T h i s , i n turn, "implies that 6fCx;e) + r6gCx;e) > 0 and so, by the l i n e a r i t y of the Gateaux d i f f e r e n t i a l s i n e , 6f(x;e) + rSgCx;e) = 0 , the r e s u l t of theorem 3 . 1 . 2 . 2 . 3.3.2 Inequality Constraints - Global Case As stated e a r l i e r , Theorem 3.2.5 i s very s i m i l a r to Theorem 3 . 1 . 1 . 1 . In f a c t , both require convexity of X q , f and g . Thus the r e s u l t s of Theorem 3.2.5 follow. If the i n t e r i o r point assumption i s added to Theorem 3 . 2 . 5 , then the assumptions of 3.2.5 are equivalent to 3 . 1 . 1 . 1 R e c a l l that the i n t e r i o r point condition implies the existence of x 1 i n - 50 -X such that g(x^) < 6 .. . With t h i s condition added, the r e s u l t s of Theorem 3.2.5, namely ( r Q , r ) ^ 0, ( r Q , r ) >_ 0, rgCx) = 0 and r Q f ( x ) + rgCx) ^ r Q f ( x ) + rg(x) for a l l x i n X , would imply r Q > 0 since i f r = 0 then rg(x,) < 0 . Hence, with r > 0 , without o • 6 1 o los s of generality r = 1 and the r e s u l t s of Theorem 3.1.1.1 appear. 3.3.3 E q u a l i t y Constraints The assumptions of Theorem 3.2.2 w i l l be derived from those of theorem 3.1.3.2. The set X and the cone K can both be defined as o X . Since i n 3.1.3.2, the equality constraint h and the objective func-t i o n a l f are continuously Frechet d i f f e r e n t i a b l e , assumption 3. and assumption 4 i n 3.2.2 follow immediately with F and H equal to-the Frechet d i f f e r e n t i a l s . Thus theorem 3.2.2 can be applied and the following r e s u l t s hold: (r ,s) = 0 , r G(e) + sH(e) > 0 for a l l e i n X and r > 0 . o . o — o — Now, l e t the condition that x be a regular point of the t r a n s -formation h be added to the assumptions of theorem 3.2.2. This implies that h'(x) maps onto Rk . If r Q = 0 then sh''(x)e >^ 0 for a l l e i n X , and thus, by the l i n e a r i t y i n e of the Frechet d i f f e r e n t i a l s , sh/Cx)e = 0 . Since s ^ 0 , t h i s implies that some of the components of h'(x)e must be 0 for a l l e i n X , hence the rank of h'(x) i s - k le s s than k but t h i s contradicts the fact that h^(x) maps onto R Therefore, without loss of g e n e r a l i t y , r = 1 and f'Cx)e + sh''(x)e >^ 0 for a l l e i n X so that by l i n e a r i t y i n e of the Frechet d i f f e r e n t i a l s , f"(x) + sh(x) = 0 . - 51 -CHAPTER' FOUR: APPLICATION TO OPTIMAL CONTROL 4.0 Introduction In an optimal control problem, the dynamics are described by a system-of d i f f e r e n t i a l equations of the form ^ - f ( x ( t ) , uCt)) CD where xCt) i s an n-dimensional "state" v e c t o r , u.(t) i s an n-dimensional co n t r o l vector and f i s a mapping of Rn x R1" Rn . This system when supplied with an i n i t i a l state x( t 0 ) and a control input function u , produces a vector-valued, function x . Let the i n t e r v a l [t ., t'^J represent the i n t e r v a l on which x and u are defined. A l s o , i n addi t i o n to t h i s dynamic system, the c l a s s i c a l . o p t i m a l control problem has an objective f u n c t i o n a l of the form t. 1 £ ( x , u ) d t J = J i "0 and a f i n i t e number of terminal c o n s t r a i n t s . g.(x(t.)) = c. for i = 1, ... r °x x i ' or e q u i v a l e n t l y gCx(t^)) = c C2) Thus, an optimal control problem consists of f i n d i n g the pair of functions Cx,u) minimizing J while s a t i s f y i n g the system Cl) and the terminal constraints C2)• By considering the problem as one formulated i n Rn x ^ a n d by t r e a t i n g the d i f f e r e n t i a l equation Cl) and the terminal constraint (2) as - 52 -connecting u arid x , the optimal c o n t r o l would reduce to a mathematical programming problem. Some assumptions must be made f i r s t . Let the vector-valued function f have continuous p a r t i a l d e r i v a t i v e s with respect to x and u . Let u €. u C .C m[t ,t^] where U i s the cl a s s of admissible c o n t r o l functions and C m [ t ,t-] the set of continuous m-dimensional o 1 functions on [ t ^ t ^ ] . Also assume for any given u £ U and for an i n i t i a l condition x ( t Q ) » equation (1) defines a unique continuous function x(t) where t > t . If x i s the function r e s u l t i n g from the a p p l i c a t i o n of a given c o n t r o l u , then x i s said to be the t r a j e c t o r y of the system produced by u . Let X denote the clas s of a l l admissible t r a j e c t o r i e s . F i n a l l y assume that I. and g have continuous p a r t i a l d e r i v a t i v e s with respect to t h e i r arguments. Now, l e t X = C n [ t , t j , U = C m I t , t j and define o 1 o 1 A(x,u) = x(t) - x ( t Q ) h f ( x ( s ) , u(s))ds = 0 . Observe that t h i s i s •v t o i s simply the integrated form of the d i f f e r e n t i a l equation (1). Then A i s a mapping from C n [ t o , t ^ ] x C m [ t o , t ^ ] into C n [ t o > t ^ J . Thus the Fre'chet d i f f e r e n t i a l of A e x i s t s , i s continuous and i s given by the formula A'(x,u)(h,v) = h(t) -t V f(x,u)hCx)ds t X fcl V fCx,u)vCs)ds . (3) t U o o for a l l (h,v) i n X x u • Also, since g has continuous p a r t i a l d e r i v a -t i v e s , the terminal constraint g i s a mapping from C n [ t o , t ^ ] into R r with Fre'chet d i f f e r e n t i a l : g'(x)h = V g(x)h(t ) f o r a l l h i n X . (4) - 53 -Since the transformation A and g define the constraints of the optimal c o n t r o l problem and since these constraints are a c t u a l l y ones of e q u a l i t y , the question of r e g u l a r i t y of these constraints i s equivalent to asking i f , at the optimal t r a j e c t o r y , that i s , at (x,u), the Frechet d i f f e r e n t i a l s A'(x,u) and g'(x) , taken as a p a i r , map onto X x R (see d e f i n i t i o n 3.1.2.1). To e s t a b l i s h t h i s , two assumptions are needed: (i) V^gCx) has rank r and ( i i ) the system (3) i s c o n t r o l l a b l e , that i s , f o r any e i n Rn there e x i s t s v i n U such that h(t) -x V f(x,u)h(s)ds — t x tl V f (x,u)v.Cs)ds = 0 , (5) t - U o o and M t J - e • (6) have a s o l u t i o n h i n X . Using ( i ) , i t i s clear that the p a i r (A>,g'') i s onto i f for any e i n Rn and any y i n X there i s an (h,v) i n X x U such that rt net) - J 1 V f(x,u)h(s)ds -t X X V uf(x,u)v(s)ds = y(t) (7) o o and h ( t x ) = e (8) If v = 0 then by the fundamental existence theorem for l i n e a r V o l t e r r a i n t e g r a l equations [Appendix, Theorem 6 ] , equation (7) has a s o l u t i o n ii . Now, l e t h be the s o l u t i o n of C5) and C6) w i t h e = e - h(t^) . Then I t i s clear that h = h + h s a t i s f i e s (7) and (8). Hence the constr-a i n t s are r e g u l a r . - 54 -4.1 Basic Necessary Conditions For Optimality. The.basic necessary conditions s a t i s f i e d by the s o l u t i o n to the optimal c o n t r o l problem w i l l be given here. Theorem 4.1.1 r t Let (x,u) minimize J = ^ £ ( x , u ) d t subject to ^ = f ( x , u ) , fco xCt Q) fixed- and g(x(t^)) = C . A l s o , assume that the r e g u l a r i t y con-d i t i o n s are s a t i s f i e d at (x,u) . Then there i s an n-dimensional vector-valued function A(t) and an r-dimensional vector y such that f or a l l t i n I t j . t ^ ] (a) - | ^ = [ V x f ( x ( t ) , u ( t ) ) ]TA ( t ) + ! V x £ ( x ( t ) , u ( t ) ) ]T (9) (b) ACtj) = [ V ^ g C x C t j ) ) ] ^ (10) (c) [ A ( t ) ]TV u f ( x ( t ) , u (t)) + V u £ C x C t ) , GCt)) = 0 . ( I D Proof; dx Since - j— = f (x,u) can be rewritten i n the form A_(x,u) = 0 as seen i n the introduction and since g(x(t^)) - C = 0 , the minimization problem to be considered.has only equality c o n s t r a i n t s . Since A, g and J are continuously Frechet d i f f e r e n t i a b l e since the r e g u l a r i t y conditions are s a t i s f i e d , and since .(x,u) i s the s o l u t i o n to the minimization problem, by theorem 3.1.3.2, there e x i s t s X 6 N B V [ t Q , t j ] , the normalized space of functions of bounded v a r i a t i o n (see Luenberger 110J, Dual of C[t , ^ 3 ) , and. y 6 R such that - 55 -V Kx,u)h(t)dt + X t _ 1 d[X(.t)]T[h(.t) - V fCx,u)hCs)ds] X and + y V xg(xCt I))hCt 1) = 0 V J l(x,u)v(t)dt + _ 1 d[.X(t)] T V uf (x,u)v(s)ds = 0 CL2) (13) for a l l (h,v) i n X x U • Without l o s s of g e n e r a l i t y , set X(t^) = Equation (12) i s equivalent to V Jt(x,u)h(t)dt + X ft h(t)dACt) - dX(t) V^f(x,u)h(s)ds X + yxV x g ( x ( t 1 ) ) h ( t 1 ) = 0 Then in t e g r a t i n g by parts the t h i r d term of the above equation and sub-s t i t u t i n g \ ( t j ) = 6 , equation (12) can be rewritten as V xHx,u)h(t)dt + h(t)dX(t) + 1 [ X ( t ) ] T V x f ( x , u ) h ( t ) d t + y V xg(x(t 1))h(t 1) = 0 for a l l h i n X . (14) Thus, i t i s cl e a r that X can have no tumps i n (t ,t,) since otherwise o 1 a s u i t a b l e h i n X can be constructed to make the second term of (13) large compared with the other terms. However there must be a jump at t ^ of magnitued - Vg (x(t,))y . Since (13) holds for a l l continuous h , X JL i t holds, i n p a r t i c u l a r f o r a l l continuously d i f f e r e n t i a b l e h with hCt-^) - M b ) = 0 . Therefore, integrating by parts the second term, equation (12) becomes 1 { Vx^Cx,u)hCt);^ 1:^ = o or. e q u i v a l e n t l y , rt 1 {CVxACx,u) + [ ( t ) ] T V xfCx,u))hCt) - l X ( t ) ] T }dt = 0 . (15) Let B(t) = {V £ ( x , u ) • + IX-(S)] V f(x,u)}ds . Integrating by p a r t s , X X ; IVx£Cx,u) + [X(t)]Vf(x,u)]h(t)dt = 1 B(t) dt since t d t o h ( t Q ) = h ( t o ) = hO^) = 0 . Thus equation (15) becomes 1 {B(t) + U ( t ) ] T } : | £ ' d t = 0 . This implies that - X(t) = [B(t)] + c [Appendix: Theorem 8] for some constant c arid hence by the d e f i n i t i o n of B , equation (9) holds. Equation (13), a f t e r i n t e g r a t i n g the second term by p a r t s , becomes V u>l(x,u)v(t)dt + 1 [ X ( t ) ] T V u f ( x , u ) v ( t ) d t = 0 or e q u i v a l e n t l y , rt 1 I V u £ ( x , u ) + !X.(t')]TV f (x,u)]v(t)dt = 0 for a l l v i n U . (16) Let D(t) = V u £ ( x , u ) + TX(t)] V uf(x,u) . Then equation (16) becomes rt. D(t)v(t)dt = 0 (17) - 57 -If Dtt) :f 0 at a p o i n t , say D ( t ) > 0, then by c o n t i n u i t y , D(t) > 0 i n a neighbourhood of that p o i n t . Let v be any continuous function which i s zero outside the neighbourhood but which i s greater than zero somewhere r t l D(t)vCt)dt > 0 , contradicting (17). Thus D(t) t o i n s i d e . Then i s equal to zero and equation (11) holds. F i n a l l y , by changing the boundary condition on A(t^) from T A(t,) = 6 to A O O = JV- g ( x ( t T ) ) J y to account for the jump, X w i l l J- X X X be continuous throughout f t ^ j t ^ J and the theorem i s proved. 4 . 2 A n Example Problem i i i ; Optimal Co n t r o l . Consider the problem of f i n d i n g the m-dimensional c o n t r o l function u that minimizes the quadratic objective f u n c t i o n a l 1 ( [ x ( t ) ]T Q x(t) + I u ( t ) J T R u ( t ) ) d t t o subject to the l i n e a r dynamic constraint Ay; ^ = F x(t) + B u ( t ) , xCt ) f i x e d , (18) where Q i s an n x n symmetric p o s i t i v e - s e m i d e f i n i t e matrix, R i s an m x m symmetric p o s i t i v e - d e f i n i t e matrix, F i s an n x n matrix and B i s an n x m matrix. Applying the necessary conditions of Theorem 4.1.1, - f£ = F TA(t) = Q x ( t ) , X ( t J =.9 (19) [ A ( t ) ]T B + [ u ( t ) ]T R = 0 . - 58 -Since R i s p o s i t i v e d e f i n i t e , t h i s implies that - I T u(t) = - R B X(t) . and thus the dynamic l i n e a r constraint (18) becomes ^ = F x C t )— B R_ 1BTACt), x ( t Q ) fi x e d . (20) Observe that equations (19) and (20) form a l i n e a r system of d i f f e r e n t i a l equations whose s o l u t i o n s a t i s f i e s the r e l a t i o n : A(t) '= P(t ) x ( t ) where P(t) i s the n x n matrix sol u t i o n of the R i c c a t i d i f f e r e n t i a l equation HP T - I T ££. + P F + F P - P B R B P + Q = U, P(t,) = 0 . dt 1 - 59 -CHAPTER FIVE:./DEVELOPMENTSt In the l a s t few years, a l o t of work has been done in.the development of necessary optimality c r i t e r i a f o r programming problems wit h both equality and i n e q u a l i t y c o n s t r a i n t s . The general form of t h i s problem i s G: min{f(x): x € X, gtx) <_0, h(x) = 0} where f : X R, g: X ^ Y and h: X -> Z . The following cases have been presented: 1) X, Y, Z f i n i t e dimensional 2) X, Y l i n e a r spaces and no equality constraints 3) X, Z Banach spaces and no i n e q u a l i t y constraints 4) " X, a l i n e a r space and Y, Z f i n i t e dimensional spaces. D i f f e r e n t i a b i l i t y assumptions were required for optimality r e s u l t s i n the l o c a l case of (2) a s w e l l as cases Cl) and (3). In case (4), Pshenichnyi required the existence of convex approximations of f and g and a l i n e a r approximation of h as well as a convex approximation of X . B. D. Craven [4] does an extension to case (3). In h i s problem f i s not a f u n c t i o n a l but rather a mapping into a Banach space. His main r e s u l t w i l l be stated here for comparison to Theorem 3.1.3.2. Craven's Main Result. Let X, Y and Z be Banach spaces and l e t U . be an open subset i n X . Let f : U -> Y be Frechet d i f f e r e n t i a b l e and fi.:'. U -> Z be continuously Frechet d i f f e r e n t i a b l e . Assume (by r e s t r i c t i n g Y and Z) that fQJ) i s dense i n Y and h(U) i s dense i n Z . Let E = {x: x € U, h(x) = 0, h'Cx) i s an onto map} . Then. fCx) i s stationary - 60 -subject to the constraints h(x) = 0 at x = x € E i f and only i f there ex i s t s a continuous l i n e a r map M: Z -> Y such that f'(x) = Mir Cx) . H. Halkin and L. Neustadt [7] and L. Neustadt [12] present the case where the number of i n e q u a l i t y constraints i s i n f i n i t e and the number of equality constraints i s f i n i t e ; that i s , i n problem G, the spaces X, Y are infi n i t e . d i m e n s i o n a l and Z i s f i n i t e dimensional. The assumptions on f, g, h and X were s i m i l a r to Pshenichnyi's; that i s convex approximations were used and thus, the r e s u l t s were i n terms of these convex approximations. M. Altman [1] developed the necessary c r i t e r i a for the reverse problem; that- i s where the number of equality constraints i s i n f i n i t e and the number of i n e q u a l i t y constraints i s f i n i t e In Bazaraa and Goode's paper [3] , the necessary conditions f or the case where there are i n f i n i t e l y many equality and i n e q u a l i t y c o n s t r a i n t s , are developed. These r e s u l t s are probably the most general so far a v a i l a b l e . Before the main r e s u l t s can be stated a few d e f i n i t i o n s are required: Ca) The problem to be considered i s : 8: min{fCx): x 6 S, gCx) e cSL C, h (x) = 0} where f: X -> R, g: X + Y and h: X -> Z; X, Y, Z are normed l i n e a r spaces; S i s a subset of X, c% C i s the closure of C where C i s a convex cone i n Y . Cb) The cone of i n t e r i o r d i r e c t i o n s f o r an a r b i t r a r y set S and x i n c% S i s defined.as: DCS,x) = {x: there i s a b a l l B about the o r i g i n and <S > 0 such that y£x + B and H CO,6) imply that x + Xy £ S} . - 61 -Cc) The cone of tangents for an arbitrary set S and x in ci S is defined as: T(S,x) = {x: given any 6 > 0, there exists a A 6 Co,<5) and z 6 B. such that x + Ax + Az € S where o Bg is a ball:around the origin with radius 5} . Cd) The functions• f and g are differentiable at x with derivatives F and G in the following sense: 1/A Cf Cx + Az) - f (x)) -> FCy) for A -f; 0+, z -> y and 1/A (g(x + Az) - g(x)) + G(y) for A ^ 0+, z -> y . Ce) G is ci C-convex if • GCAx + Cl - A)y) - AGCx) - Cl - A)GCy) € cJl C for each x, y and A •= (0,1) . Cf) The level set L is defined as L = {x: hCx) = 0} . CNote: if x is the solution of B then, obviously, x L) . Remarks (1) The cone of i n t e r i o r d i r e c t i o n s i s s i m i l a r to the cone K used by Pshenichnyi. C2) If f and g are d i f f e r e n t i a b l e at x i n the above sense then f and g are obviously Gateaux d i f f e r e n t i a b l e at x when z = y . But Gateaux d i f f e r e n t i a b l e at x need not imply the above d e f i n i t i o n since z may not converge to y . - 62 -Main Result;; Theorem: Suppose that x solves problem 8 and suppose that D(S,x) i s convex. Let M be a nonempty convex subset of TCL,x) . Then, there e x i s t s a non-zero (u,v,w) i n R x Y x x such that : CD u >_ o, v t c , w e M ( l i ) vg(x) = 0 C i i i ) (uF + vG + w)x >_ 0 for a l l x i n DCS,x) . Extensions: Cl) If x i s i n the i n t e r i o r of S then uF + vG + w = 0 C2) I f S i s convex and has a non-empty i n t e r i o r then condition C i i i ) i s equivalent to CuF + vG + w) Cx) _^ CuF + vG + w) Cx) for a l l x i n S . C3) If b i s Frechet d i f f e r e n t i a b l e at x with d e r i v a t i v e H, i t can be shown that T(L,x) C N(H) . I f TCL,x) = NCH) then the set M can be chosen such that M = NCH) and thus w £ CNCH))"1. The assumption N(H) C T(L»x) can be viewed as a r e g u l a r i t y assumption. Here N(H) i s the n u l l space of H . This condition i s . implied when either (a) h i s af f i n e or Cb) X, Z are Banach spaces, h i s continuously Frechet d i f f e r e n t i a b l e , at x , and the range of H i s equal to Z . This i s equivalent to Luenberger's regular point d e f i n i t i o n CSection 1.2.3) C4) I f either Z i s f i n i t e dimensional or X and Z are Banach spaces and range of H i s c l o s e d , then w can be. written as a composition of H and a continuous l i n e a r f u n c t i o n a l on Y . - 63 -From t h i s theorem and points. (3) and C4) the.following two theorems are immediate. Theorem: Let X, Y, Z be normed l i n e a r spaces, where Z i s f i n i t e dimensional. Suppose that f and g are d i f f e r e n t i a b l e : i n the sense of d e f i n i t i o n Cd) with, d e r i v a t i v e s F and G and l e t H be a continuous l i n e a r transformation fronr X . to Z with N(H) C T(L,x) , . eg. by l e t t i n g h be a f f i n e . I f x i s the s o l u t i o n to 8 then there exists a non-zero (u,v,w) £ R x Y x Z such that ( i ) U >_ 0,;. V & C Cii ) vgCx) = 0 C i i i ) CuF + vG + wH) (x) >^ 0 for a l l x i n D(S,x) . Theorem: Let X and Z be Banach spaces and Y be a normed l i n e a r space. Suppose that f and g are d i f f e r e n t i a b l e at x as i n d e f i n i t i o n (d) with d e r i v a t i v e s F and G. Further suppose that h i s continuously Frechet d i f f e r e n t i a b l e at x with d e r i v a t i v e H . If x solves B then * * there e x i s t s a non-zero (u,v,w) i n R x X X z such that * ( i ) u > 0, v € C Cii) vg(x) = 0 C i i i ) CuF + vG + wH) Cx) >. 0 for a l l x i n DCS,x) . Remark: I f , i n the above theorem, S i s convex, f i s convex, g i s - 64 r-cl C-convex and g i s a f f i n e then condition C i i i ) i s equivalent to uf Cx) + vG(x) + wH(x) >_ uf Cx) + vg Cx) + whCx) - uf Cx) . Hence i f x solves 8 then there e x i s t s (u,v,w) f 0 such that cond-i t i o n s C i )» ( i i ) and the above i n e q u a l i t y . h o l d . - 65 -APPENDIX 1. Bounded Inverse Theorem [2] Let X be a Banach space, D a subspace of X and Y , a normed l i n e a r space. Suppose A: D -* Y i s a closed l i n e a r transformation and suppose the range of A , A C D ) i s of- category II . Then: (a) . A i s onto; that i s A C D ) = Y (b) there ex i s t s an m > 0 such that f o r any yfe Y there i s some x 6 D such that Ax = y and ||x[| <_ mfl.y'|| . (c) I f A 1 e x i s t s , i t i s a bounded l i n e a r transformation. 2. Brouwer's Fixed Point Theorem [5] Any continuous map f of a closed b a l l i n Rn into i t s e l f has at lea s t one fix e d point; that i s , a point x such that f Cx) = x . 3. Separating Plane Theorem [ l l ] Let X and Y be two non-empty d i s j o i n t convex sets i n Rn . Then there e x i t s a plane {x: x Rn , cx = a} , c f 0 which separates them; that i s , cx <_ a <_ cy for a l l x i n X , y i n Y . 4. Separating Hyperplane Theorem [.10 ] Let and be convex sets i n the normed l i n e a r space X such that Kj- has i n t e r i o r points and has no i n t e r i o r points of . Then there i s a closed hyperplane H separating and K^ ;. that i s , it it it it there i s an x i n X such that sup x Cx) 1 . i n f x Cx) • xfeK^: x f r ^ 5. Property, of Bounded Linear Operators i n Banach Spaces [10] Let X and Y be normed spaces and l e t f be an element i n the normed space of a l l bounded l i n e a r operators from X into Y . Let the - 66 -range of f , denoted by R(f) , be closed. Then R(f ) = [N(f)] where N(f) i s the n u l l space of f . 6. Fundamental Existence Theorem of Linear V b l t e r r a Integral equations [9] If cx (a) y(x) = h(x) + X K ( x , t ) y ( t ) d t where a i s constant; a (b) K(x,t) i s r e a l and continuous i n the rectangle a <_ x <_ b , |K(x,t)| < M i n R , K(x,t) £ 0 ; (c) h(x) t 0 i s r e a l and continuous i n I: a <_ x <_ b ; then the equation (a) has one and only one continuous s o l u t i o n y(x) . 7. Regularly Convex Sets [11] * D e f i n i t i o n : Let B be the conjugate space to a Banach space B * * A set X i n B i s said to be r e g u l a r l y convex i f , f o r every fun c t i o n a l A * x not i n X , there e x i s t s an element x i n B such that o ' ' o x ' ( x ) < x ( x ) - e for a l l x i n X and some e \> 0 . o o o -* Theorem: A set X i s r e g u l a r l y convex i f and only i f i t i s convex and * weak closed. 8. Property of Euler-Lagrarige Equations__[l_pv] rt If a(t) i s continuous i n [ t ^ j t ^ ] and 2 a(t)h.(t)dt = 0 fcl for every h i n the normed l i n e a r space c o n s i s t i n g of a l l functions on the i n t e r v a l [t^,t2] which are continuous and have continuous d e r i v a t i v e s with h(t^) = hO^) = 0 then a(t) = c i n f t ^ , t 2 ] where c i s a constant. - 67 _ BIBLIOGRAPHY 1. M. Altman, "A General Maximum P r i n c i p l e f or Optimization Problems", Studia Mathematica, V o l . 31, No. 4, 1968. 2. G. Bachman and L. N a r i c i , Functional A n a l y s i s , Academic Press. 3. M. S. Bazaraa and J . J . Goode, "Necessary Optimality C r i t e r i a i n Mathematical Programming i n Normed Linear Spaces!1, Journal of Optimi- zation Theory and A p p l i c a t i o n s , March 1973, V o l . 11, No. 3. 4. B. D. Craven," A Generalization of Lagrange M u l t i p l i e r s " , B u l l e t i n of A u s t r a l i a n Mathematical Society, V o l . 3, 1970. 5. N. Dunford and J . T. Schwarz, Linear Operators: Part I General Theory, Interscience, New York 1958. 6. A. M. G e o f f r i o n , "Duality i n Non-Linear Programming: A S i m p l i f i e d Applications-oriented Development", PerspectivesV i n Optimization, Addison-Wesley. 7. H. Halkin and L. W. Neustadt, "General Necessary Conditions for Optimization Problems", Proceedings of the National Academy of Science, V o l . 56, No. 4, 1966. 8. Kushner, "Necessary Conditions for Continuous Parameter Stochastic Processes", SIAM Journal of C o n t r o l , Aug. '72 V o l . 10, No. 3. 9. W. V. L b v i t t , Linear Integral Equations, McGraw-Hill, 1924 . 10. D. G. Luenberger, Optimization by Vector Space Methods, John Wiley and Sons, 1969. 11. 0. L. Mangasarian, Non-Linear Programming, McGraw-Hill 1969. 12. L. W. Neustadt, "A General Theory of Extremals", Journal of Computer and System Sciences. V o l . 3,. No. 1, 1969. 13. B. D. Pshenichnyi, Necessary Conditions for an Extremum, Marcel Dekker Inc., New York 1971. 14. W.. Rudin, P r i n c i p l e s of Mathematical A n a l y s i s , McGraw-Hill, 1964.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Necessary conditions for a solution of a non-linear...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Necessary conditions for a solution of a non-linear programming problem Lee, Linda May 1973
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Necessary conditions for a solution of a non-linear programming problem |
Creator |
Lee, Linda May |
Publisher | University of British Columbia |
Date Issued | 1973 |
Description | The conditions required for a solution of general non-linear programming problems of the form min{f(x): x є X, g(x) ≤ 0, h(x)=0}; where f is called the objective function, g the inequality constraint and. h the equality constraint, are presented in this thesis. The following cases are studied: (1) X, a finite dimensional space; f, a real valued function; and g and h finite dimensional vector functions. (2) X, an infinite dimensional space; f, a real valued function; and g and h either finite or infinite dimensional vector functions. An application of this type of problem to optimal control will be given and the recent developments in this area will be discussed. |
Subject |
Nonlinear programming |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-03-23 |
Provider | Vancouver : University of British Columbia Library |
Rights | 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. |
DOI | 10.14288/1.0080441 |
URI | http://hdl.handle.net/2429/32767 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1973_A6_7 L45.pdf [ 3.32MB ]
- Metadata
- JSON: 831-1.0080441.json
- JSON-LD: 831-1.0080441-ld.json
- RDF/XML (Pretty): 831-1.0080441-rdf.xml
- RDF/JSON: 831-1.0080441-rdf.json
- Turtle: 831-1.0080441-turtle.txt
- N-Triples: 831-1.0080441-rdf-ntriples.txt
- Original Record: 831-1.0080441-source.json
- Full Text
- 831-1.0080441-fulltext.txt
- Citation
- 831-1.0080441.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0080441/manifest