Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The sensitivity of optimal value functions in differential inclusion problems Loewen, Philip Daniel 1983

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

Item Metadata

Download

Media
UBC_1983_A6_7 L63.pdf [ 3.68MB ]
Metadata
JSON: 1.0095673.json
JSON-LD: 1.0095673+ld.json
RDF/XML (Pretty): 1.0095673.xml
RDF/JSON: 1.0095673+rdf.json
Turtle: 1.0095673+rdf-turtle.txt
N-Triples: 1.0095673+rdf-ntriples.txt
Original Record: 1.0095673 +original-record.json
Full Text
1.0095673.txt
Citation
1.0095673.ris

Full Text

T H E S E N S I T I V I T Y OF IN  OPTIMAL VALUE  DIFFERENTIAL INCLUSION  FUNCTIONS  PROBLEMS  By PHILIP B.Sc,  DANIEL  LOEWEN  The U n i v e r s i t y of A l b e r t a , 1981  A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE  in THE FACULTY OF GRADUATE STUDIES I n s t i t u t e of A p p l i e d Mathematics and S t a t i s t i c s  We accept t h i s to  t h e s i s as conforming  the r e q u i r e d  standard  F. H. C l a r k e  R. A. Restrepo  THE UNIVERSITY OF BRITISH COLUMBIA August 1983 (c)  P h i l i p D a n i e l Loewen, 1983  In  presenting  requirements  this for  thesis  an  of  British  it  freely available  agree for  that  by  for  understood  that  his  that  reference  for  or  be  her or  shall  f u l f i l m e n t of at  the  University  Library  shall  and  study.  I  copying  granted  by  the  of  publication be  allowed  of  this  It  this  without  P h i l i p Loewen  of  Mathematics  The U n i v e r s i t y o f B r i t i s h 1956 Main M a l l Vancouver, Canada  V6T  1Y3  Date  DE-6  (3/81)  10 August  1983  Columbia  thesis  of  my  is  thesis  permission.  Department  make  further  head  representatives.  not  the  the  extensive  may  copying  f i n a n c i a l gain  degree  agree  purposes  or  for  I  permission  department  partial  advanced  Columbia,  scholarly  in  my  written  ABSTRACT In many p r a c t i c a l s i t u a t i o n s , t h e parameters o f a c o n t r o l system a r e n o t known e x a c t l y .  F o r t h i s r e a s o n , much r e c e n t  literature i s  concerned w i t h the s e n s i t i v i t y o f dynamic o p t i m i z a t i o n problems to s m a l l perturbations  of t h e i r b a s i c c h a r a c t e r .  s e n s i t i v i t y of a general  differential  This t h e s i s discusses the  i n c l u s i o n problem t o p e r t u r b a t i o n s  of i t s o b j e c t i v e f u n c t i o n , dynamic c o n s t r a i n t , and endpoint Such p e r t u r b a t i o n s , d e f i n e a Value optimal  value.  gradients,  here i n t r o d u c e d  function  V(u)  by a f i n i t e - d i m e n s i o n a l v e c t o r  by i n d u c i n g  V .  A f t e r Chapter I reviews the c a l c u l u s o f g e n e r a l i z e d  Chapter I I p r o v i d e s  a f o r m u l a f o r a c e r t a i n q u a n t i t a t i v e index the generalized  The b a s i c approach i s t h a t used by C l a r k e  Nonsmooth Analysis The  (New York:  Wiley-Interscience,  i n Optimization  s p e c i a l case.  Chapter I I I extends t h e s e n s i t i v i t y  and  i n the analysis  of Chapter I I to t r e a t f r e e time problems, i n which t h e p l a n n i n g i s a f u r t h e r choice v a r i a b l e .  gradient  1983)., Theorem 3.4.3.  r e s u l t s p r e s e n t e d i n Chapter I I compare w e l l w i t h C l a r k e ' s  appropriate  u ,  changes i n t h e problem's  of t h e problem's s e n s i t i v i t y t o changes i n u : of  conditions.  period  A b r i e f d i s c u s s i o n o f c o n t r o l l a b i l i t y and  an example from mathematical economics c o n s t i t u t e Chapter IV.  F. H.  (ii)  Clarke  CONTENTS  Abstract  i i  L i s t of Figures  v  Acknowledgement  vi  Chapter I  Generalized Gradients  1  1  S e n s i t i v i t y and S t a b i l i t y  1  2  Perpendiculars  3  3  Normal and Tangent Cones  6  4  Generalized Gradients  7  5  A n a l y t i c Formulation  8  6  The L i p s c h i t z Case  11  7  Examples  13  Chapter I I  Sensitivity  o f t h e D i f f e r e n t i a l I n c l u s i o n Problem  17  1  M u l t i f u n c t i o n s , Tubes, and T r a j e c t o r i e s  17  2  The D i f f e r e n t i a l I n c l u s i o n Problem  21  3  Perturbations  25  4  Sensitivity Analysis  28  5  Application:  38  A c c u r a t e Dynamics  Chapter I I I The F r e e Time Problem  46  1  Formulation  46  2  Multiplier  3  Sensitivity Analysis  50  4  Application:  53  5  Endpoint  Rules  f o r P(0)  47  The Minimum Time Problem  P e r t u r b a t i o n s and Normal Cones  (iii)  55  Chapter IV  Applications  62  1  Controllability  62  2  Example:  65  A One-sector Economy  Bibliography  70  Appendix:  71  An A p p l i c a t i o n of Gronwall's I n e q u a l i t y  (iv)  LIST  Typical sets  C  The graph o f  T .  f o r which  OF  FIGURES  i n t T (x) = 0  (v)  ACKNOWLEDGEMENTS  I t g i v e s me g r e a t p l e a s u r e t o thank Frank C l a r k e f o r s u p e r v i s i n g the work which grew i n t o  this thesis.  coupled w i t h h i s unshakeable  H i s w i l l i n g investment o f time,  optimism, m o t i v a t e d me t o make t h e most o f  h i s many apt s u g g e s t i o n s and i n c i s i v e comments. George, Helga, and Laura Loewen, and e s p e c i a l l y s u s t a i n e d me i n t h i s e f f o r t .  The l o v e and p r a y e r s o f o f Kimberley Loewen,  F i n a l l y , I must thank Rodrigo  and Frank C l a r k e f o r r e a d i n g t h e f i n a l  (vi)  manuscript.  Restrepo  CHAPTER GENERALIZED  1  SENSITIVITY  AND  I  GRADIENTS  STABILITY  The a n c i e n t Chinese Book of Changes ( [ 4 ] , Appendix  I I , Hexagram 42)  asserts that The s u p e r i o r man, when he sees what i s good, moves toward i t ; and when he sees h i s e r r o r s , he t u r n s from them. S i m i l a r remarks adorn the opening pages o f almost every modern textbook o f optimization.  Though i t may sound t r i t e ,  the t r u t h cannot be a v o i d e d :  i n s t i n c t i v e l y seeks t h a t which i s the b e s t .  A f t e r unanimously  t h a t t h i s Innate c r a v i n g — n o t merely f o r e x c e l l e n c e , b u t f o r  man  affirming pevfection—  i s honourable, the textbooks d i f f u s e i n t o v a r i o u s areas o f a p p l i c a t i o n t o indulge i t .  Each t e x t , however, r e g a r d l e s s o f i t s area o f a p p l i c a t i o n , must  u l t i m a t e l y concede t h i s p o i n t :  once a p r a c t i c a l problem of o p t i m i z a t i o n  has been s e t up, i t s s o l u t i o n a l o n e has l i t t l e use. Granted, n u m e r i c a l p r e d i c t i o n s o f u l t i m a t e p r o d u c t i v e c a p a c i t y and i t s attendant healthy p r o f i t s  ( f o r example) l o o k wonderful on paper.  r e s u l t s a r e w o r t h l e s s u n l e s s they a r e accurate.  But such  Many f a c t o r s a f f e c t the  r e l i a b i l i t y o f n u m e r i c a l " s o l u t i o n s , " even i f computational e r r o r s a r e ignored.  At the v e r y o u t s e t , the equations e x p r e s s i n g a mathematical  problem o f o p t i m i z a t i o n i n e v i t a b l y o v e r s i m p l i f y t h e p h y s i c a l under study.  situation  And once these e q u a t i o n s a r e s e t down, t h e i r parameters must be  - 1 -  2. evaluated.  Error and uncertainty  formulation  even further.  whose formulation ask,  i n t h i s process skew the mathematical  Given a purportedly  p r a c t i c a l optimization problem  and data are necessarily imprecise,  we are compelled to  "If the model and i t s measured data are 'close' to the r e a l s i t u a t i o n  and the correct data, w i l l i t s results necessarily be solution?"  This i s a question of s t a b i l i t y .  true  To answer i t , we might well  seek a numerical index of the problem's sensitivity basic character.  'close' to the  to small changes i n i t s  If a problem i s extremely sensitive to measurement errors,  for example, i t i s r e l a t i v e l y unstable, and any " r e s u l t s " should be approached warily. Quantitative predictions of a problem's s e n s i t i v i t y are a v i t a l adjunct to i t s actual solution.  They help direct an investigator's never-ending  struggle against parameter errors by showing where precise measurements are most c r u c i a l .  They can also be used for gain:  the careful manager can apply  a detailed s e n s i t i v i t y analysis to select the small changes i n his control parameters which w i l l pay the largest dividends.  This application i s w e l l -  known i n l i n e a r programming problems where, according to J o e l Franklin [ 3 ] , i t explains  "why  the dual vector i s cherished by o i l company v i c e  presidents  and not just by mathematicians." This thesis provides a quantitative s e n s i t i v i t y analysis for a s p e c i f i c sort of dynamic optimization problem. problem  seeks to find an absolutely continuous function  s a t i s f i e s the end conditions x(t) e F ( t , x ( t ) ) f(x(a),x(b)). point  The conventional differential  [t,x]  (for  (Here  t F  in  [x(a),x(b)]  e S  x:[a,b]  R  n  function  mapping which carries each  into a nonempty compact convex subset of  R .) n  Under reasonable  hypotheses, t h i s problem has a solution, and we c a l l the minimum cost Now  which  and the dynamic constraint  [a,b] ) while minimizing the cost  i s a multifunction—a  inclusion  i f the nature of the problem i s perturbed s l i g h t l y , say by a small  V(0)  .  3.  vector  u  in  R  , then the s o l u t i o n and  These changes d e f i n e the value V(u) The  function  the minimum c o s t w i l l V:R  W {+ }  m  [a,b],  s o l u t i o n of the unperturbed problem i s a s s o c i a t e d w i t h  the problem's s e n s i t i v i t y  i s measured by  f o r which Theorem II.4.1 p r o v i d e s  a  VV(0)  it  almost never e x i s t s .  it  i s , there  b a r r i e r , we  i s no  In f a c t , V might not  guarantee t h a t i t must be  f o l l o w a path marked out by  a generalised  gradient  which d e s c r i b e s  nondifferentiable functions. the g e n e r a l i z e d g r a d i e n t  of  Chapter I reviews C l a r k e ' s  III.  from Chapter I I of  2  the v a l u e  I t i s the l a t t e r  W(0) even be  at  theory  ;  quantity  c o n t i n u o u s — e v e n when  Clarke.  To  get p a s t  H i s work ( [ 1 ] )  this  defines  the d i f f e r e n t i a l p r o p e r t i e s of  Theorem II.4.1 a c t u a l l y p r o v i d e s V  V(0)  a r i s e s immediately:  differentiable.  F. H.  0 , not  for  VV(0)  .  The  of g e n e r a l i z e d g r a d i e n t s  which emphasizes t h e i r geometric a s p e c t s Chapters I I and  .  [x(a),x(b),u]eS}.  formula.  A s e r i o u s o b s t a c l e to the c a l c u l a t i o n of  and  remainder of  i n a sequence  thereby s e t s up  A l l of the r e s u l t s r e p o r t e d  a formula f o r  the new  i n s e c t i o n s 2-6  work i n  are  taken  [1].  PERPENDICULARS  2.1  Convex S u b g r a d i e n t s  theory  D i f f e r e n t i a l c a l c u l u s — t h a t elegant  of l o c a l a n a l y s i s so f a m i l i a r  differentiable) setting—has  n  -> RJ {+<*>} .  the p o i n t 3f(x)  x  :=  {?eR  n  at  complete  to a f a m i l y of  functions  T h i s f a m i l y i s the s e t of convex f u n c t i o n s  I f such a f u n c t i o n i s f i n i t e and  , i t s subgradient  and  i n the smooth ( i . e . c o n t i n u o u s l y  a well-known e x t e n s i o n  which need not be d i f f e r e n t i a b l e . f:R  by  00  := i n f { f ( x ( a ) , x ( b ) , u ) : x ( t ) e F ( t , x ( t ) , u ) on  change t o o .  x  i s the  : <£,y-x> < f ( y ) - f ( x )  lower semicontinuous at  set for a l l  y  in  R  n  }.  4.  If  f  happens t o be d i f f e r e n t i a b l e a t  singleton f  {Vf(x)} ; c o n v e r s e l y ,  i s d i f f e r e n t i a b l e at  x  if  and  9f(x) reduces t o the  x , the s e t  3f(x)  i s the s i n g l e t o n  V f ( x ) = X, .  {?} , then  The s u b g r a d i e n t  clearly  gener-  a l i z e s the o r d i n a r y n o t i o n o f d i f f e r e n t i a t i o n t o t h e f a m i l y o f convex ... functions.  I t a l s o obeys s u i t a b l e analogs o f the d i f f e r e n t i a t i o n r u l e s so  familiar i n ordinary calculus:  t h i s f e a t u r e confirms  the s u b g r a d i e n t  as a  u s e f u l and a p p r o p r i a t e g e n e r a l i z a t i o n . To a p p r e c i a t e the g e o m e t r i c a l that a vector in  C  v  i s normal  i f <v,c-x> < 0  t o a g i v e n c l o s e d convex s e t  fora l l  c  in  C .  C .  (Alternatively,  passes through normal t o  C  x x  n  Now f o r any f u n c t i o n of p o i n t s i n R xR n  that  f  f  C .)  : <v,c-x> < 0 f :R  fora l l  t o some o t h e r  e p  .  f  f  in  N  of f  i s the s e t  i s c l o s e d , and  i s a convex s e t . that  [ y , r ] e e p i f }.  . . ( x , f ( x ) ) i f and o n l y i f epi f <£,y-x> < r - f ( x ) f o r a l l y i n R and r > f ( y ) . J  n  That i s , 3f(x)  = U  at  C }.  ( x , f ( x ) ) = {[?,-g] : < [ ? , - g ] , [ y , r ] - [ x , f ( x ) ] > <.0  lies in  C  f :  s t u d i e d here, we f i n d  for [C,-T]  point  t o a hyperplane which  i s lower semicontinuous i f and o n l y i f e p i f  i s a convex f u n c t i o n i f and o n l y i f e p i f  N  has a n o n p o s i t i v e  : r > f(x) } .  For the convex f u n c t i o n  Hence  c  ->- Ru {+<*>} , t h e epigraph  n  x  The c o l l e c t i o n o f v e c t o r s  l y i n g on o r above t h e graph o f  e p i f := { [ x , r ] Note t h a t  the s e t  x  recall  a t the p o i n t  forms a c l o s e d convex cone, t h e normal aone to  := {veR  c  i s a vector perpendicular  and supports  at  N (x)  v  C  That i s , i f v  p r o j e c t i o n onto every v e c t o r drawn from t h e base p o i n t in  9f(x) , we  s i g n i f i c a n c e of t h e s e t  : U,-l] € N  e p  .  f  (x,f(x)) } :  x:  5.  the s u b g r a d i e n t to  epi f .  known:  c o n s i s t s of the f i r s t  components of c e r t a i n v e c t o r s normal  In the smooth o n e - v a r i a b l e case, the analogous p r o p e r t y i s w e l l -  the v e c t o r  at the p o i n t The  n  [f'(x),-l]  i s p e r p e n d i c u l a r to the graph of  y - f(x)  [x,f(x)] .  f o r e g o i n g geometric  o b s e r v a t i o n s h i n t t h a t a s t i l l more g e n e r a l  c l a s s of e x t e n d e d - r e a l - v a l u e d  f u n c t i o n s would permit  d i f f e r e n t i a l analysis  i f o n l y the a p p r o p r i a t e g e n e r a l i z a t i o n of the convex a n a l y s t s ' normal cone c o u l d be found.  I t i s admittedly  difficult  to induce a u n i v e r s a l concept  of "normal v e c t o r " from the s u p e r f i c i a l d i s c u s s i o n p r e s e n t e d can i n v e s t i g a t e a simple r e l a t e d concept  here, but  which w i l l a i d the e f f o r t .  A  we study  of p e r p e n d i c u l a r s c o n s t i t u t e s the remainder of s e c t i o n 2.  2.2  Euclidean Distance  Euclidean  distance d^(x)  Given any nonempty c l o s e d s e t  function  corresponding  := min{|x-c| :  to  C  C  in  any  R  at one x  in  or more p o i n t s i n  onto  C .  - d (y)  c  R  n  The v e c t o r  Let  v  in  R  | x - y  vxC  counterpart: C  at x  .  .  For  i s evidently attained  x, y  in  R  n  we  | .  be a p o i n t l y i n g i n a g i v e n c l o s e d subset  n  is  •perpendicular x + v  onto  to  C C .  at x  i n a s i n g l e p o i n t , namely  x  .  |v|  and  C  i f the p o i n t  of x  When t h i s r e l a t i o n h o l d s ,  T h i s a n a l y t i c a l d e f i n i t i o n has a simple  the c l o s e d b a l l of r a d i u s  of  have  x  p r o v i d e s the unique p r o j e c t i o n of we w r i t e  d (x)  v  Every such p o i n t i s c a l l e d a projection  | <  c  Perpendiculars .  C .  Note t h a t f o r any p o i n t s  | d (x)  2.3  , the minimum d e f i n i n g  n  , the  c e C } .  |v| denotes the E u c l i d e a n norm of the v e c t o r  x  n  i s d e f i n e d as f o l l o w s :  Here, of c o u r s e , given  R  centre  x+v  geometrical meets the s e t  Thus t h i s d e f i n i t i o n reduces to the u s u a l  6.  one  if  C  convex.  i s a h y p e r p l a n e , and hence The  N  (x) = {v  : v l C at x }  geometric d e f i n i t i o n of p e r p e n d i c u l a r i t y has  when  C  is  the form of a  s e p a r a t i o n p r i n c i p l e ; as such, i t i m p l i e s a c e r t a i n i n e q u a l i t y which w i l l prove u s e f u l i n Chapter I I .  2.4  Proposition  Let  C  be a nonempty closed  .^Ic-x]  then  <v,c-x>  ^  PROOF  By d e f i n i t i o n ,  for  2  all  |(x+v) - x| <  c  in  subset  of  R  .  n  If  vlC at x j  C .  |(x+v)-c|  for a l l  c  In  C .  In  terms of the i n n e r product, t h i s i n e q u a l i t y reads <v,v>  <  <x+v-c,x+v-c>  =  <v,v> - 2<v,c-x> +<c-x,c-x> .  Rearranging t h i s statement y i e l d s the d e s i r e d c o n c l u s i o n .  3  3.11  NORMAL AND  Normal Cones  x , we  may  r  first  limit i 1.  CONES  For any nonempty c l o s e d s e t  d e f i n e the s e t  {  The  TANGENT  i  V  [ [  r  N  (x)  n  v.—K)  :  ±  C  „ , v . l C at x,  ±  1  -j , x.—>x } u  by computing l i m i t s of n o r m a l i z e d  must converge to the g i v e n p o i n t  need not be  1  may  containing a point  n  r rt i {0}  convex.  Together w i t h  t h e i r corresponding x  .  N  (x)  coincides with  t h e r e f o r e use  a r b i t r a r y closed set. o n l y t h a t the s e t  C  The  can  perpen-  base p o i n t s  x^  in  I t i s e v i d e n t l y a c l o s e d s e t , but  the o r i g i n , i t generates a c l o s e d convex We  are not  disappointed:  the u s u a l cone of normals when  C  i s convex.  the c o n s t r u c t i o n above to d e f i n e the normal (Indeed, the m a n i f e s t l y l o c a l n a t u r e of be  by  .  perpendiculars.  cone whose n o t a t i o n i s d e l i b e r a t e l y s u g g e s t i v e .  We  R  to be the c l o s e d convex cone generated  d i c u l a r s must d i m i n i s h i n l e n g t h , and  the s e t  in  s e t i n t h i s u n i o n i s the c o l l e c t i o n of a l l u n i t v e c t o r s which  be o b t a i n e d  C  •  l o c a l l y c l o s e d near  x .)  confirm that t h i s g e n e r a l i z a t i o n i s appropriate  The  cone to N  (x)  an  requires  r e s u l t s of s e c t i o n 4  and u s e f u l .  7.  3.2  Tangent Cones  i s simply  The tangent  cone t o an a r b i t r a r y nonempty c l o s e d s e t C  the c l o s e d convex cone p o l a r t o t h e normal cone: T (x) := {w : <W,v> < 0  fora l l  v  i n N (x) } .  I t has the f o l l o w i n g i n t r i n s i c c h a r a c t e r i z a t i o n .  3.3  Proposition  A vector  i f i t satisfies converging there all  4  4.1  w  the following  to  x  and every  is a sequence  {w^}  in  R  is tangent  n  criterion.  For every  sequence  {t^} ^  converging  to  w  n  C  x  sequence  (OJ ) 00  such  at  i f and only {x^}  decreasing  in  to  zero,  x^ + t^w^ e C  that  C  for  i .  GENERALIZED  Definition  GRADIENTS  L e t an e x t e n d e d - r e a l - v a l u e d f u n c t i o n  We suppose throughout s e c t i o n 4 t h a t and  to  that  gradient  epi f of  f  x  3f(x)  x  := {  [x,f(x)] .  C  :  e N  i s convex and lower semicontinuous.  ^epi f ( ' ^ ( ) ) x  x  Then t h e  :f i s f i n i t e ,  f  R  If  x  to d e f i n e t h e asymptotic  generalized  of s e c t i o n 2 when  f  happens t o l i e on the boundary  t h e second component o f every v e c t o r i n  generalized  gradient  T h i s p o s s i b i l i t y f o r c e s us of  f  at  CO := {5 : [?,0] € N  e p i  f  (x,f(x)) } .  I t i s always a c l o s e d convex cone c o n t a i n i n g  the o r i g i n .  x :  n  is finite,  (x,f(x)) } .  need n o t be s t r i c t l y n e g a t i v e .  8 f(x)  f  on  i s t h e ( c l o s e d convex) s e t  Note t h a t t h i s d e f i n i t i o n reduces t o t h e subgradient  of t h e s e t where  be d e f i n e d  i s a p o i n t a t which  i s l o c a l l y c l o s e d near at  f  .  8.  4.2  Recession  Cones  The  r e c e s s i o n cone of convex a n a l y s i s i s the key  to  00 the r e l a t i o n s h i p between  9f(x)  nonempty c l o s e d convex s e t which  K + C  C  remains a subset  However, the e x p r e s s i o n K = fi.c, i i : i-x»  and  9 f(x) .  in  R  of  C..  SAO x  i s more u s e f u l i n c a l c u l a t i o n .  cone of a  i s the l a r g e s t convex cone  n  ,  The recession  I t may c,eC i  be  g i v e n by  K  K = {v  given  for  : v+C  c  C}.  }  It f a c i l i t a t e s  the proof of the f o l l o w i n g  results.  CO 4.3  Proposition  If  9f(x)*0 , then  4.4  Proposition  The  set  3f(x)*0  9f(x) u  9 f(x)  is  (9°°f(x)\{0})  the  recession  is not  cone of  empty.  9f(x).  Moreover,  if  then  CO N  5  ANALYTIC  Any  . (x,f(x)) = f  (9 f ( x ) x { 0 } ) u  FORMULATION  student  of c o n v e n t i o n a l  c a l c u l u s would r i g h t l y b a l k a t the  of computing the d e r i v a t i v e of a f u n c t i o n which makes the v e c t o r  [?,-l]  opment of s e c t i o n s 2-4. a n a l y s i s i s elegant The  and  f  perpendicular  i t a t i o n i s q u i t e u n d e r s t a n d a b l e , and  calculus.  u r(9f(x)x{-l}) . f >0  by  l o o k i n g f o r a number  to the graph of  Although the geometric approach to i n s t r u c t i v e , i t cannot r e p l a c e a  functions.  The  t,  H i s hesdevel-  differential  well-developed  need to t r a n s l a t e the p i c t o r i a l concepts of the  replaces sets with  f .  i t p o i n t s out a weakness i n the  e x p o s i t i o n i n t o u s e a b l e formulas m o t i v a t e s s e c t i o n 5« transformation  prospect  foregoing  first  step of  the  9.  5.1  "Support F u n c t i o n s  its  support  function,  Any  c l o s e d convex s e t  C  R  in  i s characterized  n  by  namely  o" (p) := sup{<p,v> : v e C } . c  The  support f u n c t i o n takes v a l u e s  f i n i t e - v a l u e d i f and C = {v  5.2  only i f  to d e f i n e the directional v  for a l l  For any  derivative  l » > x  v  t + 0  exist.  But  if  f  e x i s t s (somewhere i n f 1  nonempty. R  in  n  }  Clearly,  .  f :R—->-Ru { °}  function  , one  +o  n  at a point  x  It i s  where  may  attempt  f(x)<°°^ i n d i r e c -  of  v  f o r which t h i s l i m i t  i s a lower semicontinuous convex f u n c t i o n , the [-°°,+ ] ) f o r e v e r y  v  00  , / . , x _ i n f f(x+tv) ^ ' " t>0 t Y  X  f , x, and  R  in  , and  n  i s given  does  limit  by  f(x)  v ;  c a l c u l u s of convex s u b g r a d i e n t s i s based on the f o l l o w i n g remarkable  f ' ( x ; * ) is  the  support  3 f ( x ) = {? Moreover, the f u n c t i o n be)  p  C*0  t  Of c o u r s e , t h e r e are many c h o i c e s  The  , provided  as r  not  {*<»}  i s bounded and  : <p,v> ^ a (p)  Directional Derivatives  tion  C  R u  in  and  of  the  set  : <?,v> < f ' ( x ; v ) f'(x;«)  8f(x)  T  £ ( > f ( x ) ) , and x  e  p  i  a spectacular  .  i s sublinear  8f(x)  and  in  (as any T  R  n  }  .  support f u n c t i o n must  , ,.(x,f(x)) . epi r  l i n k between the s e t  the s e t  That i s ,  for a l l v  i t s e p i g r a p h i s the c l o s e d convex cone  epigraph forges polar  function  N  Thus  ^ ^(x,f(x))  i t s support f u n c t i o n  the  and i t s f'(x;*).  I t i s u l t i m a t e l y t h i s support f u n c t i o n , the d i r e c t i o n a l d e r i v a t i v e , which y i e l d s the many r e s u l t s of the s u b g r a d i e n t  calculus.  fact:  10.  5.3 and  Generalized  Directional Derivatives  setting.  which i s f i n i t e a t  x  N  to be  N  and  i n s i g h t of the  3f(x)  invaluable.  p r i a t e l y , and  convex case.  And  .  An  -»• R u  f :R  n  -* R u  f °(x; •) :R  n  I t would g e n e r a l i z e  discovered  /  . x V  (Here, and  {±~},  X  ;  V  J  [x,f(x)] .  if  T  . ,.(x,f(x)) epi r  does  If  the  d i r e c t i o n a l d e r i v a t i v e appro-  need to b u i l d a complete c a l c u l u s .  f u n c t i o n whose e p i g r a p h i s  l i m sup inf y- -»• x wev+eB a -> f ( x ) a > f(y) t + 0 B  His T e p  £  f(x,f(x))  f(y+tw) - a t  denotes the open u n i t b a l l of the  3f(x)*0 , t h i s d e f i n i t i o n y i e l d s the  9f(x) = {<; : <5,-v> < f°(x;v)  for a l l  f°(x;v) = sup{<?,v> : ? e 3f(x) difficult  turn  by  throughout t h i s t h e s i s ,  i n question.)  the  such an independent d e f i n i t i o n .  defined  limit £+0  :  {*o°}  independent d e f i n i t i o n of t h i s f u n c t i o n  thereby p r o v i d e the t o o l we  T. R o c k a f e l l a r has  f 0  The  a function  . ,.(x,f(x)) and T . ,.(x,f(x)) , and epi r epi r 3f(x) have been e s t a b l i s h e d a l r e a d y . They  r e s u l t , p r e s e n t e d i n [ 1 ] , i s t h a t the is  geometric  the e p i g r a p h of some f u n c t i o n , then t h i s f u n c t i o n must be  support f u n c t i o n of would be  consider  and whose e p i g r a p h i s l o c a l l y c l o s e d near  ^ ^(x,f(x))  c a r r y a l l the  R.  Once a g a i n , we  correspondences between  between  out  p e r f e c t u n i t y of the  a n a l y t i c a s p e c t s of the s u b g r a d i e n t c a l c u l u s encourages s i m i l a r r e a s o n i n g  i n the g e n e r a l  The  The  v  in  space  formulas R  }  n  } .  t a s k of d e r i v i n g a complete s e t of d i f f e r e n t i a t i o n r u l e s i s not  y e t complete, but  i t now  has  i s d i r e c t e d to s e c t i o n 2.9  of  a solid  conceptual substructure.  [1] f o r an account of r e c e n t  The  reader  developments.  11.  6  THE  LIPSCHITZ  The  CASE  d i f f e r e n t i a l a n a l y s i s of nonsmooth f u n c t i o n s  s e v e r a l important s p e c i a l c a s e s . ized gradient instance. function  f :  c o i n c i d e s w i t h the convex subgradient  9f(x) = {Vf(x)} .  Let  |f(x) - f ( y ) | < k|x holds for a l l f  x, y  i s Lipschitz  valued  gradient  R  n  has  general-  appropriate  f o r any  smooth functions  a l l convex f u n c t i o n s .  be  f i n i t e at  x^  .  I f the i n e q u a l i t y  - y|  i n some f i x e d neighbourhood of  (of rank  and u n i f o r m l y  f:R  i n the  S e c t i o n 6 d e a l s w i t h a c l a s s of  a l l smooth f u n c t i o n s and  L i p s c h i t z Functions  above  have a l r e a d y observed t h a t the  I t a l s o reduces to the c o n v e n t i o n a l  which c o n t a i n s  6.1  We  introduced  k ) near  x^  .  XQ  , then the  In p a r t i c u l a r ,  continuous on a neighbourhood of  x^  function  f  is finite-  .  I t can be shown  t h a t i f a convex f u n c t i o n i s f i n i t e on an open s e t , then i t i s L i p s c h i t z near each p o i n t of t h a t s e t .  The  c o r r e s p o n d i n g statement f o r smooth f u n c t i o n s  f o l l o w s immediately from the mean-value theorem. The  f o l l o w i n g p r o p o s i t i o n shows t h a t the asymptotic g e n e r a l i z e d  gradient  of a L i p s c h i t z f u n c t i o n i s t r i v i a l .  6.2 epi  Proposition f  is locally  Suppose that closed near  f:R  n  + Eu  [x,f(x)] .  {+°°}  is finite  Then conditions  at  x , and  that  (a)^Cc) are  equivalent. Ca)  is Lipschitz  near  x .  Cb)  9f (x)  is nonempty and bounded.  Cc)  d f(x)  = {0}  m  .  For the remainder of S e c t i o n 6, we i s L i p s c h i t z near  x  .  assume t h a t the f u n c t i o n  f :R  n  -> R  Rademacher's c l a s s i c a l theorem a s s e r t s t h a t a  L i p s c h i t z f u n c t i o n i s d i f f e r e n t i a b l e almost everywhere.  According  to  the  f o l l o w i n g r e s u l t , t h i s a l l o w s us t o compute the g e n e r a l i z e d g r a d i e n t o f by  taking l i m i t s of ordinary  6.3  Theorem  those points  Let  f  gradients.  S be any set of measure of x  in some neighbourhood  zero in R  where  f  which includes  n  is not  all  differentiable.  Then 9f (x) = c o { The  in  6.5  ^  t  Vf(x.)  :  x. + x , x. I S } .  g e n e r a l i z e d g r a d i e n t o f a L i p s c h i t z f u n c t i o n has the f o l l o w i n g  important c l o s u r e  6.4  1  Proposition  afCx^)  property.  {x^}  If the sequence  for each  i while  Directional Derivatives  converges  f  x  3  and i f  r,  i s L i p s c h i t z , the g e n e r a l i z e d  d i r e c t i o n a l d e r i v a t i v e o f item 5.3 assumes the f o l l o w i n g s i m p l i f i e d f  of . ) x  v  =  l  l  lies  £ e 9f(x) .  -> t, , then  When  to  form:  P f(y+tv) - f ( y ) y -> x t t \ 0 m  S U  This d i f f e r e n c e quotient  l o o k s v e r y much l i k e t h a t d e f i n i n g the c o n v e n t i o n a l  directional derivative:  the o n l y changes a r e t h a t the base p o i n t  near  x  and " l i m sup" r e p l a c e s  The  which c o o p e r a t e w i t h  f°(x;-)  i n t h e L i p s c h i t z case c u t s  a g e n e r a l i z e d c a l c u l u s down t o a manageable s i z e ,  a l t h o u g h the t a s k remains f o r m i d a b l e . the sums, p r o d u c t s ,  F. H. C l a r k e  [1] p r e s e n t s  rules f o r  q u o t i e n t s , and c o m p o s i t i o n s o f L i p s c h i t z f u n c t i o n s Theorem 6.3 t o put t h e g e n e r a l i z e d g r a d i e n t s o f a great  many L i p s c h i t z f u n c t i o n s w i t h i n easy r e a c h .  Two o f h i s r e s u l t s appear below:  the f i r s t has a f a m i l i a r c l a s s i c a l c o u n t e r p a r t ;  the Second i n v o l v e s a method  of combining f u n c t i o n s which cannot be t r e a t e d w i t h We l e t  varies  "limit."  substantial s i m p l i f i c a t i o n of  the j o b o f d e v e l o p i n g  y  f ^ , f2> ... ., f k : R  n  R  classical  be f u n c t i o n s L i p s c h i t z near  techniques. x .  13.  6.6  Proposition  (a)  For  any  a(c f +c f )(x) 1  Equality  holds  (b)  1  2  if  6.7  P r o p o s i t i o n The  1  pointwise  f ( x ' ) := m a x C f ^ x ' ) is Lipschitz  near  x  3f.(x) where  c  + c 3f. (x) 2  2  2  2  maximum  .  1  function  : i=l,2,...,k  }  co{3f (x) i  : i e I(x) } ,  f  is  is  the  set  of indices  at  which  attained.  g i v e n nonempty c l o s e d subset  ^QC")  .  and  the maximum defining  function  '  x .  I ( x ) := a r g max{f^(x) : 1=1,2,...,k }  For any  3  f (x)3f (x) + f (x)3f (x)  c  2  and  Cj^B^Cx)  is smooth at  9(f f )(x) 1  c  2  scalars  d e f i n e d i n item 2.2  C  of  R  , the E u c l i d e a n  n  distance  i s everywhere L i p s c h i t z of rank 1.  can compute i t s g e n e r a l i z e d g r a d i e n t by a p p l y i n g Theorem 6.3  We  to the f o l l o w i n g  lemma.  6.8  Lemma  unique  6.9  If  projection  y  Proposition  Let  of the  exists in  x  and  C , and  l i e in  is nonzero  then the point  s  Vd-,(x) = C C .  Then  x  has  a  ^ ~ .i . |y - x| x  3d (x)  equals  the  convex  hull  set limit .  { r  Corollary  ^ i r ••• I  :  Iv^l  N (x) = ~u r>0 L  7  Vd^(x)  r3d  _ v.-K) l  (x) .  , v . i C at x. i l (See  item  , x.-*x I  3.1.)  ,  }  u  • r«i {0}  .  .  C  EXAMPLES  The  two  examples c o m p r i s i n g  s e c t i o n 7 i l l u s t r a t e the concepts of  review above, and w i l l l a t e r be u s e f u l . i e n t s of E u c l i d e a n d i s t a n c e f u n c t i o n s .  Both i n v o l v e the g e n e r a l i z e d  the grad-  14.  7.1  C a r t e s i a n Products  and  R  n  containing  Let  C^  the p o i n t s  and  x^  tangent cone i n P r o p o s i t i o n 3.3  V c / V V By  =  x^  readily  e < o x  )  be nonempty c l o s e d subsets of .  The  implies  V* "  x  c h a r a c t e r i z a t i o n of  II.2.4 we 3 d  c * 0  C l  =  m  the  that  '  1  N  C  at  XQ  )  X  N  C  •  and  c  3 d  c  ( j K 0  let  v l C^ at x^  o  >  <  ^e/V  x  of P r o p o s i t i o n  [x,y]  n  .  For i f x'  |(x+u) - x|  [x,y] +  u  C^  according  rr { [ U  to  f o r which  t h a t the p o i n t  [u,v]  [x',y]  in  than does the l a t t e r ' s  t o P r o p o s i t i o n 6.9,  3d  the  i >  V ]  =  (x ,x ) n  o  X  L  i  C^xc^  given  1  set  limit i 1 i~> Uu^v^l  ,  r :  [  i ' i  u  V  *  ]  1  For any v e c t o r  [u,v]  i s the convex h u l l  n  u  [  °'°  mm » ]  [u ,v ] i C xC  .  must have  [x,y]..  of the o r i g i n and  1  Then we  .  c  (x )  .  f a i l e d to be p e r p e n d i c u l a r  in  T h i s would imply the absurd c o n c l u s i o n l i e s n e a r e r to the p o i n t  6.9.  [u,v] l C x C ^ at  , t h e r e would be a p o i n t 1  Now  •  )  <V*i>  |(x+u) - x |  projection  1  ( X 1  statement, namely t h a t  can prove t h i s w i t h the h e l p  u l CQ at XQ  0  ( X 0  require a s l i g h t l y stronger  To b e g i n the p r o o f ,  3d  R  polarity,  In item  CQ  and  0  ^ c / V V  We  T  C^  i n this set,  L e t us prove t h i s f o r  u  u —we  ±  Q  lies in  may  3d  assume  at  1  (x ) n  u*0  [x^y^ and  .  v  Then  1 i s a sequence of v e c t o r s which obey  [x ,x ]} Q  1  lies in  {u.}  1 u^ X CQ at x^ ->• x^  and whose  lengths  converge t o z e r o .  u./|u.|  limit i-x»  converges t o an element o f  u./|u.| 1  (0,1]  So a l o n g some subsequence, which we do not r e l a b e l ,  ,  1  need n o t e q u a l  u = r limit i-x»  3d  u .  of  in  (x.) i s a convex s e t c o n t a i n i n g  u e 3d_ ( x ) . n  u  Q  Upon a p p l y i n g a s i m i l a r  3d  (x.-.)  3d  x  (x ) .  The l a t t e r i s a convex s e t c o n t a i n i n g 0, so  1  C  8 d  C  ( x ( )  0  )  *\<*1>  X  required.  7.2  A Diagonal  define R xR n  3d  r  v , we f i n d t h a t the s e t o f u n i t v e c t o r s d e f i n e d above i s a  ^ x c / V V as  the v e c t o r  0  C  subset  Of course,  n  But we can be sure t h a t , f o r some  u,/|u | ., S i n c e  the o r i g i n , we conclude t h a t  argument t o  (x ) .  Set  L e t a nonempty c l o s e d subset  G := D + Cx{0} , where .  n  The s e t G  C  of  D := {[u,u] : u e R } n  may a l s o be w r i t t e n  R  be g i v e n , and  n  i s the d i a g o n a l of  G = {[y,x] : y e C + x} — t h i s  shows t h a t i t may be i n t e r p r e t e d as the "graph" o f the s e t - v a l u e d mapping x  C + x , which a r i s e s n a t u r a l l y i n Chapter I I .  3dg(c+u,u) 3d G (c,0)  f o r some  , s i n c e t r a n s l a t i o n by  Observe t h a t i f ment were f a l s e , product  c i n C, u i n R  n  .  This s e t i s c l e a r l y i d e n t i c a l to  [u,u] does n o t a f f e c t t h e l o c a l n a t u r e  [u,v] i G a t [x,y] , then v = -u .  t h e r e would be a v e c t o r  <[u,v],[a,a]>  positive.  For  a  in  Whenever  t  {|[u,v]|  2  R  n  o f G.  For i f t h i s s t a t e -  which makes the i n n e r  t>0 , c o n s i d e r t h e d i s t a n c e  |([x,y] + [u,v]) - ( [ x , y ] + t [ a , a ] ) | =  We seek t o compute  =  |[u,v] - t [ a , a ] |  - 2t<[u,v],[a,a]> + t | [ a , a ] |  I s l e s s than the p o s i t i v e q u a n t i t y  2  2  }  %  .  2< [ u , v ] , [ a , a ] > / | [ a , a ] |  2  ,  16.  this distance  i s s t r i c t l y l e s s than  i s a point of  G  T h i s cannot be:  which i s c l o s e r t o  That i s ,  [x,y] + t [ a , a ]  [x,y] + [u,v] than i s the c l o s e s t p o i n t .  v = -u .  Note a l s o t h a t suppose not.  |[u,v]| .  [u,v] l G a t [x,y] i m p l i e s  Then some p o i n t  c in C  u X C a t x-y .  i s such t h a t  Again,  |u| > |((x-y)+u) - c| .  Consequently |[u,v]|  >  |[x-y+u-c,v]|  T h i s i n e q u a l i t y shows t h a t But  |C[x-y,0]+[u,v]) - [ c , 0 ] | .  [u,v] i s not p e r p e n d i c u l a r  t h i s too i s i m p o s s i b l e :  [u,v] x G a t [x,y] .  =  [u,v] l G a t [x-y,0]  We must have  for Then  v . = -u. i x r  some  '  u'  V]  limit  U  V  fo°r a l l l  l  =  in  l  i  m  c  G  Of c o u r s e , t h i s i m p l i e s G  t  c  ±  ±  l  {fu,-u] :  r  72  3  Applying  =  '"  [U  [u^,v^] -> [0,0] .  u e 9d (c) } . c  u e N (c)' } .  II.5.3.  -  U ]  . i  P r o p o s i t i o n 6.9, we conclude t h a t  that  We w i l l use t h i s f a c t i n item  while  J  ^"^'"-"i  {[u,-u] :  as  u. X C a t (x.-y.) -> c , so we have l i ±  - v/zluj  8d (c) .  9d (c,0)  N (c,0)  l  and  [x-y,0] .  |[« »v ]|  -1- G a t [ x ^ y ^ -*- [c,0]  i  at  i s e q u i v a l e n t to  [u,v] i s o b t a i n e d  [u^"^] /  [-L>-J^  some sequence  [U  for  =  G  u X C a t x-y .  Suppose now t h a t the v e c t o r [u,v]  to  c  CHAPTER SENSITIVITY  A differential which has  OF  II  DIFFERENTIAL  THE  inclusion  INCLUSION  i s a generalization  PROBLEM  of a d i f f e r e n t i a l  proven p a r t i c u l a r l y u s e f u l i n the study of dynamic  equation  optimization.  I t s symbolic form, x ( t ) e F ( t , x ( t ) ) a.e. i n d i c a t e s that i n the set  x(")  i s an a r c whose d e r i v a t i v e a t almost every time  i n t o which the mapping  i s an a b s o l u t e l y  can  x ( t ) e { f ( t , x ( t ) ) } a.e. constraints  are  Any  1 and  Chapter 3.  Sections  3-5  governed by  differential  POLYFUNCTIONS,  successful  Multifunctions  T  lies  (An  arc  equation  the d i f f e r e n t i a l  inclusion  study of a problem whose dynamic  set  S  subset  the  With t h i s  s e n s i t i v i t y of o p t i m i z a t i o n  [1]  problems  inclusions.  TUBES,  AND  TRAJECTORIES  Y:S  i n t o a subset of  of  R R  n  be a t t r i b u t e d to  i f the s e t C  a  2 of Chapter I I review the h i g h l i g h t s of C l a r k e  A multifunction  i s measurable  every c l o s e d  differential  i n c l u s i o n ' s general properties.  discuss  t o p o l o g i c a l p r o p e r t i e s may tion  The  [t,x(t)] .  t  f o r m u l a t e d as a d i f f e r e n t i a l i n c l u s i o n must i n c o r p o r a t e  motivation, sections  element of the  c a r r i e s the p o i n t  thus be phrased as  thorough u n d e r s t a n d i n g of the  1.1  F  continuous f u n c t i o n . )  x ( t ) = f ( t , x ( t ) ) a.e.  1  ,  R  n  {seS  - 17  .  When T .  : T(s)  .  -  i s a mapping c a r r y i n g  n  S  i s a subset of  For example, the  n C * 0 }  each R  m  ,  multifunc-  i s measurable f o r  5  1.2 if  Continuity f o r every  e>0  s e SQ + SB .  is,  ^^so^  e  Hence i f T graph  of  {s^} <= S  YQ  A  N  and  ^ SQ  {Y^}  semicontinuous  Y^  obeying  €  in S  n  i s c e r t a i n l y closed  are obtained  SQ  T ( s ) c r(.s ) + eB  such t h a t  V  at  as  at  SQ — t h a t  [SQ,YQ] = l i m [S^JY^]  r(s^)  fora l l  i .  i s upper semicontinuous everywhere, then t h e f o l l o w i n g s e t ( t h e  T ) i s closed: Gr(T)  The  6>0  In t h i s c a s e ,  whenever  f o r sequences  i s upper  t h e r e e x i s t s some  whenever YQ  r  The m u l t i f u n c t i o n  generalized  :=  { [s,y] :  gradient  y e r(s) } .  of a L i p s c h i t z function  f  i s a closed  multifunction  ( P r o p o s i t i o n 1.6.4) which, i n f a c t , c a n be shown t o be upper s e m i c o n t i n u o u s . A stronger T .  c o n t i n u i t y c o n d i t i o n may a l s o be imposed on the m u l t i f u n c t i o n  We say t h a t TCs^)  r  i s Lipschitz  C  T(s ) + k ^ - s ^ B  (of rank  k J on  fora l l  2  ( R e c a l l t h a t the c o l l e c t i o n o f c l o s e d subsets o f has  closed values,  Hausdorff m e t r i c L i p s c h i t z o f rank are g i v e n ,  1.3  s^ s R  2  in  S .  i s metrizable.  n  the c o n d i t i o n t h a t i t be L i p s c h i t z w i t h r e s p e c t  i s p r e c i s e l y that s t a t e d here.) k  on  S  i f , whenever  there e x i s t s a point  y^  in  I n other words,  s^,  in  T(.s^)  S  such t h a t  Note t h a t a ( n o n t r i v i a l ) L i p s c h i t z m u l t i f u n c t i o n valued,  S i f  T  and |  y  r  If  t o the V is i n T(s^)  —¥"2 I - ^Is-j.— 2 ^ " 3  can never be empty-  and must be upper semicontinuous and measurable.  Tubes  Our i n t e r e s t i n d i f f e r e n t i a l i n c l u s i o n s prompts us t o i n v e s t i g a t e  multifunctions  d e f i n e d on p a r t i c u l a r subsets o f  i s c a l l e d a tube { t :  RxR  n  .  The s e t SI <= RxR  (on [a,b] ) i f t h e s e t [t,x] e SI f o r some  i s an i n t e r v a l — s a y [a,b] — a n d  there  x  in R  n  }  e x i s t continuous  functions  n  w:[a,b] -* R  and  n  fi =  e: [a,b]  (0,°°)  { [t,x] :  such t h a t  t e [a,b] ,  x e w(t) + e(.t)B } .  For n o t a t i o n a l ease, we d e f i n e the p r o j e c t i o n s R in  :=  { x :  for  t  [a,b]  1.4  Special Properties  [ t , x ] e fi }  .  Two s p e c i a l p r o p e r t i e s o f a m u l t i f u n c t i o n r  prove u s e f u l i n the study o f d i f f e r e n t i a l i n c l u s i o n s ,  is  r:fi -*• R  n  measurably  L i p s c h i t z on fi i f (a)  f o r each [a,bj  (b)  x  in R  , the m u l t i f u n c t i o n  n  [a,b] , the m u l t i f u n c t i o n  on  k : [ a , b l -> [Q, )  such t h a t f o r each  00  x -»- F ( t , x )  t  i s L i p s c h i t z o f rank k ( t )  .  (To make sense o f c o n d i t i o n when [ t , x ] i Q, .)  The m u l t i f u n c t i o n an i n t e g r a b l e f u n c t i o n T ( t , x ) <= <j)(t)B  ( a ) , we adopt the c o n v e n t i o n t h a t  A measure o f t h e L i p s c h i t z c h a r a c t e r  the r e l a t e d constant  1.5  i s measurable on  , and  t h e r e i s an i n t e g r a b l e f u n c t i o n in  t -»- r ( t , x )  F  i s p r o v i d e d by  K := e x p ( / ^ k ( t ) d t ) Y  i s integrably  bounded  <J>:[a,b] -»• [0,°°)  p r e v a i l s f o r each  Trajectories  of  T ( t , x ) =? 0  (by  ij) J on fi i f there i s  f o r which t h e i n c l u s i o n  [ t , x ] i n fi .  We a r e now s u f f i c i e n t l y prepared t o study the d i f f e r e n t i a l  inclusion x(t) e r(t,x(t)) An for  a.e.  on  [a,b]  .  R -valued arc x(*) s a t i s f y i n g this r e l a t i o n s h i p i s c a l l e d a n  T , o r simply  ematician  a  T-trajectory..  trajectory  Faced w i t h t h i s d e f i n i t i o n , a math-  immediately asks, "Must such a t r a j e c t o r y e x i s t ? "  Theorem 3.1.6 o f  Clarke  [1] answers, "Yes," by p r o v i d i n g c o n d i t i o n s under which an F-trajectory.  t r a j e c t o r y admits a nearby  below a l s o concludes t h a t a c e r t a i n f i n d frequent The and  that i t s values  requires that  V  there  be  a multifunction  T  T-trajectory exists:  X:[a,b] -> R  X ( t ) + e ( t ) B c o,  (b)  For every  t  and  n  [a,bj  t  multifunction  Theorem  (i)-(iii) a  If.  below,  {x^}  in  x  in  on  fi  , and  ,  that there e x i s t  E(')  on  [a,b]  [a,b]  . x' -»- r(t,,x')  i s upper  X(t) + e(t)B .  i s measurable, f o r every  is a sequence  of arcs  then i t admits  [a,b]  I t also :  t ' ->-T(t',x)  a subsequence  on  [a,b]  which  [ t , x j e i n t fi .  satisfying  converges  conditions  uniformly  to  ^-trajectory. e X(t)  (i)  x (t)  (ii)  ^ ( t ) e T(t,x (t)+y (t)) + r (t)B  ±  and i  and  {r^}  uniformly [a,b] (iii)  fi  hold..  , the m u l t i f u n c t i o n  semicontinuous a t every p o i n t  1.6  < > j ) on  a positive function  conditions  f o r every  in  follow.  i s d e f i n e d on some tube  i n t e g r a b l y bounded (by  (a)  t h i s theorem w i l l  are nonempty, compact, convex s e t s .  such t h a t the f o l l o w i n g t h r e e  The  s e q u e n t i a l compactness r e s u l t  a p p l i c a t i o n i n the d i s c u s s i o n to  theorem assumes t h a t  (c)  The  approximate  The The  are  ±  i  i  sequences  to zero  and  whose measures  sequence  proof  | x ( t ) | < t()(t)  {x^a)}  a.e. for  of measurable {k^}  appears i n C l a r k e  all  to  b-a  [a,b] t  functions  is a sequence  converge is  on  .  in  A on  ±  , where [a,b]  of measurable  .  bounded. [ 1 ] , Theorem 3.1.7.  {y } ±  converging  subsets  of  21.  2  THE  2.1  DIFFERENTIAL  Formulation  problem  may  CP)  be  The  INCLUSION  f i x e d time v e r s i o n of the differential  formulated  F - t r a j e c t o r y . x(*)  constraints P  represents  interval F:RxR  n  i ( t ) e F ( t , x ( t ) ) a.e.,  e S .  for  +«>••) d e f i n e d  , objective function  , and  P  c o n s t r a i n t set  f :R xR n  S c R xR n  i t s v a l u e by d e t e r m i n i n g an a d m i s s i b l e  x(')  to problem  s o l u t i o n i s a genuine o p t i m i z a t i o n  eliminate  2.2  Hypotheses  The  is (b)  :  we  are to c a l c u l a t e  x(/)  on the  f(x(a),x(b))  .  interval  Such an  P ; the b u s i n e s s of i s o l a t i n g  arc  a  problem.  any  admissible  arc.  The  P  might  be  f o l l o w i n g hypotheses  f a c i l i t a t e a f r u i t f u l study of the problem.  assume t h a t the data of problem  [x,y] e S  S  The m u l t i f u n c t i o n F  P  i s c l o s e d ; i t s f i r s t p r o j e c t i o n , namely  f o r some  y } ,  compact.  tube,  F  i s d e f i n e d on some tube  i s m e a s u r a b l y L i p s c h i t z and  are nonempty compact convex s e t s . • " " tube c o n t a i n i n g r  time  (a)-(d) below.  endpoint c o n s t r a i n t s e t {: x  for  However, the form i n which,  F-trajectory  Throughout s e c t i o n 2, we  s a t i s f y conditions (a)  a t t a i n e d by  t h i s p o s s i b i l i t y , and  endpoint  R , multifunction  S u p e r f i c i a l a n a l y s i s - suggests t h a t the infimum d e f i n i n g f i n i t e without b e i n g  the  i n terms of the given  challenge:  which minimizes the o b j e c t i v e f u n c t i o n i s c a l l e d a solution  i f i t satisfies  n  .  n  t h i s number appears c o n s t i t u t e s an i m p l i c i t  [a,b]  [x(a),x(b)] e S } .  S t r i c t l y speaking, the above e x p r e s s i o n  a number ( p o s s i b l y  [a,b]  -* R  n  :  i s admissible  [x(a),x(b)]  inclusion  as  inf{ f(x(a),x(b))  An  PROBLEM  Q  on  [a,b]  .  On  this  i n t e g r a b l y bounded; i t s v a l u e s  Also,  F  has  an e x t e n s i o n  which r e t a i n s :these - p r o p e r t i e s .  to some  (c)  The o b j e c t i v e f u n c t i o n  f  I s L i p s c h i t z o f rank  on the s e t  S n (fi~xfi7) . a b Now suppose Unfortunately, closed.  P  has a f i n i t e value:,  the answer i s "No," e s s e n t i a l l y because t h e tube  P , as we now show.  v e r s i o n of  P  a tube c o n t a i n i n g b o t h t o fi .)  With Theorem 1.6 i n mind, we c o n s i d e r a  fi  (Hypothesis (b) allows  and fi ; t h i s e x t e n s i o n  T h i s new problem, say  l i m i t f(x.(a),x^(b)) = i n f P .  t h a t Theorem 1.6 a p p l i e s , w i t h subsequence o f S  and  Hypothesis  then  s  (x^(')}  P  a  I f the s o l u t i o n t o  t o an  x(*) i s admissible  [a,bj .  x(•) .  for P ;  So i f P  has a f i n i t e ,  solution. P  spends some time on the boundary o f  x(t) e  fi  fc  fora l l  constraint:  ^ , we must  i s i n f l u e n c e d by t h e problem's t  in  [a,b] .  Such a p o i n t -  many s t a t e c o n s t r a i n t s ,  i n c l u d i n g this; one, may be cast i n t o the g e n e r a l in  arcs f o r  F-trajectory  f ( x ( a ) , x ( b ) ) = i n f P~ .  w i s e c o n d i t i o n i s c a l l e d a state  t  of admissible  i t s c o n c l u s i o n h o l d s t h a t some  acknowledge the p o s s i b i l i t y that, i t s c h a r a c t e r i m p l i c i t requirement t h a t  so i t admits a  Hypotheses (a) and (b) above a s s u r e  X ( t ) = fi^ :  X ( t ) are closed s e t s ,  admits  t o be extended to  i s unique when r e s t r i c t e d  {x^t')}  converges u n i f o r m l y  (c) i m p l i e s t h a t  F  P , a l s o has a f i n i t e v a l u e ,  m i n i m i z i n g s e q u e n c e — t h a t i s , a sequence  value  i s not  i n which the competing t r a j e c t o r i e s l i e not i n fi , b u t i n  the s l i g h t l y l a r g e r s e t fi .  Since  fi  However, an a f f i r m a t i v e answer i s p o s s i b l e f o r a problem c l o s e l y  r e l a t e d to  which  must a s o l u t i o n a r c e x i s t ?  form  g(t,x(t)) < 0  The arguments t o f o l l o w may a l l be m o d i f i e d  for a l l  t o account f o r  e x p l i c i t s t a t e c o n s t r a i n t s o f t h i s form, b u t t h e i r e s s e n t i a l f e a t u r e s a r e c l e a r e s t when the s t a t e c o n s t r a i n t s a r e i n a c t i v e a l o n g when  g(t,x(t)) < 0  fora l l  t  in  [a,b] .  solutions.  T h i s i s our f i n a l  That i s ,  hypothesis.  (d)  P  has  and  2.3  a s o l u t i o n ; a l l s o l u t i o n s to problem  therefore  solve  M u l t i p l i e r Sets  of necessary  P  actually l i e in  P .  Every s o l u t i o n to problem  conditions—the  counterparts  P  s a t i s f i e s a c e r t a i n set  i n our f i e l d of the famous E u l e r -  Lagrange e q u a t i o n i n the c l a s s i c a l c a l c u l u s of v a r i a t i o n s . these c o n d i t i o n s H:ftxR -* R  l i e s the Hamiltonian  defined  n  note t h a t  the the [1]:  :=  max{  v e F(t,x)  <p,v> :  H(t,x,rp) = rH(t,x,p)  [a,g] (Here, and  f o r problem  e 9H(t,x,p)  i f and  for a l l  variables.)  For every a r c  triples  x(-)  m u l t i p l i e r set [p,C,AJ  (a)  c = [£,n]  (b)  p: [a,b] ->- R  Other p r o p e r t i e s  gradient  of  H  admissible  lies n  in  p(-)  3H  is a  for  (corresponding  P  and  refers  only Clarke  multifunction  a l l scalars  to. x(.-) )  M^(x)  r , A > 0 , the  c o n s i s t s , of a l l  ( a ) - ( c ) below.  9f (x(a) ,x(b)) .  3 H ( t , x ( t ) , p ( t ) ) a.e.  e  i s c a l l e d the adjoint  on  inclusion [a,b]  The  arc  The  a d j o i n t t r a j e c t o r y s a t i s f i e s the transversality  Here  H  r > 0 .  are p r e s e n t e d i n  i s an a r c obeying the Hamiltonian  [p(a),-p(b)]  of  for  1.6.  s a t i s f y i n g conditions  l>p(t),x(t)]  Cc)  [ra,g] e 9H(t,x,rp)  only i f  s a t i s f y i n g the hypotheses of Theorem  X  function  r > 0 , whence  the most noteworthy i s the a s s e r t i o n that  index  P , which i s the  of  } .  throughout s e c t i o n 2, the g e n e r a l i z e d  Ix,p]  At the h e a r t  by  H(t,x,p) We  Q ,  e AU,n]  E := A[£,n] +  f u n c t i o n f o r the s e t  or costate  .  trajectory. condition  + r | [A,E] | 9dg(x(a) ,x(b) ) .  [-pCa) ,p(b) ] and S , defined  dg.  i s the E u c l i d e a n  i n item 1.2.2.  distance  Applying  the remarks p r e c e d i n g  A M (x)  belongs to  [8p,r;,gA] e W  i f and o n l y i f  r  t h i s d e f i n i t i o n , we note t h a t BA  (x)  us agree t o s c a l e when n e c e s s a r y , and thus r e s t r i c t two  cases:  when  A=0  A=0  and  and  A=l .  p(*)=0 :  Of course,  conditions  Theorem (Necessary C o n d i t i o n s )  Then for any  [p,C,A] PROOF  r  with  exceeding  According { x :  Suppose  (The constant  the arc  K  t o H y p o t h e s i s 2.2(a), t h e r e [x,y] € S  I t f o l l o w s t h a t the a r c  (b) and (c) h o l d  f o r some  trivially  ( a ) - ( c ) as  possibility.  r := (2K^+2) (1+KlnK)  X + ||p|| > 0 .  B > 0 . Let  our a t t e n t i o n t o o n l y  any l e g i t i m a t e theorem p r o p o s i n g  n e c e s s a r y c o n d i t i o n s must e l i m i n a t e t h i s  2.4  fora l l  [p,£,A]  x(.») solves  there  exists  is defined  a  problem  P  multiplier  in item 1.4.)  I s a constant  M  such t h a t  y } c MB .  x(') solves  P  i f and o n l y i f the a r c  [x(a),x(*)J  s o l v e s the r e l a t e d problem min{  f (y (b),y(b))  :  Q  [y ,y] Q  g {0}xF(t,y) ,  Ty (b),y(b)] 0  where  D := { [u,u] :  u £ R  n  },.  [y (a),y(a)] e D n 0  e S } ,  T h i s problem has the form t r e a t e d i n [ 1 ] :  i t s s o l u t i o n t h e r e f o r e admits a n o n t r i v i a l m u l t i p l i e r i n C l a r k e ' s provided an a r c  r  exceeds  r . ( [ 1 ] , Theorem 3.4.3).  [PQ,P] , a s c a l a r  m,,  sense,  Such a m u l t i p l i e r c o n s i s t s o f  A > 0 , and a v e c t o r  t, s a t i s f y i n g the f o l l o w i n g  conditions. (i)  C = [5»n] £ 3 f ( x ( a ) , x ( b ) )  (ii)  [-p ,-p,0,x](t) 0  6  .  M^(x)  8 H ( t , x ( a ) , x ( t ) , p ( t ) , p ( t ) ) a.e. , where 0  H(t,yQ,y,qQ,q) = H(t,y,q) . M^(x)  T h i s i m p l i e s c o n d i t i o n (a) d e f i n i n g  , and i m p l i e s t h a t  p  T h i s e s t a b l i s h e s (b) i n t h e d e f i n i t i o n o f n  i s constant.  (iii)  [p (a),p(a)] e r|[A,E]|3d^(x(a),x(a)) this forces  (iv)  .  0  p^ = -p(a)  -[-p(a),p(b)] =  By  item 1.7.2, w i t h  C = {0}  .  [ ( a ) , - p ( b ) ] £ A? + r | [A,E] | 3 d ( x ( a ) , x ( b ) ) P  .  g  T h i s reduces to the t r a n s v e r s a l i t y c o n d i t i o n (c) d e f i n i n g  M^(x)  .  The m u l t i p l i e r s e t s d e f i n e d here p e r t a i n to a more g e n e r a l problem do those of t h e same name i n [ 1 ] . objective function  f  i s compact and  i s closed.  in  To r e c o v e r the s p e c i a l case,  independent of We  3 f ( x ( b ) ) , whereupon item 1.7.1  may  x(a)  , and  take  c  an  where  xC  [0,£]  •  than  consider  S := q -^  [£,1")] =  then take  f o r some t,  reduces c o n d i t i o n (c) to a p a i r of  t r a n s v e r s a l i t y c o n d i t i o n s of the form C l a r k e p(a)  ,  (x(a)) ^0 -p(b) e XZ + r|[X,E]|3d_ (x(b)) . l minor d i f f e r e n c e p e r s i s t s : i n these two  presents:  r|[A,E]|3d  6  L  One  whereas the  3  3.1  E  i n [1] s i g n i f i e s o n l y  E =  [-p(a),A£+p(b)],  A? + p ( b ) ! .  PERTURBATIONS  The Value  Function  No  i n f i n i t e l y accurate data. and  expressions,  t r u l y a p p l i e d o p t i m i z a t i o n problem  presents  Q u a n t i t a t i v e u n c e r t a i n t y i s severe i n  the s o c i a l s c i e n c e s ; even i n the s t r i c t l y  econometrics  c o n t r o l l e d l a b o r a t o r i e s of  p h y s i c a l s c i e n c e s , measurement e r r o r s a r e i n e s c a p a b l e .  And  the  even i f the  parameters of a g i v e n problem are i n f i n i t e l y p r e c i s e , an a l e r t manager  may  w e l l i n q u i r e about the consequences of changing them s l i g h t l y .  To  t h i s q u e s t i o n , we  differential  embed the problem of s e c t i o n 2 i n a f a m i l y of  i n c l u s i o n problems indexed P(u)  by the p e r t u r b a t i o n v e c t o r  inf{ f(x(a),x(b),u) :  x e F(t,x,u)  ,  u  in  R  m  address  :  [x(a),x(b),u] e S } .  When of  u  .u  vary  slight alter  i s fixed  at zero,  i n a neighbourhood  changes.  The s o l u t i o n  the numerical  monitors  this  i s the problem of s e c t i o n of zero,  arcs  variation:  As t h e v a l u e s  the data of the problem  ( i f they  v a l u e o f t h e infimum.  the l a t t e r  2.  exist) The  undergo  change t o o , and u s u a l l y  value function  V ( u ) := i n f P ( u ) .  Sharp  V:R  m  estimates  R  u {+<»}  of  8V(0)  00 and  9 V(0)  P(0)  t o s m a l l changes  3.2  Hypotheses  consider  provide considerable insight  assumptions (a)  Slight  some m i n o r  completeness,  in  u  .  changes  into  the sensitivity  They a r e t h e g o a l o f t h i s i n t h e forms  of  c o n d i t i o n s ( a ) - ( d ) below r e f o r m u l a t e  The e n d p o i n t  constraint  chapter.  f , F, and S  amendments t o t h e b a s i c h y p o t h e s e s  f o r the unperturbed  of problem  f o r c e us t o  of item  2.2.  For  the corresponding  case.  set  S  i s closed; i t s f i r s t  projection i s  compact. (b)  The m u l t i f u n c t i o n The  tube  and  some  ft p>0  F  i s d e f i n e d o n some t u b e  has t h e f o r m .  F(t,x,u)  also measurably L i p s c h i t z and  convex.  Also,  which r e t a i n s (c)  As  (d)  i n item  b  x B) P  2.2, we l e t  f  solve  has a s o l u t i o n ; P(0) .  i n  bounded  [x,u] ; i t s values  n  ft°  on  m  c RxR  n  [a,b] .  on [a,b]  o n ft , w h e r e i t i s a r e nonempty,  compact,  t o some t u b e  c o n t a i n i n g ft  i s Lipschitz  of rank  on t h e s e t  . P(u)  considering admissible arcs P'(.O)  i s integrably  c RxR xR  these p r o p e r t i e s .  n (iTx F a  f o r some t u b e  has an e x t e n s i o n  The o b j e c t i v e f u n c t i o n S  by  F  ft°xpB  ft  in  be t h e v e r s i o n o f problem ft  P(u)  obtained  i n s t e a d o f ft .  a l l solutions  of  P(0)  l i e i n ft , a n d t h e r e f o r e  The  proof o f Theorem 4.1 r e l i e s on a weak t e c h n i c a l assumption.  statement ( e ) , and throughout t h i s chapter, solving (e)  P(0)  Y  F o r every a r c  x(-) i n Y , the m u l t i f u n c t i o n  S , d e f i n e d i n item 1.3.1.  (e) can be v e r i f i e d  directly.  i n t T :(x(a) ,x(b) ,0) * 0 g  [x,y,u] -> N (x,y,u) i s s  [x(a),x(b),0] .  Closed m u l t i f u n c t i o n s are d e f i n e d i n item 1.2;  Corollary 2).  denotes t h e s e t of a r c s  .  closed at the point  set  In  N  i s the normal cone to t h e  In s e v e r a l i n t e r e s t i n g s i t u a t i o n s ,  Hypothesis  F o r example, i t h o l d s a u t o m a t i c a l l y i f  for a l l x(-) i n Y  ( C l a r k e [ 1 ] , Theorem 2.5.8,  Section III.5 discusses t h i s hypothesis  i n detail.  We r e t a i n hypotheses ( a ) - ( e ) throughout s e c t i o n s 3 t o 5.  A f u r t h e r hypo-  t h e s i s i s i n t r o d u c e d i n item 3.4.  3.3 of  M u l t i p l i e r Sets  The a d j o i n t t r a j e c t o r y c o r r e s p o n d i n g  to a s o l u t i o n x(-)  P(0) c a r r i e s u s e f u l i n f o r m a t i o n about t h e s e n s i t i v i t y o f the problem.  When t h i s a r c i s a p p r o p r i a t e l y augmented by an a r c which t r a c e s the p r e c i s e  CO form o f t h e p e r t u r b a t i o n , t h e d e s i r e d c h a r a c t e r i z a t i o n s o f assume a p a r t i c u l a r l y elegant, form.  Of course,  3V(0) and  the new a r c s l i g h t l y  3 V(0)  alters  the appearance o f the m u l t i p l i e r s e t s . For any s c a l a r  \>0 and a r c  multiplier  set (corresponding  [p>q>S»^]  f o r which the f o l l o w i n g t h r e e c o n d i t i o n s h o l d .  Ca)  ?=  (b)  [p,q]:[a,b]  U,n,n']  lies  -> R xR n  in m  to  x(-) admissible f o r x(-) )  M\X)  i s an a r c obeying  the i n c l u s i o n a.e. on  where - H(t,x,u,p) := sup{ < p,v> : v c F(t,x,u) } . [ p ( a ) , - p ( b ) , - q ( b ) ] e A[5,n,n'] + N ( x ( a ) , x ( b ) , 0 ) . s  X  c o n s i s t s o f a l l quadruples  3f(x(a),x(b),0) .  [-p(t) ,-q(.t) , x ( t ) ] e 3 H ( t , x ( t ) , p , p ( t ) )  (c)  P(0) , t h e index  [a,b] ,  28.  3.4 if  Nondegeneracy  The  p e r t u r b a t i o n s t r u c t u r e of problem  some index 0 m u l t i p l i e r corresponding  q(a)  = 0  but  p * 0 .  i s nondegenerate—that  The  to a s o l u t i o n of  P  is  degenerate  P(0)  has  s e n s i t i v i t y a n a l y s i s of s e c t i o n 4 assumes t h a t  P  i s , that  [p>q>£>°] e M°(Y) (Here, of course,  and  M (Y) =  u  q(a)  M (x)  = 0  imply  p = 0 .  . )  xeY The  term "nondegenerate" r e f e r s to the way  the problem's data at ; U T 0 . .  Conditions  the i n f o r m a t i o n about the f i r s t - o r d e r given arc  x(')  irrelevant.  The  .  of  F  and  , the  S  show t h a t the a r c  u-dependence of  r e s u l t i n g hypothesis  i f the p e r t u r b a t i o n s As we  A=0  By s e t t i n g  3.3  the p e r t u r b a t i o n  influences  'q'(')  F, S, and  u-dependence of  f  f  along  c o n s p i r e to a l l o w  I t i s independent  f o r e x a m p l e — i n s e c t i o n 5 we  investigate  a problem whose p e r t u r b a t i o n s t r u c t u r e i s nondegenerate even though  SENSITIVITY  IV.2.  ANALYSIS  The m u l t i p l i e r s e t s of item 3.3 of  V  through a c e r t a i n mapping  ponding to an a d m i s s i b l e a r c notation t h i s way;  Q[M^(x)] Q[M^(Y)]  Theorem 4.1  P(0)  The minimum-time problem of s e c t i o n III.4 i s a u t o m a t i c a l l y  nondegenerate, as i s Example  4  trivial  q(a)=0 .  s h a l l see, nondegeneracy i s a m i l d h y p o t h e s i s .  be abnormal.  the  i s rendered  r e q u i r e s t h a t the m u l t i p l i e r be  of the u s u a l d e f i n i t i o n of n o r m a l i t y ,  may  carries  x(-)  a r e l i n k e d to the d i f f e r e n t i a l  Q .  For any m u l t i p l i e r  , we  define  Q(p,q,£,A)  r e f e r s to a l l p o s s i b l e v a l u e s denotes  u xeY  of  4.  [p>q,C 9 A] := -q(a)  corres.  obtained  The in  Q[M (x)] . A  i s the main r e s u l t of t h i s t h e s i s .  remainder of s e c t i o n  -q(a)  properties  I t s proof o c c u p i e s  the  29.  4.1 is  Theorem ( S e n s i t i v i t y ) locally  closed-near  the cone  one  also  [0,V(0)] 1  Q[M^(Y)]  is pointed,  3.1(a)-(e)  and 3.4  3  epi V  and  = 7o{ Q[M (Y)] n 3V(0)  3V(0) If  Under Hypotheses  +  Q[M°(Y)] n 3°°V(0) } .  the. closure  operation  is superfluous  and  has —0  oo  oo  3 V(0) = co{ Q[>T(Y);] n 3 V(0) } . (A subset o f combination  i s pointed  m  i f zero cannot be o b t a i n e d as a p o s i t i v e  linear  o f i t s nonzero elements.)  Corollary 1 PROOF  R  If  Q[M°(Y)] =  The cone  {0}  0 , then  V  is f i n i t e . and Lipschitz.  i s c e r t a i n l y p o i n t e d , so  3°°V(0) = {0}  near  0 .  by the Theorem.  Apply P r o p o s i t i o n 1.6.2.  Corollary 2  If  x  •  solves  P(0)  then i t has a multiplier  [p,q,?,A]  with  X + |q(a)| > 0 . PROOF  I f Y = {x(")}  the proof i s simple:  either  Q[M^(x)]  does not equal  {0} , whence the c o n c l u s i o n i s immediate, o r i t does, i n which case t h e s e t 3V(0)  must be nonempty ( P r o p o s i t i o n 1.6.2). 3V(0)  the unique  c o  {  Q [ M ( x ) ] n 3V(0) } 1  M"*"(x) * 0 .  a l s o , whence Now i f  ^  But then  x  i s not t h e unique  s o l u t i o n to the problem  s o l u t i o n to  P(0) , t h e a r c  P(0), where t h e data o f problem  as f o l l o w s . f(x ,x,y ,y,u) Q  0  F(t,x ,x,u) Q  := f ( x , y , u ) + e y  Q  := {e|x - x ( t ) | } x F ( t , x , u )  S := { [0,x,r,y,u] :  [0,x(-)J  2  [x,y,u]  e S ,  r e R}  is  P are  Any  e>0  will  s e r v e , p r o v i d e d we choose i t s u f f i c i e n t l y s m a l l to r e t a i n t h e  b a s i c hypotheses.  The argument above a s s e r t s t h a t  [-PQ,P, q, C, A] w i t h X + |q(a)| multiplier  i n M^(x) w i t h  >0 :  to t h e i r  t h i s m u l t i p l i e r reduces r e a d i l y t o a D  c a l c u l a t e t h e g e n e r a l i z e d g r a d i e n t s of V  definitions:  = { 5 :  [?,-]] e N  V  (0,V(0))  3°°V(0) = { x, :  U , 0] e N  V  (0,V(0))' } .  av(0)  has a m u l t i p l i e r  X + |g(a)| > 0 .  To prove Theorem 4.1, we w i l l by a p p e a l i n g  [0,x(-)]  }  To ensure t h a t these e x p r e s s i o n s make sense, we b e g i n w i t h t h e f o l l o w i n g result.  4.2  u  Lemma  in  P(u) (b)  x^(-) lies  6B , the condition  exist  constants  The set- e p i V  <S>0. and  e>0  V(u) < V(0) + e implies  He in fi (and hence solve  PROOF u^  (a) There  P(u)  is- locally'closed  such that  for all  that a l l solutions,  to  also), hear  [0, V(0) ]. .  (a) I f no such c o n s t a n t s e x i s t , then t h e r e must be a sequence 0  with  V(u^) < V(0) + 1 / i such t h a t f o r each  o f problem  P(u^) does not l i e i n ^ .  i n fi , so Theorem 1.6 a s s u r e s  that  Nonetheless,  {x^(')'}  = i n f H O T * f (x(a),x(b),0) <  < Thus e q u a l i t y h o l d s throughout and t h i s implies that  x(«) l i e s  l  x^(-)  Now by Hypothesis  3.2(d),  f (x. (a) ,x.(b) ,u.)  l  m  S  x(-) solves  i n ,fi .  each a r c  has a subsequence t e n d i n g  u n i f o r m l y to some a r c x ( - ) a d m i s s i b l e f o r P(0) . V(0)  i , some s o l u t i o n a r c  U  P  ( V ( 0 ) + l / i ) = V(0) .  P(0) .  According  to 3.2(d),  Consequently any u n i f o r m l y approxim-  a t i n g sequence o f a r c s must e v e n t u a l l y l i e i n fi .  This contradicts the f a c t  t h a t each a r c x ^ ( ' ) c o n t a i n s p o i n t s o u t s i d e fi , and thereby  establishes (a).  (b)  L e t {[u_^,v^]} be a sequence o f p o i n t s ( [ 0 , V ( 0 ) ] + hSBxheB)  c o n v e r g i n g to the p o i n t be t h e s o l u t i o n t o  n  [u,v] •  i n the s e t  epi V ,  P(u.) , so t h a t  V(u.) > f ( x ( a ) , x . ( b ) , u . )  1  1  v  By p a r t  admissible  =  f o r . P(u) .  l i m i t v. i  i  >  (a), f(x(a),x(b),u)  The proof  is  Proposition  Let  a cone containing  the  closed  limit • i CO  =  f(x(a),x(b),u)  Thus  f(x.(a),x.(b),u.) i i i .  [u,v] e e p i V  as r e q u i r e d .  D  ( [ 5 ] , Proposition 15).  and  D°° be closed  the. point  0  subsets  of  and the recession  R  such, that  m  cone of  D .  D°°  Ibr  cone N  in  converges u n i f o r m l y to  >  > V ( u ) . Hence  i  o f Theorem 4.1 i s b u i l t on t h e f o l l o w i n g geometric  p r o p o s i t i o n of R o c k a f e l l a r  4.3  {x_^}  L e t x^(«) fora l l  1  (We do not r e l a b e l . )  l i m i t V(u.) » i i co  -> co  1  i  Theorem 1.6 a s s e r t s t h a t some subsequence o f an a r c x ( * )  [u,v] e e p i V .  We must show  R xR  { rU,-l]  :=  :  r >0 ,  ? e  D  } n {[?,0] :  ?e  D}  one has  m  [ ? , - l ] e co N }  { t, : If  the cone  is  superfluous,  D°° is pointed,  —T_  Q[M ( Y ) ] n 3V(0)  D  on the right-hand  =  side  co D°° .  we must s u c c e s s f u l l y i d e n t i f y —f)  co  and  operation  has  [£,0] e • co N }  To complete t h e proof,  co (D + D°°) .  the closure  and one also  { C :  =  with  D  with  co  Q[*T-(Y)] n 3 V(0) .  Both these s e t s a r e  c l o s e d , being the i n t e r s e c t i o n o f c l o s e d s e t s .  ( Q[M (Y)]  i s c l o s e d by  A  oo Theorem  1.6.)  Moreover,  D  i s t h e i n t e r s e c t i o n o f two cones c o n t a i n i n g  00 z e r o , and i s t h e r e f o r e such a cone i t s e l f . c o n t a i n s t h e r e c e s s i o n cone o f N  where!  epi v ° ' (  H N  2  V ( 0 ) )  V  :=  { r[?,-l]  :=  {  :  [?,' 0] :  D  D , and t h a t  =  We b e g i n w i t h t h e l a t t e r  I t remains o n l y t o show t h a t  r > 0 ,  ' £ e QtM^CY).] n 9V(0) }  c e Q[M°(Y)] m 3°°V(Q) } .  assertion.  OO  The v e r y d e f i n i t i o n s o f N To prove  3V(0) and  t h e r e v e r s e i n c l u s i o n , we w i l l use t h e d e f i n i t i o n o f t h e normal cone  It motivates  Lemma  where  p e r p e n d i c u l a r v e c t o r s g i v e n i n item 1.3.1.  t h e f o l l o w i n g lemma.  Suppose  [v,-G]  a < V(0) + e  P(u) j a scalar  X  and in  ||[p,q]| + | [ ^ _ g ] |  >  0  y  Ca)  show t h a t  ,.(.0,V(0).) •• c "co" ( N 'Cl N ) . epi V 1 z  i n terms o f l i m i t s , of n o r m a l i z e d  4.4  d V(0)  £ = [£,n,n']  is perpendicular  u e <SB .  {0,1}  3  Then there  an.arc  and conditions  H-es in  to. e p i V  [p,q]  3  exists  (a)-(d)  [p(a),-p(b),-q(b)] e | [ ^ _ g ] |  PROOF  A  v  (  a  ) =  A  Since  solution  x ( - ) to  r, such  that  9f(x(a),x(b),u) .  Co)  q  [u,a] ,  hold.  [ - p ( t ) , - q ( t ) , x ( t ) ] e 3 t f ( t , x ( t ) , u , p ( t ) ) a.e. on  "  a solution  and a point  Cb)  W  at the point  [a,b]  [g»n,n'3 + N ( x ( a ) , x ( b ) , u ) g  . .  |[vI-B]| ' V(u).:< a < V(0) + E , Lemma 4.2  x ( . ) a d m i s s i b l e f o r P(u) .  assures that  Now f o r any  u'  P(u) has a :.  i n 6B, every  33.  F-trajectory  yC')  V(u') Hence  admissible  <  for  P(u') obeys  f(y(a),y(b),u')  <  f ( y ( a ) , y ( b ) , u ' ) + a - f(x(a),x(b),u) .  [ u ' , f ( y ( a ) , y ( b ) , u ' ) + a - f ( x ( a ) , x ( b ) , u ) ] e e p i V , and P r o p o s i t i o n 1.2.4  implies  that - <v,u'> + % | [ u ' - u , f ( y ( a ) , y ( b ) , u ' ) - f ( x ( a ) , x ( b ) , u ) ] |  f(y(a),y(b),u')  f ( x ( a ) , x ( b ) , u ) - <v,u> .  > E q u a l i t y h o l d s when . y = provides  x  [x("),u]  and u ' = u , so we deduce t h a t  a l o c a l s o l u t i o n f o r t h e (unperturbed) d i f f e r e n t i a l  inclusion  problem whose d a t a a r e f (x,x ,y,y ) := 1  fCx.y.y^ -<v,x >  1  +  ±  %|[ -u,f(x,y, )-f(x(a),x(b),u)]| y i  F(t,x,x )  Note t h a t for  :=  { [x.x^y.y^  H(t,x,x ,p,q) = 1  [x.y.y.^ e S ,  :  tf(t,x,x^,p)  t h i s problem, so we may apply  a scalar  A  (i)-(iii)  .  [£,n.»n']  e SB } .  an a r c  [p,q] ,  i n 3f(x(a),x(b),u)  such  below h o l d .  e[5,0,Ti,n'] + [0,-v,0,0]  (ii)  [-p,-q,x,0](t)  e  [-p,-q,x](t)  3 t f ( t , x ( t ) , u , p ( t ) ) a.e. on  (iii)  ;L  I t provides  (D  e  x  A l l t h e hypotheses o f item 2.2 h o l d  Theorem 2.4.  i n {0,1} , and a v e c t o r  that conditions  l i e s i n 3f(x(a),u,x(b),u) .  3 H ( t , x ( t ) , u , p ( t ) , q ( t ) ) a.e. on [a,b].'  [p(a),q(a),-p(b),-q(b)]  e  This  implies  [a,b]..  A( 3[?,0,n,n'] + [0,-v,0,0] ) + N (x(a),u,xCb),u) . s  Now  u  vector  ,  := F ( t ,x,x.) x {0} , and  1  S  2  y i  lies  i n <5B by assumption, so t h e second component o f every  i n N (x(a),u,x(b),u) g  i s zero..  Condition  ( i i i ) therefore  reduces t o -q(.a) = Av and [p(a),-pCb),-q(b)] e  Xgte.n.n']  + N (x(a),x(b),u) . s  2  34.  To complete t h e p r o o f , we simply ( i i ) and ( i i i ) ,  a t corresponding points  [v^,-3^] [u^,a^]  ] -* [0,V(0)] , and t h e l i m i t o f  ±  equals (say)  t o' ^0'' v  -  *  of v e c t o r s  f o r the adjoint  [v^,-f3^] -*• [0,0] ,  [v^-B^.] / J [v ,-3 ] | ±  ±  Item'1-3.1 t e l l s us t h a t  ^  So t h e d e s i r e d i n c l u s i o n i n v o l v i n g  e s t a b l i s h e d i f we o n l y prove  perpendicular to  i s g i v e n , where  N e  p  p r e c i s e l y t h e c l o s e d convex cone generated by v e c t o r s t h i s way.  |[v,-3]| i n  (a)-(d).  Suppose now t h a t a sequence  [u ,a  [p,q] by  [p,q] / J [ v , - $ ] |  and take t h e s c a l e d a r c  t r a j e c t o r y i n conclusions  epi V  d i v i d e the a r c  [VQ,-3Q] e  u  ^ y(0,V(0)) i s [VQ, ^Q^ —  ^ ^(0,V(0)) .  e x i s t s and  obtained w i l l be  T h i s i s a consequence  of t h e f o l l o w i n g lemma.  4.5  Lemma  Let  is a solution  x(0  3f(x(a),x(b),0)  be the unit vector introduced above. Then there  [VQ,-3Q]  to  P:(0)3  an arc  [p,q] y.  and a vector  [-p,-q,x](t) e- 3 H ( t , x ( t ) , 0 , p ( t ) ) a.e. on  Cb)  [p(a) ,-p(b) ,-q(b)] e 0 U,n,n'] + N ( x ( a ) ,x(b) ,0) , and  Cc)  -q(a) = v  o  vectors  n  [a,b]  ,  g  .  Q  For a l l  i  s u f f i c i e n t l y l a r g e , Lemma 4.4 a p p l i e s t o t h e p e r p e n d i c u l a r  [-^>~3^] t o generate s o l u t i o n s v  quantities  ^  such that  Ca)  PROOF  [5,n,n']  ,  x ^ ( ' ) f o r P(u^) and c o r r e s p o n d i n g  [p^,q^] , and' [?^»i"|^,r)!J  f(x.(a),x.(b),u.) I i  s a t i s f y i n g 4.4(a)-(d).  = V(u.) < a. + V ( 0 ) . i l I  Note t h a t  35.  Now  we  observe t h a t  \^ * 0  suppose a subsequence of the = 0  for a l l  for a l l arc  i  by  i .  for a l l s u f f i c i e n t l y large  " m u l t i p l i e r s " above (which we  Then 4.4(d) i m p l i e s t h a t  by the n o n t r i v i a l i t y c o n d i t i o n . 1 / |p_j,(a)| : the r e s u l t  We  q^(a) may  i .  do not  To see  this,  relabel)  has  = 0 , whence  p^(a)  * 0  t h e r e f o r e s c a l e the a d j o i n t  i s a sequence of a r c s  [p^,q^,x^]  on  [a,b]  such t h a t [ - P , - q , x ] (t) i  i  i  [p (a),-p 1  sequence  i  (b)] e N (x (a),x O  while  q^(a)  1  9f/  on  [a,b]  P(0)  1  = 0 . of i n i t i a l p o i n t s of these a r c s i s  to an a r c  [p,q,x]  Therefore  such t h a t  [p(a),-p(b),0]  x(")  on  [a,b]  ,  s  while  q(a) = 0 . use H y p o t h e s i s 3.2(e).)  But  above, f ( x ( a ) , x ( b ) , 0 ) = l i m i t f ( x . ( a ) , x . ( b ) , u . ) i-x»  < l i m i t a . = V(0)  l i m i t arc  supported:  solves  P(0)  .  T h i s cannot be  the  A s i m i l a r argument e s t a b l i s h e s t h a t the sequence  1 / |p^(a)| and  the case,  then s c a l i n g the  bounded.  Applying  P . i s bounded.  solutions with  Theorem 1.6  the  three  i - t h m u l t i p l i e r by  l e a d s to a f a m i l y of m u l t i p l i e r s and  { [p (a) , 1. (a) ,x. (a) ] }  {p_^(a)}  by the note , so  c o n c l u s i o n s j u s t d e r i v e d c o n t r a d i c t the nondegeneracy of problem  For i f t h i s were not  is  N ( x ( a ) , x ( b ) , 0 ) , and  e  (To o b t a i n the second c o n c l u s i o n , we  x(-)  a further  and  [-p,-q\x](t) e 8f/(t,x(t) , 0 , p ( t ) ) a.e.  |p(a)| = 1  ,  (b),u ) , and 1  s a t i s f i e s the hypotheses of Theorem 1.6.  subsequence converges u n i f o r m l y for  a.e.  i  1  {[p^(a),q^(a),x^(a)]}  bounded, and  admissible  1  (b),-q 1  |p.^(.a)| = 1 The  8H.(t,x (t),u ,p (t))  e  allows  1 .'  q^(a) the  -»• 0 :.  36.  e x t r a c t i o n of a subsequence of t h e s e m u l t i p l i e r s along to z e r o ,  p^  to some nonzero a r c  a solution for compromised.  P(0) This  .  Once a g a i n ,  i s absurd:  the  Thus the sequence of i n i t i a l as  i t s t a n d s , and  Theorem 1.6  A  (for  = 1  |p^(a.) | = 1  sequence points  y i e l d s a subsequence of  to the  solution  x(')  described  i n the c o n c l u s i o n s  a l w a y s ) , and  must be  (a).,q^(a) ,x  i .  converges x^(-)  P  to  is  bounded.  (a) ] }  i s bounded  A f i n a l a p p l i c a t i o n of  {[p^(•),q^(*),x^(•)]}  and  3f  {p^(a)}  {[p  the a d j o i n t a r c  of the lemma.  argument uses t h e f a c t t h a t  q^(a)  the nondegeneracy of problem  for a l l large  uniformly  which  (Note:  which converges  [p('),q(')] this last  limiting  i s c l o s e d , which i s j u s t i f i e d by  Proposition  1.6.4.)  •  A i d e d by Lemma 4.5, Suppose f i r s t conclusions we  find  -q(a)  =  t h a t the  v /e Q  prove t h a t  [v^,-^]  Upon d i v i d i n g the a r c  lies  [p,q]  x(-)  has  a m u l t i p l i e r of index  N^ u N  in  by  1  2  .  in [p,q]  ,  with  . But  0  [^,-1]  0  -po  .  now  renaming the r e s u l t i n g a d j o i n t a r c s as  solution  construction,  V  may  *''0  ( a ) - ( c ) and  3Q by  that  we  e  so  =  [v ,-B ] 0  vQ/30  -q(.a) =  -1 Q[M (Y)]  e  Q  n 3V(0)  N . e p  6  V  9V(0)  (0,V(0)) .  In o t h e r  words,  .  e  This  implies that Second, assume  an  index  0  [VQ,~3Q]  lies  3Q = 0 .  m u l t i p l i e r f o r the  in  Then  N^  .  [p,q]  solution  i s an a d j o i n t a r c a s s o c i a t e d x(*)  , and  -q(a)  = v^  .  Of  with  course,  [v„,0] U v -e  e 3V(0)  n 3VC0)  Q[M°CY)_]  Q  [v„,0] U  because  and  N  e  . „('0,V(.0)') epi V  [vQ,0]  by c o n s t r u c t i o n .  Therefore  lies in N  We have f i n a l l y e s t a b l i s h e d t h a t  "N  V  (0,V(0)) c co" (t^  the reverse i n c l u s i o n i s obvious, e q u a l i t y holds.  u N ) 2  .  Since  Only one s t e p remains i n  the p r o o f o f Theorem 4.1.  4.6  .Lemma  set  Q[M (Y)]  PROOF  Q[M^(Y)] n 3°°V(0)  The set n 3V(0)  1  contains  the recession  .  R e c a l l t h a t t h e r e c e s s i o n cone o f a s e t C 0+  C  :=  cone of the  { l i m i t 6.y. :  6.  y . e C ,  i i  l  i n :.R  i s t h e cone  m  + 0 }  .  l  1 ->- oo CO Since  +  3 V(0)  always c o n t a i n s  0  3V(0)  be e s t a b l i s h e d once we show t h a t lies  ( P r o p o s i t i o n 1.4.3), t h e lemma w i l l  Q[M^(Y)]  contains  0+  i n the former s e t , so we examine a nonzero element  T h i s element must be o b t a i n e d as  q = l i m i t -S.q.(a)  Q[M"*"(Y)] . q  of  Zero  the l a t t e r .  f o r a sequence  i -> oo (x^(-)} i n Y with corresponding m u l t i p l i e r s [p^>q^»?^»l] and s c a l a r s 6^ + 0 . When we w r i t e [p^,q^] f o r ^ Pi»^i li-l ^ ' conditions defining c  n t  i e  1  a multiplier,  the H a m i l t o n i a n i n c l u s i o n i s unchanged and t h e t r a n s v e r s a l i t y  c o n d i t i o n assumes  t h e form  [p,(a),-p.(b),-q  1  1  (b)]  £  1  Under t h i s s c a l i n g , we now have  U  6  sequence.  and t h e sequence  The sequence  (p^(a)}  t h a t o f Lemma 4.5.  n'] + N (x ( a ) , x (b),0) .  o l  q = l i m i t -q.(a) . i  i s a bounded  ,n  1 X 1 1  oo  {x^(a)}  In p a r t i c u l a r ,  (q.(a)}  i s bounded by H y p o t h e s i s 3.2(a),  must a l s o be bounded by an argument  Hence t h e a r c s  1  i d e n t i c a l to  { [p^-( *) ,q^( *) >x^( •) ] } have a convergent  38.  subsequence by Theorem 1.6. converges u n i f o r m l y [p(*),q(*)]  As  ,  8 AO  to a f u r t h e r s o l u t i o n  and  the subsequence of  x(*)  in  Y  s a t i s f y i n g the H a m i l t o n i a n i n c l u s i o n and  and  arcs  an a d j o i n t p a i r  the t r a n s v e r s a l i t y  condition [p(a),-p(b),-q(b)] Moreover, one  has  q  =  £  N (x(a),x(b),0) . s  l i m i t -q.(a) i  =  -q(a)  .  That i s ,  q  lies  in  ->- co  Q[M°(Y)] . The  5  •  proof of Theorem 4.1  APPLICATION:  i s complete.  ACCURATE  DYNAMICS  C e r t a i n i n t e r e s t i n g s e n s i t i v i t y problems a r i s i n g i n the study of d i f f e r e n t i a l i n c l u s i o n s i n v o l v e no p e r t u r b a t i o n s t h i s s e c t i o n , we perturbation  i n v e s t i g a t e two  o f the o b j e c t i v e f u n c t i o n  t r a n s l a t e the t e r m i n a l  5.1  such cases.  set i n  Reduced C o n d i t i o n s  the H a m i l t o n i a n H(t,x,p) = sup{  <p,v>:  [p,q,£,A]  first  of s e c t i o n s  veF(t,x)  } .  that  F  3 and With  q  H  (c)  e  3H(t,x(t),p(t))  now  conditions.  a.e.;  i s constant.  [p(a),-p(b),-q]  £  A[£,n,n'] + N ( x ( a ) , x ( b ) , 0 ) . g  no  u-dependence,  independent of  must be a constant a r c .  i s an a r c obeying the i n c l u s i o n  q  has  c o r r e s p o n d i n g to an a d m i s s i b l e  [-p(t),x(t)]  perturbations  4 reduces to  (b)  n  a  n  the f o l l o w i n g reduced  R  involves only  f ; i n the second,  s a t i s f y 3.3(a) and p:[a,b]  In  R ..  the H a m i l t o n i a n i n c l u s i o n i m p l i e s multiplier  The  When the m u l t i f u n c t i o n  K(t,x,x^,p)  i n t h e i r dynamics.  arc  x(*)  x^ A  must  ,  Further  r e d u c t i o n i s p o s s i b l e i n t h e s p e c i a l case i n which t h e endpoint  constraint set S  i s a l s o independent of  s l i g h t l y and t h i n k o f _S  as a subset  of  u . R  n><  R  n  L e t us abuse our n o t a t i o n i n o u r d i s c u s s i o n of t h i s  possibility. 5.2  Theorem  Let the function  V(u)  V:R  := i n f { f ( x ( a ) , x ( b ) , u )  where the data obey Hypotheses 9V(0) PROOF  When  S  N (x(a),x(b),0) Now when  R u {+«>} be defined  m  A=0, 9V(0)  i s independent o f  =  and 3.4,  ,  [x(a),x(b)] e S } ,  Then  9°°V(0) = {0} and  U.n.n'] e 9f ( x ( a ) , x ( b ) ,0) u , the t h i r d  Condition  q=0 — t h u s  i e F(t,x)  3.2(a)-(e)  = co{ n' e 3 V ( 0 ) :  i s zero.  :  by  for  x e Y } .  component o f every v e c t o r i n  5.1(c) i m p l i e s t h a t -q = An' , t h e r e f o r e .  Q[M°(Y)] = {0} .  Theorem 4.1 a s s e r t s  that  co{ Q [ M ( Y ) ] n 9V(0) } . 1  This i s p r e c i s e l y the desired conclusion. Note t h a t t h e v a l u e  function defined  • i n t h e theorem i s L i p s c h i t z o f rank  CO near  0  by H y p o t h e s i s 3 . 2 ( c ) .  We may t h e r e f o r e o b t a i n  d i r e c t l y from P r o p o s i t i o n 1.6.2 w i t h o u t r e c o u r s e the f u n c t i o n  f  i s regular  2 . 3 . 1 6 ) — f o r example, when Theorem 5.2 s i m p l i f i e s  { n' : where  if  to Theorem 4.1.  A l s o , when  (see [ 1 ] , e s p e c i a l l y P r o p o s i t i o n s 2.3.15 and . f  i s smooth o r c o n v e x — t h e c o n c l u s i o n o f  because  U,n,n'l e 9f (x(a) ,x(b) ,0) } =  9g(0) ,  g(u) := f ( x ( a ) , x ( b ) , u ) .  Corollary 1 PROOF  9 V(0) = {0}  e x t 9V(0)  c  { n' :  [£,n,n'] e 9 f ( x ( a ) , x ( b ) , 0 )  f o r xeY } .  Apply the f o l l o w i n g well-known converse of t h e Krein-Milman Theorem:  C c R  m  i s compact, then  co C  i s a l s o compact and  e x t ( co C ) c c .  •  The  perturbation  discussed  by Theorem 5.2 has such a s i m p l e  structure  t h a t a c o m p l e t e l y d i f f e r e n t approach w i l l a l s o y i e l d a f o r m u l a f o r 8V(0) . We d i r e c t t h e i n t e r e s t e d r e a d e r to s e c t i o n 2.8 of [ 1 ] , where C l a r k e the theory leads  of p o i n t w i s e  maxima and t h e i r g e n e r a l i z e d  co{ n' : U,n,n'] e 3 f ( x ( a ) , x ( b ) , 0 )  c  ( [ 1 ] , Theorem 2.8.3.)  It therefore  fails  f o r x(-) Y e  s i d e does not i n v o l v e t h e r e s t r i c t i o n  to eliminate  the p o s s i b i l i t y  i s computed on t h e r i g h t - h a n d  includes  3V(0) .  of t h e c o n v e n t i o n a l  t h a t the s e t whose convex  side contains  no p o i n t s o f  Thus C o r o l l a r y 1 o f f e r s a s i g n i f i c a n t  theory.  d i r e c t l y responsible  } .  n' e 3V(0) .  3V(0)  t h a t i t s members a r e s u f f i c i e n t l y w e l l d i s t r i b u t e d t h a t t h e i r  hull  theory  T h i s formula i s weaker than t h a t g i v e n by Theorem  5.2 because i t s r i g h t - h a n d  but  That  to the f o r m u l a 3V(0)  hull  gradients.  develops  at a l l ,  convex  refinement  The geometric approach o f Theorem 4.1 i s  f o r t h i s i n c i s i v e new e s t i m a t e ,  a f a c t which suggests  t h a t t h e t e c h n i q u e s o f s e c t i o n 4 might be p r o f i t a b l y a p p l i e d t o o t h e r b a s i c problems o f t h e g e n e r a l i z e d  calculus.  P u r s u i t of t h i s  possibility  would l e a d us f a r from t h e main t r a c k o f t h i s e x p o s i t i o n , but we can note the f o l l o w i n g improvement o f P r o p o s i t i o n 1.6.7.  Corollary 2  Let  g ,g 1  2 >  -  • •,g :R  some p >0 . Then the pointwise g(u')  is L i p s c h i t z on ext  where  :=  R  m  k  minimum  min{ g ^ u ) 1  :  i>e functions  function  i = 1,2,.'."..:.. . ,k }  pB and  3g(0)  1(0) := { i :  o.: u g ±  £ 3 g (0).  :  Lipschitz  i e 1(0) } ,  ( 0 ) = g(0) } .  on  pB for  41.  PROOF from  Set  C := { 1, 2, . . ., k } .  C o r o l l a r y 1, f o r  problem where  g  may be expressed  n=l , F ( t , x , u )  5.3  equals  Endpoint  presented  g^(u)  and  f  whenever  Perturbations  P  i s a L i p s c h i t z f u n c t i o n f o r which  x=y=i .  •  F. H. C l a r k e [1] d e r i v e s the n e c e s s a r y c o n d i t i o n s  problem's s e n s i t i v i t y to a d d i t i v e endpoint R e f l e c t i o n on t h i s  Let the f u n c t i o n V(u) (The s l i g h t CQ  :=  V:R  (See h i s Theorem  t h e p l a u s i b i l i t y of i t s hypotheses.  -> R u {+«>}  n  inf{ f(x(b)) :  x  C^  be d e f i n e d by F(t,x) ,  e  change to t h e argument l i s t  i s compact and  perturbations.  inclusion  s p e c i a l case w i l l h e l p us a s s e s s the r e l a t i v e  s t r e n g t h of Theorem 4.1 and determine  Here  [0,1] x (-l,n+l)::x B ,  i n s e c t i o n 2 from a c l o s e study o f the d i f f e r e n t i a l  3.4.3.)  immediately  as the v a l u e f u n c t i o n of a  := {0} , ft :=  S : = { 0 } x C x { l } x C x p B , f(x,y,u)  The c o n c l u s i o n f o l l o w s  of  i s closed:  f  x(a)  e  C  Q  ,  s h o u l d not be  the set  S  x(b)  C^u  e  } .  confusing.)  of s e c t i o n s 3 and 4  may be w r i t t e n :  where  S =  u (C ueR n  Q  x (C-j+u) x {u}) = C  u e R  D := { [u,u] :  [p>q»C»A]  } .  n  c o r r e s p o n d i n g to some a d m i s s i b l e a r c  z = [0,n,0]  (b)  [-p,x](t) e 3 H ( t , x ( t ) , p ( t ) ) a.e.  (c)  [ p ( a ) , - p ( b ) , - q ] ;e  and  1  A c c o r d i n g t o item 5.1, a m u l t i p l i e r  (a)  But  x (C x{0> + D) ,  Q  , where  N (x(a),x(b),u) s  t h i s reduces  to  n  lies  in  x(")  q  A[0,n,0] + N ( x ( a ) , x ( b ) , 0 )  on  .  g  = N  c  N  ( x ( a ) ) x { [v,-v] 0  as f o l l o w s .  3f(x(b)) . [a,b] ;  C  reduces  (x(a)) x N  c  x  {  Q  }  +  D  :  i s constant.  (x(b),0) ,  v e N C  (x(b)) } l  by t h e  arguments of s e c t i o n SE-..7. p(a)  e N  (x(a)) L  q ---=  Thus c o n d i t i o n (c) i m p l i e s t h a t and  0 - An  -p(b)  e  N_ L  Combining these o b s e r v a t i o n s , we  Q[M\X)]  (x(b)) . l f i n d t h a t f o r any  = { An+p(b) :  p:[a,b] t-p,x]  e  R  admissible arc  i s an a r c  n  x(*)  satisfying  3H(t,x,p) a.e.,  p(a)  N  e  (x(a)), c  and  -p(b)  e \r\ + N  5.4 of  Conclusions Theorem 4.1  ([1]). sets The  The  lies  s i m i l a r to those  That theorem adduces formulas r e p l a c e d by  X  E[M^(Y)]  sets  slightly  -p(b)  e  r|[A,E]|3d  e  of  E :=  An + p(b)  and in  3V(0)  . Q  r > r :=  with  3.4.3 the  (2K +2)(l+K&n K) f  Q[M (Y)] X  by  .  their  (x(b))  r  (la)  ,  (lb)  l  to C o r o l l a r y 1.6.9, the  be r e c o v e r e d  (r,-H>°) , we  have  .  sharper  A  right-hand .  to e s t a b l i s h t h a t the e s t i m a t e without  sides.  Thus C l a r k e ' s  t h a t of Theorem 4.1,  than t h a t of 4.1  transversality  from these by f o r m a l l y s e t t i n g  E[M^(Y)] c Q[M (Y)]  appears more p r e c i s e than  .C^  and  t a k i n g the c l o s u r e of the r e s u l t i n g  substantially and  According may  However, i t i s d i f f i c u l t  CQ  to those of 4.1,  f o r any  (x(a))  An + r | [ A , E ] | 3 d  conditions defining  ..r  throws the a s s e r t i o n s  0  C  of  Q  of C l a r k e ' s Theorem  can o n l y be d i s t i n g u i s h e d from  L  r = +°°  } .  s t r o n g e r t r a n s v e r s a l i t y c o n d i t i o n s , which r e a d p(a)  where  identical  E[M*(Y)]  l  9f(x(b))  above e x p r e s s i o n f o r the s e t s  i n t o a form v e r y  Q[M (Y)]  in  o  ( x ( b ) ) , where L  n  ,  For  values  estimate  e s p e c i a l l y as r+r  involving  E  p r i o r knowledge of the  is sets  .  To I f we  see  this, Q  let  consider  denote  any  An +  nontrivial multiplier  p(b)  , then c e r t a i n l y  second t r a n s v e r s a l i t y c o n d i t i o n  TUTQTT  The  1  N  N  ( C  X  (  A  |  <  )  A | C | +  M^(Y)  Q/|[A,Q]|  may  be  in e B-  replaced  M^(Y)  .  Thus  the  by  •  )  L  |Q[ < | [ A , Q ] |  inequality |p(b)  €  defining  [p,?,A]  (  also implies |.U,Q] |  >  2  A  )  that so  P(b)  |[A,Q1 A c c o r d i n g to G r o n w a l l ' s i n e q u a l i t y (compare Appendix 1 ) , |p(a) |  <  (1 + K £n K)|p(b) |.  Together w i t h the p r e v i o u s i n e q u a l i t y , t h i s i m p l i e s v e r s a l i t y condition defining  TuftlT f o r any  r > r :=  e  r  *  V  n  x  (  may  e  )  An +  may  be r e p l a c e d  r  trans-  by  )  ( 2 b )  .  In s h o r t ,  be r e p l a c e d  e r|[A,Q]|B n N  p(a)  a  (1+K^)(1+K£n K)  o b t a i n e d from Theorem 4.1  -p(b)  M^(Y)  that the f i r s t  the  transversality  conditions  by  (x(a))  |[A,Q]|B n N  (3a)  (x(b))  p  (3b)  l  L  f o r any (1)  r  exceeding  r .  In  t h i s form, t h e i r s i m i l a r i t y to  conditions  is especially striking. Not  only  do  d i r e c t i o n s as do  the r i g h t - h a n d s i d e s of t h o s e of  (1)  ( c f . C o r o l l a r y 1.6.9), but  magnitude r e s t r i c t i o n s of i d e n t i c a l form. t e d i n (1) must exceed  (3) s p e c i f y e s s e n t i a l l y the same they a l s o  Indeed, the v a l u e s of  r = 2r > 2 , w h i l e any  r > r  involve r  permit-  w i l l serve i n (3).  Thus the magnitude r e s t r i c t i o n s i n (3) are more s t r i n g e n t  than those i n  (1)  in  some i n s t a n c e s .  But  regardless  sets  CQ  In o t h e r  5.5  and  , we  also acquit  can be  sure t h a t the c o n c l u s i o n s  to t h o s e of  [ 1 ] ,  The  are a u t o m a t i c a l l y  a n a l y s i s above shows c l e a r l y -p(b)  r e q u i r e no  a r e not  = An + q  i s zero  that i f  A  a l s o , whence  result.  nondegenerate, f o r example.  and p  standard  q  vanish  i s the zero  simultaneously, arc.  Hypotheses  analogous to the b a s i c hypotheses i n [ 1 ] ,  f u r t h e r defense.  are  i n a c t i v e along  even i n the more g e n e r a l a treatment v e r y  H y p o t h e s i s 3 . 2 ( d ) has  every s o l u t i o n to form  P(.O)  g(t,x(t)) < 0  and  been d i s c u s s e d  s i m i l a r to t h a t  The  in section 4 .  and  0  x(')  We  above:  N  (')  must be  x(a)  t  in  and  [a,b]  have i g n o r e d  no  x(b)  ease  expense. Clarke's  multifunctions whenever the  arc  ° 1  solves  must pay  P(0) .  f o r our  Theorem 4 . 1 .  T h i s a d d i t i o n a l assumption r e p r e s e n t s  imprecise  The  standard  knowledge of the p e r t u r b a t i o n ' s  the p r i c e  which no  unavailable  other  r e s u l t uses t h e a d d i t i v e form of t h e  hypotheses a r e r e q u i r e d .  i n the g e n e r a l  we  structure in perturbations  to reduce the a u x i l i a r y problem ( c f . Lemma 4 . 4 ) to a f r e e - e n d p o i n t for  , permit  them to  analogue i n  ( i n t h i s case) t h a t the  c l o s e d at  problem  Active state constraints,  conceptual  o n l y h y p o t h e s i s of Theorem 4 . 1 which has  work i s 3 . 2 ( e ) , which r e q u i r e s (•)  .  for a l l  the n o t a t i o n a l burden i n t h i s t h e s i s a t l i t t l e  N  the  substan-  amounts to the assumption t h a t the s t a t e c o n s t r a i n t s d e f i n i n g the  P(0)  C  s e l e c t i o n of  of Theorem 4 . 1 a r e  and  3.4.3,  themselves when compared to those of the  3 . 2 ( a ) - ( c ) are s t r i c t l y  it  Theorem  stricter.  hypotheses Theorem 4 . 1 imposes on t h i s s p e c i a l case  A d d i t i v e endpoint p e r t u r b a t i o n s  then  ( 1 ) are  weaker.  Hypotheses  The  of c o u r s e , c o n d i t i o n s  of which s i t u a t i o n i s imposed by a s p e c i f i c  identical in spirit tially  cases,  problem  T h i s s p e c i a l i z e d approach i s  s e t t i n g of s e c t i o n 4 .  Nonetheless, Hypothesis  3.2(e) i s not a s e r i o u s f l a w i n our t h e o r y . holds a u t o m a t i c a l l y i f  (x(a)) * 0  intT C  x(-)  in Y .  As noted and  0  C  if N  (x(a)) C  0  or  N C  (x(b)) * 0  int T  The l a t t e r hypotheses a r e v e r y m i l d :  shows, they can o n l y f a i l  i n s e c t i o n 3.2, i t for a l l  l as Lemma III.5.2  (x(b))  contains a l i n e :  r  the  l  d e f i n i t i o n o f item 1.3.1 i n d i c a t e s t h a t the o n l y c l o s e d p l a n e s e t s int T (x) = 0  (below)  C  with  bear a c l o s e resemblance to one of t h e s e t s shown i n F i g u r e 1.  F i g u r e 1.  S i m i l a r geometric,  Typical sets  features  C  f o r which  i n t T (x) = 0 .  a r e r e q u i r e d to o b t a i n  i n t T (x) = 0 f o r Li  higher-dimensional  sets  C .  i s offered i n section III.5. h o l d s f o r a l l convex s e t s  CQ  A more d e t a i l e d d i s c u s s i o n o f t h i s For the present, and  hypothesis  i t s u f f i c e s t o note t h a t i t  , and f o r a l l s e t s whose  boundaries  are smooth, and f o r t h e g r e a t many o t h e r s e t s which do not d i s p l a y the pathologies i l l u s t r a t e d  i n F i g u r e 1.  Our t h e o r y  i s not s u b s t a n t i a l l y  weakened by e x c l u d i n g from c o n s i d e r a t i o n those problems whose s o l u t i o n s end at i n f i n i t e l y  sharp  p o i n t s of t h e c o n s t r a i n t s e t s .  In s h o r t , both t h e  hypotheses and the c o n c l u s i o n s o f Theorem 4.1 compare w e l l w i t h those of t h e standard  theory.  CHAPTER THE  III  FREE T I M E PROBLEM  FORMULATION  1 I. 1  Free Time  The  predetermined time i n t e r v a l  [a,b]  Chapter I I s u i t s many p r a c t i c a l problems p e r f e c t l y . when s e l e c t i n g an o p t i m a l  assumed throughout  I t a r i s e s , f o r example,  investment p o l i c y f o r a f i v e - y e a r economic p l a n .  However, not a l l problems permit  t h i s assumption.  R e a l i g n i n g the o r b i t  of  a space s a t e l l i t e u s i n g minimum f u e l , f o r i n s t a n c e , r e q u i r e s a c a r e f u l  choice  of the p l a n n i n g  allows  period.  The free  t h i s a d d i t i o n a l complication. P(u)  time problem  s t u d i e d i n t h i s chapter  I t reads as f o l l o w s :  inf{ f(a,x(a),b,x(b),u)  :  x(t)  e  F ( t , x ( t ) , u ) a.e.  [a,x(a),b,x(b),u] S i n c e the i n i t i a l and  t e r m i n a l times  a  and  p a r t of the s o l u t i o n , the o b j e c t i v e f u n c t i o n S  depend on them e x p l i c i t l y .  perturbation vector i n  R  must now  f  and  We  will  u  p e r t u r b a t i o n s by  i n v e s t i g a t i n g the g e n e r a l i z e d g r a d i e n t at  Clarke  := i n f P(u)  study the s e n s i t i v i t y of  and  constraint set  represents  a  P(0) 0  to such of i t s v a l u e  .  [1] d e r i v e s n e c e s s a r y  c o n d i t i o n s f o r o p t i m a l i t y i n the  turbed) f r e e time problem by r e d u c i n g I I . 2.4.  (unper^  i t to the f i x e d - t i m e case of Theorem  T h i s f a c t e x p l a i n s the s l i g h t l y s t r o n g e r hypotheses i n t r o d u c e d  corroborates  extensions  the s p i r i t of Theorem 3.3:  to f r e e - t i m e  as  s m a l l d e v i a t i o n s i n t o the  P(.O)  V(u)  ,  be determined  endpoint  nominal problem  function  .  which i n t r o d u c e s  [a,b]  S } .  £  b  Here, as i n Chapter I I ,  m  on  theorems.  known f i x e d - t i m e r e s u l t s  below,  allow  I. 2  Hypotheses  Throughout Chapter I I I , t h e d a t a o f problem  P  must  satisfy  hypotheses ( a ) - ( e ) . (a)  The c o n s t r a i n t s e t projection  (b)  S c RxR xRxR xR n  { [s,x] :  n  i s c l o s e d and nonempty. I t s  m  e S }  [s,x,t,y,u]  i s compact.  SQ  := i n f { s :  [s,x,t,y,u]  e S }  is finite;  t^  := sup{ t :  [s,x,t,y,u]  e S }  i s also  The m u l t i f u n c t i o n [SQ,^]  F(t,x,u)  ; i t s values  i s defined  This implies  that  we assume t h a t  finite.  on some tube ft c R x R x R n  a r e nonempty compact convex subsets o f R  n  on  m  .  F  is  i n t e g r a b l y bounded on ft , where i t i s a l s o j o i n t l y L i p s c h i t z of (constant)  rank  k  in  [t,x,u] k(t  another c o n s t a n t ft°xpB  for  . K := e  ( R e c a l l that t h i s c o n d i t i o n  defines  -s ) 0  0  some tube ft° c RxR  F has an e x t e n s i o n  .  n  .)  We assume t h a t  on  [s^jt^]  t o some tube c o n t a i n i n g  ft  and some  ft  has t h e form p>0 , and t h a t  which r e t a i n s t h e s e  properties. (c)  The o b j e c t i v e f u n c t i o n  f  i s L i p s c h i t z o f rank  on t h e s e t  S c (ft^xft^xpB) . (d)  Problem  P(0)  has a s o l u t i o n ; a l l s o l u t i o n s o f  hence s o l v e . P(0)  .  which the a d m i s s i b l e (e)  F o r every a r c  Here problem  arcs are confined  x ( * ) w i t h domain  the m u l t i f u n c t i o n  P(u)  [s,x,t,y,u]  P(0)  l i e i n ft , and  i s a v e r s i o n of  P(u) i n  to ft , j u s t as i n item  II.2.2.  [a,b] p r o v i d i n g a s o l u t i o n f o r P(0) ,  ->- Ng(s,x,t,y,u)  i s closed at the point  [a,x(a),b,x(b),0] .  2  MULTIPLIER  RULES FOR P C O )  Every s o l u t i o n t o t h e unperturbed f r e e time problem c e r t a i n necessary c o n d i t i o n s — t h e I I . 2.4.  free-time  conterparts  These c o n d i t i o n s a r e p r e s e n t e d i n C l a r k e  P(0)  must obey  o f those i n Theorem  [ 1 ] , but we o f f e r  slightly  more g e n e r a l turbed  statements here.  f r e e time problem a r e simply  1.2(a)-(d) i n t h e event t h a t is required. S  first  2.1  help  on  I t s conclusions  in  perfectly  F  r  £ = [£,n]  (b)  p:[a,b] -> R  transparent.  exceeding  lies n  Suppose  that  the arc  problem  x(t) e F(x(t))  a.e.  ,  [x(a),x(b)]  r := ( 2 K + 2)(1 + K an K) , there f  p , and a vector  in  £  such that conditions  e  is a  S } .  scalar (a)-(c)  3f(x(a),x(b)) .  is an arc obeying  H(x(t),p(t)) = 0  [p(a),-p(b)]  PROOF  II.2.4,  rule.  the Hamiltonian  [ - p ( t ) , x ( t ) ] e 3 H ( x ( t ) , p ( t ) ) a.e.  (c)  only  X + ||p| > 0 .  (a)  and  and t h e dimension o f the s e t  c l o s e l y resemble those of Theorem  the free-time  {0,1} j an arc  hold with  and  Note t h a t no form of (e)  C o n d i t i o n s — A u t o n o m o u s Case)  [a,b] solves  Then for any  f  e s t a b l i s h a general m u l t i p l i e r  min{ f ( x ( a ) , x ( b ) ) :  (P)  X  renders  Theorem (Necessary  x(*)  t h e obvious r e d u c t i o n s o f Hypotheses  does not appear. of  an unper-  r e s u l t d e a l s w i t h t h e case when t h e problem has no e x p l i c i t  time-dependence. will  hypotheses g o v e r n i n g  i n t h e d i s c u s s i o n t o f o l l o w , but new n o t a t i o n would  obscure what t h e c o n t e x t The  u  The argument l i s t s  change s l i g h t l y  and  The s t a n d a r d  e  a.e.  on  on  [a,b]  ,  [a,b] .  X[5,n] + r 3 d ( x ( a ) , x ( b ) ) s  A l t h o u g h both t e r m i n a l times  inclusion  a  and  b  . may v a r y  i n principle,  we  observe t h a t t h e v a l u e o f an a r c depends o n l y upon i t s shape:  any a d m i s s i b l e  arc  y'(t)  y ( ' ) on  d e f i n e d on  [a',b']  has t h e same v a l u e  [a'+T,b'+x] .  choice v a r i a b l e .  as the r e l a t e d a r c  I n s h o r t , o n l y t h e duration  b-a  := y ( t - t )  i s a significant  We t h e r e f o r e l o s e no g e n e r a l i t y i n assuming t h a t time  a  is  fixed.  Under t h i s assumption,  the v e r y same bookkeeping  prove Theorem II.2.4 reduces problem  P  d e v i c e used to  to an autonomous f r e e time  problem  f o r which a m u l t i p l i e r r u l e i s g i v e n i n [ 1 ] , C o r o l l a r y to Theorem 3.6.1. We  argue j u s t  as we  this multiplier  2.2  d i d i n Theorem II.2.4 to deduce the p r e s e n t theorem  rule.  •  Theorem (Necessary C o n d i t i o n s )  solves  the free-time  (P)  min{  Then for any p:[a,b] -> R (a)-(c)  n  hold  f(a,x(a),b,x(b)) r  exceeding  , a vector with  [a,5,x,n]  (b)  [h(t),-p(t),x(t)]  throughout  that  ||p||>  lies  such  v :=  :  the arc  x(*)  on  [a,b]  (2K^ + 2) (1 + K £n K) X  {0,1}  exist  such  an  that  arc conditions  3f(a,x(a),b,x(b)) .  e 9 H ( t , x ( t ) , p ( t ) ) a.e.  Chapter  in  there  0 .  in  that  [a,x(a),b,x(b)] e S } .  x e F ( t , x ) a.e.,  t, , and. a scalar  X +  £ =  an arc  Suppose  problem  (a)  is  from  on  [ a , b ] , where  h ( t ) = H ( t , x ( t ) , p ( t ) ) a.e. on III,  the generalized  gradient  h:[a,b] -> R  [a,b] .  of  H  (Here,  refers  and  to all  its  arguments,) (c)  t-h(a),p(a),h(b),-p(b)] e  PROOF time  Problem  P  is clearly  A[a,£,T,n]  + r3d (a,x(a),b,x(b)) . g  e q u i v a l e n t to the f o l l o w i n g autonomous f r e e -  problem: min{  f(x (a),x(a),x (b),x(b)) Q  Q  :  [x ,x] e { l } x F ( x , x ) , Q  Q  [x (a),x(a),x (b),x(b)j e S } , 0  whose H a m i l t o n i a n i s  H ( X Q , X , P Q , P ) = p^ + H ( X Q , X , P )  the s t a n d a r d hypotheses, and the a r c its  solutions.  vector  0  [x^(t),x(t)]  Consequently t h e r e e x i s t an a r c  C, , and a s c a l a r  X  in  {0,1}  such t h a t  . :=  T h i s problem [t,x(t)]  obeys  i s one of  [pQ,p]:[a,b] -> R x R  n  , a  conditions 2.1(a)-(c) hold.  PgCt) + H ( t , x ( t ) , p ( t ) ) = 0 a.e.  In p a r t i c u l a r , 2.1(b) i m p l i e s t h a t Upon d e f i n i n g  h ( t ) := - p ^ ( t ) , c o n c l u s i o n s ( a ) - ( c ) o f t h e p r e s e n t theorem  f o l l o w immediately. it  To see t h a t  cannot be z e r o . 0  For i f p  A + |p||  i s the zero a r c , then  = H(t x(t),p<t)) = -P (t) r  a.e. ,  Q  which i m p l i e s t h e absurd  must be p o s i t i v e , note that  conclusion that  A + |[PQ,P]| = 0 .  The theorem  stands.  3 3.1  •  SENSITIVITY  ANALYSIS  M u l t i p l i e r Sets  The reader who has endured t h e s l i g h t abuses o f n o t a t i o n  i n s e c t i o n 2 w i l l undoubtedly ism t o r e a d a b i l i t y .  f o r g i v e another  small concession of p e r f e c t i o n -  C o n d i t i o n s ( a ) - ( c ) below d e f i n e a m u l t i p l i e r s e t f o r the  p e r t u r b e d v e r s i o n o f the f r e e - t i m e problem i n t r o d u c e d i n s e c t i o n 1.  Though  these c o n d i t i o n s d i f f e r s l i g h t l y from those i n item II.3.3, we p e r s i s t i n calling  the present s e t M \ X ) a l s o .  We a r e p e r m i t t e d t o do so because  the c o n t e x t s i n which the d i f f e r e n t s e t s a r i s e a r e easy t o d i s t i n g u i s h ; we e x e r c i s e the o p t i o n because i t h i g h l i g h t s the analogy between the s e n s i t i v i t y r e s u l t s o f Theorem II.4.1 and those o f Theorem 3.3 below. For any s c a l a r the index all  A  A>0  and a r c x ( )  multiplier  quadruples  set (corresponding  [p,q,£, A]  (a)  C. = [a, 5, x, n, n']  Cb)  [p,q] : [a,b]  n  m  where  H(t,x,u,p)  x(*) )  M \ X ) c o n s i s t s of  .  i s an a r c obeying t h e i n c l u s i o n e  3H(t,x(t),0,p(t))  := sup{ <p,v> :  i s an a r c such t h a t  to  8f (a,x(a) ,b,x(b) , 0 )  lies i n  R xR  [a,b] a d m i s s i b l e f o r P ( 0 ) ,  satisfying conditions (a)-(c)..  [h(t),-pCt),-q(t),x(t)] L  on  -  v £ F(t,x,u)  h(t) = ff(t,x(t) , 0 , p ( t ) )  a.e. }  a.e.  and on  on  [a,b]  ,  h:[a,b] -> R [a,b]  .  (c)  For the g i v e n a r c  x(')  ,  o b t a i n e d from m u l t i p l i e r s Q[M (Y)]  =  A  u x Y  A[a,5»T,n»n'1 + N g ( a , x ( a ) , b , x ( b ) , 0 ) .  e  [-h(a),p(a),h(b),-p(b),-q(b)] Q[M (x)]  denotes the s e t of a l l v e c t o r s  A  [p,q»?,A]  c o r r e s p o n d i n g to  x( ) -  .  We  -q(a) also define  Q[M (x)] , A  e  where  3.2  Y i s the s e t o f s o l u t i o n s to  Nondegeneracy  multiplier in  .  J u s t as i n item II.3.4, the f r e e - t i m e problem  \=0  nondegenerate i f  P(0)  and  M (Y)  q(a)=0  imply  p=0  whenver  P  [p,q,?,A]  is is a  .  A  The n o t a t i o n e s t a b l i s h e d i n item 3.1  a l l o w s us to t r a n s c r i b e  the  s e n s i t i v i t y r e s u l t s of Theorem II.4.1 i n t o the f r e e - t i m e case.  3.3  Theorem  Under Hypotheses 1.2(a)-(e) and 3.2, one has  3V(0)  c!7{ QjNp'CY) ] n 3V(0)  =  If the oone Q[M^(Y)]  is pointed,  Q[M°(Y)] n 3°°V(0) }  +  the closure  operation  is superfluous  and  one also has co  3 V(0)  —r\  „  co  co{ Q [ t T ( Y ) ] n 3 V(0)  =  The proof of Theorem 3.3,  } .  l i k e i t s s t a t e m e n t , i s n o t h i n g but a t r a n s -  p o s i t i o n of the arguments i n s e c t i o n I I . 4 .  A very l i g h t  i t s content j u s t as w e l l as a r e p e t i t i v e account  of the  L i m i t i n g t e c h n i q u e s l i e a t the c o r e of Theorem 3.3, Theorem I I . 4 . 1 .  sketch w i l l  convey  details. j u s t as they do i n  The proof of Theorem II.4.1 d e a l s w i t h sequences of a r c s  d e f i n e d on a g i v e n i n t e r v a l  [a,b]  , and  invokes Theorem I I . 1 . 6 , r e p e a t e d l y .  However, i t never uses the a d d i t i o n a l f l e x i b i l i t y which the s e t s that t e c h n i c a l r e s u l t .  A^  g i v e to  For the f r e e - t i m e problem, the sequences of a r c s which  a r i s e i n the proof c a r r y a l o n g sequences of c o r r e s p o n d i n g i n t e r v a l s of definition  ^ i ' ^ ^  •  A c c o r d i n g to H y p o t h e s i s  1.2(a), we may  e x t r a c t subsequences i f n e c e s s a r y and assume t h a t  a. -*• a  immediately and  b_. -> b  for  some  SQ< a < b <  [a,b]  .  I f we then extend each a r c i n the sequence to  so t h a t i t s a t i s f i e s I I . 1 . 6 ( i ) , t h e Theorem may be a p p l i e d  with  A. := [a.,b.] n [a,b] .  1  T h i s s m a l l m o d i f i c a t i o n jJ u s t i f i e s a l l t h e  11  a p p l i c a t i o n s of Theorem II.1.6 i n t h e f r e e - t i m e Free t o a p p l y so w i t h abandon.  directly  case.  t h e l i m i t i n g arguments i n t r o d u c e d  i n Chapter I I , we do  I n c o n j u n c t i o n w i t h H y p o t h e s i s 1.2(d), such an argument  i m p l i e s t h a t e p l ' V ' i s I d e a l l y c l o s e d near [6 ,V(0) ] and t h a t an analogue o f :  H y p o t h e s i s 1.2(d) h o l d s  i n a neighbourhood o f  0  (compare Lemma I I . 4 . 2 ) .  We may t h e r e f o r e c a l c u l a t e t h e g e n e r a l i z e d g r a d i e n t s o f  V . at  0  straight  from t h e i r d e f i n i t i o n s .  R o c k a f e l l a r ' s p r o p o s i t i o n (II.4.3) a i d s i n t h i s  i t s t e c h n i c a l hypothesis  f o l l o w s j u s t as i n Lemma II.4.6.  i s to i n v e s t i g a t e t h e p r o p e r t i e s o f a normal v e c t o r a sequence o f p e r p e n d i c u l a r s  [0,0]., as such p e r p e n d i c u l a r  [v.^,-8^] ± e p i V  f '~^0'' v  0  [v^,-g  ]  =  at  i " " ^ ! Jfv^-Bj |  A l l t h a t remains  '• o ~^0'' v  task  ,  0 D t a  lned  from  [ u ^ , ^ ] -* [0,V(0)] ,  '  E  x  a  m  i  n  i  n  8 J  u  s  t  o  n  e  l e a d s t o an a u x i l i a r y f r e e - t i m e problem without  p e r t u r b a t i o n through P r o p o s i t i o n 1.2.4; t h e n e c e s s a r y c o n d i t i o n s 2.2 y i e l d a corresponding  quadruple  l i e f we r e q u i r e  (compare Lemma I I . 4 . 4 ) .  II.1.6 serve t o r e c o v e r vector The  [VQ,~BQ]  [p^>q^»£^,A^]  which s t r o n g l y resembles t h e multipV. S e v e r a l a p p l i c a t i o n s o f Theorem  s i m i l a r m u l t i p l i e r conditions i n v o l v i n g the l i m i t  (Lemma I I . 4 . 5 ) — t h i s i s where nondegeneracy i s e s s e n t i a l .  formulas i n t h e theorem merely r e s t a t e these c o n d i t i o n s .  overview o f t h e p r o o f .  Here ends our  4  APPLICATION:  THE  MINIMUM  TIME  PROBLEM  To s o l v e the minimum time problem, one must i s o l a t e an F - t r a j e c t o r y which t r a n s f e r s a g i v e n  initial  point  v  to the o r i g i n i n l e a s t time.  The minimum time i t s e l f v a r i e s w i t h t h e s t a r t i n g p o s i t i o n , thereby d e f i n i n g the f u n c t i o n  T:R  T(v)  -> R y  n  :=  {+°°} v i a  inf{ T :  x(t)  F ( t , x ( t ) ) a.e.  €  x(0) = v , In a p p l i c a t i o n s , t h e o r i g i n of  R  x(T) = 0 } .  often represents  n  the o p e r a t i n g  an e l e c t r i c a l o r mechanical system i n which d e v i a t i o n s must be c o r r e c t e d  [0,T],  on  as q u i c k l y as p o s s i b l e .  from the nominal  The g e n e r a l i z e d  r e l a t e s the s e n s i t i v i t y o f t h e minimum t i m e - v a l u e to s m a l l initial  deviation  f(a,x(a),b,x(b),u)  V  :=  [0,v,0,0,0] +  :=  3T(v)  changes i n the  v , Theorem 3.3 a l l o w s us to e v a l u a t e  , where t h e d a t a d e f i n i n g  S  gradient  state  v .  For f i x e d nonzero 9V(0)  point of  3T(v)  as  are b ,  u  ({0}x{u}xRx{0}x{ }) , u  u R e  and  a multifunction  F(t,x)  For any F - t r a j e c t o r y the c o n d i t i o n s  independent of [0,T]  x(«) on  defining a multiplier  (a)  r, = [ 0 , 0 , 1 , 0 , 0 ]  (b)  [h,-p,x](t)  u .  with  x(0)=v  [Pjq,?»A]  in  and  M (x) A  x(T)=0 , r e a d i l y imply  ,  e 3H(t,x(t),p(t))  and  q(t) = 0  a.e. on [0,T] , where  h ( t ) = H ( t , x ( t ) , p ( t ) ) a.e. , and Cc)  [-h(0),pC0),h(T),-p(T),-q] : e  AtO',0,1,0,0] + N (0,v,.T,0,0) . s  The a n a l y s i s o f s e c t i o n 1.7 a l l o w s us t o compute N  =  u ,(Rx{u}x{0}xRx{- }) t  U£R  u  f o r any  base p o i n t i n  S .  1..2(e)).  Also, condition  defining  V  the  Thus  N  i s a closed m u l t i f u n c t i o n  (c) i m p l i e s  q=p(0)  so the  i s nondegenerate (Hypothesis 3.2).  (Hypothesis  perturbation  These c o n d i t i o n s  l e a d to  expression Q[M (x)] A  =  { -p(0)  :  [h,-p,x] e 9H(t,x,p) a.e.  on  [0,T]  ,  h(t) =H(t,x(t),p(t))  on  [0,T]  ,  h(T) Under Hypotheses 1.2(a)-(d) we 9T(v)  =  9V(0)  =  may ^o~{  = X } .  apply  Theorem 3.3  f i n d that  T  This implies  X=0  implies  v  , with  9T(v)  9T(v)  c  { -p(0)  :  f o r some s o l u t i o n w i t h x(0)  •  p=0  (this w i l l  Q[M°(Y)] = {0}  = co{  (as i n C o r o l l a r y II.5.2) the a t t r a c t i v e  ext  Q[M (Y)] A  about 9T(0)  inclusion x  on  = v, p:[a,b] -»• R  [0,T(v)] n  are defined  obeys  •• for.some a r c : . h / : s . t . h(T(v))  of s e n s i t i v i t y developed here cannot p r o v i d e  , s i n c e the  we  1  h ( t ) = H ( t , x ( t ) , p ( t ) ) a.e.,  information  and  be  Q[M (Y)]n9T(v) } .  [h,-p,x] e 9H(t,x,p)  Note t h a t the theory  expression  1  0 e i n t F ( T ( v ) , 0 ) ) , then  i s L i p s c h i t z near  to d e r i v e the  Q[M (Y)]n9V(0) + Q[M°(Y) ] n9°°V(0) ;, } .  I f the data of the problem are such t h a t the case i f , f o r example,  a.e.  " s o l u t i o n a r c s " r e q u i r e d to  on the degenerate i n t e r v a l  [0,0]  .  define  = 1 } . any  5  ENDPOINT P E R T U R B A T I O N S AND Each of the  three  NORMAL CONES  s p e c i f i c perturbation  and  I I I . 4 ) p r e s e n t s endpoint c o n s t r a i n t s  for  some g i v e n m u l t i f u n c t i o n  the mold of problem S • :=  P  u  i f we  (C(u)  u R  C:R  i n the form  RxR xRxR  m  n  take {u})  x  a n a l y s e s above ( s e c t i o n s  S  to be  n  .  [a,x(a),b,x(b)]  II.5 C(u)  e  Such c o n s t r a i n t s f i t i n t o  the graph  of  C :  .  m  e  The  reverse  approach i s p o s s i b l e too:  c o n s t r a i n t s may  be  recast  i s the graph  set  S  i s given,  the  endpoint  as  [a,x(a) ,b,x(b) ] S  i f the  C(u)  e  :=  of the m u l t i f u n c t i o n  { [a,x,g,y] : so d e f i n e d .  [;a,x,g,y,u]  Hence the  S  e  } ;  formulation  of endpoint c o n s t r a i n t s i n terms of a m u l t i f u n c t i o n , which a r i s e s n a t u r a l l y in  the  examples s t u d i e d above, r e t a i n s a l l the g e n e r a l i t y i n h e r e n t  formulation  of problem  P  .  have such simple s t r u c t u r e s ( s e c t i o n 4) reverses  The that  s p e c i f i c multifunctions N ( ) -  g  the  spirit  of our  a p r e a s s i g n e d endpoint p e r t u r b a t i o n it  seeks to impose c o n d i t i o n s  closed To  C  This  section  i n s t e a d of t r y i n g to prove that S  has  a well-behaved normal cone,  which w i l l guarantee t h a t  N  g  is a  multifunction. s i m p l i f y the n o t a t i o n ,  multifunction of  on  scheme  automatically  (item I I . 5 . 5 ) .  previous studies:  the  a n a l y s e d above a l l  i s either closed  o r by m i l d a u x i l i a r y hypotheses  in  T:R  m  -> R , n  we  i n v e s t i g a t e an upper semlcontinuous  whose graph i s  G  :=  { [x,y]  C .  modulo an  insignificant  permutation of  components  :  ye  F'(x) }j  instead  56.  5.1  Example  compact convex s e t s , but whose graph be c l o s e d at t h e o r i g i n . the  We  G  whose v a l u e s a r e  has a normal cone which f a i l s to  r(u)  define  R  :=  [0,f(u)]  , where  f:R -> R  is  p i e c e w i s e l i n e a r f u n c t i o n which l i n e a r l y i n t e r p o l a t e s t h e f o l l o w i n g  {  f(t)  r  The m u l t i f u n c t i o n  bounded by the x - a x i s  0  if  Now  n  and the graph o f  2.  IT/4  N (0,0) = {0}xR G  radians,  (-0,0] u  n  {2  n an  integer}  f  2  as shown i n F i g u r e  The graph o f  the d e f i n i t i o n i n item 1.3.1  , but t h a t  through  t e  values:  = 1, i 2, i 4" s e v i d einft l yt L= i p3s.c2h~i t"z ; f i ot rs n graph s t 3, he . r e.g i o n  Figure  n>2  r:R  Here i s a L i p s c h i t z m u l t i f u n c t i o n  .  i t defines  r  shows t h a t  N (2 , 0 )  (at l e a s t near  = R  n  Worse y e t , i f the s e t  m u l t i f u n c t i o n which i s compact-convex-valued  2.  G  2  for a l l  i s rotated  [0,0]) the graph of a  and L i p s c h i t z and has a compact-  convex-valued L i p s c h i t z " I n v e r s e , "  but whose normal cone s t i l l  m u l t i f u n c t i o n which i s not c l o s e d a t r  function  but  [0,0]  .  r ^(y)  i s the m u l t i f u n c t i o n  (The  defines a  " i n v e r s e " of a m u l t i y e r(x)  } .)  •  Example 5.1 shows t h a t a m u l t i f u n c t i o n may obey s e v e r a l s t r o n g  hypotheses,  stubbornly  I t does not,  := { x :  r e f u s e t o generate a graph w i t h a well-behaved normal cone.  however, u n e a r t h a s e r i o u s shortcoming i n our t h e o r y .  F o r no  p e r t u r b a t i o n problems o f i n t e r e s t i n v o l v e a c o n s t r a i n t m u l t i f u n c t i o n l i k e Why?  Loosely  speaking,  r - i s u n a c c e p t a b l e because i t has,  no u-dependence near z e r o . r  order,  To see t h i s , observe t h a t t h e L i p s c h i t z rank of  can be made a r b i t r a r i l y s m a l l by r e s t r i c t i n g  s m a l l e r neighbourhoods o f  to f i r s t  T .  0 .  The f l a w s  t h e domain o f  r  of  r  to ever  w i l l become even more  apparent as our study proceeds.  5.2  Lemma  Let  conditions  G  be a closed  (a) and (b) ave equivalent.  the multifunction  N (•) is closed  (a)  G i n t T (z) * 0 . G  Cb)  N (z)  that  According N (•) G  (a => b) in R  m + n  T (z) (j  R  m + n 3  Moreover,  and let  either  zeG .  Then  of them implies  that  at z .  If  t o Theorem 2.5.8 ( C o r o l l a r y 2) o f [ 1 ] , c o n d i t i o n (a)  i s closed a t  z .  We need o n l y  show  must imply  v=0 .  v e N (z) — i m p l i e s G no l i n e :  (Otherwise  Hence  <v,w> < 0  T (z) l i e s G for a l l  -v i N (z) G  u n l e s s v=0 .  by d e f i n i t i o n ,  N (z) is r  implies  (a) <=> ( b ) .  i n t T (z) * 0 , then the a s s e r t i o n t h a t  , which i s absurd.)  contains  of  is pointed.  G  PROOF  subset  <v,w> = 0  for a l l  w  i n a proper subspace o f w  i n T (z) — t h a t i s , G  In.other words, pointed.  N (z) (J  (b =>  a)  If  i n t T (z) = 0 , then G  Every l i n e i n the o r t h o g o n a l N (z) G  i s not  Corollary set  with  PROOF  If  G  is  lies  n  i n a proper subspace of  complement of t h i s subspace l i e s  either  E i t h e r hypothesis  set  with  nonempty interior  c o n d i t i o n 5.2(a) holds  have an a p p e a l i n g  epi-Lipschitzian A:R  n  -»- R  i f and  n  "'"xR  at  R x  smooth  and  n  geometric s i g n i f i c a n c e .  G  has  I t t e l l s us  x  in  C .  The  set  i f t h e r e are an i n v e r t i b l e l i n e a r U  of  that  the same form ( l o c a l l y ) as  To s i m p l i f y the n o t a t i o n , we  a point  , a neighbourhood  •  ( r e p o r t e d i n [1]) adds even more  only i f  of a L i p s c h i t z f u n c t i o n . of  or a  N (•) is closed at z . G implies that N (z) i s pointed. G  i n s i g h t i n t o the shape of a s e t s a t i s f y i n g these c r i t e r i a .  C  N (z) , so G  then  f o l l o w i n g r e s u l t of R o c k a f e l l a r ' s  c l o s e d subset  m + n  •  a convex  c o n d i t i o n s of Lemma 5.2  epigraph  in  R  Contrapose.  nonempty interior,  The The  pointed.  T (z) G  x , and  a function  C  consider  the a  is . -  transformation <Ji:R ^ -> R n  such t h a t U n C and  ij)  5.3  Theorem  following  U n A  =  _ 1  (epi  i s L i p s c h i t z hear the  two  (a)  int T (x)  (b)  C  c  Let  C  <f>) R  be a closed  assertions  are  n  ''"-component of subset  R  n  , and  . let  xeC  .  Then  the  equivalent.  * 0 .  is epi-Lipschitzian  at  x .  More s p e c i f i c r e s u l t s e n s u r i n g  elusive.  of  A(x)  S u b s t a n t i a l progress  that  N_, G  i s a closed  multifunction-seem  i s p o s s i b l e , however, i n the v e r y  s i t u a t i o n where the c o n s t r a i n t s e t i s determined by a system of  common inequalities.  r  Consider the multifunction r(u) where each  m  If a point  :=  then  { y n  :  Let  f (u,y)<0 } ,  i s Lipschitz.  r  -> R  u  2  k  The graph of  i s simply the set  { [u,y] : f ^ u . y ^ O , f (u,y)<0, . . ., f (u,y)<0 } . 2  r  as above, with  i e 1(0,y) }  is closed  k  i s given, we define  be given  { 9f^(0,y) : N (•) G  f ( , y ) < 0 , f (u,y)<0, . . 1  [0,y] i n G  Theorem  vectors  =  f^:R xR G  5.4  :  defined by  at  1(0,y) : = ' { i : .  If the set of  linearly  independent,  y e 1(0)  is positively  f^(0,y)=0 } .  [0,y] .  A  PROOF  l(0,y) = 0 , then the indicated set of vectors i s empty and  If  t r i v i a l l y p o s i t i v e l y l i n e a r l y independent. so  [0,y] e i n t G  and  N (*,•)  reduces to  But also {0}  f (0,y) < 0 i  for a l l i ,  on a neighbourhood of  "  G  f0,y] .  The conclusion follows.  Define f  We therefore assume  f(u,y) := max( f^(u,y) :  i s L i p s c h i t z near G  i=l,2,...,k  }.  1(0,y) * 0 . I t i s easy to see that  [0,y] , and that  = ' { [u,y] :  f(u,y) < 0 = f(0,y) } .  Now by Proposition I". 6. 7, 3f(0,y)  c  C O  {  9f (0,y) : ±  By assumption, the right-hand independent: 0 i  9f(0,y) .  i t follows that  i e 1(0,y) } .  side of this i n c l u s i o n i s p o s i t i v e l y l i n e a r l y 9f(0,y)  i s too, and i n p a r t i c u l a r that  Theorem 2.4.7 (Corollary 1) of [1] therefore applies; i t  asserts that N„(0,y)  c  G  But the right-hand  u r9f(0,y) . r>0  side contains no l i n e , because  l i n e a r l y independent.  Hence  3f(0,y) i s p o s i t i v e l y  N (0,y) i s pointed, and the desired conclusion G  follows from Lemma 5.2.  D  Corollary  N  (0,y)  c  u r£0  G  The  e KO,y)  there  v  in  constraint  £  in  8^(0,^)  .  reduction  be  such t h a t whenever  m + n  .  c l o s e l y r e l a t e d to the well-known  qualification  of  Of  Mangasarian-Fromowitz  (unperturbed) mathematical programming.  reduces to t h i s c o n d i t i o n i f each f u n c t i o n u  R  may  ,  This i s very  of  1 e 1(0,y) } .  1  i s a vector  <v,s> < 0 f o r a l l  it  8f,(0,^) :  p o s i t i v e l i n e a r independence r e q u i r e d by P r o p o s i t i o n 5.4  expressed as f o l l o w s : i  r co{  f^  i s smooth and  course, u-dependence i s t h i s t h e s i s ' s raison  serves  to show that  weaker than the standard  d'etre,  the h y p o t h e s i s of P r o p o s i t i o n 5.4  constraint q u a l i f i c a t i o n .  For  Indeed,  independent but  this  i s even  the many d i f f e r e n t  u-dependences p o s s i b l e i n the c o n s t r a i n t f u n c t i o n s make the p o s i t i v e l i n e a r independence of { V f.(0,y) : set  1(0)  { Vf^(0,y) : i  e  1(0,y) } .  s a t i s f i e s the  i e 1(0,y) }  even more l i k e l y than t h a t of  In p a r t i c u l a r , i f the unperturbed  constraint  (unperturbed) Mangasarian-Fromowitz c o n d i t i o n ,  the h y p o t h e s i s of the p r o p o s i t i o n h o l d s a u t o m a t i c a l l y .  Mathematical  programmers invoke the c o n s t r a i n t q u a l i f i c a t i o n to ensure t h a t the d e f i n i n g the f e a s i b l e s e t are not P r o p o s i t i o n 5.4 s t r a i n t s and The  somehow degenerate:  constraints  the h y p o t h e s i s of  seeks o n l y to a v o i d degeneracy i n the combination of con-:,  perturbations.  c o n s t r a i n t s e t s of Example 5.1  be a v o i d e d .  then  V  The m u l t i f u n c t i o n  P r o p o s i t i o n 5.4,  with  f 2 ( u , y ) := y - f ( u )  .k=2  , where  .  To f  I t i s a simple matter to compute  i l l u s t r a t e the degeneracy which must  defined see  t h e r e has  t h i s , take  the form t r e a t e d  f ^ ( u , y ) := -y  i s the f u n c t i o n c o n s t r u c t e d 3 f ( 0 , 0 ) = {[0,-1]} 1  and  by  and  i n Example  5.1.  8f (0,p)={[0,+l]}. 9  These s e t s c l e a r l y f a i l  to be p o s i t i v e l y l i n e a r l y  q u a n t i t a t i v e i n d i c a t i o n t h a t the m u l t i f u n c t i o n i n v o l v e s an u n a c c e p t a b l e p e r t u r b a t i o n  structure.  T  independent of Example  CHAPTER I V APPLICATIONS  1 1.1  CONTROLLABILITY Admissible Arcs  S m a l l changes i n t h e d a t a d e f i n i n g a d i f f e r e n t i a l  i n c l u s i o n problem n e c e s s a r i l y i n d u c e v a r i a t i o n s i n t h e problem's admissible arcs. A(u)  I n t h i s s e c t i o n , we i n v e s t i g a t e t h e admissible  :=' { x  e  AC[a,b] :  x(t)  e  s a t i s f y Hypotheses  e  S } .  We as sume t h a t  F  empty, t h e n no  F - t r a j e c t o r y j o i n s an a c c e p t a b l e p a i r o f i n i t i a l and t e r m i n a l  states.  S  sets  F ( t , x ( t ) , u ) a.e. on [a,b] ,  [x(a),x(b),u] and  family of  II.3.2(a)(b).  I f A(u) i s  Systems and c o n t r o l e n g i n e e r s e x p r e s s t h i s unhappy o c c u r r e n c e by  s a y i n g t h a t t h e d y n a m i c a l system d e f i n i n g  A(u)  i s not  controllable.  P r o p o s i t i o n 1.4, below, advances a c o n d i t i o n w h i c h ensures t h a t n o n v o i d — t h a t i s , t h a t t h e system d e f i n i n g near  0 .  A(u)  A(u) i s  is c o n t r o l l a b l e — f o r  The b a s i c approach i s due t o C l a r k e ( [ 1 ] , see s e c t i o n 3.5).  u It  r e l i e s h e a v i l y on t h e s e n s i t i v i t y a n a l y s i s o f Chapter I I . C o r r e s p o n d i n g _ r e s u l t s f o r problems w i t h f r e e t i m e p e r m i t a c l o s e l y analogous but r e q u i r e more n o t a t i o n .  - 62 -  treatment,  1.2  Normality  An a r c x ( . )  II.3.4 h o l d when  Y  i s replaced  (a)  [-p(t),-q(t),x(t)]  (b)  [p(a),-p(b),-q(b)]  imply t h a t  q(a)=0 .  and  :=  by  i s normal i f Hypotheses 11.3.2(e) and  {x(.)} , and i f t h e two c o n d i t i o n s  e gH(t,x(t),0,p(t))  a.e.  on  [a,b]  and  N (x(a),x(b),0)  e  g  (By II.3.4, i t f o l l o w s  When an o b j e c t i v e f u n c t i o n V(u)  i n A(0)  f  i s given,  i n f { f(x(a),x(b),u)  that  p=0  i t defines :  a c o r r e s p o n d i n g o p t i m i z a t i o n problem  and  q=0 .)  a value  function  x ( 0 e A(u) } P .  We say t h a t  P  i s normal  i f H y p o t h e s i s 11.3.4(d) h o l d s and each o f t h e a r c s s o l v i n g  P(0) i s normal.  1.3  near zero.  PROOF  Lemma  If problem  If  P  P  is normal, then  i s normal, then  V  is Lipschitz  Q[M°(Y)] = {0}.. Apply Theorem 4.1,  C o r o l l a r y 1.  1.4  •  Proposition  are positive is an arc  Suppose the arc  constants x(»)  in  [x - x ^ PROOF  and  A(u) =.  Its values  :=  the problem d e f i n i n g  such  |x(t) - x ( t )  inf{ /  are clearly  M  P  is normal.  that for each  u  Then there  in  eB , there  b  I dt  <  M|u| .  m  |x(t) - x ( t ) | dt : When  x ( - ) e A(u) } .  u=0 , t h e unique solution..to  i s x(«) ; i t f o r c e s  may a l s o be expressed as t h e v a l u e  i n c l u s i o n problem  A(0)  V:R'->- R u" {+»} d e f i n e d by  nonnegative. V(0)  in  such that  Consider the f u n c t i o n V(u)  V  z  x(«)  V(0) = 0 .  The f u n c t i o n  f u n c t i o n of t h e p e r t u r b e d  whose d a t a i n c o r p o r a t e  differential  a s c a l a r a r c x ( * ) as f o l l o w s . n  f(x ,x,y ,y,u) 0  F(t,x ,x,u)  :=  0  S The a r c  :=  0  :=  y  Q  {|x - x ( t ) | } x F ( t , x , u )  { [0,x,r,y,u] :  [x,y,u] e S ,  r e R }  [0,x(*)]_ i s the unique s o l u t i o n to problem  P(0) .  Hypotheses I I . 3 . 2 ( a ) - ( d ) e v i d e n t l y h o l d f o r problem below w i l l  e s t a b l i s h Hypothesis  Any m u l t i p l i e r the t r a n s v e r s a l i t y  P ; the analysis  11.3.2(e).  [pQ>P»q,C,A]  corresponding to  [0,x(«)l  must obey  condition e  [ p ( a ) , p ( a ) , - p ( b ) -,-p(b),-q(b)] Q  Q  A[0,0,1,0,0,0] + N (0,x(a),0,x(b),0) . s  Upon computing N (0,x,y,r,u) = { [s,£,0,n,n' ] :  U,n,n'] e Ng(x,y,u),  g  we f i n d t h a t t h i s i m p l i e s (i)  P Q ( ° ) = -X and  [p(a),- (b),-q(b)] P  H(t,x ,x,u,p ,p) 0  N (x(a),x(b),0) .  £  The H a m i l t o n i a n f o r problem 0  seR } ,  s  P is =  p | x - x ( t ) j + H(t,x,u,p) . Q  By P r o p o s i t i o n 1.6.6, 3H(t,0,x(t),0,p (t),p(t))  c  0  { [0,5, ,0,ri] Y  The H a m i l t o n i a n i n c l u s i o n i m p l i e s (ii)  {0} x p ( t ) B x {[0,0,0]} + Q  U , Y , u ] e 3H(t,x(t),0,p(t))  :  PQ(*)  =  _  A  A N C  *  [ - p ( t ) , - q ( t ) , x ( t ) ] e ABx{[0,0]} + 3H(t,x(t),0,p(t))  a.e.  }.  Now adjoint  if  A=0  , conditions  ( i ) and  component of a m u l t i p l i e r  ( i i ) above e x h i b i t  in  M^(x)  .  [p,q]  S i n c e the a r c  x  as the i s non-.  degenerate by assumption, H y p o t h e s i s II.3.4 h o l d s f o r t h e problem introduced here. hence and  [0,x(«)l V  Moreover,  i s a normal a r c as d e f i n e d i n item 1.2,  i s normal f o r problem  P .  Thus  i s L i p s c h i t z near zero by Lemma 1.3.  p o s i t i v e constants M|u| Thus f o r any  M  u  EXAMPLE:  and  e  in  fl  i s a normal problem,  In p a r t i c u l a r , t h e r e a r e  =  V(u)  for a l l  eB , t h e r e i s some a r c =  P  and  such t h a t  |v(u) - V ( 0 ) |  >  fx -  2  x  P  |x(t) - £ < t ) | dt  x(*) <  u  in  in  M|u|  eB .  A(u)  such that  .  A ONE-SECTOR ECONOMY  C o n s i d e r a f a c t o r y manager's problem as he s i t s down to p l a n h i s c o r p o r a t e s t r a t e g y f o r t h e f i x e d time p e r i o d f a c t o r y i s measured  by i t s p r o d u c t i v e c a p a c i t y  instant, a certain fraction  u(t)  [0,T] .  The s t a t e of h i s  x(t)  a t time  t .  o f t h e f a c t o r y ' s p r o d u c t i v e e f f o r t may  a p p l i e d toward i n c r e a s i n g i t s c a p a c i t y f o r p r o d u c t i o n : the r e s u l t c a p a c i t y grows a c c o r d i n g to the law i s t o be s o l d a t a f i x e d p r i c e :  At each  x(t) = u(t)x(t)  .  be  i s t h a t the  The remaining output  the t o t a l p r o f i t s over the i n t e r v a l  [0,T]  T amount t o fraction  ( l - u ( t ) ) x ( t ) dt . u(t)  in  The manager's o b j e c t i v e i s to choose the  [0,1] to maximize h i s company's p r o f i t :  i t can be posed  as the f o l l o w i n g o p t i m i z a t i o n problem. max{  /J  ( l - u ( t ) ) x ( t ) dt :  x(t) = u(t)x(t)  ,  0 < u(t) < 1 ,  x(0) = c > 0 } T h i s problem i s a s i m p l i f i e d v e r s i o n o f the Ramsey model f o r a o n e - s e c t o r economy p r e s e n t e d i n Fleming and R i s h e l  [ 2 ] , Example I I . 2 . 2 .  I t can be  solved d i r e c t l y  i n s e v e r a l ways; P o n t r y a g i n ' s maximum p r i n c i p l e w i l l  yield  a unique c a n d i d a t e f o r the s o l u t i o n , f o r example. Suppose now no  t h a t the f a c t o r y manager r e v i s e s h i s o b j e c t i v e :  l o n g e r wants to maximize h i s t o t a l p r o f i t s , but  the present  rate i s  max{  /  e  Q  6 , he  the p l a n n i n g  ( l - u ( t ) ) x ( t ) dt  :  x(t) = u(t)x(t) , = c > 0  0 < u(t) < 1 ,  } .  propose to e s t i m a t e the s e n s i t i v i t y o f h i s expected r e t u r n as  near z e r o .  To do  V(6)  so, we  :=  d e f i n e the v a l u e  -/J  min{  e  period.  seeks  x(0) We  r a t h e r seeks to maximize  v a l u e of the revenue he w i l l g a i n d u r i n g  I f the d i s c o u n t  he  _ < S t  <5  varies  function  ( l - u ( t ) ) x ( t ) dt  :  x(t) = u(t)x(t) , 0 < u(t) < 1 , x(0)  (V measures the n e g a t i v e how  t h i s optimal  problem, and  how  c o n t r o l problem can be  say,  can d e f i n e a s w i t c h i n g  optimal  T>1  strategy  {  Pontryagin's p r i n c i p l e . time  x := T + ^- £n(l-6)  u ( t ) = 1 j.^ ^ - j ^  ce~  c(l-6)  1 / 6  e  T  Our  study w i l l show  9V(0)  .  To make the  .  t h a t the c o n t r o l problem d e f i n i n g  d i r e c t l y by a p p l y i n g , one  assume  > 0 } .  c a s t as a d i f f e r e n t i a l i n c l u s i o n  Theorem II.4.1 a p p l i e s to c a l c u l a t e  problem i n t e r e s t i n g , we Note f i r s t  of the f i r m ' s maximum p r o f i t . )  = c  •  T  h  e  productive  on  [0,x]  on  [x,T]  V(.S)  can be  solved  A f t e r some c a l c u l a t i o n , and  discover  the  c a p a c i t y obeys  The a d j o i n t t r a j e c t o r y comes to u-6)/6  r  a-syi,  L(l-o) P ( t >  *  =  "  t  1  To express  V  -t  r n  on  [0,x]  r  - e  )  the ( n e g a t i v e ) present v a l u e i s L'Hospital's rules give  ] e  "^  6t  (e  j  e  V(5) = -c(l-<5)  V(0) = - c e  T - 1  and  (1—(5)/6  V'(0)  TI  [T,T]  on  e  ;  (1—6)T  = -c(^-T)e  as the v a l u e f u n c t i o n of a d i f f e r e n t i a l  '. .  T _ 1  inclusion  problem, d e f i n e f(x ,x,y ,y,S) 0  0  F(t,x S := Then  ,x,6)  := - y  ,  Q  := { [e~  x(l-v),xv] :  0 < v < 1 } , and  {[0,c]}xRxRxR .  V(fi) = min{  f(  X()  ( 0 ) ,x(0) , x ( T ) ,x(T)) :  [x ,x]  Q  e F(t,x ,x,6)  Q  Q  ,  [x (0),x(0),x (T),x(T)]£S } . 0  0  The H a m i l t o n i a n i s —St f / ( t , x , x , <S,p ,p) = max{ Q  p e  Q  Q  <5t  x ( l - v ) + pxv  :  —  = p^e  = p^e  x + max{  x + max{px - p^e  —6t ,  r = max{px , P Q £ I t i s even e a s i e r to compute and  9f = {[0,0,-1,0,0]} Now  to compute  to p r o h l 6m  P(0)  N  g  v(px - p^e  0 < v < 1 }  —St  x)  :  x , 0} ,  X } = x«max{p , p^e  = RxRx{[0,0,0]}  0 < v < 1 }  _  St, }  at any base p o i n t i n  S  everywhere.  8V(0) u s i n g Theorem 4.1,  we  need o n l y c o n s i d e r s o l u t i o n s  — t h a t , i s , the easy pirobXem i n which no d i s c o u n t r a t e appears.  And any a r c s o l v i n g  P(0)  has a n o n t r i v i a l m u l t i p l i e r  C o r o l l a r y 2 of Theorem I I . 4 . 1 . a r c and H  [pQ,p,q,C,A]  has no  So suppose  -p^ = 0 .  implies that  0  p^  [XQ(«),X(«)]  i s ah  admissible Then  since  The t r a n s v e r s a l i t y c o n d i t i o n e  [p ,p(0),-p ,-p(T),-q(T)]  by  s  the c o r r e s p o n d i n g n o n t r i v i a l m u l t i p l i e r .  x^-dependence,  0  [pQ»P q,?»A]  A[0,0,1,0,0] + RxRx{[0,0,0]}  i s the constant a r c  A. , and t h a t  p(T) = q(T) = 0 .  With t h e a i d of P r o p o s i t i o n 1.6.7, we f i n d t h a t t h e H a m i l t o n i a n i n c l u s i o n implies  •  [0,A,-Atx,x,0]  •• •  if  p  0 ,0,x]  if  p > A  convex h u l l of t h e s e  if  p = A  [0>-p -q,x ,x] e 3 n ( t , x , x , 0 , p , p ) = < [0,p, 5  0  0  0  <;A  »  Now  when  A=0  , -q=0  Q[M°(Y)] = {0} implies that x = x x  Q  on  on  = x(T)  .  We may  p = -1  [0,T-1] on  [T-1,T] .  implies  therefore  on and  q=0  .  The m u l t i p l i e r i s t r i v i a l  take  A=l  [T-1,T] , w h i l e x = 0  [T-1,T] .  We  on  .  Then  -p = p  also obtain  q = 0  p(T) = 0 < 1 = A  on  [T-1,T] , w h i l e on  [0,T-1] . x  Q  1 ..for problem  {  e ^  P(t)  P(0) .  1  T - t x(t) =  I  ce  T-l  ^  on  [0.T-1]  on  [T-1,T]  on on  [0,T-1] [T-1,T]  = 0  [0,T-1]  Upon i n t e g r a t i n g t h e s e e q u a t i o n s , we f i n d  i p l i e r of index  and  on and  Consequently [0,T-1]  and  q = tx(t)  t h e unique multt-  69.  x ( 0  t ) =  l  V.  {  on  [0,T-1]  T - l . T+l) ce (t-  on  [T-1,T]  ce ^(^-T)  on  [0,T-1]  on  [T-1,T]  T  T 1  W  Hence  T-l -q(0) = -ce (h-T)  (t -T ) 2  2  i s the o n l y p o i n t i n  —1 Q[M (Y)] .  I t follows  T-l that  8V(0) = {-c(^-T)e  than t h a t r e q u i r e d to f i n d  } .  The a n a l y s i s of t h i s  V(6)  case i s much  d i r e c t l y and then compute  simpler,  9V(0) .  BIBLIOGRAPHY  1.  C l a r k e , Frank H.  Optimization  Wiley-Interscience, 2.  3.  Optimal  Franklin, Joel. Nonlinear  4.  and Raymond W.  Control.  1980.  Legge, J .  The  Rishel.  New York:  Methods. of Mathematical  Programming,  Verlag,  New  York:  1983.  Fleming, Wendell H.,  Stochastic  and Nonsmooth Analysis.  Chinese  Fixed  Point  Classics.  Deterministic  Springer-Verlag, Economics:  Theorems.  V o l . I.  Linear  New York:  London:  and  1975. and Springer-  Triibner and  Co.,  1861. 5.  Rockafellar,  R. T.  "Lagrange M u l t i p l i e r s and Sub.derivatives of  Optimal V a l u e F u n c t i o n s i n N o n l i n e a r Programming."  Programming  Study,  17 (1982), 28-66.  - 70 -  Mathematical  APPENDIX  AN  APPLICATION  Let the m u l t i f u n c t i o n may  then compute  F  |p|k(t)  [t,x,p]  near  p .  INEQUALITY  s a t i s f y t h e hypotheses o f Chapter I I .  H(t,x,p) := sup{<p,F(t,x) >} .  avers t h a t f o r any g i v e n of rank  OF GRONWALL'S  , the map  Thus t h e f i r s t  P r o p o s i t i o n 3.2.4 of [1]  x' ->H(t,x',p) component of  (by Theorem 1.6.3) a convex combination of v e c t o r s [p,x](-)  i s an arc such t h a t -p(t)  Hence  e  | |p(t) | - |p(a)|  |p(t) |  <  in  |  i s Lipschitz  8H(t,x,p) i s  |p[k(t)B  [-p,x] e 8H(t,x,p) a.e.,  |p(t)|k(t)B  We  . If  we must have  a.e.  <  |p(t) - p ( a ) |  <  |/ pCs) ds|  <  /  <  /  fc  a  | p ( s ) | ds  fc  a  fc  a  |p(s)|k(s)  ds , and  |p( ) | + fl |p(s) |k(s) ds . a  a By Gronwall's i n e q u a l i t y (Fleming and R i s h e l |p(t)|  In p a r t i c u l a r , p(b)  = 0  Lemma 1  <  p(a)  implies  |p(a)| + |p(a)| /  k(s)  exp(/^ k(x)  dx} ds .  p(t) = 0  f o r t>a .  I n l i k e manner,  fc  a  = 0  implies  p(t) = 0  If the adjoint  f o r t<b .  trajectory  [ 2 ] , p. 198),  s  We summarize.  for a Hamiltonian  system  ever  vanishes,  i t is the zero arc.  Corollary and  If  the arc  [p,q,?,A] e M ( x ) A  [p,q] vanishes  is a multiplier  somewhere,  for a perturbed  then i t is the zero arc.  - 71 -  problem  

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
United States 4 0
China 2 0
Poland 1 0
City Views Downloads
Ashburn 3 0
Pittsburgh 1 0
Unknown 1 2
Shenzhen 1 0
Beijing 1 0

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

Share

Embed

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

Comment

Related Items