UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Necessary conditions for a solution of a non-linear programming problem Lee, Linda May 1973

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

C.I NECESSARY CONDITIONS FOR A SOLUTION OF A NON-LINEAR PROGRAMMING PROBLEM  by  LINDA MAY L E E B.Sc,  U n i v e r s i t y o f 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 t h e Department of Mathematics  We a c c e p t t h i s t h e s i s as conforming to t h e required  THE  standard  UNIVERSITY OF BRITISH COLUMBIA  September, 1973  In p r e s e n t i n g an  this thesis  advanced degree at  the  Library  I further for  shall  the  of  this thesis  written  representatives.  of  British  be  g r a n t e d by  requirements  Columbia,  for reference  the  I t i s understood  for f i n a n c i a l gain  o  The U n i v e r s i t y o f B r i t i s h V a n c o u v e r 8, C a n a d a  the  Columbia  shall  Head o f my  that  not  be  I agree and  for extensive copying of  permission.  Department  Date  University  permission  s c h o l a r l y p u r p o s e s may his  f u l f i l m e n t of  make i t f r e e l y a v a i l a b l e  agree t h a t  by  in partial  that  study.  this  thesis  Department  copying or  for  or  publication  allowed without  my  - i i -  ABSTRACT  The  conditions  required  programming problems of the  rain{f(x):  where and.  f h  f o r a s o l u t i o n of g e n e r a l  non-linear  form  x € X  ,  g(x)  ±0  i s c a l l e d the o b j e c t i v e f u n c t i o n ,  ,  h(x)  g  = 0}  ;  the i n e q u a l i t y c o n s t r a i n t  the e q u a l i t y c o n s t r a i n t , a r e p r e s e n t e d i n t h i s t h e s i s .  cases a r e  The  following  studied: (1)  X, and  (2)  X, and  a f i n i t e d i m e n s i o n a l space; g an g  and  h  f ,  f i n i t e dimensional vector  i n f i n i t e d i m e n s i o n a l space; and  h  a r e a l valued  f,  function;  functions.  a r e a l valued  e i t h e r f i n i t e or i n f i n i t e d i m e n s i o a n l  function; vector  functions. An and  a p p l i c a t i o n o f t h i s type of problem to o p t i m a l c o n t r o l w i l l be the r e c e n t developments i n t h i s a r e a w i l l be  discussed.  given  - iii  -  TABLE OF CONTENTS  Chapter 1.  Preliminary Material  1.0  Introduction. •  1.1  D i f f e r e n t i a b i l i t y Concepts  2  1.2  Inverse  5  Chapter 2.  and  • • •.  1  I m p l i c i t F u n c t i o n Theorems......  O p t i m i z a t i o n Problems i n F i n i t e D i m e n s i o n a l 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.  O p t i m i z a t i o n Problems i n L i n e a r Spaces  3.0  Introduction.  26  3.1  G e n e r a l C r i t e r i a f o r O p t i m i z a t i o n by L i n e a r Space Methods  26  3.1.1  G l o b a l Necessary C o n d i t i o n s  3.1.2  L o c a l Necessary C o n d i t i o n s  3.1.3  Necessary C o n d i t i o n s  3.2  Pshenichnyi's  3.3  Comparison of P s h e n i c h n y i ' s  Chapter 4.  ....36 Approach to Luenberger's  48  A p p l i c a t i o n To Optimal C o n t r o l  4.1  B a s i c Necessary C o n d i t i o n s  4.2  Example  Bibliography.  33  Approach..  Introduction  Appendix  ...29  for Equality Constraints......  4.0  Chapter 5.  ..26  Developments  .51 for Optimality  54 57  •  59  65  »67  - iv -  ACKNOWLEDGEMENTS  I am indebted  t o D r . Rodrigo Restrepo f o r s u g g e s t i n g  of t h e t h e s i s and f o r h i s encouragement d u r i n g  the t o p i c  the research of the t o p i c .  My s p e c i a l thanks goes t o D r . U l r i c h Haussmann f o r a l l o w i n g me a generous amount o f h i s time and f o r h i s many c o n s t r u c t i v e comments d u r i n g the thesis  preparation.  - 1 -  CHAPTER ONE;  1.0  PRELIMINARY MATERIAL  Introduction D u r i n g the l a s t decade, the.problem of o p t i m i z a t i o n has  attracted  a l o t of a t t e n t i o n , s i n c e such problems a r i s e i n many f i e l d s ; f o r example, i n automatic c o n t r o l t h e o r y , economics and optimization economics and  problems are not new c o n t r o l theory and  p u t e r , an i n t e n s i v e and  even i n b i o l o g y .  Although  i n mathematics, owing to the demands of a l s o owing to the appearance of the  com-  s y s t e m a t i c i n v e s t i g a t i o n of such problems has  only  r e c e n t l y been s t a r t e d . The  first  c a t e g o r y of problems was  studied  This f i e l d  i s c a l l e d Calculus  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  functions and  of V a r i a t i o n s and  as e a r l y as  are c o n s i d e r e d , s u b j e c t  0. B o l z a The  d e a l s w i t h problems of  and  The  or more unknown  to e q u a l i t y c o n s t r a i n t s .  G. A.  Bliss  d i d s i g n i f i c a n t work w i t h t h i s type of problem. 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 o b j e c t i v e f u n c t i o n and linear.  1925.  theory f o r t h i s problem was  can be dated to By 1951,  c o n s t r a i n t s are a l l  w i d e l y developed by G. B.  Dantzig  1948. the Kuhn-Tucker t h e o r y was  necessary conditions  developed.  This gives  the  f o r an extremum i n convex programming problems  when i n d i f f e r e n t i a l f o r m , f o r m u l a t e s the n e c e s s a r y c o n d i t i o n s  for  and, non-  convex programming problems i n a f i n i t e d i m e n s i o n a l s p a c e . In the decade f o l l o w i n g , the t h e o r y of o p t i m a l c o n t r o l was veloped.  The  b a s i s of t h i s theory i s P o n t r y a g i n ' s Maximum P r i n c i p l e .  p r i n c i p l e p e r m i t t e d t h e , s o l u t i o n of v a r i o u s  problems of mathematical  deThis and  - 2applied nature The necessary  and thus s t i m u l a t e d work i n mathematical programming. embedding o f o p t i m a l c o n t r o l theory i n t o a g e n e r a l theory of  c o n d i t i o n s was f i r s t  Dubovitski.  c a r r i e d out by A. A. M i l y u t i n and A. Y.  They w i t h H. H a l k i n and L. W. Neustadt have taken  "modern" i n f i n i t e d i m e n s i o n a l This t h e s i s presents  the present  approach. the conditions required f o r a s o l u t i o n of  g e n e r a l n o n - l i n e a r programming problems.  The g e n e r a l problem i s of t h e  form min{f(x):  f  i s c a l l e d the o b j e c t i v e f u n c t i o n ,  the e q u a l i t y c o n s t r a i n t . made:  the space  sional,  f  two  f  X  < 0, hCx) = 0}  g  ;  t h e i n e q u a l i t y c o n s t r a i n t and  on which  f,  g,  and  I n Chapter Three,  a f u n c t i o n a l d e f i n e d on  X .  X  h g  a r e d e f i n e d i s f i n i t e dimenand  h  are f i n i t e  dimensional  i s assumed t o be i n f i n i t e  dimensional  From here the problem breaks down t o  d i s t i n c t problems depending on the dimension of t h e range of t h e c o n s t r -  a i n t f u n c t i o n s ; that i s , f i n i t e or i n f i n i t e dimensional. a brief  Chapter Four g i v e s  i n t r o d u c t i o n to o p t i m a l c o n t r o l problems and t o t h e i r s o l u t i o n u s i n g  mathematical programming r e s u l t s  .  A l s o an example i s g i v e n .  F i n a l l y , Chapter F i v e d i s c u s s e s the. r e c e n t developments i n n o n - l i n e a r gramming problems.  The r e s t o f t h i s f i r s t  r e q u i r e d i n the l a t e r  1.1  h  I n Chapter Two, the f o l l o w i n g assumptions a r e  i s a r e a l - v a l u e d f u n c t i o n and  vector functions. and  x £ X, gCx)  Differentiability Let  X,  Y  pro-  chapter d e a l s w i t h the t o o l s  chapters.  Concepts. be normed l i n e a r spaces and  f  be an o p e r a t o r  defined  - 3 on a domain c o n t a i n e d i n  1.1.1  X  and range c o n t a i n e d i n  Definition The o p e r a t o r  f:  X .-> Y  X  i f t h e r e e x i s t s an o p e r a t o r  e  in  X  te-UM2l  „  Gateaux d i f f e r e n t i a b l e at  6f(x;e)  which i s l i n e a r ^  in  x e  in for a l l  =  o  - f ( x ) = X6f(x;e) + r ( x , A e )  for a l l  where  e in X .  A  A-K)  1.1.2  Definition The o p e r a t o r  if  is  and which s a t i s f i e s  f ( x + Ae)  l i m  Y .  f:  X -* Y  t h e r e e x i s t s a continuous  i s Frechet d i f f e r e n t i a b l e at  l i n e a r operator  f ( x ) - f ( x ) = f ( x ) ( x - x) + r ( x ; x - x)  where the f u n c t i o n  r(x,z)  i s such t h a t  lim  fCx):  for a l l x  ^^>l^  | |^o  e > 0  6^-0  there e x i s t s  I f the d e r i v a t i v e of  f  f  i s continuous  t i n u o u s l y F r e c h e t d i f f e r e n t i a b l e on  i s continuous ||x - x|j < 6  such t h a t  X  satisfying  in  I = 0  in  X  .  PT  z  The F r e c h e t d e r i v a t i v e of  X -> Y  x  at  x  implies  i n some open sphere  i f given ||f'Cx) - f ( x ) | | < e . S, f  i s con-  S .  Remark: If  f'(x)  differential i.e.  i s a F r e c h e t d i f f e r e n t i a l then i t i s a l s o a Gateaux  f(js)e  = <5f(x,e)  for a l l e  in  X .  But the  converse  i s not always t r u e  1)  In the u s u a l 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 P r o p e r t i e s o f F r g c h e t D e r i v a t i v e s . I f f o l l o w s from the d e f i n i t i o n that i f f  d i f f e r e n t i a b l e at  x  then  a f + gg  i s Frechet  and  g  a r e Fre*chet  d i f f e r e n t i a b l e at  x  and  (af + (Bg)'(x) = a f ' t x ) + gg'Gx) .  The  c h a i n r u l e and an i n e q u a l i t y which r e p l a c e s t h e Mean Value  Theorem f o r the o r d i n a r y d i f f e r e n t i a b l e f u n c t i o n s a l s o . h o l d f o r F r e c h e t differentiable function. i n Luenberger ferenced  x  The i n e q u a l i t y w i l l be s t a t e d here as i t w i l l be r e -  later. Let  Let  [10].  The p r o o f s w i l l not be g i v e n here but may be found  be F r e c h e t d i f f e r e n t i a b l e on an open s e t X in X . r o be i n X and suppose t h a t x + ah i s i n X fora l l a , o o  0 < a < 1 .  f  Then  || f (x + h) - f (x) 1 < ||b.| sup ||f'(x + ah) || 0^a<l 1.1.3  .  Definition. A functional  f  d e f i n e d on a normed l i n e a r space  be q u a s i - d i f f e r e n t i a b l e a t a p o i n t closed set lim  * F(x) C X f (x + Xe)  ,+ x->o H  A  x  =  i s s a i d to  i f t h e r e e x i s t s a convex weak  such t h a t f (x)  X  f  f*6.FCx)  *  c  ^  f ( j ra  U  &  ± n  x  - 51.2  I n v e r s e arid I m p l i c i t F u n c t i o n Theorems T h i s s e c t i o n d e a l s w i t h the major r e s u l t s from a n a l y s i s u n d e r -  l y i n g the l a t e r  theorems i n o p t i m i z a t i o n .  The commonly known v e r s i o n s o f  the I n v e r s e and I m p l i c i t F u n c t i o n Theorems f o r c o n t i n u o u s l y functions i n  Rn  w i l l be s t a t e d .  f o r p r o o f s of these theorems.  differentiable  The reader i s r e f e r r e d to Rudiri [14]  An I m p l i c i t F u n c t i o n Theorem g e n e r a l i z e d  to f u n c t i o n a l s d e f i n e d on l i n e a r spaces and an Inverse F u n c t i o n f o r Banach spaces w i l l be p r e s e n t e d .  1.2.1  I n v e r s e F u n c t i o n Theorem. Let  E  We. f o l l o w the p r o o f s i n [10] and [ 1 3 ] .  Rn  of  where  f  be a c o n t i n u o u s l y d i f f e r e n t i a b l e mapping of an open s e t Rn  into  y = f(x) . (a)  where  (b)  i f V  y g by  i s i n v e r t i b l e f o r some  open s e t s  is in  V  U  in  E  and  i s the i n v e r s e of g(f(x)) = x  f  for a l l  f  V  in  Rn  where  x  is in  i s one to one on  U  and  U  f(U) = V ;  (which e x i s t s by (a)) d e f i n e d i n x  in  U  then  g  i s a continuously  V .  I m p l i c i t F u n c t i o n Theorem. Let  let  and  and where  d i f f e r e n t i a b l e f u n c t i o n on  1.2.2  x  Then  there e x i s t and  f ''(x)  f  (x,y)  be a v e c t o r of an open s e t  be a c o n t i n u o u s l y d i f f e r e n t i a b l e  d e f i n e d on  E  which s a t i s f i e s  (1)  f ( x , y ) = 0,  (2)  V f(x,y)  E  contained  in  Rn+m  and  n-dimensional v e c t o r f u n c t i o n  the f o l l o w i n g c o n d i t i o n s :  i s non-singular; that i s , ;  V^f(x,y)K = 0  implies  K = 0 .  - 6-  Then t h e r e i s a neighbourhood vector function  e  of  x,  and an  m-dimensional  which i s c o n t i n u o u s l y d i f f e r e n t i a b l e on  Z  such t h a t  (x) ,  (a)  y = e  (b)  f(x,e(x)) = 0 f o r a l l  1.2.3  i n Rn  Z  x i nZ .  G e n e r a l i z e d I n v e r s e F u n c t i o n Theorem. B e f o r e the theorem can be s t a t e d , a d e f i n i t i o n i s r e q u i r e d .  1.2.3.1  Definition. Let  f  an open s e t E D  be a c o n t i n u o u s l y Fre*chet d i f f e r e n t i a b l e mapping from  i n a Banach space  i s such t h a t  f^Cx)  maps  X  X  onto  r e g u l a r p o i n t of the t r a n s f o r m a t i o n  1.2.3.2  Y ,  the p o i n t  x  Y .  If  x in  i s s a i d to be a  f .  Theorem: Let  x  transformation  be a r e g u l a r p o i n t of a c o n t i n u o u s l y F r e c h e t f  mapping the Banach space  Then t h e r e i s a neighbourhood K  i n t o a Banach space  such t h a t the e q u a t i o n  and the s o l u t i o n s a t i s f i e s  V  X  i n t o a Banach space  of the point  f(x) = y  differentiable  y = f Cx)  Y .  and a c o n s t a n t  has a , s o l u t i o n f o r every  y  in V  ||x - x|| < _ K||y - y|| .  Proof: Let q u o t i e n t space  L  o  be the n u l l space of r  X/L  q  i s a Banach s p a c e .  elements e q u i v a l e n t to d e f i n e d by x  x ,modulo  A[x] = f^(x)x  y i e l d i d e n t i c a l elements  then y  A  L  q  f'(x). If  [x]  and i f A  Since  L o  i s c l o s e d , the '  denotes the c l a s s o f i s an o p e r a t o r on X / L  Q  i s w e l l - d e f i n e d s i n c e e q u i v a l e n t elements  i n Y .- A l s o , by d e f i n i t i o n ,  A  i s linear,  - 7c o n t i n u o u s , one-to-one and onto and h e n c e , by the Bounded I n v e r s e Theorem [Appendix, Theorem 1 ] , Let  y  has a continuous  be an element o f  zero element i n L ^ . X/Lq  A  Y  linear inverse.  close to  y  and l e t  g Q = 0, t h e  Now d e f i n e the sequence of elements  and a c o r r e s p o n d i n g sequence  d"gn}  with  §  n  >  a  n  from  element from  L^ ,  r e c u r s i v e l y by L  As  n  - L = A _ 1 ( y - f ( x + g^ •-•)). . n-1 n-1  IIL - L , I] = i n f n n-1" ,T  11  ^at  l|g -6 g ., || , n-l" '  select g °n  1 1 6  CD  from the c o s e t  n  L  such  ||gn-gn.1fli2||Ln-Ln_1|  Rewriting ( 1 ) , Ln  .-1. = A (y -H±  + B _ )) n  1  +Ln_x  ,.  = A "'"(y - f ( x + g T) + A [ g - ] ) by the d e f i n i t i o n o f \J \ ° n - l ° n - l and = A - 1 (J y " f ( x + g .) + f ( x ) g ..) n-1 ° n - l and  similarly,  Define  g  = tg  L  = A  1  the p r o p e r t i e s o f  by t h e d e f i n i t i o n o f  ( y ~ f (x + g _ „ ) + f ( x ) g _ „ ) .  ± + (1 - t ) g n _ 2  and l e t  " F ( x + g _ ) || = ||g _ n  2  n  1  A , A  Thus  differentiable  ( S e c t i o n 1.1.2.1), t h i s i m p l i e s  ||F<* + g ^ )  .. n-1  F(x) = - A _ 1 ( f ( x ) - f'(x)x) .  A p p l y i n g the g e n e r a l i z e d mean v a l u e i n e q u a l i t y f o r F r e c h e t functions  L  - g ^ s u p J l T f e  + gfc) ||  .  - 8 Hence L  l n  L  " n-l'l  - l  A _ 1  H  g  8  " n - l ~ n-2"  By t h e s e l e c t i o n o f  S  U  p  f  H '<* 0< t < l  +  g  }  t  f  (  " ' *>H  ( 2 )  '  and by t h e d e f i n i t i o n o f  ,  h±\\ - | | 8 l - g j l 1 2|| - L j | =211^11 = 2f|A-1f| ||y - y|| . Ll  This implies f o r  ||y - y||  s m a l l enough t h a t  and hence, i n t h i s p a r t i c u l a r case 0 < t < 1 . e x i s t s an  By the c o n t i n u i t y o f  r > 0  f o r e (2) becomes: the p r e c e d i n g  such t h a t  <  f 9 r some  f " at x ,  f o r a given  - L^|| < e||A "'"H ||g^ - gQ|| .  i n e q u a l i t y implies that  e > 0  flgj  By the s e l e c t i o n o f  8 l  >  e,  I' g k " g k - l H  IIgj - I I  There-  ||g2 - g j | <_ 2\\h^ - I. || <_ 2e|[ A "*"|| || g^ - g £  = || t g f c _ 1 + (1 - t ) g k _ 2 | | < r ,  Moreover i f (4) holds f o r a l l  there  f o r j|x - x|| < r .  |g 2 " Sill 1 2 | l g l " U Similarly i f  r > 0  ||gtH= || t g ^ + : 0- ~ t) g Q || < r f o r  ||f'(x) - f "(x) || < e  Hence f o r s u f f i c i e n t l y s m a l l  "Jr  ||g]_lj  l-lK-l  k <_ n ,  "g k J  ( 3 )  then  ( 4 )  '  then  + ( g 2 - g_):+ ••• + ( g n - g __>H n  I2||gl|| < r ,  so t h a t all  ||gt|| = | | t g n + (1 - t ) g n _ 1 | | < r  k. Hence the sequence  •  T  h u s by i n d u c t i o n (4) h o l d s f o r  converges t o an element  g  and c o r r e s p o n d i n g l y  ~9 the sequence  {L^}  converges to a c o s e t  f (x + g) = y  F i n a l l y , by  1.2.4  letting  x  be  i = 1 , . ... , m  ||g| < ^ g j  K = 4||A''^|| ,  Generalized Implicit Let  for  and  a be  L  .  Thus  < 4||A || ||y. - y|| . _1  the theorem i s p r o v e d .  F u n c t i o n Theorem.  m-dimensional v e c t o r , l e t continuous  r e a l valued  X €  R  and  let  f\ (A,x)  f u n c t i o n s which s a t i s f y  the  following conditions:  (a)  f ..(0,0) = 0 f o r i = 1 ,  (b)  f_j.(A,x)  (c)  V-.f.CO.O) =0 A X  (d)  Vxf(0,0)  o  and  X  X = 0,  i s d i f f e r e n t i a b l e at for  i = 1,  x = 0 ;  m  i s non-singular  Then the system of e q u a t i o n s small  m ;  there e x i s t s  f_^(A,x) = 0  a solution  x(A)  has  a solution  with  for sufficiently  the p r o p e r t y  that  A  Proof: Condition  f(X,x) -  where  ^* z z:  inequality  -> o  (b) i s e q u i v a l e n t to  f(0,0) as  - AV^fCO.O) -  z -> 0 .  Now  xV fC0,0)|| x  < rcA  2  + j|x||2 )  CD  a p p l y i n g c o n d i t i o n s ( a ) , (s) , Cd) , the  ( 1 ) becomes  f(X,x) =  (Vxf(0,0))Cx) +rCX,x)  C2)  ||r(A,x) || £ x(A  where  2  + ||x||2 ) .  Gonsider the mapping  _ 1  ( 2 ) , t h i s becomes £  r ( A  2  1  g(X,-x) = x - (V f ( 0 , 0 ) ) f ( X , x ) .  g(A,x) = - ( V ^ CO ,0))  2  + ||x| )|| ( V x f ( 0 , 0 ) ) | | . - 1  assumption t h a t  rCz)  where  ^  X  A ,  T ( A ) <_ A  A ,  there exists a  f o r a l l such  A .  Further since  A  2  vA  +  A2) <  By d e f i n i t i o n  (3)  f o r s u f f i c i e n t l y small  A  of infimum, f o r every such  T CD  it ( A )  By d e f i n i t i o n  2 - /2 2 2 T ( A ) - A < Kr(/A + (T(A) - A ) ) . /2  + x 2 ) < x}  Kx(A 2  T ( A ) such t h a t  K r ( A 2 + ( T * ( A ) ) 2 ) <_ x * ( A ) .  f u n c t i o n and s i n c e  sup r C t ) where 0<t<z  -*• 0 .  K = || (? f ( 0 , 0 ) ) 1 | | . S i n c e  Kr(  wCz) =  T(A) = i n f i x : K r ( A 2  Now s e t  ||gCA,x)||  i s a non-decreasing f u n c t i o n can be made s i n c e i f  W  and thus  and  Without any l o s s of g e n e r a l i t y , the  i t were n o t , r ( z ) can be r e p l a c e d by w(z) > r C z )  r (X ,x)  Applying  of  £. t ( A ) + A  and  x(A) ,  r ( z ) i s a non-decreasing  Since  2 + w  <_ A + w  for  A > 0 ,  w > 0 ,  + (x(A) - A 2 ) 2 ) £ Kr (A + ix(A) - A 2 I) .  this  implies  Thus,  x(A) - A 2 < Kr"(A + |r(A) - A 2 |) . x(A) < A f o r s u f f i c i e n t l y s m a l l A ,  Kr (A + |x(A) - A 2 1) <_Kr(A + A) = Kr C2A) .  Thus  TCA) - A 2 < KrC2A) + 0  Z  as  — z * 0, -  or  <  2 K  *(2D  A — Za -> 0 as X -* 0 . A  +  A  a n d  s i n c e  • ^  Thus  T  W A  -> 0  as  A + 0  - 11 If  ||x|| '< T * ( X )  || gCX ,x) || < K r ( A  2  then  + ||x||2 ) <  KrcA  2  t h i s i m p l i e s t h a t the continuous l i n e a r map ||x|| <_ T (x) i x , Theorem x(X) of  into i t s e l f . 2],  such t h a t g(X,x)  g(X,x)  MU •>  -> 0  and  f(X,x(X)) = 0 ;  as  g(X,x)  ) < t*CA) .  maps the b a l l [Append-  has a f i x e d p o i n t ; t h a t i s , t h e r e e x i s t s a p o i n t  under r ccoonnssiiddeerraattiico n has a s o l u t i o n . implies  (T*(X))2  Hence, by Brouwer's F i x e d P o i n t Theorem  x(X) = g(X,x(X))  implies  +  X  0  ||x(X) || < x ( X ) .  But the d e f i n i t i o n  t h a t i s the s e t of n o n - l i n e a r A l s o , since  lk_i_ll< ^ A A  }  equations  this  CHAPTER TWO:  2.0  OPTIMIZATION PROBLEMS IN FINITE DIMENSIONAL SPACES.  Introduction T h i s chapter  presents  the n e c e s s a r y and s u f f i c i e n t s  conditions  f o r o p t i m a l i t y when the o b j e c t i v e f u n c t i o n and c o n s t r a i n t s a r e f i n i t e dimensional.  The mathematical programming problem to be s t u d i e d here i s :  min f ( x ) :  M:  x € Xq,  is a functional, ction,  h  isa  d e f i n e d on  2.1 N e c e s s a r y  X  g  hCx) = 0  where  i s an m-dimensional v e c t o r  f fun-  k-dimensional vector f u n c t i o n , a l l ,  o  g(x) 1 0 ,  a subset o f  R° .  Conditions.  In the n e c e s s a r y o p t i m a l i t y c o n d i t i o n s , the d i f f e r e n t i a b i l i t y p r o p e r t y o f the f u n c t i o n s p l a y a c r u c i a l r o l e s i n c e t h i s i s used t o l i n e a r i z e the n o n l i n e a r programming problem.  Lemma 2.1.1 Let int X ^ ,  • be a convex s e t i n R n  X  and l e t  E  be an open s e t i n R n  v e c t o r f u n c t i o n and l e t  h  on some open s e t c o n t a i n i n g fCx) = 0  and  continuously for  j = 1,  and  hCx) = 0  w i t h a non-empty i n t e r i o r :  h(x) = 0 .  .  Let  f  -^.-dimensional  be a k - d i m e n s i o n a l v e c t o r f u n c t i o n , b o t h d e f i n e d X  q  Let  .  Let  x  be an element from  f  be d i f f e r e n t i a b l e a t  d i f f e r e n t i a b l e i n an open s e t c o n t a i n i n g k  be an  be l i n e a r l y i n d e p e n d e n t .  have no s o l u t i o n  x  i n X r\ E  x  x ,  E , let h  and l e t  I f the equations  be  Vh^(x)  f(x) < 0  then t h e e q u a t i o n s  - 13 -  VfCx)(x  - x) < 0  and  V h ( x ) ( x - x) = 0  have no s o l u t i o n  x  in  int X o  Proof:  Case  k > n :  j = 1,  Case  T h i s case i s excluded because the assumption t h a t  k ,  k == n :  i s l i n e a r l y independent i m p l i e s that  S i n c e the l i n e a r independence of  i s e q u i v a l e n t to the n o n - s i n g u l a r i t y v o f h o l d because  V h ( x ) ( x - x) = 0  Vh(x)  implies that  the l i n e a r nor the n o n l i n e a r e q u a t i o n s  Case 3  0 < k < The  the way  and  fCx) < 0  proof  Instead -  VhCx)(x  '(x) ,  j = 1,  ..., k  V f ( x ) ( x - x) < 0  (x - x) = 0 .  V f ( x ) ( x - x) < 0  cannot  Thus n e i t h e r  can be  solved.  i t w i l l be a p p l i e d , not  the proof shows t h a t i f the equations  and  such t h a t  x^  have a s o l u t i o n  For a l l is in  R  n-k  x  in and  x  in  the way  it  V f ( x ) ( x - x) < 0  then the equations o h(x) = 0 have a s o l u t i o n x i n X A E . o x in int Xq be. such t h a t Vf Cx) (x --x) < 0 and  Vh(x) (x - x) = 0 .  R  let  x2  is in  int X  Cx^.x,,) R  k  .  form a p a r t i t i o n of Then  Vh(x)  h(x)  = (V X  V  h(x)) X  ,  f o r t h i s case f o l l o w s from an i n d i r e c t a t t a c k because  x) = 0  Let  x  ,  k i n .  :  n  the lemma i s s t a t e d i s the way  i s proved.  Vh  Vh.Cx) ,  Since  VhCx)  ,  l  i s non-singular, this implies i n p a r t i c u l a r  that  2  V  hCx)  i s non-singular.  Thus, s i n c e  hCx) = 0 ,  ^2  V  hCx)  is  ^2  non-singular x ,  "and s i n c e  and  h  i s c o n t i n u o u s l y d i f f e r e n t i a b l e i n an open s e t c o n t a i n i n g  the I m p l i c i t F u n c t i o n Theorem [ s e c t i o n 1.2.2] s t a t e s t h a t t h e r e  an open s e t  W  in  R  n-k  containing  x^  and  exists  a k-dimensional d i f f e r e n t i a b l e  -  vector function  (a)  e  x 2 = eCxD Since  W  such t h a t f o r a l l is differentiable  e(x, + 1  in  h  W,  such t h a t  and  hCx^,e(xD) = 0  (b)  since  x. 1  f o r a l l • x^  is in  W  by c h a i n r u l e ,  V  W . 6 o  W  = e ( x j + 6 v e ( x - ) ( x - x j + o(6) l l 1 1' i s d i f f e r e n t i a b l e at  in  , . there e x i s t s  6 < 5 , • (x- + S(x •-•x,-)) i s i n o 1 1 1 a t x^ i n W , t h i s implies that  - xn))  x  W  i s open and  i Since  all  on  14 "  x  and  .  Thus, s i n c e ' •  for a l l  e  . (1) O '  hCx^,eCxD) = 0 . f o r  since  h(x)Ve(x..) = 0  h(x) + V  6 < 6  > 0  and m u l t i p l y i n g  ^2 by  (x, - x )  But V  x  ^  t h i s becomes  V  h(x) (x  Vh(x)(x - x) = 0  the assumption  and  C2) and  eC^  the f a c t t h a t  + 50^  Because o(6) is in  ,  - xj)  x  there e x i s t s X  o  .  = x2  is in  x2  i s i n "7X and s i n c e " X o o is in X q f o r a l l 6 < 6^;  = VeCxJC^ - x j  = eCxD  ,  + <5(x2 - x 2 )  int  6^ > 0  In rp a r t i c u l a r  Thus  V  x2  to h(x) ( x 0 - x „ ) 2 I  o(6)  x2  K(x)  implies  (2);  (1) becomes  for a l l  6 < 6q  .  (3)  (by assumption) and by d e f i n i t i o n of  such t h a t f o r a l l 5, 1  V  .  equation  +  - x ) = 0 .  h(x)Ve(x )(x  the n o n - s i n g u l a r i t y of  (x2 - x2)  Using  ^2  i s equivalent  h C x ) ^ - x.) + V h ( x ) ( x 9 - x „ ) = 0 . 1 1 x2 I I  V : hCx)Ve(x,)(x n - x..) x2 . i i i  — x  - x ) + V  -i-  -L  can be  chosen such t h a t  i s convex, -  that i s ,  8 < 6^,  J  ^ A o (o) (x^,x2 H j~- ) 0 < 6, *<<5 1 o  .  Since  a — — o(6)~ 6 ) ( x . , x 0 ) + 6 ( x - , x 0 -\ ~ - ) / v V i » 2 1' 2 . o (x^ + S(x - x^) , * 2 + 6 ( x 2 - x 2 ) +  *  (1-  o(6))  _ 15 _  is in  Xq  which by a p p l y i n g e q u a t i o n  e ( x , + S(x - x , ) ) ) • i s i n 1 1 1 in  E  and  since  E  X  is  (3) i s . e q u i v a l e n t to  for a l l  o  6 < 6. . 1  open, t h e r e e x i s t s  Furthermore s i n c e  <$2 > 0  Cx^ + S(x^ - x ^ ) , eCx^ + 6 Cx^ - x ^ ) ) )  6 < 6^,  (x^ + <S(x^ - x ^ ) , x  is  such that f o r a l l  is in  E .  Hence, l e t t i n g  6^ = min{6 ,6 } , 1  2  Cx, + <5(x, - x j . - ^ i c . + 6(x '- x . ) ) ) 1  1  1  "  Since  .,  5 < 6  h ^  f ^  +  4  -  f f(  X ; L  X;L  and  ±  f  ±  x^  X P\ E o in  since  ,  and  since for a l l 4  '  0  then f o r  + 6(2^---x^-))) = 0 .  6, < 6„ and 4  W  <5 < 6. . (4) 3  for a l l  6„ < 6 < 6 3 — 2 • o  i s d i f f e r e n t i a b l e at  such t h a t  <5.  W  - x ) , e(K  ±  F i n a l l y , since existence of  for a l l  Is i n  + S(x  is in  1  h(x^, e(x^)) = 0  Cx, + clCx, - x,-)) l 1 1  6 < 6 o all  1  !  x,  t h i s i m p l i e s the  such t h a t f o r a l l  o  6 < 6,  4  ) , e(x ; L + 6 ( x 1 - x ^ ) ) )  + 6(X;L - xx) , x2  = f CCx 1 ,x 2 ) + 6 ( 3 ^ -  X ; L  + 6(x2  , x2  - x2)  - x2  + o(5))  +  ,  by e q u a t i o n  (3)  )) , r  = fCx) + elfV v f ( x ) ( x . - x.) + V f ( x ) C x - x „ ) + V f ( x ) x^ 1 1 x2 2 / x2  ]  0  9  by  ,  the d i f f e r e n t i a b l i t y of  f  +0(6) at  x  ,  = 6{VfCx)Cx - x)] + 7„ ftx)o(<5) + o ( j 5 ) x2 since  But by assumption such t h a t  - V f ( x ) ( x . - x) < 0  6_ < <S, 5 4  f C ^ + S(x  ±  and  - x^,  f(x) = 0 .  which i m p l i e s t h a t t h e r e e x i s t s  such t h a t  e(K  ±  +  6(2^  - x1)))  < 0  for a l l  5 < <5 . 5  ^5 > 0  - 16 -  Hence, l e t t i n g  6 = min{6^,(5^} ,  f  and  6 < <5  + 6(X;L - x ^ , e O ^ + 6 0 ^ - x 1 ) ) ) < 0  (x.. + 6 ( x . - x . ) ) i l ±  ,  - x)  h(xx+ 6 ^  where  for a l l  ±  e(x  isin X H o  + 5(i  ±  - x^))) = 0  ±  E .  Case 4 k = 0 : Suppose t h e r e e x i s t s  x  i n int X  Then i t must be shown t h a t t h e r e e x i s t s Since and  E  x  i s i n X /~\ E  x  q  in X  (by h y p o t h e s i s )  q  E  satisfying  and s i n c e  X  f(x) < 0 i s convex  q  i s open, t h e r e e x i s t s  (x + <5(x - x ) ) ' i s i n X H there e x i s t s  6.. > 0 1  <5 > 0 such t h a t f o r a l l 8 < 6 < 1 , o o E . By t h e d i f f e r e n t i a b i l i t y o f f a t x ,  such t h a t  cL < <S 1 o  and such t h a t f o r a l l  f ( x + S(x - x ) ) = fCx) + S[Vf ( x ) ( x - x) +  = S[Vf ( x ) ( x - x) +  By t h e assumption exists  V f ( x ) ( x - x) < 0 .  satisfying  §2 > 0  Vf (x) (x - x) < 0  such t h a t  6^ < 6^  ]  o  6 < cS, 1  ^1^- ] , since  f(x) = 0  and by d e f i n i t i o n o f  .  o(<$) ,  there  and such t h a t f o r a l l 6 < 6^ ,  f (x + <5(x - x ) ) < 0 .  'Lemma 2.1.2 Let  X , o  E,  x  and  f  be as g i v e n i n Lemma 2.1.1.  Let h  be  a k - d i m e n s i o n a l v e c t o r f u n c t i o n which i s c o n t i n u o u s l y d i f f e r e n t i a b l e i n an open s e t c o n t a i n i n g X n Q  E  x .  then t h e r e e x i s t s  If  -  p  f(x) < 0  and  SL ' -  in R ,  q  h(x) = 0  in R  k  with  have no s o l u t i o n i n p f- 0,  - - / (p,q) F 0  _ 17 _ satisfying in the closure of X  [pVf (x) + qVhCx)]Cx - x ) >. 0 for a l l x  o  Proof: Case 1: Vh.Cx),  j = 1, ... , k .linearly dependent. -  This, implies that there exists  q in R  that ' qVh(x) = 0 . Therefore for p = 0, for a l l x Case 2:  where  q ^ 0 such  [pVf(x) + qVhOOKx - x) = 0  in the closure of X  VhjCx), j = 1, . . . , k, Since  and  k  X  o  linearly  i s convex, then  independent.  int X  o  HCx) = VhCx) Cx - x) . D e f i n e f o r each  i s convex. x  in  Let  int X q  ,  FCx) = V f ( x ) ( x - x) the s e t  VJ  SCx) = (Cy.z): y € R , z € R , y > FCx), z = H(x)} and l e t S = £  k  S(x) .  x int X o Observe t h a t for  S i s convex s i n c e i f  Cy^>-j_) z  anC  *  ^2^2^  a  r  e  ^  ^ '  n  0 < X < 1, Cl - X)y + Xy > (I - A)FCx ) + XF(x ) , x  2  1  2  (1 - X)VfCx)Cx - x) + XVf(x)(x - x) , x  = Vf(x)[Cl  2  - X ) ( X l - x) + X ( x 2 - x ) ] ,  = F ( ( l - X ) x + Xx ) ; x  2  and Cl - X)z + \z = (1 -. X)RCx ) + M(x ) ±  ±  1  2  ,  = (1 " ^)Vh(x) ( x 1 - x) + XVh(x) ( x 2 - x)  ,  t n e n  -  18  -  = Vh(x) [ ( 1 - A) (  = H [ ( l - \)x  f(x) < 0  Since Lemma  2.1.1,  <  2  + Ax ] .  1  2  h(x) = 0 have no s o l u t i o n  and  F(x)  - x) +.\A(x - x) ] ,  X;L  and  0  H(x) =  x  in X H  have no s o l u t i o n  0  x  o  J  in  Z ( 0 , 0 ) i s not i n S  This implies that separation  which i s i n R  .  that for  Then t h e r e e x i s t s (u,v)  in S ,  p  int  X  o  k x  R  •  theorem [Appendix, Theorem 3 ] f o r t h e convex s e t s  Z {(0,0)}  E , by  Apply the S and  k  e R  qfcR  and  where  pu + qv >_ 0 . . Note t h a t  (p,q)  p > 0  ^  such  0  s i n c e each u.^  can be made as l a r g e as d e s i r e d . Let and  v =,H(x)  S(x)  e > 0 , where  x  and hence i n S .  u = FCx) + ee i s i n int X Thus  q  where .  e  i s t h e a l l ones v e c t o r  Then o b v i o u s l y  pu + qv = pF(x)  (u,v) i s i n >^ 0  + pee + pH(x)  or e q u i v -  alently, pF(x) But  since  e > 0  + qK(x)  + qH(x)  x  i n int  XQ  .  >_ 0  for a l l  x  i n int  XQ  .  i-nf (pF(x) + qH(x)) > 0 . x€int X o F i n a l l y , since  in fact  for a l l  i s chosen a r b i t r a r i l y , one must have  pF(x)  Hence:  >_ - epe  [pVf(x)  (1)  - qVhCx)](x - x)  l i n e a r , e q u a t i o n (1) h o l d s f o r a l l  x  i s continuous i n x  i n the closure of  X  Q  .  Theorem 2 . 1 . 3 Let int X  o  .  X  Let x  o  be a convex s e t i n R  n  w i t h a non-empty  be a s o l u t i o n t o t h e m i n i m i z a t i o n  problem  interior: M .  Let f  and  - 19 "  and  g  be d i f f e r e n t i a b l e a t  i n an open s e t c o n t a i n i n g R  and  s  in R  x  x .  and  h  be c o n t i n u o u s l y  Then t h e r e e x i s t s  closure of  X  Q  in R ,  r in  such t h a t  C r Q V f ( x ) + ieVg(x) + s V h ( x ) ) C x - x) >_ 0  (a)  V  differentiable  for a l l  x  i n the  ; o  (b)  rg(x) = 0 ;  jCc)  Cr Q ,-f) > 0 ;  (d)  G ,r,s) i 0 . 0  Proof: Let I U  J = { I , 2,  the s e t I fined  g Cx) = 0}  I = {i:  and  ±  m} J  and l e t  m^.,  <5 > 0 o  E = {x:  J = {i:  m^  X  q  gAx) < 0}  then  denote t h e number o f elements i n  r e s p e c t i v e l y so t h a t  on some open s e t c o n t a i n i n g  there e x i s t s  and  m^ + nij = m . and s i n c e  g  Since  g  i s continuous a t  Note t h a t at x  x  g  J  i s an open s e t i n R n .  < 0,||x - x|| < <5 } o  Rn  to  f  and  i s i n X Q P\ E .  g  in  in X n X- O  where  F(x) = [ f ( x ) - f ( x ) ,  E ,  E .  a r e . Also, since  Now, s i n c e  blem, then t h e e q u a t i o n s x  R x  F(x) = (f (x) - f Cx) , gjCx)) = (0,0)  since  x ,  such t h a t  I f Lemma 2.1.2 can be a p p l i e d , t h e theorem i s p r o v e d . the mapping from  i s de-  x  isin X  q  F  F Cx) < 0  and  be  gI(x)] . i s differentiable  and  x  i s i n E,  i s t h e s o l u t i o n t o the m i n i m i z a t i o n  f (x) — f ( x ) •< 0  or equivalently  x  and t h a t  Let F  pro-  h(x) = 0  have no s o l u t i o n  H(x) = 0  have no s o l u t i o n  and  Hence, by Lemma 2.1.2, t h e r e e x i s t s  Cr , r T )  in R x  R  »  "20  s  ( r ^ r ^ . ) >_ 0 ,  i n R.k w i t h  CC^.rJVFCx) + s V h ( x ) ) ( x - ic) d e f i n i t i o n o f F, By d e f i n i n g and  -  (r ,r^,s) / 0 . satisfying o  for a l l x  > 0  ( r V f Cx) + -r^Vg '(it) + s V h ( x ) ) ( x - x) > 0 .  this implies that  Q  and r = ( r ^ r ^ . ) .  Xj = 0  i n the c l o s u r e o f X ,., and, by  i n R™,  rg(ic) = r ^ C x )  +  r^jCx)  = 0  rVgCx) = r Vg Cx) + r Vg Cx) = r Vg Cx) . Hence the theorem i s proved. JL  i-  J  J_  J  J-  Remark: on X  I f the c o n v e x i t y requirement X  ment t h a t  be open then a s t r o n g e r n e c e s s a r y o p t i m a l i t y c o n d i t i o n than  q  Ca) i n the p r e v i o u s theorem i s o b t a i n e d .  condition  F r i t z - J o h n S t a t i o n a r y P o i n t Necessary  Theorem  X  q  fCic) = min{fCx):  x  open b a l l around  —.  x  O p t i m a l i t y Theorem.  be an open s e t i n R M  of the m i n i m i z a t i o n problem  x  T h i s i s known as t h e  2.1.4 Let  at  i s r e p l a c e d by the r e q u i r e -  q  and h  x  .  Let x  be a ( g l o b a l ) s o l u t i o n  or a l o c a l s o l u t i o n thereof; that i s  C\ B.Cx), gCx)  £ X  n  o o with radius  6 I  < 0,  hCx)  — Let f  where  = 0}  B.(x) i s an 0  and g  be d i f f e r e n t i a b l e  be c o n t i n u o u s l y d i f f e r e n t i a b l e i n an open s e t c o n t a i n i n g  —  Then t h e r e e x i s t s  Cr ,r,s) f 0  such t h a t  d  • * •i n Rm ,.  —  r o  i n R,  r Vf(x) + Q  r  s  rVg(ic) + sVh(x) =  lc  in R 0,  where  rg(ic)  = 0  and  ( r , r ) >_ 0 . o  Proof: Let Then s i n c e radius  X  x q  be a g l o b a l o r l o c a l s o l u t i o n o f the m i n i m i z a t i o n problem.  i s open, t h e r e e x i s t s  X such that  B. (x) C A  fCx)  O  = min{fCx):  B^Cx)  B„(x)C X  >  an open b a l l around  and such t h a t O  x € B (ic) , g(x) <^0, h(x) = 0 } .  x  with  - .21 ~ Since  B. Cx) A  i s convex and has a non-empty i n t e r i o r  Theorem 2.1.3 can b e . a p p l i e d R  k  ,  CrQ,r,s) f 0  where  thus g i v i n g  (r"0>-r) >_ 0  T  r  in R  m  ,  s  in  fora l l x  i n B. Cx) A  CD  rg(x) = 0 . Since, f o r some  in  i n R,  Q  such t h a t  (r VfCx) + rVg(x) + s V h ( x ) ) ( x - x) > 0 o and  (x € B Cx)) , A  B^Cx),  p > 0,  Cx - p [ r Q V f C x ) + rVg(x) + sVh(x)])  t h e n , by i n e q u a l i t y ( 1 ) » t h i s  is  implies  r Q V f ( x ) + rVgCx) + sVh(x)  =0  Remark: In t h e F r i t z - J o h n n e c e s s a r y o p t i m a l i t y c r i t e r i a , t h e r e i s no guarantee t h a t  r^ > 0 .  If' r  = 0  the necessary o p t i m a l i t y c r i t e r i a  does not say much about the m i n i m i z a t i o n i t s e l f , disappears;  problem s i n c e t h e f u n c t i o n  thus any o t h e r f u n c t i o n c o u l d p l a y i t s r o l e .  f ,  It i s  p o s s i b l e to exclude such cases by i n t r o d u c i n g r e s t r i c t i o n s , known as c o n straint qualifications  g(x) <_ 0  on t h e c o n s t r a i n t s  and  h (x) = 0 .  There  a r e many c o n s t r a i n t q u a l i f i c a t i o n s , some.weaker than o t h e r s but a l l g i v i n g the same r e s u l t , namely  r  Q  > 0 .  The one presented  next g i v e s a v e r y  elegant proof a l t h o u g h i t s r e s t r i c t i o n s a r e not t h e weakest. straint qualifications  Other con-'  can be found i n Mangasarian [ 1 1 ] .  The mod i f l e d Arrow-Hurwicz-Uzawa C o n s t r a i n t Q u a l i f i c a t i o n . Let and  Xq  be an open s e t i n R n  k - d i m e n s i b n a l v e c t o r f u n c t i o n s on  hCx)'= 0} .  The f u n c t i o n s  g  and  h  Xq  ,  let g and l e t  and  h  X ={{x:  be  m-dimensional  x 6 X  Q  , gCx) ±_ 0,  a r e s a i d to s a t i s f y t h e m o d i f i e d  -  22 -  Arrow-Hurwicz-Uzawa c o n s t r a i n t q u a l i f i c a t i o n a t Ca)  g  i s d i f f e r e n t i a b l e at  Cb)  h  i s continuously  Cc)  Vh^(.x)  Cd)  there and  for  d i f f e r e n t i a b l e at k  where  Rn  in  I = {i:  Mangasarian r e f e r s o n l y  x  . such t h a t  g^Cx)  = 0}  Vg^Cx)z > 0  .  A d i f f e r e n t approach where the c o n s t r a i n t  q u a l i f i c a t i o n s i n v o l v e both t h e / o b j e c t i v e :  if  to the r e s t r i c t i o n s . o n the c o n s t r a i n t s  and not on the o b j e c t i v e f u n c t i o n .  [6]v  X  a r e l i n e a r l y independent  exists a solution- z  been developed by G e o f f r i o n  in  x  i = 1,  Vh(x)z = 0  x  f u n c t i o n and the c o n s t r a i n t s has  T h i s approach s i g n i f i c a n t l y weakens t h e  h y p o t h e s i s demanded by Mangasarian but i n t h i s chapter Mangasarian's approach w i l l be  described. The f o l l o w i n g theorem i s known as t h e Kuhn-Tucker  point Necessary O p t i m a l i t y  Theorem  Theorem.  2.1.5 Let  Xq  Rn  be an open s e t i n  of the m i n i m i z a t i o n g  problem  be d i f f e r e n t i a b l e a t  an open s e t c o n t a i n i n g  M  x  v  in  Rk  such t h a t  x  be a g l o b a l s o l u t i o n  or a l o c a l s o l u t i o n t h e r e o f .  and l e t . h  x .  and l e t  Let  g  be c o n t i n u o u s l y  and  Hurwicz-Uzawa c o n s t r a i n t q u a l i f i c a t i o n a t Rm,  Stationary-  h  Let  f  and  d i f f erentiable i n  s a t i s f y the m o d i f i e d Arrowx .  Then t h e r e  exists  V f O O + uVg(x) + vVhCx) = 0, u > 0,  u  and  in ugOO = 0 .  Proof: Since  Xq,  f,  g,  h  and  Theorem 2.1.4, t h i s i m p l i e s t h a t t h e r e  x  s a t i s f y the assumptions of exists  r  in  R,  r  in  Rm  ,  - 23  and  s  in  R  k  where  (rQ,r,s)  r VfCx) + rVg(x) + sVh(x) = 0 u = r/rQ  Suppose  Case 1:  and  such t h a t  rg(x) = 0 . s  v =  /  r  t n e  '  0  Note t h a t i f  > 0  T  Q  theorem i s p r o v e d .  r^ = 0 .  r = 0 . This implies that  s ^ 0  the c o n s t r a i n t q u a l i f i c a t i o n ,  r = 0  then  and  sVh(x) = 0 .  Vh. '(x)' f o r  sVhCx) = 0  independent t h e r e f o r e i f Thus, i f  ^ 0, C r Q , r ) > 0 and.  Q  then by l e t t i n g  -  Since  i = 1,  then  s = 0  k  h  satisfies  are  linearly  which i s a c o n t r a d i c t i o n .  r. > 0 .  o Case 2:  r f'0  .  This implies that J = {i:  g^G). < 0}  .  r > 0 .  Let  I = {i:  g Cx) = 0}  and  ±  Then  rg(x) = r^gjCx) = 0  (1)  and  ?VgCx) + sVh(x) = r I V g C x ) + r / g / x ) + iVh(x) = 0 .  (2)  I  By d e f i n i t i o n of Tj. > 0 .  I  and  J ,  equation  Substituting this into  (1) i m p l i e s t h a t  I  f  and  g  and  Vh(x)z = 0 .  Thus, s i n c e  z  •  in  r]. > 0  r I V g . C x ) z + sVh(x)z = ( r ; [ V g I ( x ) + s V h ( x ) ) z > 0 ]  thus  (3)  s a t i s f y the m o d i f i e d Arrow-Hurwicz-Uzawa  c o n s t r a i n t q u a l i f i c a t i o n , then t h e r e e x i s t s Vg ] [ (x)z > 0  = 0  ( 2 ) , t h i s implies that  ? I Vg Cx) + s"Vh(x) = 0  Since  r  Rn  such t h a t  for a l l  s  in  R  c o n t r a d i c t i n g equation  k  , (3).  Therefore,  for  r / 0,  > 0 .  r o  2.2  -Sufficient Optimality C r i t e r i a . •  Theorem  2.2.1 . Let  X  be an open set i n  q  RN-  and l e t f ,  g,  h  be, respec-  t i v e l y , a numerical function, an m-dimensional vector function and a k-dimensional vector function, a l l defined on let  f  and  g  X  .  o be convex and d i f f e r e n t i a b l e at. x  Let  x  be i n  equality constraint. that  (x,u,v)  If there exists  in R  and  in  R  Since  h  v  such  s a t i s f y the following conditions:  VfCx) + uVgCx) + vVhCx) = 0 ,  Cb) (c) Cd)  ugCx) = 0 , gCx) < 0 , hCx) = 0 ,  (e)  u > 0 ,  x  lc  u  Ca)  then  o ' be a l i n e a r  and l e t h  _  X  i s a solution of the minimization  problem  M .  Proof: X = {x:  Let  x € X , gCx) ± 0, hCx) = 0} q  hCx) = Bx - d = 0  linear equality constraint, B  is a  Bx = d  k x n  matrix and  d  can be substituted f o r Since  f  .  for a l l x  i s some constant vector i n hCx) = 0  and  R  .  X  where Then  VhCx) = B .  i s convex and d i f f e r e n t i a b l e at  fCx) - fCx) 1 VfCx)Cx - x)  in  is a  for a l l x  x , in X .  CD  - 25: -  Condition  Ca) implies that  Vf(x) = - uVgCx) - vVhCx)  or equivalently, C2)  Vf (x) Cx - x) = - uVgCx) Cx - x) - vVhCx) Cx - x) . h(x) = 0,  Since  Bx = d,  and by: the l i n e a r i t y of  VKCx) Cx - x) = BCx - x) = 0 and d i f f e r e n t i a b l e at u  0,  gCx) f_ 0  x ,  for a l l x  X .  Vg(x) (x - x) ^gCx)  ugCx) = 0,  and  in  for a l l x  h , Also, since  - gCx) in  .  i s convex  But because  X  - uVgCx) Cx - x)>^ u"[ - gCx) + gCx) ] = - ug(x) Therefore  g  >. 0 .  equation (2) becomes: VfCx) Cx - x) >_ ^ ugCx) >_ 0 .  Hence by inequality (1)»  f Cx) - f Cx) >_ 0  g(x) <_ 0  x-  h(x) = 0,  and  is in  X .  for a l l x Thus  x  in  X  and  since M .  i s the solution to  Remark: The assumptions of this theorem, namely, the convexity of and  g  f  and the l i n e a r i t y of the equality constraint, can be weakened  somewhat since not a l l the properties of convex functions are needed. example,  f  entiable at  need only be.pseudo-convex at  x ;  x  where  f Cx)' >_.f (x) > g g(x) <^ g(x)  in  X  and i f  and where f o r , ;  x ,  0 < A < 1 ,  X  f  is differ-  VfCx)Cx - x) >_ 0,  that i s for  in  X  where X ,  then  and f i n a l l y the equality constraint  hCx)  = 0  h  Cl - A)x +? Ax  x  then  is in  need not be l i n e a r so long as x .  is in  be quasi-convex at  gCCl - X)x + Ax) <^ gCx)  concave at  x  that i s i f  For  i s d i f f e r e n t i a b l e , quasi-convex and  quasi-  The proof i s very s i m i l a r to the previous proof and can be  found i n Mangasarian  [11],  - 26 -  CHAPTER THREE:  3.0  OPTIMIZATION PROBLEMS IN LINEAR SPACES  Introduction: In t h i s c h a p t e r ,  o p t i m a l i t y c r i t e r i a a r e developed f o r mathematical  programming problems where t h e o b j e c t i v e f u n c t i o n a l and t h e c o n s t r a i n t s a r e d e f i n e d on l i n e a r spaces. and  sufficient  pings  The f i r s t  section deals with  c o n d i t i o n s f o r t h e problem w i t h  c o n s t r a i n t s which a r e map-  from a l i n e a r space i n t o a normed space.  approached i n two ways:  the g l o b a l theory  l o c a l theory using d i f f e r e n t i a b i l i t y .  The n e c e s s a r y c r i t e r i a a r e  r e l y i n g on c o n v e x i t y  modified  S e c t i o n 3.2 d e a l s w i t h  and t h e  A l s o , necessary conditions f o r the  case where o n l y e q u a l i t y c o n s t r a i n t s a r e p r e s e n t developed.  the necessary  i n t h e problem w i l l be  the necessary c r i t e r i a f o r a s l i g h t l y  problem; namely, where t h e c o n s t r a i n t s a r e a c t u a l l y f u n c t i o n a l s  d e f i n e d on a l i n e a r space.  F i n a l l y , i n S e c t i o n 3.3, a comparison o f t h e  necessary, c o n d i t i o n s f o r t h e two problems i s p r e s e n t e d .  3.1  G e n e r a l C r i t e r i a f o r O p t i m i z a t i o n by L i n e a r SpaCe Methods. T h i s p r e s e n t a t i o n f o l l o w s Luenberger [10]  3.1.1  Global Necessary  Conditions.  The b a s i c problem t o be c o n s i d e r e d  L^:  min{f(x): subset on  X  q  i n this section i s :  x 6 X , gCx) 1 8} q  o f a l i n e a r space and  normed space  g  X ,  where f  X  Q  i s a convex f u n c t i o n a l  i s a convex mapping from Z  i s a convex  XQ  w h i c h has a p o s i t i v e cone  into a P .  - 27 R x Z .  C o n s i d e r t h i s problem i n the space  If  s o l u t i o n to t h i s problem then, by c o n v e x i t y , t h e r e would p l a n e which l i e s below  f(x)  which goes through the p o i n t responds to the p o i n t  for a l l x (y ,8)  ( l , z )• i n  y  where  q  were the  e x i s t s a hypergCx)  1 9  and  This separating hyperplane c o r -  R x Z  where  { f ( x ) + z* gCx)} .  = inf °  .  Q  X  in  u  x€X  o Theorem 3.1.1.1 X  Let  be a l i n e a r space and  X  Z  a convex  be a normed l i n e a r space w i t h p o s i t i v e cone  interior.  Let  f  P  X  to  Z .  .  Let  h a v i n g a non-empty X  be a r e a l - v a l u e d convex f u n c t i o n a l on  convex mapping from  X  subset of  o  r  and  q  Assume the e x i s t e n c e o f a p o i n t  g  a  x^  in  X f o r which gCx^) < 8 ;• t h a t i s , g(x^) i s an i n t e r i o r p o i n t of N = - P . l e t y = inf{f(x): x € X , gGO < 0} and assume y is o o — o q  *  finite.  Then t h e r e i s an element  *  z  in  Z  o y = i n f { f Cx) + z gCx): o o Furthermore, i f the infimum i s a c h i e v e d by an  *  ,  z  > 8 o — x € X } . o x  X  in  <. 8  then  f o r which  o  J  gCx)  such t h a t  z g(x) = 0 . Q  Proof: In ACx)  W = R x z>  the space  = {Cr»z):  r >_ f Cx),  d e f i n e the f o l l o w i n g s e t s :  z >_gCx)}  f o r each  x  X  in  ;  let  let A =U  A(x)  x^X  0  o and l e t  B = {(r,z):  r <_ y , z <_ 8}  .  Obviously  CM ,8) o  is in  B  and,  - 28 -  since  is in  x^  X q , .the'point  Since  f  and  and by d e f i n i t i o n of since  N = - P  g  CfCx^)., g C x D )  is in A .  a r e convex, t h e s e t s  Uq, A  contains  A, and  B  a r e convex  no i n t e r i o r p o i n t s o f  has an i n t e r i o r p o i n t , by t h e d e f i n i t i o n o f  an i n t e r i o r p o i n t .  B . B  Also,  i t contains  Thus by the s e p a r a t i n g h y p e r p l a n e theorem, [Appendix,  Theorem 4] t h e r e e x i s t s a non-zero element  w  *  *  = (r ,z ) o o' o  in W  *  such  that  * r Q r ^ + Z Z ^ ±_  r  Since that  x^ — VQ ro — > 0  r 0  Q  2  +  Z  Z 0  and arid  * 2  ^ /.9  *  zo — > 0 .  o ra 1 1  1,Z1^  "'"n ^  Cby d e f i n i t i o n o f But suppose rr  r  a n t  ^ r 2' Z 2  ^  ^  n  ^  B ) , equation Cl) implies  =0  then s i n c e  Q  *  w w  i s non-  Q  * zero,  Z  q  > 0.  implies that  Z  Since Q  (yo,0)  Z ^ >_  0  is in  B ,  ^ i' \}  for a l l  x  for r *  z  n  Q  = 0  ^ .  equation Cl)  In p a r t i c u l a r f o r  * CfCx^), gCxD)  in A ,  t h i s implies that  z Q g ( x ^ ) >_ 0 .  But t h i s  contra-  * d i e t s the f a c t that  gCx,) < 0 ° 1  and  w i t h o u t l o s s o f g e n e r a l i t y , take Now a p p l y i n g of  B  x^ = 1  r  o  > 0 .  o  Therefore  A ,  it = i n f { r + z z: o  x€  (U q ,0)  which  that  ( r , z ) € A} ;  x 6 Xq}  X , gCx) < 9} o —  c o n s i d e r i n g o n l y those  = u o  and  i s an element  e q u a t i o n 1 then imples  = i n f { f C x ) + z*gCx):  < inf(fCx): —  r. > 0 o  = 1 .  and t h e f a c t t h a t  and i s a r b i t r a r i l y c l o s e t o u  z  gCx) <_ 0 ;  by d e f i n i t i o n of u 3 o  by d e f n . of  since x  in  A ;  *  z > 0 o — Xq  for  and  - 29  -  Thus the f i r s t p a r t of the theorem i s p r o v e d . Suppose t h e r e e x i s t s an  x  in  — y  —  = f(x) .  Q  O  because  —  O  *  g(x) < 6 .  and  o v  —  g(x)  this  _  > 9 ,  z  such t h a t  •  <_ 0  and  _  Q  *  < f Cx)  y  ?t  y^. < fCx) + z gCx) ,  S i n c e by above,  —  Xq  Thus  implies _  z g Cx)  —  = 0 .  O  Remarks; The  Ca) A  .  The way  the theorem i s s t a t e d , the c o n v e x i t y of  the c o n v e x i t y of may  theorem depends p a r t i a l l y on the c o n v e x i t y of the  f  and  g .  be somewhat weakened as  A  As  A  i s guaranteed  i n the f i n i t e d i m e n s i o n a l s t u d y ,  may  be convex w i t h o u t  set  f  and  g  by  this being  convex. The assumption the e x i s t e n c e , of an i n t e r i o r p o i n t of  Cb) and  the assumption t h a t  gCx^) < 9  f o r some  x^  in  Xq  P,  guarantee the  e x i s t e n c e of a n o n - v e r t i c a l s e p a r a t i n g h y p e r p l a n e . Only convex c o n s t r a i n t s of the form  Cc) considered.  Linear equality constraints,  to convex i n e q u a l i t i e s the same way  hCx ) <_ 9 1  3.1.2  9  and  as t h e r e never e x i s t s an  and  = 9 ,  - hCx) ^_ 9 x^  1 9  have been  although equivalent  cannot be t r e a t e d i n  which s i m u l t a n e o u s l y  renders  - hCx^ _< 9 .  L o c a l Necessary The  hCx)  h(x)  gOO  Conditions  l o c a l theory of o p t i m i z a t i o n p a r a l l e l s the t h e o r y f o r  finite  dimensions s i n c e g e n e r a l i z a t i o n s of the concepts of d i f f e r e n t i a l s , g r a d i e n t s , and  such to normed l i n e a r spaces are u s e d .  It also parallels  g l o b a l case as the u n d e r l y i n g p r i n c i p l e s a r e s u b s t a n t i a l l y the same: the s e p a r a t i n g h y p e r p l a n e argument i s a g a i n u s e d .  the  - 30 -  The b a s i c problem here i s :  L :  min{f ( x ) :  x € X, g(x) <_ 0}  l i n e a r space,, f and Z  g  where  X  i s a normed  i s a r e a l - v a l u e d f u n c t i o n a l on  i s a mapping from  X  X  i n t o the normed space  which has a p o s i t i v e cone  P .  A g a i n , as i n the g l o b a l c a s e , an assumption must be i n c l u d e d i n the theorem  to guarantee the e x i s t e n c e of a n o n - v e r t i c a l h y p e r p l a n e .  The  analog to the i n t e r i o r p o i n t c o n d i t i o n i s the f o l l o w i n g d e f i n i t i o n of a r e g u l a r p o i n t 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  cone i n X  to  Z  Z  X  and  Z  be normed l i n e a r s p a c e s .  which has a non-empty i n t e r i o r .  Let  g  which i s Gateaux d i f f e r e n t i a b l e a t  x  in  s a i d to be a r e g u l a r p o i n t of the i n e q u a l i t y if  Let  t h e r e e x i s t s an  e  in  X  such t h a t  P  be a p o s i t i v e  be a mapping from X .  g(x) <_ 6  The p o i n t if  x  g(x) < 8  is and  gCx) + <SgCx;e) < 6 .  Theorem 3.1.2.2 Let  X  be a normed l i n e a r space and  w i t h a p o s i t i v e cone  P  Z  be a normed l i n e a r  h a v i n g 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 r e a l - v a l u e d f u n c t i o n a l on  X  and  d i f f e r e n t i a b l e mapping from  x  i s the s o l u t i o n to  problem  and  there e x i s t s a  x z  o  X  to  Z .  i s a r e g u l a r p o i n t o f the i n e q u a l t i y in  Z  &  —  z g(x) = 0 .  for a l l e  in  be a Gateaux  g(x) <_ 0 ,  such t h a t  f ' ( x ) e + z* 6g(x;e) = 0  and futhermore  Suppose  g  space  X  then  - 31  -  Proof: For A(e)  each  e  = { ( r , z ) e R X 'Z:  A l s o d e f i n e the set convex, (0,0)  i s i n both B  X  d e f i n e the  ,  A(0)  A  set  r > f ' ( x ) e , ' z > g(x) + g'(x)e}  B = {(r,z):  is in  (0,6)  observe t h a t ior  in  and  r <_ 0, z <_ 0 }  and  B .  B  .  let  Obviously  A = U e€X  A  and  i s a cone w i t h v e r t e x at  A l s o , from the d e f i n i t i o n of  c o n t a i n s an i n t e r i o r p o i n t s i n c e  N = - P  ACe).  B  are Hence  ( 0 , 0 ) .  B  one  has  an  may-  inter-  point. In order  Theorem 4) Suppose and  to a p p l y the S e p a r a t i n g Hyperplane Theorem  i t must be  A  does.  shown t h a t  A  c o n t a i n s no  Then t h e r e e x i s t s an  g(x) + 6g(x;e) < 0 .  e  in  C o n s i d e r the l a t t e r  g(x)•'+ 6g(x;e) the p o i n t  X  such t h a t  inequality.  such t h a t the sphere i s c o n t a i n e d  . p,  in  This and  N .  in  N  .  Thus the  h  |g(x + ah)  - g(x)  a ,  since  < 0  implies  center  For  0 < a < radius  is in  N  .  i s Gateaux d i f f e r e n t i a b l e ,  - a S g ( x ; e ) | <_ o(a)  g(x + ae)  f ( x + ae) <^ f ( x ) . c o n t a i n s no  g  .  point  (1 - a ) g ( x ) + a(g(x) + Sg(x;e)) = g(x) + a6*g(x;e)  For f i x e d  B  6f(x;e)  a(g(x) + Sg(x;e)) i s the c e n t e r of an open sphere of  contained  small  (Appendix,  i n t e r i o r p o i n t s of  t h a t t h e r e e x i s t s an open sphere of some r a d i u s , say  ap  and  < 0 .  ,  Similarly  i t follows that f o r <5f (x;e)  < 0  implies that  T h i s c o n t r a d i c t s the o p t i m a l i t y of  i n t e r i o r p o i n t s of  B  T h u s , by the S e p a r a t i n g  sufficiently  x  .  Hence  A  . Hyperplane Theorem, t h e r e i s a c l o s e d  1,  - 32 hyperplane  H  s e p a r a t i n g the s e t s  non-zero element  ( r ,z ) o o  in  A  R x Z  and  B ;  that i s , there e x i s t s a  such t h a t  A  A  r r „ + z z- < g < r r . + z z. o 2 o 2 — — o 1 o l for a l l A  and  (r^,z^) B ,  in  A  and  {v^z^)  in  B .  5=0  and  that  t h i s implies that  *  r r . + z z. > 0 o 1 o 1 — •  Since  (0,9)  for a l l  (ri,z.)  in  A  for a l l  Cr0,z0)  in  B  1' r  i s i n both  Cl)  and  *  r r „ + z z_ < 0 o I o 2 —  I  I  •  (2)  In order f o r e q u a t i o n C2) to h o l d , the d e f i n i t i o n of B implies that * * r >• 0 and z > 9 . Suppose r = 0 . Then s i n c e ( r ,z ) i s a r r o — o — o o o * " * * non-zero element i n R x z » 9 . Equation 1 implies that Z D Z ^ Z  0  >  Q  (r^,z^)  for a l l the p o i n t  in  implies that  -  > 0  A  since  x  But  for a l l  t h e r e e x i s t s an  Thus a c o n t r a d i c t i o n i s reached s i n c e  for a l l  = 1  X  Q  e  e  in  X,  and  can  the f a c t t h a t  equation  e  Z  > 0 .  Q  Q  9  is in  X ,  _  > .9  and  this  g(x) £ 9  assume t h a t  X  such  inequality  r  = 1 .  C<5f(x;e), g(x) + <5gCx;e)) i s  for a l l  e  t h i s implies that A  imply t h a t  in  Therefore  in  X  A  In p a r t i c u l a r , s i n c e Z  X,  ,  Cl) becomes  6fCx;e) + z*Cg(x) + <SgCx;,e)) > 0  A  in  i s a r e g u l a r p o i n t of the  and w i t h o u t l o s s of g e n e r a l i t y , one  ,  A  A  -  z Q ( g ( x ) + <5g(x;e))>^ 0 .  Applying in  i n p a r t i c u l a r , s i n c e by the d e f i n i t i o n of  g(x) + 6gCx;e) < 9  gCx) <_ 9 . rQ  ;  g(x) -I- <5g(x;e)) i s i n  C6f(x;e), *  that  A  _  z g'Cx) <_ 0 . o  _  Z gCx) >_ 0 . Q  A  Thus  .  _  zog(x) = 0 .  But  -33  -  F i n a l l y , by the l i n e a r i t y o f Gateaux d i f f e r e n t i a l s w i t h r e s p e c t  to  e ,  5 f ( x ; e ) + z . 6g(x|e)' = 0 .  Remark With t h e r e g u l a r i t y c o n d i t i o n on extended t o i n c l u d e e q u a l i t y c o n s t r a i n t s e x i s t s an  3.1.3  e  in X  such t h a t  Necessary C o n d i t i o n ^  x ,  t h i s theorem cannot be  h(x) = 0  h ( x ) + Sh(x;e) < 6  for Equality  s i n c e t h e r e never and  - h(x)  - 6h(x;e) < 0 .  Constraints.  For problems w i t h e q u a l i t y c o n s t r a i n t s o n l y , a n e c e s s a r y o p t i m 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 p r e s e n t e d here.  R e f e r e n c e s w i l l be made to t h e d e f i n i t i o n o f a r e g u l a r p o i n t o f a  transformation  [ S e c t i o n 1.2.3J and t o t h e G e n e r a l i z e d  Inverse Function  Theorem  [ S e c t i o n 1.2.4] . The  b a s i c problem i s {min  f(x):  space,  x (£. X, h(x) = 0}  f  i s a real-valued  i s a mapping from  X  where  X  i s a Banach  f u n c t i o n a l on  i n t o a Banach space  X  and  h  Z .  Lemma 3.1.3.1 Let point  x  f  a c h i e v e a l o c a l extremum s u b j e c t  and assume t h a t  f  and  i n an open s e t c o n t a i n i n g  x  and t h a t  transformation in  X  h  satisfying  h  are continuously x  (see d e f i n i t i o n 1.2.3).  h^Cx)^  = 0.  to  h(x) = 0  a t the  Frechet d i f f e r e n t i a b l e  i s a r e g u l a r p o i n t of t h e Then  f'(x)e = 0  for a l l  e  - 34 -  Proof: Assume t h a t t h e l o c a l extremum i s a l o c a l minimum. Suppose t h e r e e x i s t s an h'Cx)e = 0 . then x  T  e  D e f i n e t h e mapping  T:  in X  such t h a t  X->R)j Z  i s continuously Frechet d i f f e r e n t i a b l e T'(x) = ( f ( x ) , h ' C x ) )  and  implies that exists a  y  h'(x) maps in X  X  .  Since  onto  Z;  x  i n an open s e t c o n t a i n i n g  that i s , f o r a l l  d i f f e r e n t i a l s , t h i s implies that  h ' C x ) C y + Ae) = h ' ( x ) y  f ' C x ) ( y + Ae) = f ' ( x ) y + A f ( x ) e -  fora l l  f ' C x ) C y + Ae) = t ,  be chosen such t h a t from T .  X  to  R x Z .  Thus  x  z  in  By t h e l i n e a r i t y o f  A .  and  T(x) = ( f C x ) , h(x))  such t h a t  i s a r e g u l a r point of  h'Cx)y = z .  such t h a t  f'Cx)e ^ 0  F o r any  and hence  h ,  Z  this  there Frechet  and t  in R ,  T'(x)  A  can  i s an onto map  i s a r e g u l a r point of the transformation  By t h e G e n e r a l i z e d I n v e r s e F u n c t i o n Theorem [ S e c t i o n 1.2.4], f o r any  e > 0  there exists a vector  such t h a t  x  in X  T ( x ) = ( f ( x ) - 6, 9) ,  and  <5 > 0  with  |x - x| < e  c o n t r a d i c t i n g the assumption t h a t  x  i s a l o c a l minimum.  Theorem  3.1.3.2 Let  exists  f, h  an element  A z o  and  x  be as i n t h e p r e v i o u s lemma. *  in  Z  such t h a t  Then t h e r e  — * — f'Cx) + z h'Cx) = 9 o  .  Proof: Lemma 3.1.3.1 i m p l i e s t h a t of  the transformation  h'Cx)  h'Cx) .  f ' ( x ) i s orthogonal  to the n u l l s p a c e  By t h e d e f i n i t i o n o f F r e c h e t d i f f e r e n t i a l ,  i s a bounded l i n e a r o p e r a t o r .  Since  h ' C x ) niaps  space, t h i s i m p l i e s t h a t t h e range o f t h e o p e r a t o r  h'Cx)  X  onto  Z ,  i s closed.  a Banach Thus,  - 35 -  by the property of bounded l i n e a r operators defined on Banach spaces — * (Appendix, Theorem 5),  fCx)  i s an element i n the range of  This implies the existence of  z  in  Z  h'(x) .  such that  f-(x) = - h'Cx)* z* , or an a l t e r n a t i v e notation f ( x ) •+ z* h'(x) = 3.1.4  Sufficient  0 .  Conditions  By the necessary conditions for optimality i n problem  L  as  seen i n theorem 3.1.1.1, convexity and the existence of i n t e r i o r points guarantee the existence of a separating hyperplane.  But these are too  strong to impose for s u f f i c i e n c y since the appropriate hyperplane could exist i n the absence of these conditions. Theorem 3.1.4.1 Let  f  X  be a real-valued functional defined on a subset  of o  a l i n e a r space Z  X .  Let  g  having a non-empty p o s i t i v e closed cone  element  z  o  in  Z  ,  z  X  be a mapping from  > 0 o —  P .  and an element  q  into the normed space  Suppose there exists an  x  in  X  o  such that  f Cx) + z*g(x") 1 f Cx) + z*gCx) 1 f (x) + z*gCx) for a l l x to  g Cx) < 0 —  in  X ,  z  q  with  x  *  >_ 0 in  in X  . o  Z  *  .  Then  -  x  minimizes  f Cx)  subject  - 36  -  Proof:  & Since  f ( x ) + z g ( x ) <_ f Gx)' + "Z g(x)  it  t h i s implies that  *  since  z^ >_ 0  z^g(x) <_ 0  it —  z g(x)  and  < z g(x) — o  *  thus  .  If  *  z^ >_ 0 .  g(x)  and  _  *  Then, s i n c e  *  it  <_ 0  thus,  it for a l l  Assume t h a t  -  *  z  x1  -  N = - P  >_ 6  in  >_ 0  is in  Xq  in  ic Z ,  it  Gz, + z ) > 0 1 o —  equivalently i s a closed  cone,  _ Therefore,  since  it Z  it ,  and  t h i s implies that  that  gCx^  <_ 0 .  zQg(x) = 0 . Therefore,  since  *  f (x) + Z Q gCx) _< f (x) + z^gCx)  _  or  z  it  then  _  z Q gGx) <_ 0 .  it  z g(x) <_ z^g(x)  z.> 0 1 —  Gz^ + z Q ) g ( x ) • <_ z Q gGx)  for a l l  t h i s implies  for a l l  *  for a l l  *  f Gx) + z^gGx) <_ f GxD  + zQg(x^) .  x  Since  in  *  X q , this implies  _  z^g(x) = 0  by the  that  previous  * p a r t of t h i s p r o o f and that  f(x) ^ f C x D in  .  also since Therefore  and  x  3.2  o P s h e n i c h n y i ' s Approach  X  The  ZQ x  >_ 0 ,  g(x^)  minimizes  fGx)  <_ 0 ,  this  subject  implies  to  gCx)  £0  .  necessary c r i t e r i a f o r o p t i m a l i t y derived  in this  section  are f o r the f o l l o w i n g problem:  P:  min{fCx):  x € X Q , gGx)  <_ 0, h(x) =0}  some s e t i n the l i n e a r space i = 1, defined  m on  X  and  h  assumptions on  Theorem 3.2.2 X,  f,  h  and  j = 1,  f , g^ k  Xq  is  for are f u n c t i o n a l s  .  T h i s p r e s e n t a t i o n f o l l o w s P s h e n i c h n y i 113]. 1)  for  X  where  The,major r e s u l t s  are:  i s the b a s i c theorem of the s e c t i o n .  It's  a r e the weakest g i v e n f o r t h i s type of problem.  - 37 -  The method of p r o o f i s v e r y s i m i l a r to the o t h e r s i n t h a t a s e p a r a t i n g p l a n e argument  i s used. 2)  g  Theorem 3.2.4  r e s t r i c t s theorem 1 t o the c a s e where  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 a t  x  f  and  and  X  f  and  i s a Banach Space. 3) e °  Theorem 3.2.5  r e s t r i c t s theorem 1 to t h e case where  a r e convex and bounded, h X  Banach space  X  i s l i n e a r and  o  i s a convex s e t i n the  .  Pshenichnyi's f i r s t  theorem i s s i m i l a r i n statement to Mangas-  a r i a n 's /Minimum P r i n c i p l e N e c e s s a r y O p t i m a l i t y Theorem f i n i t e d i m e n s i o n a l case.. X , q  f,  g,  h  [ S e c t i o n 2.1.3] i n " t h e  R e c a l l t h a t Mangasarian's r e q u i r e d assumptions on  were:  1)  X  2)  f  and  3)  h  i s c o n t i n u o u s l y d i f f e r e n t i a b l e ' i n an open s e t c o n t a i n i n g  q  i s a convex s e t i n g  R  w i t h a non-empty  n  are d i f f e r e n t i a b l e at  interior.  x .  x . P s h e n i c h n y i ' s b a s i c assumptions a r e :  then f o r  1)  X  X  2)  t h e r e e x i s t s a convex cone  A>>  0  i s a l i n e a r space,  i s some s e t i n  q  X  .  such that i f e i s i n K k x(A) = x + e + E r.CA)e. i s i n i=l  s u f f i c i e n t l y small,  K  1  X  o  where  e.  1  for  i = 1,  k  a r e any v e c t o r s i n  X  1  and the f u n c t i o n a l s  r.CX) r.  satisfy  lim—: = 0 . •X-0 , , f(x(A)) - f(x) x  n  3  )  u  l j J U  • A-s-0  A  £  F  C  e  )  a  n  d  l  i  m  _ i ^ A->0  g , ( x ( A ) ) " g(X> -<G (e) ±  A  - 38 -  for to  i = 1,  m  where  F  and  a r e convex f u n c t i o n a l s w i t h r e s p e c t  e . . h.(x(A)) -  4)  tional  lim A+0  h.(x)  -H.(e) A  where  1  H.  i s a linear  func-  1  . XQ  Observe t h a t P s h e n i c h n y i makes no c o n v e x i t y assumptions d i r e c t l y on 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  h i s r e s u l t s a r e i n terms of  F,  G, > and  and  h .  Thus  H .  Thelemma p r e c e d i n g theorem 3.1.2 H^,  f, . g  proves t h a t i n the case where  a r e l i n e a r l y independents, the s e p a r a t i n g p l a n e argument can  be a p p l i e d i n Theorem 3.2.2 Lemma  .  3.2.1 Let  X ,• X,  f , '.g  x  be the s o l u t i o n to t h e m i n i m i z a t i o n problem and  h  s a t i s f y assumptions 1 through 4.  E. , ...., H, - be l i n e a r l y independent.?;". D e f i n e X  I = {.i:  g.Cx) X  each s e t .  ¥• 0}  and l e t m  Also, l e t g. (x) = 0}'. •,  X  ,  m  denote the number o f elements i n  J  Then the convex h u l l o f the s e t m  K =  where  1  tv  J = {i:  P  U(Cr,s,t) € R X R e^K  , X R :  r - FCe),  s = G (e), t =  HCe)}  and the s e t M  P = {'Cr,s,t) e R x R  I  k 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  t h a t the e x i s t e n c e of an element i n the i n t e r s e c t i o n c o n t r a d i c t s the  - 39 -  minimality  of  f(x) .  implies that since such  Let  (r,s,t)  (r>s,t)  is in  coK  3  where  coK A  P  3  there e x i s t s  3  .  This  3  in  Cr , s , t )  K  that 3  ( r , s , t ) = Z X. ( r , s  j  = F(e3),  that  e°  s3  is  3  X. > 0  3  3  3  are i n  K  Z X. = 1  t 3 = H(e J )  K  i s convex and  3  K  .  e  3  in  e ° = Z A.e 3  Let  Z X. = 1  i  .  j J  then f o r some  GjCe ) and since  and  J  (r ,s ,t )  =  in  ,t )  J  Furthermore, s i n c e r3  be an element i n  K  and  where  , observe  X. > 0  3  .  3  Therefore  FCe°) <_ Z X. F ( e 3 ) j  since  F  i s convex w i t h r e s p e c t  to  e  ,  3  -  Z X. r 3  j  ,  J  = r ;  similarly  G^Ce°) 1 s  FCe°) •< 0,  and,  Gj.Ce ) < 0 0  since  and  C o n s i d e r the s e t of Tl)^(X,r^,r ,  • • • ,r^) = h^Cx  2  a3  are i n  5.. ij  = 0  X  if  and  and  = 1,  ..., k  since  H ( e ° ) = t ..  (r,s,t)  where  for  P  .  equations  + Xe° +  6.. = 1 ij  k Z r.a3) j=l 3  if  i = 1,  = 0  for  i = 1,  ) =  H.Ca  i = i .  ..., k  r ± CA) lim — - — = 0 X A->0 _  C o n s i d e r the p o i n t s  Thus  i s also i n  x(A)  has  k  where  that i s  Then by  the  Theorem [ S e c t i o n 1.2.5] the system of  ijj. (X,r 1 ,.... , r , ) = 0 i  HCe°) = 0  a r e chosen such t h a t  i 4 i  Implicit Function  is linear,  H  a solution  Generalized  equations r . (X)  for  . _ = x + Ae° +  k  E  3=1  r.(A)a3 3  where .".A > 0 ,  - 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  Similarly by definition i = 1, :..., m,  fCxC )) < fCx)  for sufficiently small  A  g,  g^xCX)) < g^x)  ±  thus implying  + X ^ C e ) + oCX^ 0  0  gjCxCX)) < 0 . Finally by construction of  x  for  g^-CxCX)) <_ gjCx) + XjGj.Ce ) + oCAj.) . But  gj-Cx) = 0 and G^(e°) < 0 . Thus for sufficiently small  sufficiently small  A^ .  X ,  xCX) , hCx'CX)) = 0  for  X . Therefore a contradiction to the assumption that  is the solution to  P is obtained.  Theorem 3.2.2 Assume 1 through 4 a g a i n . problem  P  such t h a t and  _  If  i s a s o l u t i o n to t h e m i n i m i z a t i o n  r 6 Rm  then t h e r e e x i s t s r 6 R , • _ _ o  r Q F ( e ) + r G(e) + sH(e) >_ 0  rg(x) =  x  for a l l  , e  s £ R in  k  where  Cr , r , s ) ^ 0 o  K  where  ( r Q , r ) >_ 0  0 .  Proof: Case  1:  set  (r  Case  2:  lemma  o  coKA P = <f> . Since  coK and P are f i n i t e dimensional convex  sets, they can be separated; that i s , there exists a vector m  T  R XR  k  XR  s u c  h that  rr+  +  Cr^.s^jt^)  i n coK ,' thus for a l l point  ^ 2 2' 2^  "*"  c  >S  t  Cr,Sj.,t) in  nP  >_ 0 >_ x^r + s ^ + t t 2  s i n K , and for a l l  ' h i s implies that T  rFCe) + Sj-Gj-Ce) + tHCe) > 0 for a l l e i n K  for a l l  (r,ij)  and a l s o t h a t and  s =  (s^jSj)  ?F(e)  and  ,  >_ 0  since  < 0  the theorem i s proved  + sG(e) + tH(e) >_ 0  since  By.letting  e  in  K  with  g-j-Cx) = 0  and  (r,s) >0  s^. = 0 .  N e x t , 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 i s a Banach space and  f  and  t i a b l e w i l l be p r e s e n t e d . functions  g^  for  i = 1,  m  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  I t w i l l be shown t h a t i f  Lipschitz condition  X  are quasi-differen-  c o n t a i n s a l l Gateaux d i f f e r e n t i a b l e f u n c t i o n a l s  functionals.  Sj.= 0  since  for a l l  sg(x) = s^g^Cx) + S j g j ( x ) = 0  < 0 .  and  f  and  and a l l convex  also s a t i s f y a  g^  then  lxm  A+0  • fCx(X)) - f (x) r? A  _ „  =, -,.,sup  fVCx)  *  r \e)  and g ( x I X ) ) . - g.(x)  A  ±  lim  = A  A+0 i.e.  sup  g (e)  g*€S.Cx)  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  a r e comparable  to Luenberger's l o c a l case (Theorem 3.1.2.2) which i s i n terms o f Gateaux differentials.  Lemma  3.2.3 Let  assumption 2. X  X  be a Banach s p a c e .  Let  f,  g±  for  Assume the e x i s t e n c e o f  1=1,  m  K  as i n  be f u n c t i o n a l s d e f i n e d on  w h i c h a r e 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 t h a t f o r  - 42 h.(x(A)) - h.(x) ^ * A i - 1, ...., k , lim • • = h. (e) for some h. in X A+0 • where x is the solution to the minimization problem V ~. If the sets 1  and GJj*-) for i = 1,;..., m  FCx)  1  are bounded then i f  A _ * _ A sup f (e) + Z r . sup g (e) + Z s.h.Ce) > 0 °f*€FCx) 1-1 g? 6;c5) 1=1 ~ M  r  K  1  i  1  1  1  t  r  I  for a l l e  in K , i t is necessary and sufficient that there exists *  r -  *  f t F(x) and g  functionals  ±  * r- f +  m  Z  _  r.  -  6 G^x)  k * r . g. +  for i = 1,  such that  _ * * Z s. h. i s in K j=l J  1=1  m  J  Proof: The proof for sufficiency is obvious. Let  A" A A — A N = {x : x = r f +  "f 6 F(x) and g± € G Q) ±  for F(x)  i = 1, and  m  This says that  * K  that  *  K  1  3  3  m} . Since N  and ^ ( x )  F(£)  i s convex. Also since  are, by definition, weak  closed and  <3. (x) for i = 1, m are weak compact. These * * * N is weak closed and weak compact.  Suppose there does not exist m  1  are convex by definition,  bounded, F (x) and  for i = 1,  K  for i = 1,  G^(x) for i = 1, ..., m  in turn imply that  _ A * Z r . g. + Z s. h. wher e 1-1. j-1  such that  * r f + O  f  in F(x) and g^ in  ^.(x)  * * * Z r . g. + Z s. h. . is in K . .. 1 1 . .. J 1 l-l j=l J m  k  .  * and N have an empty intersection, or equiyalently  *  - 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 a l s o convex.  Thus  K  - N  i s r e g u l a r l y convex X  [Appendix Theorem 7,]; t h a t i s , f o r every f u n c t i o n a l there e x i s t s  e  in  jit  X  jit  • ' it  for a l l ' z  S i n c e the zero f u n c t i o n a l i s not i n  it  it  z (e) < - e < 0'., Thus  *  but  in  N  *  .  since  y  ,  and  it  - N  "ft  ,  |r 1  Ie - e 1I ' o  it  *  y (e)  for a l l  *  Thus  e  for a l l  it  y  in  i s bounded f o r a l l  x Ce) < - e  G .Cx)  o  i s so s m a l l  A I 1Ix. Ce - e )1 I + 1  for a l l  o  x  o  i n ' Cx)  y  *  is in  x  *  in  K  by prop-  N  e  in  A  x.  K  i n 0 . Cx)  + E sJ . , j 3=1. for  * J  J h . Ce  - e1 ) o  1 = 1, . . . , m .  A  M  A  K  0 < r sup f (e ) + E r . sup g. Ce ) + E 1 ° f* ° i = l 1 g* ° j=l  •  *  M  A  M  = x*Ce)'+ e/2  1  r . g.Ce) + x x  s. h.Ce ) 1 1 °  A  K  f Ce ) + E r . g.Ce ) + E ° ix 1 ° j=l i =  < r f (e) + E o .=  K  that  A  A  *  K  *  in  a r e bounded, t h e r e e x i s t s  E J r . I Ix Ce - e 1) . ' i 11 o o i=l.  A  and  o  M  and  K  supremum p r o p e r t y  < r - 0  - N  t h i s implies that  1  where  K  e > 0 .  it  e r t i e s . of c o n j u g a t e cones and F(x)  K. - N  K  mt y (e) = 0 . y l K*  i s a cone,  Since  in  (e) - x (e) > e > 0  This implies that  K  not i n  such t h a t  z (e) < x (e) - e o  x  q  s 3  3  h Ce ) + e/4 0  A  K  E j = 1  s . h (e) + e/4 j 3  + e/4  < e/4  Then by  - 44  -  it Thus, and  it  x (e) 2l - e/2  x Ce) < - e  for a l l  it in  x  3.2.4 Let  f,  g_^  for  i = 1,  f u n c t i o n a l s on a Banach space  ... , m X  .  and  Let  the e x i s t e n c e of  K  for  X  r  j = 1,  j = 1,  k  for  as i n assumption 2.:  be some s e t i n  If  f  and  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 has  j = 1,  k,  m i n i m i z a t i o n problem i n Rm — ^ Cx) and r  and it g_^ r f O  and  futhermore  s  in  in  *  then i n o r d e r t h a t  P , R^  G^Cx) m  +  i t i s necessary where for  *  E r . g.+ . . . X X 1=1  ... , k X .  Assume  o g^  for  i = 1  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 a r e q u a s i - d i f f e r e n t i a b l e and  hj  N  so n e c e s s i t y i s e s t a b l i s h e d .  Theorem  be  .contradicting  it  x  that there e x i s t s  k  m  *  h^  for  a Gateaux d i f f e r e n t i a l  be a s o l u t i o n to  ( r o , r , s ) ^ 0, and  i = 1  if  m  r  the in  Q  R  functionals< f  ,  in  such t h a t  *  I s. h . £ K . . . X X i=l  with  Cr ,r) > 0 o —  v  r gCx) = 0 .  Proof: If i  = 1,  f, for  e. °i  i t can be shown t h a t the g i v e n assumptions on m  and  and h. j  i.= 1,  for  j =1,  i n theorem 3.2.2 m  k  f,  g_^  for  imply t h a t the c o n d i t i o n s on  a r e s a t i s f i e d and  that  F Cx)  and  ,are bounded, then by Lemma 3.2.3, t h i s . t h e o r e m  G': Cx) l is  proved. Since it  f  and  g_^  for  i s s u f f i c i e n t to c o n s i d e r j u s t  i = 1., .„..., m f .  Since  s a t i s f y the same c o n d i t i o n s  - 45 -  fCx(A))rf(x)  f(x(A)) - f ( x  =  +  Ae)  ^f(x  +  Ae)  - f(x)  ^  a  n  d s i n c e >  b  y  E r.CA)e. f Cx(A)) - f (x + A e ) A  d e f i n i t i o n of x ( A ) ,  f  < L  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 t a k i n g  lim  f  (x(A)) - f(x)  E  *  f  1  and  C e )  f o r a  l  l  x  (  a  limits,  )  i n  x  s i n c e  1  = 0  f (X + e ) - f ( x )  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 o f  A  lim A-H-0  =  s  u  p  f  * . (  e )  ^  T  h  u  g  b  y  s  e  t  t  i  n  g  (y  F  e  similarly  that  G.(e) =  s  u  p  sup  F  and  for  s i n c e e q u a l i t y has been  f  g.(e)  for  i = 1, . . . , m,  this  implies  1  m  and  g^  a r e convex w i t h r e s p e c t t o for  i = 1, . . . , m  e  and  i s more than met  established.  F i n a l l y , since  *  f * ^ ) x  i = 1, of  f  f 6FCx)  g*€GCx)  assumption 3 r e q u i r e d  h^  f o r j = 1,  k  has a Gateaux d i f f e r e n t i a l  at  x  f o r j = 1,  k  and s i n c e  f o r j = 1,  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 o r f i  =  f*6F(x) 1  hj  ^  because  r.CA)e.  i=l  lim L A-H-0  s u p  1  fV(x)  A  A-H-0  —  =  1  i-l  = 1  yields h,(x(A)> - h (x) * lim A A-H-0  Thus s e t t i n g  k and  satisfy  g^ f o r  m  H.Ce) = h . ( e ) ,  J  J  * =h.(e)  H.,  [ S e c t i o n 1.1.1] i s t h e r e q u i r e d  for a l l  xCA)  in X  3  by d e f i n i t i o n o f Gateaux d i f f e r e n t i a l s  3  l i n e a r f u n c t i o n a l f o r assumption 4 .  Suppose n > 0  F(x) i s n o t bounded.  there e x i s t s  e n  *  with  le I = 1 1 n  t h a t f o r every  and a f u n c t i o n a l  f n  1  f C e) > n - e n n "—  such t h a t  This implies  f o r some  e > 0 .  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  fCx + Xe ) - fCx) = X n  Since  f  i n FCx)  i s a quasi»  that  sup f *€ F(x)  f*Ce ) + oCX) n  > X f*Ce„) + oCX)  —  n  n  > X Cn - e) + oCX) .  Since  f  ]fCx + ^>^) ~ fCx)| <_LX ,  also s a t i s f i e s a L i p s c h i t z condition,  t h i s now i m p l i e s  LX >_ X(n - e) + oCX)  be chosen so l a r g e t h a t i s reached.  n - e > L  .  since  n  Thus L  L > n - e . i s fixed.  But  n  can  Thus, a c o n t r a d i c t i o n  F i n a l l y , s i n c e t h e same argument h o l d s f o r  G^Cx), i = 1,  the theorem i s p r o v e d . The  f i n a l theorem presented i n t h i s s e c t i o n i s a p a r t i c u l a r i z a t i o n  of the problem  to t h e case where  P  convex bounded f u n c t i o n a l s , where f u n c t i o n a l s , and  X  f  and  g^  f o r i = 1,  h_. f o r j = 1,  k  i s a convex s e t i n t h e Banach space  m  are  are linear X .  This  theorem  o i s s i m i l a r t o Luenberger's g l o b a l case  [3.1.1].  Theorem 3.2.5 Let  f  and  g^  f o r i = 1,  on a Banach space  X .  Let  f u n c t i o n a l s on  and  let X  X  h^. f o r j = 1 ,  m  be convex bounded k  functionals  be bounded l i n e a r  be a convex s e t i n X . I f x i s the o s o l u t i o n t o the m i n i m i z a t i o n problem P , i t i s n e c e s s a r y t h a t t h e r e  m,  - 47. —  exists  r  ~~  in R ,  Q  in R  r  xn.  lc  —  and  ~~  in R  s  with  ^  (r ,r,s) ^ 0 Q  such  that r f Cx) + r g Cx) + shCx) > t f Cx) + rg Cx) + shCx) Q  Q  in X  for a l l x  (r ,r) > 0 o —  where o  rgCx) = 0 .  and moreover  f  Proof:  Let K  Then  K  = {e:  e = ACx - x)  i s a cone and i f  for x  is in K  e  in  XQ,  X  f x, /.A >• 0} .  x(X) .= x + Ae  then  isin X o  for small  A  since  X  i s convex.  Since  f  i s a convex functional  o  i .  f Cx + Ae) - f Cx) —  lim  A-H-0  .Then  F  S e  i = 1, . . . . m .  h.(x + Ae) - h.(x) lim — A^+0  ^ _  C  F  -  ,  ^  C  —  \  Since  h. x  .  to  j_ -r. / \ j r / - , \ L e t FCe) = fCx + e) - f Cx) .  T  e .  Similarly define  i s a linear functional ,  3h.Cx) =  X  ~  F  f Cx + e) - f Cx)  i s a convex f u n c t i o n a l w i t h r e s p e c t  for  G.Ce) x  9f Cx) - — <  by theorem 1, t h e r e e x i s t s  —1 9e r  = h.Cx + e) - h.Cx) = H. Ce) . x x i in  Q  R ,  s  in  R^  where  Thus  Cro>r,s) f 0  such that r FCe) + rGCe) + sH'Ce) > 0 o —  for: a l l  e  in K  where (r ,r) > 0 o'  —  or e q u i v a l e n t l y and by s e t t i n g  r f(x) Q  and  r (x) = 0 ; S  r C f C x + e) - f C x ) ) + rCgCx + e) - gCx)) + sChCx + e) - h(x))- > 0 Q  e = x - X  q  f o r some  x  in  XQ,  this implies  - rgCx) + shCx) >_ i f Cx) + r g ( x ) + shCx) Q  for a l l  x  in  XQ .  - 48 -  3.3 Comparison  o f P s h e n i c h n y i ' s Approach:to Luenberger's .  In Luenberger's m i n i m i z a t i o n problems t h e r e can be an number of c o n s t r a i n t s s i n c e the i n e q u a l i t y c o n s t r a i n t Z ,  i s a mapping i n t o  a normed l i n e a r space o f any d i m e n s i o n , f i n i t e or i n f i n i t e and  i l a r l y the e q u a l i t y c o n s t r a i n t of  g  infinite  any d i m e n s i o n .  h  i s a mapping i n t o  Z ,  sim-  a Banach space  Thus P s h e n i c h n y i ' s problems a r e 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  P s h e n i c h n y i ' s r e s u l t s a r e b e t t e r than Luenberger's s i n c e P s h e n i c h n y i ' s assumptions a r e 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  r e s t r i c t e d t o the case where the number of  L  c o n s t r a i n t s i s f i n i t e , to P s h e n i c h n y i ' s problem  P  w i l l be p r e s e n t e d .  S i n c e , i n 1 L u e n b e r g e r ' s p r e s e n t a t i o n , g l o b a l and l o c a l eases w i t h i n e q u a l i t y c o n s t r a i n t s and the case w i t h e q u a l i t y c o n s t r a i n t s o n l y a r e a l l handled s e p a r a t e l y , the comparison w i t h P s h e n i c h n y i ' s assumptions w i l l ' a l s o handled s e p a r a t e l y but f i r s t observe t h a t the problems can be deduced from choosing of  Xq  P  by s e t t i n g  Xq  from the l i n e a r space  a mathematical programming problem. r e f e r t o Kushner's paper:  L^,  be  and  to be the whole space  X .  X  qualifying  i s a way  of f u r t h e r  The  For an example o f where t h i s i s used  Necessary C o n d i t i o n f o r Continuous  Parameter  S t o c h a s t i c O p t i m a l Problem [8J.;  3.3.1  I n e q u a l i t y C o n s t r a i n t s — L o c a l Case. First  i t w i l l be.shown t h a t Theorem 3.2.2  d e r i v e Theorem 3.1.2.2.  The s e t  X  and the cone  can be a p p l i e d to K  can b o t h be d e f i n e d  - 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  t h a t assumption ( 3 ) (Theorem 3 . 2 . 2 ) h o l d s w i t h Gateaux d i f f e r e n t i a l s .  F  and  f  and  G  g  being  Hence from theorem 3 . 2 . 2 , t h e r e e x i s t s  implies  the r  €  R  ,  o r € R X  m  where  where  Cr ,-r) f 0  C r Q , r ) >_.0 Now,  such t h a t  and  r F ( e ) . + ?GCe) >_ 0  such t h a t  for a l l  e •in  rg(x) = 0 .  i f the c o n d i t i o n t h a t  x  be a r e g u l a r p o i n t of the. i n e q u a l i t y  c o n s t r a i n t i s assumed i n Theorem 3 . 2 . 2 t h i s would imply the e x i s t e n c e e  in  X  such t h a t  says t h a t  g(x) + 6gCx;e) < 6  rg(x) = 0 ,  f o r a l l .e  in  X .  C r o , r ) >_ 0 , If  r  = 0  and  g(x)  Cro,r) ^ 0  since Thus  i s as g i v e n r > 0 . r ^ 0  r ^ f C x j e ) + r5g(x;e) > 0  for a l l  e  in  X .  i n the r e g u l a r i t y c o n d i t i o n , then  But  rg(x)  = 0  hence  r<5g(x;e) < 0  and, w i t h o u t l o s s of g e n e r a l i t y ,  r  Q  (1)  r ( g ( x ) + <5gCx;e)) < 0 c o n t r a d i c t i n g Cl) •  can be taken as 1 .  w i t h the r e g u l a r p o i n t assumption added, theorem 3 . 2 . 2 says for a l l and  e  in  X  .  T h i s , i n t u r n , "implies that  3.3.2  Hence  FCe) + rG(e) >_ 0  6fCx;e) + r6gCx;e) > 0  s o , 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  6 f ( x ; e ) + rSgCx;e) = 0 ,  Theorem 3 . 2 . 2  r  ir6g(x;e) >_ 0  e  and  But  t h i s then i m p l i e s  o  If  < 0 .  of  e ,  the r e s u l t of theorem 3 . 1 . 2 . 2 .  Inequality Constraints  - G l o b a l Case  As s t a t e d e a r l i e r , Theorem 3 . 2 . 5 i s v e r y s i m i l a r to Theorem 3.1.1.1.  In f a c t , b o t h r e q u i r e c o n v e x i t y  r e s u l t s of Theorem 3 . 2 . 5 f o l l o w .  of  Xq  ,  f  and  g .  Thus the  I f the i n t e r i o r p o i n t assumption i s added  to Theorem 3 . 2 . 5 , then the assumptions of 3 . 2 . 5 a r e e q u i v a l e n t  to 3 . 1 . 1 . 1  R e c a l l t h a t the i n t e r i o r p o i n t c o n d i t i o n i m p l i e s the e x i s t e n c e of  x1  in  - 50  X  such t h a t  g(x^)  < 6 .. . W i t h t h i s c o n d i t i o n added, the r e s u l t s o f  Theorem 3.2.5, namely  ( r Q , r ) ^ 0,  r Q f ( x ) + rgCx) ^ r Q f ( x ) + r g ( x ) since i f  r  =0  o  then  l o s s of g e n e r a l i t y  3.3.3  Equality The  -  r  ( r Q , r ) >_ 0,  for a l l  rg(x,) < 0 . •6 1 = 1  and  x  rgCx) = 0  in  X  Hence, w i t h  and  ,  would imply  r  > 0  o  ,  r  > 0  Q  without  the r e s u l t s of Theorem 3.1.1.1 a p p e a r .  Constraints  assumptions of Theorem 3.2.2  theorem 3.1.3.2.  The  set  X  and  w i l l be d e r i v e d  the cone  K  from those of  can b o t h be d e f i n e d  as  o X  .  S i n c e i n 3.1.3.2, the e q u a l i t y c o n s t r a i n t  tional  f  are c o n t i n u o u s l y  assumption 4 i n 3.2.2  results  Now, formation  X  ,  Thus theorem 3.2.2  h  F  and  H  equal  can be a p p l i e d and  r G(e) .o  maps onto  t h u s , by  h'(x)e  + sH(e)  > 0 —  for a l l  x  e  in  X  func-  to-the  the  and  following  Rk  .  If  r  the l i n e a r i t y i n  Since  must be  s ^ 0 , 0  = 0  Q  e  then  sh''(x)e >^ 0  of the F r e c h e t  t h i s implies that  for a l l  e  in  r  > 0 o —  be a r e g u l a r p o i n t of the  be added to the assumptions of theorem 3.2.2.  h'(x) and  ,  l e t the c o n d i t i o n t h a t  sh/Cx)e = 0 . of  the o b j e c t i v e  hold:  (r ,s) = 0 o  that  and  F r e c h e t d i f f e r e n t i a b l e , assumption 3. and  f o l l o w immediately w i t h  Frechet d i f f e r e n t i a l s .  h  X  ,  This  trans-  implies  for a l l  k  but  T h e r e f o r e , w i t h o u t l o s s of g e n e r a l i t y , for a l l  e  in  f " ( x ) + sh(x)  X = 0  so t h a t by .  r  linearity in  = 1 e  in  some of the components  hence the rank of  t h i s c o n t r a d i c t s the f a c t that  e  differentials,  h'(x)  l e s s than  .  h^(x) and  is k  maps onto  R  f ' C x ) e + sh''(x)e >^ 0  of the F r e c h e t  differentials,  - 51 -  CHAPTER' FOUR:  4.0  APPLICATION TO OPTIMAL CONTROL  Introduction In an o p t i m a l c o n t r o l problem, t h e dynamics a r e d e s c r i b e d  by a  system-of d i f f e r e n t i a l equations o f the form  ^  where  xCt)  - f (x(t), uCt))  i s an n - d i m e n s i o n a l " s t a t e " v e c t o r ,  control vector  and  f  i s a mapping o f x  s u p p l i e d w i t h an i n i t i a l s t a t e  (t  produces a v e c t o r - v a l u e d , f u n c t i o n the i n t e r v a l on which  x  and  0  x R1"  u.(t) i s an n - d i m e n s i o n a l Rn  .  This  ) and a c o n t r o l i n p u t  x .  u  Rn  CD  L e t the i n t e r v a l  are defined.  system when  function  u ,  [ t ., t'^J r e p r e s e n t  A l s o , i n a d d i t i o n to t h i s  dynamic s y s t e m , the c l a s s i c a l . o p t i m a l c o n t r o l problem has an o b j e c t i v e f u n c t i o n a l o f the form  1  J =  £(x,u)dt  t. "0  J i  and  a f i n i t e number o f t e r m i n a l  constraints.  g.(x(t.)) = c . °x x i  for  i = 1, . . . r '  C2) or e q u i v a l e n t l y  gCx(t^)) = c  T h u s , an o p t i m a l c o n t r o l problem c o n s i s t s o f f i n d i n g t h e p a i r o f f u n c t i o n s Cx,u)  minimizing  J  w h i l e s a t i s f y i n g the system C l ) and t h e t e r m i n a l  c o n s t r a i n t s C2)• By c o n s i d e r i n g  the problem as one f o r m u l a t e d i n  t r e a t i n g the d i f f e r e n t i a l e q u a t i o n C l ) and t h e t e r m i n a l  Rn  x ^  constraint  a n  d by  (2) as  - 52 connecting  u  arid  x ,  programming problem. valued f u n c t i o n x  and  u .  f  t h e o p t i m a l c o n t r o l would reduce t o a mathematical  Some assumptions must be made f i r s t .  have c o n t i n u o u s p a r t i a l d e r i v a t i v e s w i t h r e s p e c t to  L e t u €. u C .C [t and  C [ t ,t-]  condition where  on x  (t )  »  Q  t > t  a given  [t^t^]  .  produced by  u .  respect  then  I.  and f o r an i n i t i a l  a unique c o n t i n u o u s f u n c t i o n x ( t )  x  i s s a i d t o be t h e t r a j e c t o r y o f t h e system  denote t h e c l a s s o f a l l a d m i s s i b l e t r a j e c t o r i e s . and  g  have c o n t i n u o u s p a r t i a l d e r i v a t i v e s w i t h  t o t h e i r arguments. Now, l e t  n  •v t simply the i n t e g r a t e d  is  a mapping from  , t j o  f ( x ( s ) , u(s))ds  Q  is  1  o  h  U = CmIt  , t j ,  X = C [t  A(x,u) = x ( t ) - x ( t )  Fre'chet  u £ U  i s t h e f u n c t i o n r e s u l t i n g from t h e a p p l i c a t i o n o f  Let X  F i n a l l y assume t h a t  i s the c l a s s of admissible  A l s o assume f o r any g i v e n  x  u ,  U  1  e q u a t i o n (1) d e f i n e s  If  control  .  where  t h e s e t o f c o n t i n u o u s m-dimensional  m  o functions  ,t^]  m  control functions  L e t the v e c t o r -  and d e f i n e  1  = 0 .  Observe t h a t t h i s i s  o form o f t h e d i f f e r e n t i a l e q u a t i o n  C [t ,t^] x C [t ,t^] n  m  o  o  d i f f e r e n t i a l of  A  into  C [t n  o >  t^J  (1). .  Then  A  Thus t h e  e x i s t s , i s c o n t i n u o u s and i s g i v e n by t h e  formula t  fc  V f(x,u)hCx)ds  A'(x,u)(h,v) = h(t) t for  all  (h,v) i n X x  t i v e s , the terminal w i t h Fre'chet  u  •  l  to  o Also, since  constraint  g  g  (3)  V fCx,u)vCs)ds .  X  U  has c o n t i n u o u s p a r t i a l  i s a mapping from  C [t ,t^] n  o  deriva-  into  R  r  differential: g'(x)h = V g(x)h(t  )  for a l l  h  in X .  (4)  - 53 -  S i n c e the t r a n s f o r m a t i o n the o p t i m a l c o n t r o l problem and of  A  and  g  d e f i n e the c o n s t r a i n t s of  s i n c e these c o n s t r a i n t s a r e a c t u a l l y ones  e q u a l i t y , the q u e s t i o n of r e g u l a r i t y of t h e s e c o n s t r a i n t s i s e q u i v a l e n t  to a s k i n g i f , a t the o p t i m a l t r a j e c t o r y , t h a t i s , a t differentials  A'(x,u)  and  (see d e f i n i t i o n 3.1.2.1). (i)  V^gCx)  i s , f o r any  has r a n k e  r  in  Rn  -  x  g'(x)  ,  taken as a p a i r , map  To e s t a b l i s h t h i s , two and  t  the  onto  Frechet X x  R  assumptions a r e needed:  ( i i ) the system (3) i s c o n t r o l l a b l e , t h a t  there e x i s t s  v  in t  h(t)  (x,u),  V f(x,u)h(s)ds — x  l  t o  o  U  such that  V U f (x,u)v.Cs)ds = 0 ,  (5)  and M t J  have a s o l u t i o n (A>,g'') (h,v)  h  in  X  .  i s onto i f f o r any in  X x U  Using e  - e •  (6)  ( i ) , i t i s c l e a r t h a t the p a i r Rn  in  and any  y  in  X  t h e r e i s an  such t h a t rt  net)  -  1  Jt  X  V f(x,u)h(s)ds -  Vuf(x,u)v(s)ds = y(t)  (7)  X  o  o  and h(tx)  If  v = 0  Now,  (8)  then by the fundamental e x i s t e n c e theorem f o r l i n e a r  i n t e g r a l equations ii .  = e  let  h  [Appendix, Theorem 6 ] , e q u a t i o n be  Then I t i s c l e a r t h a t a i n t s are r e g u l a r .  the s o l u t i o n of h = h + h  C5)  and  satisfies  (7) has  C6) w i t h (7) and  Volterra  a solution  e = e - h(t^) .  (8).  Hence the c o n s t r -  - 54 -  4.1  Basic Necessary Conditions For O p t i m a l i t y . The.basic necessary  c o n d i t i o n s s a t i s f i e d by the s o l u t i o n to the  o p t i m a l c o n t r o l problem w i l l be g i v e n  Theorem  here.  4.1.1 rt  Let  (x,u)  minimize  J =  ^ £(x,u)dt fc  xCtQ)  fixed- and  g(x(t^)) = C .  d i t i o n s are s a t i s f i e d at valued  function  t  Itj.t^]  in  A(t)  s u b j e c t to  ^  = f(x,u),  o  A l s o , assume t h a t the r e g u l a r i t y  (x,u) .  con-  Then t h e r e i s an n - d i m e n s i o n a l v e c t o r -  and an r - d i m e n s i o n a l v e c t o r  y  such t h a t f o r a l l  (a)  - | ^ = [Vxf(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 ) ] T V u f ( x ( t ) , u ( t ) ) + V u £ C x C t ) , GCt)) = 0 .  (ID  Proof; dx Since  - j — = f (x,u)  can be r e w r i t t e n i n t h e form  as seen i n the i n t r o d u c t i o n and s i n c e problem to be considered.has J  g(x(t^)) - C = 0 ,  only e q u a l i t y c o n s t r a i n t s .  are continuously Frechet d i f f e r e n t i a b l e  a r e s a t i s f i e d , and s i n c e  .(x,u)  and.  y 6 R  such t h a t  the minimization  Since  A,  g  and  s i n c e the r e g u l a r i t y c o n d i t i o n s  i s the s o l u t i o n to t h e m i n i m i z a t i o n  by theorem 3.1.3.2, t h e r e e x i s t s f u n c t i o n s of bounded v a r i a t i o n  A_(x,u) = 0  X 6 NBV[tQ,tj],  the n o r m a l i z e d  (see Luenberger 110J, D u a l of  problem,  space o f  C[t ,^3) ,  - 55 -  _ 1  V Kx,u)h(t)dt + X  T  V fCx,u)hCs)ds]  d[X(.t)] [h(.t) -  X  t  + y V g(xCt ))hCt ) = 0 x  I  CL2)  1  and _ 1  VJl(x,u)v(t)dt +  for a l l  (h,v)  in  Equation  X x U •  d[.X(t)]  T  V u f (x,u)v(s)ds = 0  Without l o s s o f g e n e r a l i t y , s e t  (13)  X(t^) =  (12) i s e q u i v a l e n t t o ft dX(t)  h(t)dACt) -  V Jt(x,u)h(t)dt + X  V^f(x,u)h(s)ds X  + yxVxg(x(t1))h(t1) = 0  Then i n t e g r a t i n g by p a r t s the t h i r d term o f the above e q u a t i o n and s u b stituting  \(tj) = 6 ,  equation  (12) can be r e w r i t t e n as  h(t)dX(t) +  V Hx,u)h(t)dt + x  + y V g(x(t ))h(t ) = 0 x  1  Thus, i t i s c l e a r that a suitable  h  in  X  X  1  for a l l h  in  X .  (t ,t,) since o 1  .  terms.  otherwise  Since  However t h e r e must be a jump a t (13) h o l d s f o r a l l continuous  h  t^  h ,  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 hCt-^) - M b ) = 0 .  (14)  can be c o n s t r u c t e d t o make the second term o f (13)  - Vg ( x ( t , ) ) y X  [X(t)]TVxf(x,u)h(t)dt  can have no tumps i n  l a r g e compared w i t h the other of magnitued  1  with  T h e r e f o r e , i n t e g r a t i n g by p a r t s t h e second term,  e q u a t i o n (12) becomes  1  { V ^Cx,u)hCt);^ x  = o  1:^  or. e q u i v a l e n t l y , rt 1  {CV ACx,u) + [ ( t ) ]  T  x  Let  ;  B(t)  =  V fCx,u))hCt) - l X ( t ) ]  {V £ ( x , u ) • + IX-(S)] V f ( x , u ) } d s X X  IV £Cx,u) + [X(t)]Vf(x,u)]h(t)dt = = 0 .  1  This implies that constant  c  .  1  x  h ( t Q ) = h ( t o ) = hO^)  }dt = 0 .  T  x  t  I n t e g r a t i n g by  B(t)  d t  dt  (15)  parts,  since  o  Thus e q u a t i o n (15) becomes  {B(t) + U ( t ) ] T } : | £ ' d t = 0 .  - X(t) = [ B ( t ) ]  + c  [Appendix:  arid hence by the d e f i n i t i o n o f  B  ,  Theorem 8] f o r some  e q u a t i o n (9)  E q u a t i o n ( 1 3 ) , a f t e r i n t e g r a t i n g the second term by  holds. parts,  becomes V >l(x,u)v(t)dt u  or  +  1  [X(t)]TVuf(x,u)v(t)dt = 0  equivalently, rt 1  Let  I V u £ ( x , u ) + !X.(t')]TV f ( x , u ) ] v ( t ) d t = 0  D(t) = V u £ ( x , u ) + T X ( t ) ] V u f ( x , u ) .  for a l l  Then e q u a t i o n  v  in  U  .  (16)  (16) becomes  rt. D(t)v(t)dt = 0  (17)  - 57  If  D t t ) :f 0  a t a p o i n t , say  D(t)>  i n a neighbourhood of t h a t p o i n t . i s zero o u t s i d e inside.  0,  Let  then by v  continuity,  be any  t  D(t)  > 0  c o n t i n u o u s f u n c t i o n which  the neighbourhood but which i s g r e a t e r r  Then  -  than zero somewhere  l D(t)vCt)dt  > 0 ,  contradicting  (17).  Thus  D(t)  t o i s e q u a l to zero and  equation  F i n a l l y , by A(t,) = 6  to  J-  be  (11)  changing the boundary c o n d i t i o n on = JV- g ( x ( t ) ) J  AOO X  holds.  T  X  c o n t i n u o u s throughout  X  ft^jt^J  4 . 2 A n Example Problem i i i ; O p t i m a l  T  y  and  A(t^)  to account f o r the jump,  from X  will  the theorem i s p r o v e d .  Control.  C o n s i d e r the problem of f i n d i n g the m-dimensional c o n t r o l function  u  t h a t m i n i m i z e s the q u a d r a t i c  1  t  subject  objective  functional  ( [ x ( t ) ] T Q x(t) + I u ( t ) J T R u(t))dt  o  to the l i n e a r dynamic  constraint  Ay;  ^ =  where m x B  m  Q  i s an  n x  F x(t) + B u ( t ) ,  n  xCt )  n x m  (18)  symmetric p o s i t i v e - s e m i d e f i n i t e m a t r i x ,  symmetric p o s i t i v e - d e f i n i t e m a t r i x ,  i s an  fixed,  F  i s an  n x  n  R  matrix  i s an and  matrix.  A p p l y i n g the n e c e s s a r y c o n d i t i o n s  - f£ = FTA(t) = Q x ( t ) ,  [A(t)]T B +  of Theorem 4.1.1,  X(tJ  [u(t)]T R = 0  .  =.9  (19)  - 58 -  Since u(t)  = - R  R  - I T B  i s p o s i t i v e d e f i n i t e , this implies  that  X(t) . and thus t h e dynamic l i n e a r c o n s t r a i n t = F xCt)— B R_1BTACt),  ^  x ( t Q ) fixed  (18) becomes  .  (20)  Observe t h a t e q u a t i o n s (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 e q u a t i o n s whose s o l u t i o n  A(t) '= P ( t ) x ( t )  of  s a t i s f i e s the r e l a t i o n :  where  P(t)  i s the  n x  n  matrix  solution  the R i c c a t i d i f f e r e n t i a l equation HP ££. + dt  P  T - I T F + F P - P B R B P + Q = U,  P(t,)  1  =0  .  - 59 CHAPTER FIVE:./DEVELOPMENTSt In the l a s t few y e a r s , a l o t of work has been done i n . t h e development o f n e c e s s a r y o p t i m a l i t y c r i t e r i a f o r programming problems w i t h b o t h e q u a l i t y and i n e q u a l i t y c o n s t r a i n t s .  The g e n e r a l form o f t h i s  problem i s G:  min{f(x): f:  X  x € X,  R,  g:  gtx) <_0,  X ^ Y  and  h(x) = 0} h:  where  X -> Z .  The f o l l o w i n g cases have been p r e s e n t e d : 1)  X, Y, Z  2)  X, Y  l i n e a r spaces and no e q u a l i t y  3)  X, Z  Banach spaces and no i n e q u a l i t y  4) " X,  finite  dimensional  a l i n e a r space and  Y, Z  constraints constraints  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 r e q u i r e d f o r o p t i m a l i t y r e s u l t s i n the l o c a l case o f  (2)  a  s w e l l as cases Cl) and  (3).  In case  r e q u i r e d the e x i s t e n c e o f convex approximations o f l i n e a r approximation of B. D. Craven f  h  f  ( 4 ) , Pshenichnyi  and  g  and a  as w e l l as a convex a p p r o x i m a t i o n o f  [4] does an e x t e n s i o n to case  (3).  X  I n h i s problem  i s not a f u n c t i o n a l but r a t h e r a mapping i n t o a Banach s p a c e .  main r e s u l t w i l l be s t a t e d here f o r comparison  .  His  t o Theorem 3.1.3.2.  Craven's Main R e s u l t . Let subset i n  X .  X, Y  and  Let  f:  Z  be Banach spaces and l e t  U -> Y  be F r e c h e t d i f f e r e n t i a b l e and  be c o n t i n u o u s l y F r e c h e t d i f f e r e n t i a b l e . that  fQJ)  E = {x:  i s dense i n  Y  and  x € U, h(x) = 0, h'Cx)  U . be an open  h(U)  Assume (by r e s t r i c t i n g i s dense i n  i s an onto map}  .  Z .  fi.:'. Y  U -> Z and  Z)  Let  T h e n . fCx)  i s stationary  - 60 -  s u b j e c t to t h e c o n s t r a i n t s  h(x) = 0  e x i s t s a continuous l i n e a r map  M:  at  x = x € E  Z -> Y  H. H a l k i n and L . Neustadt  i f and o n l y i f t h e r e  such t h a t  f'(x) = Mir Cx) .  [7] and L . Neustadt  [12] p r e s e n t the  c a s e where the number of i n e q u a l i t y c o n s t r a i n t s i s i n f i n i t e and the number of e q u a l i t y c o n s t r a i n t s i s f i n i t e ; t h a t i s , i n problem spaces  X, Y  a r e i n f i n i t e . d i m e n s i o n a l and  The assumptions on  f , g, h  and  X  Z  G,  the  i s f i n i t e dimensional.  were s i m i l a r to P s h e n i c h n y i ' s ; t h a t  i s convex approximations were used and t h u s , the r e s u l t s were i n terms of these convex a p p r o x i m a t i o n s . for  M. Altman [1] developed  the n e c e s s a r y  criteria  t h e r e v e r s e problem; that- i s where the number o f e q u a l i t y c o n s t r a i n t s  i s i n f i n i t e and t h e number o f i n e q u a l i t y c o n s t r a i n t s i s f i n i t e In Bazaraa and Goode's paper [3] , the n e c e s s a r y c o n d i t i o n s f o r the case where t h e r e a r e i n f i n i t e l y many e q u a l i t y 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 a r e p r o b a b l y the most g e n e r a l so f a r a v a i l a b l e .  B e f o r e the main r e s u l t s can be s t a t e d a few d e f i n i t i o n s a r e r e q u i r e d : Ca)  The problem to be c o n s i d e r e d i s : 8:  min{fCx):  f:  x 6 S, gCx) e cSL C, h (x) = 0}  X -> R, g: X + Y  and  normed l i n e a r spaces; the c l o s u r e o f Cb) and  x  in  C  S  where  h:  X -> Z;  where  X, Y, Z  i s a subset of C  X,  are c% C  is  i s a convex cone i n Y .  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 s e t S  c% S i s d e f i n e d . a s :  DCS,x) = {x:  there i s a b a l l  <S > 0  such t h a t  imply t h a t  B  about t h e o r i g i n and  y£x + B  x + Xy £ S} .  and  H  CO,6)  - 61 Cc) The cone of tangents for an arbitrary set S and x i n ci S is defined as: given any 6 > 0, there exists a A 6 Co,<5)  T(S,x) = {x:  z 6 B. such that  and  x + Ax + Az € S where  o  Bg Cd) derivatives  is a ball:around the origin with radius  5} .  The functions• f and g are differentiable at x with  F and G  in the following sense:  1/A Cf Cx + Az) - f (x)) -> FCy)  for A -f; 0 , z -> y  1/A (g(x + Az) - g ( x ) ) + G(y)  for  +  and  A ^ 0 , z -> y . +  G i s ci C-convex i f • GCAx + Cl - A)y) - AGCx) - Cl - A)GCy) € cJl C  Ce)  for each x, y and A •= (0,1) . Cf) The level set L CNote: x  i s defined as L = {x:  hCx) = 0} .  i f x is the solution of B then, obviously,  L) .  Remarks The cone of i n t e r i o r d i r e c t i o n s  (1)  i s similar  to the cone  K  used by P s h e n i c h n y i . C2) then  f  and  If g  f  and  g  are d i f f e r e n t i a b l e at  a r e o b v i o u s l y Gateaux d i f f e r e n t i a b l e a t  But Gateaux d i f f e r e n t i a b l e a t  x  since  y .  z  x  may not converge to  i n the above sense x  when  z = y .  need not imply t h e above d e f i n i t i o n  - 62  -  Main R e s u l t ; ;  Theorem: Suppose t h a t i s convex.  Let  M  x  CD (li) Ciii)  8  and  suppose t h a t  be a nonempty convex subset of  t h e r e e x i s t s a non-zero  :  s o l v e s problem  o,  u >_ vg(x)  (u,v,w) v t  c  ,  in w  e  R x Y  x  x  TCL,x) .  D(S,x) Then,  such that  M  = 0  (uF + vG + w)x  >_ 0  for a l l  x  in  DCS,x) .  Extensions: Cl)  If  x  i s i n the i n t e r i o r of  C2)  If  S  i s convex and  C i i i ) i s equivalent in  to  then  uF + vG + w = 0  a non-empty i n t e r i o r then c o n d i t i o n  CuF + vG + w) Cx) ^_ CuF + vG + w) Cx)  for a l l  x  S . C3)  If  b  i s Frechet d i f f e r e n t i a b l e at  i t can be shown t h a t  T(L,x) C N(H)  can be chosen such t h a t N(H)  has  S  C T(L»x)  n u l l space of  or  and  If  TCL,x) = NCH)  thus  H .  T h i s c o n d i t i o n i s . i m p l i e d when e i t h e r  (a)  h  Cb)  X, Z x  H  ,  a r e Banach s p a c e s , and  range of and  The  the range of  H  h  assumption  Here  N(H)  i s continuously  i s equal to  Z  i s the  H  i s c l o s e d , then  w  Z .  Frechet This i s  CSection 1.2.3)  i s f i n i t e d i m e n s i o n a l or  X  and  Z  are  can be. w r i t t e n as a  a continuous l i n e a r f u n c t i o n a l on  Y  .  H, M  i s af f i n e  If either  Banach spaces and c o m p o s i t i o n of  then the s e t  CNCH))"1.  w £  to Luenberger's r e g u l a r p o i n t d e f i n i t i o n C4)  with derivative  can be viewed as a r e g u l a r i t y a s s u m p t i o n .  d i f f e r e n t i a b l e , at equivalent  M = NCH)  .  x  -  From t h i s theorem and  63  -  points. (3) and  C4)  the.following  two  theorems a r e immediate.  Theorem: Let  X, Y, Z  be normed l i n e a r s p a c e s , where  is finite  dimensional.  Suppose t h a t  and  g  a r e d i f f e r e n t i a b l e : i n the sense  of  Cd) w i t h , d e r i v a t i v e s  F  and  definition  f  Z  l i n e a r t r a n s f o r m a t i o n fronr  X . to  letting  x  h  a non-zero  be a f f i n e .  If  (u,v,w) £ R x Y (i)  Cii) Ciii)  U >_ 0,;.  V  Z  with  G  and  let  N(H) C  i s the s o l u t i o n to x Z  H  be a  continuous  T(L,x) , . eg.  by  8  exists  then t h e r e  such that  & C  vgCx) = 0 CuF + vG + wH) (x) >^ 0  for a l l  x  in  D(S,x) .  Theorem: Let space.  X  and  Z  be Banach spaces and  Suppose t h a t  f  and  g  (d) w i t h d e r i v a t i v e s  F  and  G.  Frechet d i f f e r e n t i a b l e at  x  Y  a r e 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  F u r t h e r suppose t h a t  h  i s continuously  x  solves  with derivative  H  * t h e r e e x i s t s a non-zero  (u,v,w)  be a normed l i n e a r  in  R x X  .  If  B  then  g  is  * X  z  such that  * (i) Cii) Ciii)  u > 0, vg(x)  v € C = 0  CuF + vG + wH) Cx) >. 0  for a l l x  in  DCS,x) .  Remark: If,  i n the above theorem,  S  i s convex,  f  i s convex,  - 64  cl  C-convex and  g  r-  i s a f f i n e then c o n d i t i o n  Ciii)  i s equivalent  to  uf Cx) + vG(x) + wH(x) >_ u f Cx) + vg Cx) + whCx) - uf Cx) . Hence i f itions  x  solves  8  then t h e r e e x i s t s  (u,v,w) f 0  C i ) » ( i i ) and the above i n e q u a l i t y . h o l d .  such that  cond-  - 65 -  APPENDIX  1.  Bounded I n v e r s e Theorem [2] Let  X  be a Banach s p a c e ,  normed l i n e a r s p a c e . and  suppose t h e range o f  (b)  (c)  If  x 6 D  A  1  and  i s a closed linear  i s of- c a t e g o r y I I .  m > 0  a  transformation  Then:  such t h a t f o r any  such t h a t  Y ,  = Y  Ax = y  and  yfe Y  there i s  ||x[| <_ mfl.y'|| .  e x i s t s , i t i s a bounded l i n e a r  continuous  at l e a s t one f i x e d  transformation.  map  f  o f a c l o s e d b a l l i n Rn  point; that i s , a point  x  such t h a t  i n t o i t s e l f has f Cx) = x .  S e p a r a t i n g P l a n e Theorem [ l l ] Let  X  and  Y  Then t h e r e e x i t s a p l a n e them;  that i s ,  be two non-empty d i s j o i n t convex s e t s i n R n {x:  cx <_ a <_ cy  x  such that  and  Rn  ,  for a l l  S e p a r a t i n g Hyperplane Theorem Let  x  it  it  x  in  X  such t h a t  H  X  and  X ,  y  which separates  in Y .  Y  X  has no i n t e r i o r p o i n t s of  separating  and  it it sup x Cx) 1 . i n f x Cx) xfeK^: xfr^  P r o p e r t y , o f Bounded L i n e a r Operators Let  in  c f 0  .  [.10 ]  Kj- has i n t e r i o r p o i n t s and  t h e r e i s an  cx = a} ,  be convex s e t s i n t h e normed l i n e a r space  Then t h e r e i s a c l o s e d h y p e r p l a n e  5.  X  Brouwer's F i x e d P o i n t Theorem [5] Any  4.  D -* Y  A CD)  t h e r e e x i s t s an some  3.  A ,  A:  a subspace o f  i s onto; that i s A C D )  (a) . A  2.  Suppose  D  .  K^;. t h a t i s , •  i n Banach Spaces [10]  be normed spaces and l e t  normed space o f a l l bounded l i n e a r o p e r a t o r s from  f X  be an element i n t h e into  Y .  L e t the  - 66 -  range o f N(f)  6.  f ,  denoted by  R(f) ,  i s t h e n u l l space o f  be c l o s e d .  Then  R(f ) = [N(f)]  where  f .  Fundamental E x i s t e n c e Theorem o f L i n e a r V b l t e r r a I n t e g r a l e q u a t i o n s [9] If (a)  y ( x ) = h(x) +  (b)  K(x,t)  X  K(x,t)y(t)dt  where  a  i s constant;  a  i s r e a l and c o n t i n u o u s i n the r e c t a n g l e  |K(x,t)| < M (c)  cx  h(x) t 0  K(x,t) £ 0 ;  in R ,  i s r e a l and c o n t i n u o u s i n  I:  a <_ x <_ b ;  then the e q u a t i o n (a) has one and o n l y one c o n t i n u o u s s o l u t i o n  7.  a <_ x <_ b ,  y(x) .  R e g u l a r l y Convex Sets [11]  * Definition: *  x o  B  be the c o n j u g a t e space t o a Banach space  B  *  A set X A  Let  in B  not i n X  *  , '  i s s a i d t o be r e g u l a r l y convex i f , f o r every t h e r e e x i s t s an element '  x ' ( x ) < x ( x ) - e o o o  fora l l x  x o  in B  in X  functional  such t h a t  and some  e \> 0 . -  * Theorem:  A  set X  i s r e g u l a r l y convex i f and o n l y i f i t i s convex and  * weak 8.  closed. P r o p e r t y o f Euler-Lagrarige Equations__[l_pv] rt If  a ( t ) i s continuous i n  [t^jt^]  and  2  a(t)h.(t)dt = 0  fc  f o r every interval  h  l i n the normed l i n e a r space c o n s i s t i n g o f a l l f u n c t i o n s on t h e  [t^,t2]  h(t^) = hO^) = 0  which a r e continuous and have c o n t i n u o u s d e r i v a t i v e s w i t h then  a(t) = c  in  ft^,t2]  where  c  i s a constant.  -  67 _  BIBLIOGRAPHY  1.  M. A l t m a n , "A G e n e r a l Maximum P r i n c i p l e f o r O p t i m i z a t i o n S t u d i a Mathematica, V o l . 31, No. 4,  Problems",  1968.  2.  G. Bachman and L . N a r i c i , F u n c t i o n a l A n a l y s i s , Academic P r e s s .  3.  M. S. Bazaraa and J . J . Goode, "Necessary O p t i m a l i t y C r i t e r i a i n M a t h e m a t i c a l Programming i n Normed L i n e a r Spaces! 1 , J o u r n a l of O p t i m i z a t i o n Theory and A p p l i c a t i o n s , March 1973, V o l . 1 1 , No.  4.  B. D. Craven," A G e n e r a l i z a t i o n o f Lagrange M u l t i p l i e r s " , A u s t r a l i a n M a t h e m a t i c a l S o c i e t y , V o l . 3,  5.  N. Dunford and J . T. Schwarz, I n t e r s c i e n c e , New  6.  3.  York  Linear  B u l l e t i n of  1970.  Operators:  Part I General Theory,  1958.  A. M. G e o f f r i o n , " D u a l i t y i n Non-Linear Programming:  A  Simplified  A p p l i c a t i o n s - o r i e n t e d Development", P e r s p e c t i v e s V i n O p t i m i z a t i o n , Addison-Wesley. 7.  H. H a l k i n and L . W. N e u s t a d t , " G e n e r a l Necessary C o n d i t i o n s f o r O p t i m i z a t i o n Problems", P r o c e e d i n g s of the N a t i o n a l Academy o f S c i e n c e , Vol.  8.  56, No. 4,  1966.  Kushner, "Necessary C o n d i t i o n s f o r Continuous Parameter P r o c e s s e s " , SIAM J o u r n a l o f C o n t r o l , Aug.  9. 10.  Stochastic  '72 V o l . 10, No.  W. V. L b v i t t , L i n e a r I n t e g r a l E q u a t i o n s , M c G r a w - H i l l , 1924  3. .  D. G. L u e n b e r g e r , O p t i m i z a t i o n by V e c t o r Space Methods, John W i l e y and Sons,  1969.  11.  0. L . M a n g a s a r i a n , Non-Linear Programming, McGraw-Hill  12.  L . W. N e u s t a d t , "A G e n e r a l Theory o f E x t r e m a l s " , J o u r n a l of Computer and System S c i e n c e s . V o l . 3,. No. 1,  13.  1969.  B. D. P s h e n i c h n y i , Necessary C o n d i t i o n s f o r an Extremum, M a r c e l Dekker Inc.,  14.  1969.  New  York  1971.  W.. R u d i n , P r i n c i p l e s of  Mathematical  A n a l y s i s , M c G r a w - H i l l , 1964.  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080441/manifest

Comment

Related Items