Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The sensitivity of optimal value functions in differential inclusion problems 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
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
Citation
1.0095673.ris

Full Text

THE S E N S I T I V I T Y OF OPTIMAL VALUE FUNCTIONS IN D I F F E R E N T I A L I N C L U S I O N PROBLEMS By PHILIP DANIEL LOEWEN B.Sc, The University of Alberta, 1981 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n THE FACULTY OF GRADUATE STUDIES I n s t i t u t e of Applied Mathematics and S t a t i s t i c s We accept t h i s thesis as conforming to the required standard F. H. Clarke R. A. Restrepo THE UNIVERSITY OF BRITISH COLUMBIA August 1983 (c) P h i l i p Daniel Loewen, 1983 I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e a n d s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e h e a d o f my d e p a r t m e n t o r by h i s o r h e r r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . P h i l i p Loewen D e p a r t m e n t o f Mathematics The U n i v e r s i t y o f B r i t i s h C o l u m b i a 1956 Main Mall V a n c o u v e r , Canada V6T 1Y3 D a t e 10 August 1983 DE-6 (3/81) ABSTRACT In many p r a c t i c a l s i t u a t i o n s , the parameters of a control system are not known exactly. For t h i s reason, much recent l i t e r a t u r e i s concerned with the s e n s i t i v i t y of dynamic optimization problems to small perturbations of t h e i r basic character. This thesis discusses the s e n s i t i v i t y of a general d i f f e r e n t i a l i n c l u s i o n problem to perturbations of i t s objective function, dynamic constraint, and endpoint conditions. Such perturbations, here introduced by a finite-dimensional vector u , define a Value function V(u) by inducing changes i n the problem's optimal value. A f t e r Chapter I reviews the calculus of generalized gradients, Chapter II provides a formula f o r a c e r t a i n quantitative index of the problem's s e n s i t i v i t y to changes i n u : the generalized gradient of V . The basic approach i s that used by Clarke i n Optimization and Nonsmooth Analysis (New York: Wiley-Interscience, 1983)., Theorem 3.4.3. The r e s u l t s presented i n Chapter II compare well with Clarke's i n the appropriate s p e c i a l case. Chapter I II extends the s e n s i t i v i t y a n alysis of Chapter II to trea t f r e e time problems, i n which the planning period i s a further choice v a r i a b l e . A b r i e f discussion of c o n t r o l l a b i l i t y and an example from mathematical economics constitute Chapter IV. F. H. Clarke ( i i ) CONTENTS Abstract i i L i s t of Figures v Acknowledgement v i 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 S e n s i t i v i t y of the D i f f e r e n t i a l Inclusion Problem 17 1 Multifunctions, 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 Inclusion Problem 21 3 Perturbations 25 4 S e n s i t i v i t y Analysis 28 5 Ap p l i c a t i o n : Accurate Dynamics 38 Chapter I II The Free Time Problem 46 1 Formulation 46 2 M u l t i p l i e r Rules f o r P(0) 47 3 S e n s i t i v i t y Analysis 50 4 A p p l i c a t i o n : The Minimum Time Problem 53 5 Endpoint Perturbations and Normal Cones 55 ( i i i ) Chapter IV Applications 62 1 C o n t r o l l a b i l i t y 62 2 Example: A One-sector Economy 65 Bibliography 70 Appendix: An A p p l i c a t i o n of Gronwall's Inequality 71 (iv) L I S T OF FIGURES Typical sets C f o r which i n t T (x) = 0 The graph of T . (v) ACKNOWLEDGEMENTS It gives me great pleasure to thank Frank Clarke f o r supervising the work which grew into t h i s t h e s i s . His w i l l i n g investment of time, coupled with h i s unshakeable optimism, motivated me to make the most of h i s many apt suggestions and i n c i s i v e comments. The love and prayers of George, Helga, and Laura Loewen, and e s p e c i a l l y of Kimberley Loewen, sustained me i n t h i s e f f o r t . F i n a l l y , I must thank Rodrigo Restrepo and Frank Clarke f o r reading the f i n a l manuscript. (vi) CHAPTER I GENERALIZED GRADIENTS 1 S E N S I T I V I T Y AND S T A B I L I T Y The ancient Chinese Book of Changes ([4], Appendix I I , Hexagram 42) asserts that The superior man, when he sees what i s good, moves toward i t ; and when he sees h i s errors, he turns from them. Similar remarks adorn the opening pages of almost every modern textbook of optimization. Though i t may sound t r i t e , the truth cannot be avoided: man i n s t i n c t i v e l y seeks that which i s the best. After unanimously affirming that t h i s Innate c r a v i n g — n o t merely f o r excellence, but for pevfection— i s honourable, the textbooks d i f f u s e into various areas of a p p l i c a t i o n to indulge i t . Each text, however, regardless of i t s area of a p p l i c a t i o n , must ult i m a t e l y concede t h i s point: once a p r a c t i c a l problem of optimization has been set up, i t s s o l u t i o n alone has l i t t l e use. Granted, numerical predictions of ultimate productive capacity and i t s attendant healthy p r o f i t s (for example) look wonderful on paper. But such r e s u l t s are worthless unless they are accurate. Many factors a f f e c t the r e l i a b i l i t y of numerical " s o l u t i o n s , " even i f computational errors are ignored. At the very outset, the equations expressing a mathematical problem of optimization i n e v i t a b l y oversimplify the p h y s i c a l s i t u a t i o n under study. And once these equations are set down, t h e i r parameters must be - 1 - 2. evaluated. Error and uncertainty in this process skew the mathematical formulation even further. Given a purportedly practical optimization problem whose formulation and data are necessarily imprecise, we are compelled to ask, "If the model and i t s measured data are 'close' to the real situation and the correct data, w i l l i t s results necessarily be 'close' to the true solution?" This is a question of s t a b i l i t y . To answer i t , we might well seek a numerical index of the problem's sensitivity to small changes in i t s basic character. If a problem is extremely sensitive to measurement errors, for example, i t is relatively unstable, and any "results" should be approached warily. Quantitative predictions of a problem's sensitivity 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 crucial. They can also be used for gain: the careful manager can apply a detailed sensitivity analysis to select the small changes in his control parameters which w i l l pay the largest dividends. This application is well- known in linear programming problems where, according to J o e l Franklin [3], i t explains "why the dual vector is cherished by o i l company vice presidents and not just by mathematicians." This thesis provides a quantitative sensitivity analysis for a specific sort of dynamic optimization problem. The conventional differential i n c l u s i o n problem seeks to find an absolutely continuous function x:[a,b] R n which satisfies the end conditions [x(a),x(b)] e S and the dynamic constraint x(t) e F(t,x(t)) (for t in [a,b] ) while minimizing the cost function f(x(a),x(b)). (Here F is a multifunction—a mapping which carries each point [t,x] into a nonempty compact convex subset of Rn.) Under reasonable hypotheses, this problem has a solution, and we c a l l the minimum cost V(0) . Now i f the nature of the problem is perturbed slightly, say by a small 3. vector u i n R , then the s o l u t i o n and the minimum cost w i l l change too. These changes define the value function V:R m W {+00} by V(u) := i n f { f ( x ( a ) , x ( b ) , u ) : x ( t ) e F ( t , x ( t ) , u ) on [ a , b ] , [ x ( a ) , x ( b ) , u ] e S } . The s o l u t i o n of the unperturbed problem i s associated with the value V(0) ; the problem's s e n s i t i v i t y i s measured by VV(0) . It i s the l a t t e r quantity for which Theorem II.4.1 provides a formula. A serious obstacle to the c a l c u l a t i o n of W(0) arises immediately: i t almost never e x i s t s . In f a c t , V might not even be continuous—even when i t i s , there i s no guarantee that i t must be d i f f e r e n t i a b l e . To get past t h i s b a r r i e r , we follow a path marked out by F. H. Clarke. His work ([1]) defines a generalised gradient which describes the d i f f e r e n t i a l properties of n o n d i f f e r e n t i a b l e functions. Theorem II.4.1 a c t u a l l y provides a formula for the generalized gradient of V at 0 , not f o r VV(0) . The remainder of Chapter I reviews Clarke's theory of generalized gradients i n a sequence which emphasizes t h e i r geometric aspects and thereby sets up the new work i n Chapters II and I I I . A l l of the r e s u l t s reported i n sections 2-6 are taken from Chapter II of [1]. 2 PERPENDICULARS 2.1 Convex Subgradients 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 and complete theory of l o c a l analysis so f a m i l i a r i n the smooth ( i . e . continuously d i f f e r e n t i a b l e ) s e t t i n g — h a s a well-known extension to a family of functions which need not be d i f f e r e n t i a b l e . This family i s the set of convex functions f:R n -> RJ {+<*>} . If such a function i s f i n i t e and lower semicontinuous at the point x , i t s subgradient at x i s the set 3 f ( x ) := {?eR n : <£,y-x> < f ( y ) - f ( x ) for a l l y i n R n }. 4. If f happens to be d i f f e r e n t i a b l e at x , the set 9f(x) reduces to the singleton {Vf(x)} ; conversely, i f 3f(x) i s the singleton {?} , then f i s d i f f e r e n t i a b l e at x and Vf(x) = X, . The subgradient c l e a r l y gener- a l i z e s the ordinary notion of d i f f e r e n t i a t i o n to the family of convex ... functions. I t also obeys s u i t a b l e analogs of the d i f f e r e n t i a t i o n rules so f a m i l i a r i n ordinary calculus: t h i s feature confirms the subgradient as a useful and appropriate generalization. To appreciate the geometrical s i g n i f i c a n c e of the set 9f(x) , we r e c a l l that a vector v i s normal to a given closed convex set C at the point x i n C i f <v,c-x> < 0 for a l l c i n C . That i s , i f v has a nonpositive p r o j e c t i o n onto every vector drawn from the base point x to some other point i n C . ( A l t e r n a t i v e l y , v i s a vector perpendicular to a hyperplane which passes through x and supports the set C .) The c o l l e c t i o n of vectors normal to C at x forms a closed convex cone, the normal aone to C at x: N c(x) := {veR n : <v,c-x> < 0 for a l l c i n C }. Now for any function f :Rn ->- Ru {+<*>} , the epigraph of f i s the set of points i n R nxR l y i n g on or above the graph of f : epi f := {[x,r] : r > f(x) } . Note that f i s lower semicontinuous i f and only i f e p i f i s closed, and that f i s a convex function i f and only i f e p i f i s a convex set. For the convex function f studied here, we f i n d that N e p. f ( x , f ( x ) ) = {[?,-g] : <[?,-g],[y,r]-[x,f(x)]> <.0 for [y,r] e e p i f }. Hence [C,-T] l i e s i n N . J.(x,f(x)) i f and only i f epi f <£,y-x> < r-f(x) f o r a l l y i n R n and r > f(y) . That i s , 3f(x) = U : U,-l] € N e p. f ( x , f ( x ) ) } : 5. the subgradient consists of the f i r s t n components of c e r t a i n vectors normal to epi f . In the smooth one-variable case, the analogous property i s w e l l - known: the vector [ f ' ( x ) , - l ] i s perpendicular to the graph of y - f(x) at the point [x,f(x)] . The foregoing geometric observations h i n t that a s t i l l more general class of extended-real-valued functions would permit d i f f e r e n t i a l analysis i f only the appropriate generalization of the convex analysts' normal cone could be found. It i s admittedly d i f f i c u l t to induce a u n i v e r s a l concept of "normal vector" from the s u p e r f i c i a l discussion presented here, but we can investigate a simple r e l a t e d concept which w i l l a i d the e f f o r t . A study of perpendiculars constitutes the remainder of section 2. 2.2 Euclidean Distance Given any nonempty closed set C i n R n , the Euclidean distance function corresponding to C i s defined as follows: d^(x) := min{|x-c| : c e C } . Here, of course, |v| denotes the Euclidean norm of the vector v . For any given x i n R n , the minimum defining d (x) i s evidently attained at one or more points i n C . Every such point i s c a l l e d a projection of x onto C . Note that for any points x, y i n R n we have | d c(x) - d c(y) | < | x - y | . 2.3 Perpendiculars Let x be a point l y i n g i n a given closed subset C of R n . The vector v i n R n i s •perpendicular to C at x i f the point x provides the unique pro j e c t i o n of x + v onto C . When t h i s r e l a t i o n holds, we write vxC at x . This a n a l y t i c a l d e f i n i t i o n has a simple geometrical counterpart: the closed b a l l of radius |v| and centre x+v meets the set C i n a si n g l e point, namely x . Thus t h i s d e f i n i t i o n reduces to the usual 6. one i f C i s a hyperplane, and hence N (x) = {v : vlC at x } when C i s convex. The geometric d e f i n i t i o n of perpendicularity has the form of a separation p r i n c i p l e ; as such, i t implies a c e r t a i n i n e q u a l i t y which w i l l prove useful i n Chapter I I . 2.4 Proposition Let C be a nonempty closed subset of R n . If vlC at x j then <v,c-x> ^ . ^ I c-x] 2 for a l l c in C . PROOF By d e f i n i t i o n , |(x+v) - x| < |(x+v)-c| for a l l c In C . In terms of the inner 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 desired conclusion. • 3 NORMAL AND TANGENT CONES 3.11 Normal Cones For any nonempty closed set C i n R n containing a point x , we may define the set N (x) to be the closed convex cone generated by r l i m i t V i n „ -j r rt i { . i r : v.—K) , v.lC at x, , x.—>x } u {0} . 1 [ [ ± ± 1 1 The f i r s t set i n t h i s union i s the c o l l e c t i o n of a l l unit vectors which can be obtained by computing l i m i t s of normalized perpendiculars. The perpen- d i c u l a r s must diminish i n length, and t h e i r corresponding base points x^ i n C must converge to the given point x . I t i s evidently a closed set, but need not be convex. Together with the o r i g i n , i t generates a closed convex cone whose notation i s d e l i b e r a t e l y suggestive. We are not disappointed: the set N (x) coincides with the usual cone of normals when C i s convex. We may therefore use the construction above to define the normal cone to an a r b i t r a r y closed set. (Indeed, the manifestly l o c a l nature of N (x) requires only that the set C be l o c a l l y closed near x .) The r e s u l t s of section 4 confirm that t h i s g e n e r a l i z a t i o n i s appropriate and u s e f u l . 7. 3.2 Tangent Cones The tangent cone to an a r b i t r a r y nonempty closed set C i s simply the closed convex cone polar to the normal cone: T (x) := {w : <W,v> < 0 f o r a l l v i n N (x) } . It has the following 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 w in R n is tangent to C at x i f and only i f i t satisfies the following criterion. For every sequence {x^} in C converging to x and every sequence {t^} ^ n (OJ 0 0) decreasing to zero, there is a sequence {w^} converging to w such that x^ + t^w^ e C for all i . 4 GENERALIZED GRADIENTS 4.1 D e f i n i t i o n Let an extended-real-valued function f be defined on R n . We suppose throughout section 4 that x i s a point at which f i s f i n i t e , and that epi f i s l o c a l l y closed near [x,f(x)] . Then the generalized gradient of f at x i s the (closed convex) set 3f(x) := { C : e N f ( x , f ( x ) ) } . Note that t h i s d e f i n i t i o n reduces to the subgradient of se c t i o n 2 when f i s convex and lower semicontinuous. I f x happens to l i e on the boundary of the set where :f i s f i n i t e , the second component of every vector i n ^epi f ( x ' ^ ( x ) ) need not be s t r i c t l y negative. This p o s s i b i l i t y forces us to define the asymptotic generalized gradient of f at x : CO 8 f(x) := {5 : [?,0] € N e p i f ( x , f ( x ) ) } . It i s always a closed convex cone containing the o r i g i n . 8. 4.2 Recession Cones The recession cone of convex analysis i s the key to 00 the r e l a t i o n s h i p between 9f(x) and 9 f(x) . The recession cone of a given nonempty closed convex set C i n R n i s the l a r g e s t convex cone K for which K + C remains a subset of C.. I t may be given by K = {v : v+C c C}. However, the expression K = fi.c, : SAO , c,eC } i-x» i i x i i s more useful i n c a l c u l a t i o n . It f a c i l i t a t e s the proof of the following r e s u l t s . CO 4.3 Proposition If 9f(x)*0 , then 9 f(x) is the recession cone of 9f(x). 4.4 Proposition The set 9f(x) u (9°°f(x)\{0}) is not empty. Moreover, i f 3f(x)*0 then CO N . f ( x , f ( x ) ) = (9 f(x)x{0}) u u r(9f(x ) x{-l}) . f >0 5 A N A L Y T I C FORMULATION Any student of conventional calculus would r i g h t l y balk at the prospect of computing the d e r i v a t i v e of a function f by looking for a number t, which makes the vector [ ? , - l ] perpendicular to the graph of f . His hes- i t a t i o n i s quite understandable, and i t points out a weakness i n the devel- opment of sections 2-4. Although the geometric approach to d i f f e r e n t i a l analysis i s elegant and i n s t r u c t i v e , i t cannot replace a well-developed c a l c u l u s . The need to t r a n s l a t e the p i c t o r i a l concepts of the foregoing exposition into useable formulas motivates section 5« The f i r s t step of the transformation replaces sets with functions. 9. 5.1 "Support Functions Any closed convex set C i n R n i s characterized by i t s support function, namely o"c(p) := sup{<p,v> : v e C } . The support function takes values i n R u {*<»} , provided C*0 It i s f i n i t e - v a l u e d i f and only i f C i s bounded and nonempty. C l e a r l y , C = {v : <p,v> ^ a (p) for a l l p i n R n } . 5.2 D i r e c t i o n a l Derivatives For any function f :Rn—->-Ru {+o°} , one may attempt to define the directional derivative at a point x where f(x)<°°^ i n d i r e c - t i o n v as r l x » v > t + 0 t Of course, there are many choices of f, x, and v f o r which t h i s l i m i t does not e x i s t . But i f f i s a lower semicontinuous convex function, the l i m i t e x i s t s (somewhere i n [-°°,+00] ) f o r every v i n R n , and i s given by f ,/ Y . ,x _ i n f f(x+tv) - f(x) 1 ^ X ' v ; " t>0 t The calculus of convex subgradients i s based on the following remarkable f a c t : f'(x;*) is the support function of the set 8f(x) . That i s , 3f(x) = {? : <?,v> < f'(x;v) f o r a l l v i n R n } . Moreover, the function f'(x;«) i s sublinear (as any support function must be) and i t s epigraph i s the closed convex cone T , ,.(x,f(x)) . Thus the epi r epigraph forges a spectacular l i n k between the set N ^ ^(x,f(x)) and i t s polar T e p i £( x>f(x)) , and the set 8f(x) and i t s support function f ' ( x ; * ) . It i s u l t i m a t e l y t h i s support function, 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 subgradient c a l c u l u s . 10. 5.3 Generalized D i r e c t i o n a l Derivatives The perfect unity of the geometric and a n a l y t i c aspects of the subgradient calculus encourages s i m i l a r reasoning i n the general s e t t i n g . Once again, we consider a function f :Rn -»• R u {*o°} which i s f i n i t e at x and whose epigraph i s l o c a l l y closed near [x,f(x)] . The correspondences between N . ,.(x,f(x)) and T . ,.(x,f(x)) , and e p i r epi r between N ^ ^(x,f(x)) and 3f(x) have been established already. They carry a l l the i n s i g h t of the convex case. And i f T . ,.(x,f(x)) does turn ep i r out to be the epigraph of some function, then t h i s function must be the support function of 3f(x) . An independent d e f i n i t i o n of t h i s function would be invaluable. It would generalize the d i r e c t i o n a l d e r i v a t i v e appro- p r i a t e l y , and thereby provide the t o o l we need to b u i l d a complete calculus. R. T. Rockafellar has discovered such an independent d e f i n i t i o n . His r e s u l t , presented i n [1], i s that the function whose epigraph i s T e p £ f ( x , f ( x ) ) i s f °(x; •) :Rn -* R u {±~}, defined by f 0 / . x l i m i t l i m sup i n f f(y+tw) - a V X ; V J : £+0 y- -»• x wev+eB t a -> f(x) a > f(y) t + 0 (Here, and throughout t h i s t h e s i s , B denotes the open unit b a l l of the space i n question.) If 3f(x)*0 , t h i s d e f i n i t i o n y i e l d s the formulas 9f(x) = {<; : <5,-v> < f°(x;v) for a l l v i n R n } f°(x;v) = sup{<?,v> : ? e 3f(x) } . The d i f f i c u l t task of deriving a complete set of d i f f e r e n t i a t i o n rules i s not yet complete, but i t now has a s o l i d conceptual substructure. The reader i s directed to section 2.9 of [1] for an account of recent developments. 11. 6 T H E L I P S C H I T Z CASE The d i f f e r e n t i a l analysis of nonsmooth functions introduced above has several important s p e c i a l cases. We have already observed that the general- ized gradient coincides with the convex subgradient i n the appropriate instance. It also reduces to the conventional gradient for any smooth function f : 9f(x) = {Vf(x)} . Section 6 deals with a class of functions which contains a l l smooth functions and a l l convex functions. 6.1 L i p s c h i t z Functions Let f:R n R be f i n i t e at x^ . If the i n e q u a l i t y |f(x) - f ( y ) | < k|x - y| holds for a l l x, y i n some fixed neighbourhood of XQ , then the function f i s Lipschitz (of rank k ) near x^ . In p a r t i c u l a r , f i s f i n i t e - valued and uniformly continuous on a neighbourhood of x^ . I t can be shown that i f a convex function i s f i n i t e on an open set, then i t i s L i p s c h i t z near each point of that set. The corresponding statement f o r smooth functions follows immediately from the mean-value theorem. The following proposition shows that the asymptotic generalized gradient of a L i p s c h i t z function i s t r i v i a l . 6.2 Proposition Suppose that f:R n + E u {+°°} is finite at x , and that epi f is locally closed near [x,f(x)] . Then conditions (a)^Cc) are equivalent. Ca) is Lipschitz near x . Cb) 9f (x) is nonempty and bounded. Cc) dmf(x) = {0} . For the remainder of Section 6, we assume that the function f :Rn -> R i s L i p s c h i t z near x . Rademacher's c l a s s i c a l theorem asserts that a L i p s c h i t z function i s d i f f e r e n t i a b l e almost everywhere. According to the following r e s u l t , t h i s allows us to compute the generalized gradient of f by taking l i m i t s of ordinary gradients. 6.3 Theorem Let S be any set of measure zero in R n which includes all those points in some neighbourhood of x where f is not differentiable. Then 9f (x) = c o { 1 ^ t Vf ( x . ) : x. + x , x. I S } . The generalized gradient of a L i p s c h i t z function has the following important closure property. 6.4 Proposition If the sequence {x^} converges to x 3 and i f r, l i e s in afCx^) for each i while -> t, , then £ e 9f(x) . 6.5 D i r e c t i o n a l Derivatives When f i s L i p s c h i t z , the generalized d i r e c t i o n a l d e r i v a t i v e of item 5.3 assumes the following s i m p l i f i e d form: f o f x . v ) = l l m S U P f(y+tv) - f(y) y -> x t t \ 0 This di f f e r e n c e quotient looks very much l i k e that defining the conventional d i r e c t i o n a l d e r i v a t i v e : the only changes are that the base point y varies near x and "l i m sup" replaces " l i m i t . " The s u b s t a n t i a l s i m p l i f i c a t i o n of f ° ( x ; - ) i n the L i p s c h i t z case cuts the job of developing a generalized calculus down to a manageable s i z e , although the task remains formidable. F. H. Clarke [1] presents rules for the sums, products, quotients, and compositions of L i p s c h i t z functions which cooperate with Theorem 6.3 to put the generalized gradients of a great many L i p s c h i t z functions within easy reach. Two of 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 counterpart; the Second involves a method of combining functions which cannot be treated with c l a s s i c a l techniques. We l e t f ^, f2> ... ., fk : R n R be functions L i p s c h i t z near x . 13. 6.6 Proposition (a) For any scalars and 3 ' a ( c 1 f 1 + c 2 f 2 ) ( x ) c Cj^B^Cx) + c 23f . 2 ( x ) . Equality holds i f is smooth at x . (b) 9 ( f 1 f 2 ) ( x ) c f 1 ( x ) 3 f 2 ( x ) + f 2 ( x ) 3 f 1 ( x ) . 6.7 Proposition The pointwise maximum function f(x') := m a x C f ^ x ' ) : i=l,2,...,k } is Lipschitz near x and 3f.(x) c co{3f i(x) : i e I(x) } , where I(x) := arg max{f^(x) : 1=1,2,...,k } is the set of indices at which the maximum defining f is attained. For any given nonempty closed subset C of R n , the Euclidean distance function ^QC") defined i n item 2.2 i s everywhere L i p s c h i t z of rank 1. We can compute i t s generalized gradient by applying Theorem 6.3 to the following lemma. 6.8 Lemma If Vd^(x) exists and is nonzeros then the point x has a unique projection y in C , and Vd-,(x) = ^ ~ x . i . C | y - x | 6.9 Proposition Let x l i e in C . Then 3d (x) equals the convex hull of the set r l i m i t ^ i _ , • r«i { . r •• I : v.-K) , v.iC at x. , x.-*x } u {0} . Iv̂ l l i l I C o r o l l a r y N (x) = ~u r3d (x) . (See item 3.1.) . L r>0 C 7 EXAMPLES The two examples comprising section 7 i l l u s t r a t e the concepts of the review above, and w i l l l a t e r be u s e f u l . Both involve the generalized grad- ients of Euclidean distance functions. 14. 7.1 Cartesian Products Let C^ and C^ be nonempty closed subsets of R m and R n containing the points x^ and x^ . The c h a r a c t e r i z a t i o n of the tangent cone i n Proposition 3.3 r e a d i l y implies that V c / V V = Te 0< xo ) x V* 1" ' By p o l a r i t y , ^ c / V V = N C 0 ( X 0 ) X N C 1 ( X 1 ) • In item II.2.4 we require a s l i g h t l y stronger statement, namely that 3 d c 0 * C l < V * i > c 3 d c 0 ( j K o > x ^ e / V • We can prove t h i s with the help of Proposition 6.9. To begin the proof, l e t [u,v] l C nxC^ at [x,y] . Then we must have u l CQ at XQ and v l C^ at x^ . For i f u f a i l e d to be perpendicular to CQ at XQ , there would be a point x' i n C^ for which |(x+u) - x 1| < |(x+u) - x| . This would imply the absurd conclusion that the point [x',y] i n C^xc^ l i e s nearer to the point [x,y] + [u,v] than does the l a t t e r ' s given projection [x,y].. Now according to Proposition 6.9, 3d ( x n , x n ) i s the convex h u l l c o X L i u 1 of the o r i g i n and the set rr i l i m i t i 1 r , m m { [ U > V ] = i~> U u ^ v ^ l : [ u i ' V i ] * [ ° ' ° ] » [ u 1 , v ± ] i C QxC 1 at [ x ^ y ^ [x Q,x 1]} For any vector [u,v] i n t h i s set, u l i e s i n 3d (x n) and v l i e s i n 3d (x 1) . Let us prove t h i s f or u —we may assume u*0 . Then {u.} 1 1 i s a sequence of vectors which obey u^ X CQ at x^ ->• x^ and whose lengths converge to zero. So along some subsequence, which we do not r e l a b e l , u./|u.| converges to an element of 3d (x n) . Of course, the vector l i m i t u./|u.| need not equal u . But we can be sure that, for some r i n i-x» 1 1 (0,1] , u = r l i m i t u,/|u | ., Since 3d (x.) i s a convex set containing i-x» 0 the o r i g i n , we conclude that u e 3d_ (x n) . Upon applying a s i m i l a r C Q u argument to v , we f i n d that the set of unit vectors defined above i s a subset of 3d (x.-.) x 3d (x 1) . The l a t t e r i s a convex set containing 0, so ^ x c / V V C 8 d C ( ) ( x 0 ) X *\<*1> as required. 7.2 A Diagonal Set Let a nonempty closed subset C of R n be given, and define G := D + Cx{0} , where D := {[u,u] : u e R n} i s the diagonal of R nxR n . The set G may also be written G = {[y,x] : y e C + x} — t h i s shows that i t may be interpreted as the "graph" of the set-valued 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 . We seek to compute 3dg(c+u,u) f or some c i n C, u i n R n . This set i s c l e a r l y i d e n t i c a l to 3d (c,0) , since t r a n s l a t i o n by [u,u] does not a f f e c t the l o c a l nature of G. G Observe that i f [u,v] i G at [x,y] , then v = -u . For i f t h i s s t a t e - ment were f a l s e , there would be a vector a i n R n which makes the inner product <[u,v],[a,a]> p o s i t i v e . For t>0 , consider the distance |([x,y] + [u,v]) - ([x,y] + t [ a , a ] ) | = |[u,v] - t [ a , a ] | = {|[u,v]| 2 - 2t<[u,v],[a,a]> + t 2 | [ a , a ] | 2 } % . Whenever t Is less than the p o s i t i v e quantity 2< [u,v],[a,a]>/|[a,a]| 2 , 16. t h i s distance i s s t r i c t l y l e s s than |[u,v]| . That i s , [x,y] + t[a,a] i s a point of G which i s cl o s e r to [x,y] + [u,v] than i s the closest point. This cannot be: v = -u . Note also that [u,v] l G at [x,y] implies u X C at x-y . Again, suppose not. Then some point c i n C i s such that |u| > |((x-y)+u) - c| . Consequently |[u,v]| > |[x-y+u-c,v]| = |C[x-y,0]+[u,v]) - [c,0]| . This i n e q u a l i t y shows that [u,v] i s not perpendicular to G at [x-y,0] . But t h i s too i s impossible: [u,v] l G at [x-y,0] i s equivalent to [u,v] x G at [x,y] . We must have u X C at x-y . Suppose now that the vector [u,v] i s obtained as [u,v] = l i m i t [ u ^ " ^ ] / |[« ±»v ±]| for some sequence [U-L>V-Ĵ  -1- G at [ x ^ y ^ -*- [c,0] while [u^,v^] -> [0,0] . Then v. = -u. fo°r a l l i and u. X C at (x.-y.) -> c , so we have i x l i J ± r l l l m l t ^ " ^ ' " - " i 3 l r - . i [ U' V ] = i - v/zluj = 72 [ U '"U ] for some u' i n 8d (c) . Applying Proposition 6.9, we conclude that 9d G(c,0) c {fu,-u] : u e 9d c(c) } . Of course, t h i s implies that N G(c,0) c {[u,-u] : u e N c(c)' } . We w i l l use t h i s fact i n item II.5.3. CHAPTER I I S E N S I T I V I T Y OF THE D I F F E R E N T I A L INCLUSION PROBLEM A differential inclusion i s a generalization of a d i f f e r e n t i a l equation which has proven p a r t i c u l a r l y useful i n the study of dynamic optimization. Its symbolic form, x(t) e F ( t , x ( t ) ) a.e. , indicates that x(") i s an arc whose de r i v a t i v e at almost every time t l i e s i n the set into which the mapping F c a r r i e s the point [ t , x ( t ) ] . (An arc i s an absolutely continuous function.) The d i f f e r e n t i a l equation x(t) = f ( t , x ( t ) ) a.e. can thus be phrased as the d i f f e r e n t i a l i n c l u s i o n x(t) e { f ( t , x ( t ) ) } a.e. Any successful study of a problem whose dynamic constraints are formulated as a d i f f e r e n t i a l i n c l u s i o n must incorporate a thorough understanding of the inclusion's general properties. With t h i s motivation, sections 1 and 2 of Chapter II review the h i g h l i g h t s of Clarke [ 1 ] 5 Chapter 3. Sections 3-5 discuss the s e n s i t i v i t y of optimization problems governed by d i f f e r e n t i a l i n c l u s i o n s . 1 P O L Y F U N C T I O N S , TUBES, AND T R A J E C T O R I E S 1.1 Multifunctions A multifunction Y:S R n i s a mapping carrying each element of the set S into a subset of R n . When S i s a subset of R m , t o p o l o g i c a l properties may be a t t r i b u t e d to T . For example, the multifunc- t i o n T i s measurable i f the set {seS : T(s) n C * 0 } i s measurable for every closed subset C of R n . - 17 - 1.2 Continuity The multifunction r i s upper semicontinuous at SQ i n S i f f o r every e>0 there e x i s t s some 6>0 such that T(s) c r(.sn) + eB whenever s e SQ + SB . In th i s case, V i s c e r t a i n l y closed at SQ — t h a t i s , YQ e ^^so^ whenever YQ A N ^ S Q are obtained as [SQ,YQ] = l i m [S^JY^] f o r sequences {s^} <= S and {Ŷ } obeying Ŷ  € r(s^) for a l l i . Hence i f T i s upper semicontinuous everywhere, then the following set (the graph of T ) i s closed: Gr(T) := { [s,y] : y e r(s) } . The generalized gradient of a L i p s c h i t z function f i s a closed multifunction (Proposition 1.6.4) which, i n f a c t , can be shown to be upper semicontinuous. A stronger continuity condition may also be imposed on the multifunction T . We say that r i s Lipschitz (of rank k J on S i f TCs^) C T ( s 2 ) + k ^ - s ^ B f o r a l l s ^ s 2 i n S . (Recall that the c o l l e c t i o n of closed subsets of R n i s metrizable. I f r has closed values, the condition that i t be L i p s c h i t z with respect to the Hausdorff metric i s p r e c i s e l y that stated here.) In other words, V i s L i p s c h i t z of rank k on S i f , whenever s^, i n S and y i n T(s^) are given, there e x i s t s a point y^ i n T(.s^) such that | —¥"2 I - Îs-j.—32 ^ " Note that a ( n o n t r i v i a l ) L i p s c h i t z multifunction T can never be empty- valued, and must be upper semicontinuous and measurable. 1.3 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 to investigate multifunctions defined on p a r t i c u l a r subsets of RxRn . The set SI <= RxR n i s c a l l e d a tube (on [a,b] ) i f the set { t : [t,x] e SI for some x i n R n } i s an i n t e r v a l — s a y [a,b] — a n d there e x i s t continuous functions w:[a,b] -* R n and e: [a,b] (0,°°) such that fi = { [t,x] : t e [a,b] , x e w(t) + e(.t)B } . For n o t a t i o n a l ease, we define the projections R := { x : [t,x] e fi } fo r t i n [a,b] . 1.4 Special Properties Two s p e c i a l properties of a multifunction r:fi -*• R n prove useful 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 , r i s measurably L i p s c h i t z on fi i f (a) f o r each x i n R n , the multifunction t -»- r(t,x) i s measurable on [a,bj , and (b) there i s an integrable function k:[a,bl -> [Q,00) such that f o r each t i n [a,b] , the multifunction x -»- F(t,x) i s L i p s c h i t z of rank k(t) on . (To make sense of condition (a), we adopt the convention that T(t,x) =? 0 when [t,x] i Q, .) A measure of the L i p s c h i t z character of F i s provided by the r e l a t e d constant K := exp(/^k(t) dt) The multifunction Y i s integrably bounded (by ij) J on fi i f there i s an integrable function <J>:[a,b] -»• [0,°°) for which the i n c l u s i o n T(t,x) <= <j)(t)B p r e v a i l s for each [t,x] i n fi . 1.5 T r a j e c t o r i e s We are now s u f f i c i e n t l y prepared to study the d i f f e r e n t i a l i n c l u s i o n x(t) e r ( t , x ( t ) ) a.e. on [a,b] . An R n-valued arc x(*) s a t i s f y i n g t h i s r e l a t i o n s h i p i s c a l l e d a trajectory for T , or simply a T-trajectory.. Faced with t h i s d e f i n i t i o n , a math- ematician immediately asks, "Must such a t r a j e c t o r y e x i s t ? " Theorem 3.1.6 of Clarke [1] answers, "Yes," by providing conditions under which an approximate t r a j e c t o r y admits a nearby F - t r a j e c t o r y . The sequential compactness r e s u l t below also concludes that a c e r t a i n T-trajectory e x i s t s : t h i s theorem w i l l f i n d frequent a p p l i c a t i o n i n the discussion to follow. The theorem assumes that T i s defined on some tube fi on [a,b] , and that i t s values there are nonempty, compact, convex sets. I t also : requires that V be integrably bounded (by <j> ) on fi , and that there e x i s t a multifunction X:[a,b] -> R n and a p o s i t i v e function E(') on [a,b] such that the following three conditions hold.. (a) X(t) + e(t)B c o, for every t i n [a,b] . (b) For every t i n [a,bj , the multifunction x' -»- r(t,,x') i s upper semicontinuous at every point x i n X(t) + e(t)B . (c) The multifunction t ' ->-T(t',x) i s measurable, for every [t,xj e i n t fi . 1.6 Theorem If. {x^} is a sequence of arcs on [a,b] satisfying conditions ( i ) - ( i i i ) below, then i t admits a subsequence which converges uniformly to a ^-trajectory. (i) x ± ( t ) e X(t) and |x ±(t) | < t()(t) a.e. on [a,b] . ( i i ) ^ ( t ) e T ( t , x i ( t ) + y i ( t ) ) + r i ( t ) B for all t in A ± , where {y ±} and {r^} are sequences of measurable functions on [a,b] converging uniformly to zero and {k^} is a sequence of measurable subsets of [a,b] whose measures converge to b-a . ( i i i ) The sequence {x^a)} is bounded. The proof appears i n Clarke [1], Theorem 3.1.7. 21. 2 THE D I F F E R E N T I A L INCLUSION PROBLEM 2.1 Formulation The f i x e d time version of the differential inclusion problem may be formulated as CP) inf{ f(x(a),x(b)) : i ( t ) e F ( t , x ( t ) ) a.e., [x(a),x(b)] e S } . An F-trajectory . x(*) i s admissible for P i f i t s a t i s f i e s the endpoint constraints [x(a),x(b)] e S . S t r i c t l y speaking, the above expression for P represents a number (possibly +«>••) defined i n terms of the given time i n t e r v a l [a,b] , objective function f :R nxR n R , multifunction F:RxRn -* R n , and constraint set S c R nxR n . However, the form i n which, t h i s number appears constitutes an i m p l i c i t challenge: we are to c a l c u l a t e i t s value by determining an admissible F - t r a j e c t o r y x(/) on the i n t e r v a l [a,b] which minimizes the objective function f(x(a),x(b)) . Such an arc x(') i s c a l l e d a solution to problem P ; the business of i s o l a t i n g a s o l u t i o n i s a genuine optimization problem. S u p e r f i c i a l analysis- suggests that the infimum defining P might be f i n i t e without being attained by any admissible arc. The following hypotheses eliminate t h i s p o s s i b i l i t y , and f a c i l i t a t e a f r u i t f u l study of the problem. 2.2 Hypotheses Throughout section 2, we assume that the data of problem P s a t i s f y conditions (a)-(d) below. (a) The endpoint constraint set S i s closed; i t s f i r s t p r o j e c t i o n , namely {: x : [x,y] e S for some y } , i s compact. (b) The multifunction F i s defined on some tube Q on [a,b] . On t h i s tube, F i s measurably L i p s c h i t z and integrably bounded; i t s values are nonempty compact convex sets. Also, F has an extension to some • " r" tube containing which retains :these -properties. (c) The objective function f Is L i p s c h i t z of rank on the set S n (fi~xfi7) . a b Now suppose P has a f i n i t e value:, must a s o l u t i o n arc exist? Unfortunately, the answer i s "No," e s s e n t i a l l y because the tube fi i s not closed. However, an affi r m a t i v e answer i s possible for a problem c l o s e l y r e l a t e d to P , as we now show. With Theorem 1.6 i n mind, we consider a version of P i n which the competing t r a j e c t o r i e s l i e not i n fi , but i n the s l i g h t l y l a rger set fi . (Hypothesis (b) allows F to be extended to a tube containing both fi and fi ; t h i s extension i s unique when r e s t r i c t e d to fi .) This new problem, say P , also has a f i n i t e value, so i t admits a minimizing sequence—that i s , a sequence {x^t')} of admissible arcs for which l i m i t f(x.(a),x^(b)) = i n f P . Hypotheses (a) and (b) above assure that Theorem 1.6 applies, with X(t) = fi^ : i t s conclusion holds that some subsequence of (x^(')} converges uniformly to an F-trajectory x(•) . Since S and X(t) are closed sets, x(*) i s admissible f o r P ; Hypothesis (c) implies that f(x(a),x(b)) = i n f P~ . So i f P has a f i n i t e , values then P admits a solution. If the so l u t i o n to P spends some time on the boundary of ^ , we must acknowledge the p o s s i b i l i t y that, i t s character i s influenced by the problem's i m p l i c i t requirement that x(t) e fifc for a l l t i n [a,b] . Such a point- wise condition i s c a l l e d a state constraint: many state constraints, including this; one, may be cast into the general form g( t , x ( t ) ) < 0 for a l l t i n [a,bj . The arguments to follow may a l l be modified to account for e x p l i c i t state constraints of t h i s form, but t h e i r e s s e n t i a l features are cle a r e s t when the state constraints are i n a c t i v e along solutions. That i s , when g(t, x ( t ) ) < 0 f o r a l l t i n [a,b] . This i s our f i n a l hypothesis. (d) P has a s o l u t i o n ; a l l solutions to problem P a c t u a l l y l i e i n Q , and therefore solve P . 2.3 M u l t i p l i e r Sets Every s o l u t i o n to problem P s a t i s f i e s a c e r t a i n set of necessary conditions—the counterparts i n our f i e l d of the famous Euler- Lagrange equation i n the c l a s s i c a l calculus of v a r i a t i o n s . At the heart of these conditions l i e s the Hamiltonian for problem P , which i s the function H:ftxRn -* R defined by H(t,x,p) := max{ <p,v> : v e F(t,x) } . We note that H(t,x,rp) = rH(t,x,p) for a l l r > 0 , whence [a,g] e 9H(t,x,p) i f and only i f [ra,g] e 9H(t,x,rp) for r > 0 . (Here, and throughout section 2, the generalized gradient of H r e f e r s only the the Ix,p] variables.) Other properties of H are presented i n Clarke [1]: the most noteworthy i s the assertion that 3H i s a multifunction s a t i s f y i n g the hypotheses of Theorem 1.6. For every arc x(-) admissible for P and a l l scalars r , A > 0 , the index X m u l t i p l i e r set (corresponding to. x(.-) ) M^(x) consists, of a l l t r i p l e s [p,C , A J s a t i s f y i n g conditions (a)-(c) below. (a) c = [£,n] l i e s i n 9f (x(a) ,x(b)) . (b) p: [a,b] ->- R n i s an arc obeying the Hamiltonian inclusion l>p(t),x(t)] e 3H(t,x(t) ,p(t)) a.e. on [a,b] . The arc p(-) i s c a l l e d the adjoint or costate t r a j e c t o r y . Cc) The adjoint t r a j e c t o r y s a t i s f i e s the transversality condition [p(a),-p(b)] e AU,n] + r | [A,E] | 9dg(x(a) ,x(b) ) . Here E := A[£,n] + [-pCa) ,p(b) ] and dg. i s the Euclidean distance function for the set S , defined i n item 1.2.2. Applying the remarks preceding t h i s d e f i n i t i o n , we note that [p,£,A] A BA belongs to M r(x) i f and only i f [8p,r;,gA] e W (x) for a l l B > 0 . Let us agree to scale when necessary, and thus r e s t r i c t our attention to only two cases: A=0 and A=l . Of course, conditions (b) and (c) hold t r i v i a l l y when A=0 and p(*)=0 : any legitimate theorem proposing (a)-(c) as necessary conditions must eliminate t h i s p o s s i b i l i t y . 2.4 Theorem (Necessary Conditions) Suppose the arc x(.») solves problem P Then for any r exceeding r := (2K^+2) (1+KlnK) there exists a multiplier [p,C,A] with X + ||p|| > 0 . (The constant K is defined in item 1.4.) PROOF According to Hypothesis 2.2(a), there Is a constant M such that { x : [x,y] € S for some y } c MB . It follows that the arc x(') solves P i f and only i f the arc [x(a),x(*)J solves the rel a t e d problem min{ f (y Q(b),y(b)) : [yQ,y] g {0}xF(t,y) , [y 0 ( a ) , y ( a ) ] e D n m,, T y 0(b),y(b)] e S } , where D := { [u,u] : u £ R n },. This problem has the form treated i n [1]: i t s s o l u t i o n therefore admits a n o n t r i v i a l m u l t i p l i e r i n Clarke's sense, provided r exceeds r .([1], Theorem 3.4.3). Such a m u l t i p l i e r consists of an arc [PQ,P] , a sc a l a r A > 0 , and a vector t, s a t i s f y i n g the following conditions. (i ) C = [5»n] £ 3f(x(a),x(b)) . This implies condition (a) defining M^(x) ( i i ) [-p 0,-p,0,x](t) 6 8 H ( t , x ( a ) , x ( t ) , p 0 ( t ) , p ( t ) ) a.e. , where H(t,yQ,y,qQ,q) = H(t,y,q) . This establishes (b) i n the d e f i n i t i o n of M^(x) , and implies that p n i s constant. ( i i i ) [p 0(a),p(a)] e r|[A,E]|3d^(x(a),x(a)) . By item 1.7.2, with C = {0} , t h i s forces p^ = -p(a) . (iv) -[-p(a),p(b)] = [ P(a),-p(b)] £ A? + r | [A,E] |3d g(x(a),x(b)) . This reduces to the t r a n s v e r s a l i t y condition (c) defining M^(x) . • The m u l t i p l i e r sets defined here pertain to a more general problem than do those of the same name i n [1]. To recover the s p e c i a l case, consider an objective function f independent of x(a) , and take S := cqxC-^ where i s compact and i s closed. We may then take [£,1")] = [0,£] f o r some t, i n 3f(x(b)) , whereupon item 1.7.1 reduces condition (c) to a pair of t r a n s v e r s a l i t y conditions of the form Clarke presents: p(a) 6 r|[A,E]|3d (x(a)) ^0 -p(b) e XZ + r|[X,E]|3d_ (x(b)) . Ll One minor d i f f e r e n c e p e r s i s t s : i n these two expressions, E = [-p(a),A£+p(b)], whereas the E i n [1] s i g n i f i e s only A? + p(b)!. 3 PERTURBATIONS 3.1 The Value Function No t r u l y applied optimization problem presents i n f i n i t e l y accurate data. Quantitative uncertainty i s severe i n econometrics and the s o c i a l sciences; even i n the s t r i c t l y c o n t r o l l e d l a b o r a t o r i e s of the physical sciences, measurement errors are inescapable. And even i f the parameters of a given problem are i n f i n i t e l y precise, an a l e r t manager may well inquire about the consequences of changing them s l i g h t l y . To address t h i s question, we embed the problem of section 2 i n a family of d i f f e r e n t i a l i n c l u s i o n problems indexed by the perturbation vector u i n R m : P(u) inf{ f(x(a),x(b),u) : x e F(t,x,u) , [x(a),x(b),u] e S } . When u i s f i x e d a t z e r o , t h i s i s the problem o f s e c t i o n 2. As t h e v a l u e s of .u v a r y i n a neighbourhood o f z e r o , t h e d a t a o f the problem undergo s l i g h t changes. The s o l u t i o n a r c s ( i f they e x i s t ) change t o o , and u s u a l l y a l t e r the n u m e r i c a l v a l u e o f t h e infimum. The value function V:R m R u {+<»} m o n i t o r s t h e l a t t e r v a r i a t i o n : V(u) := i n f P(u) . Sharp e s t i m a t e s o f 8V(0) 00 and 9 V(0) p r o v i d e c o n s i d e r a b l e i n s i g h t i n t o t h e s e n s i t i v i t y o f problem P(0) t o s m a l l changes i n u . They a r e t h e g o a l o f t h i s c h a p t e r . 3.2 Hypotheses S l i g h t changes i n t h e forms of f , F, and S f o r c e us to c o n s i d e r some minor amendments to the b a s i c hypotheses of i t e m 2.2. F o r completeness, c o n d i t i o n s ( a ) - ( d ) below r e f o r m u l a t e t h e c o r r e s p o n d i n g assumptions f o r the u n p e r t u r b e d c a s e . (a) The endpoint c o n s t r a i n t s e t S 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 i s compact. (b) The m u l t i f u n c t i o n F i s d e f i n e d on some tube ft c RxR nxR m on [a,b] . The tube ft has t h e form ft°xpB f o r some tube ft° c RxR n on [a,b] and some p>0 . F ( t , x , u ) i s i n t e g r a b l y bounded on ft , where i t i s a l s o measurably L i p s c h i t z i n [x,u] ; i t s v a l u e s a r e nonempty, compact, and convex. A l s o , F has an e x t e n s i o n to some tube c o n t a i n i n g ft which r e t a i n s t h e s e p r o p e r t i e s . (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 n ( i T x F x PB) . a b As i n i t e m 2.2, we l e t P(u) be t h e v e r s i o n o f problem P(u) o b t a i n e d by c o n s i d e r i n g a d m i s s i b l e a r c s i n ft i n s t e a d of ft . (d) P'(.O) has a s o l u t i o n ; a l l s o l u t i o n s of P(0) l i e i n ft , and t h e r e f o r e s o l v e P(0) . The proof of Theorem 4.1 r e l i e s on a weak technical assumption. In statement (e), and throughout t h i s chapter, Y denotes the set of arcs solving P(0) . (e) For every arc x(-) i n Y , the multifunction [x,y,u] -> N s(x,y,u) i s closed at the point [x(a),x(b),0] . Closed multifunctions are defined i n item 1.2; N i s the normal cone to the set S , defined i n item 1.3.1. In several i n t e r e s t i n g s i t u a t i o n s , Hypothesis (e) can be v e r i f i e d d i r e c t l y . For example, i t holds automatically i f i n t T g:(x(a) ,x(b) ,0) * 0 f o r a l l x(-) i n Y (Clarke [1], Theorem 2.5.8, Corollary 2). Section III.5 discusses t h i s hypothesis i n d e t a i l . We r e t a i n hypotheses (a)-(e) throughout sections 3 to 5. A further hypo- thesis i s introduced i n item 3.4. 3.3 M u l t i p l i e r Sets The adjoint t r a j e c t o r y corresponding to a so l u t i o n x(-) of P(0) c a r r i e s useful information about the s e n s i t i v i t y of the problem. When t h i s arc i s appropriately augmented by an arc which traces the precise CO form of the perturbation, the desired characterizations of 3V(0) and 3 V(0) assume a p a r t i c u l a r l y elegant, form. Of course, the new arc s l i g h t l y a l t e r s the appearance of the m u l t i p l i e r s e t s . For any scalar \>0 and arc x(-) admissible f o r P(0) , the index X multiplier set (corresponding to x(-) ) M\X) consists of a l l quadruples [p>q>S»^] f o r which the following three conditions hold. Ca) ?= U,n,n'] l i e s i n 3f(x(a),x(b),0) . (b) [p,q]:[a,b] -> RnxRm i s an arc obeying the i n c l u s i o n [-p(t) ,-q(.t) ,x(t)] e 3H(t,x(t),p,p(t)) a.e. on [a,b] , where - H(t,x,u,p) := sup{ < p,v> : v c F(t,x,u) } . (c) [p(a),-p(b),-q(b)] e A[5,n,n'] + N s(x(a),x(b),0) . 28. 3.4 Nondegeneracy The perturbation structure of problem P i s degenerate i f some index 0 m u l t i p l i e r corresponding to a s o l u t i o n of P(0) has q(a) = 0 but p * 0 . The s e n s i t i v i t y analysis of section 4 assumes that P i s nondegenerate—that i s , that [p>q>£>°] e M°(Y) and q(a) = 0 imply p = 0 . (Here, of course, M (Y) = u M (x) . ) xeY The term "nondegenerate" r e f e r s to the way the perturbation influences the problem's data at ; U T 0 . . Conditions 3.3 show that the arc 'q'(') c a r r i e s the information about the f i r s t - o r d e r u-dependence of F, S, and f along the given arc x(') . By s e t t i n g A=0 , the u-dependence of f i s rendered i r r e l e v a n t . The r e s u l t i n g hypothesis requires that the m u l t i p l i e r be t r i v i a l i f the perturbations of F and S conspire to allow q(a)=0 . As we s h a l l see, nondegeneracy i s a mild hypothesis. It i s independent of the usual d e f i n i t i o n of normality, f o r example—in section 5 we investigate a problem whose perturbation structure i s nondegenerate even though P(0) may be abnormal. The minimum-time problem of section III.4 i s automatically nondegenerate, as i s Example IV.2. 4 S E N S I T I V I T Y A N A L Y S I S The m u l t i p l i e r sets of item 3.3 are linked to the d i f f e r e n t i a l properties of V through a c e r t a i n mapping Q . For any m u l t i p l i e r [p>q,C 9A] corres- ponding to an admissible arc x(-) , we define Q(p,q , £ , A ) := -q(a) . The notation Q[M^(x)] r e f e r s to a l l possible values of -q(a) obtained i n t h i s way; Q[M^(Y)] denotes u Q[M A(x)] . xeY Theorem 4.1 i s the main r e s u l t of t h i s t h e s i s . I t s proof occupies the remainder of section 4. 29. 4.1 Theorem ( S e n s i t i v i t y ) Under Hypotheses 3.1(a)-(e) and 3.43 epi V is locally closed-near [0,V(0)] and 3V(0) = 7o{ Q[M 1(Y)] n 3V(0) + Q[M°(Y)] n 3°°V(0) } . If the cone Q[M^(Y)] is pointed, the. closure operation is superfluous and one also has oo —0 oo 3 V(0) = co{ Q[>T(Y);] n 3 V(0) } . (A subset of R m i s pointed i f zero cannot be obtained as a p o s i t i v e l i n e a r combination of i t s nonzero elements.) Corollary 1 If Q[M°(Y)] = 0 , then V is f i n i t e . and Lipschitz. near 0 . PROOF The cone {0} i s c e r t a i n l y pointed, so 3°°V(0) = {0} by the Theorem. Apply Proposition 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 If Y = {x(")} the proof i s simple: either Q[M^(x)] does not equal {0} , whence the conclusion i s immediate, or i t does, i n which case the set 3V(0) must be nonempty (Proposition 1.6.2). But then 3V(0) ^ c o { Q[M 1(x)] n 3V(0) } also, whence M"*"(x) * 0 . Now i f x i s not the unique s o l u t i o n to P(0) , the arc [0,x(-)J i s the unique s o l u t i o n to the problem P(0), where the data of problem P are as follows. f(x Q,x,y 0,y,u) := f(x,y,u) + ey Q F(t,x Q,x,u) := {e|x - x ( t ) | 2 } x F(t,x,u) S := { [0,x,r,y,u] : [x,y,u] e S , r e R } Any e>0 w i l l serve, provided we choose i t s u f f i c i e n t l y small to r e t a i n the basic hypotheses. The argument above asserts that [0,x(-)] has a m u l t i p l i e r [-PQ,P, q, C, A] with X + |q(a)| > 0 : t h i s m u l t i p l i e r reduces r e a d i l y to a m u l t i p l i e r i n M^(x) with X + |g(a)| > 0 . D To prove Theorem 4.1, we w i l l c a l c u l a t e the generalized gradients of V by appealing to t h e i r d e f i n i t i o n s : av(0) = { 5 : [?,-]] e N V(0,V(0)) } 3°°V(0) = { x, : U, 0] e N V(0,V(0))' } . To ensure that these expressions make sense, we begin with the following r e s u l t . 4.2 Lemma (a) There exist constants <S>0. and e>0 such that for all u in 6B , the condition V(u) < V(0) + e implies that a l l solutions, to P(u) He in fi (and hence solve P(u) also), (b) The set- epi V is- locally'closed hear [0, V(0) ]. . PROOF (a) If no such constants e x i s t , then there must be a sequence u^ 0 with V(u^) < V(0) + 1 / i such that f o r each i , some so l u t i o n arc x^(-) of problem P(u^) does not l i e i n ^ . Nonetheless, each arc x^(-) l i e s i n fi , so Theorem 1.6 assures that {x^(')'} has a subsequence tending uniformly to some arc x(-) admissible for P(0) . Now by Hypothesis 3.2(d), V(0) = i n f HOT * f (x(a),x(b),0) < f (x. (a) ,x.(b) ,u.) < l l m S U P (V(0)+l/i) = V(0) . Thus equality holds throughout and x(-) solves P(0) . According to 3.2(d), t h i s implies that x(«) l i e s i n ,fi . Consequently any uniformly approxim- ating sequence of arcs must eventually l i e i n fi . This contradicts the f a c t that each arc x^(') contains points outside fi , and thereby establishes (a). (b) Let {[u_^,v^]} be a sequence of points i n the set ([0,V(0)] + hSBxheB) n e p i V , converging to the point [u,v] • We must show [u,v] e epi V . Let x^(«) be the s o l u t i o n to P(u.) , so that V(u.) > f ( x (a),x.(b),u.) f o r a l l i 1 1 i 1 1 Theorem 1.6 asserts that some subsequence of {x_̂ } converges uniformly to an arc x(*) admissible for. P(u) . (We do not relabel.) Thus v = l i m i t v. > l i m i t V(u.) > l i m i t f(x.(a),x.(b),u.) i i » i • i i i -> co i co i CO = f(x(a),x(b),u) . By part (a), f(x(a),x(b),u) > V(u). Hence [u,v] e epi V as required. The proof of Theorem 4.1 i s b u i l t on the following geometric proposition of Rockafellar ([5], Proposition 15). 4.3 Proposition Let D and D°° be closed subsets of R m such, that D°° is a cone containing the. point 0 and the recession cone of D . Ibr the closed cone N := { r U , - l ] : r >0 , ? eD } n {[?,0] : ? eD} in R mxR one has { t, : [ ? , - l ] e co N } = co (D + D°°) . If the cone D°° is pointed, the closure operation on the right-hand side is superfluous, and one also has { C : [£,0] e • co N } = co D°° . To complete the proof, we must s u c c e s s f u l l y i d e n t i f y D with —T_ co —f) co Q[M (Y)] n 3V(0) and D with Q[*T-(Y)] n 3 V(0) . Both these sets are closed, being the i n t e r s e c t i o n of closed sets. ( Q[M A(Y)] i s closed by oo Theorem 1.6.) Moreover, D i s the i n t e r s e c t i o n of two cones containing 00 zero, and i s therefore such a cone i t s e l f . It remains only to show that D contains the recession cone of D , and that N e p i v ( ° ' V ( 0 ) ) = V ' where! H := { r [ ? , - l ] : r > 0 , £ e QtM^CY).] n 9V(0) } N 2 := { [?,' 0] : c e Q[M°(Y)] m 3°°V(Q) } . We begin with the l a t t e r a s s e r t i o n . OO The very d e f i n i t i o n s of 3V(0) and d V(0) show that N ,.(.0,V(0).) • c "co" ( N 'Cl N ) . epi V 1 z To prove the reverse i n c l u s i o n , we w i l l use the d e f i n i t i o n of the normal cone in terms of l i m i t s , of normalized perpendicular vectors given i n item 1.3.1. It motivates the following lemma. 4.4 Lemma Suppose [v,-G] is perpendicular to. epi V at the point [u,a] , where a < V(0) + e and u e <SB . Then there exists a solution x(-) to P(u) j a scalar X in {0,1} 3 an.arc [p,q] 3 and a point r, such that ||[p,q]| + | [ y^_g] | > 0 and conditions (a)-(d) hold. Ca) £ = [£,n,n'] H-es in 9f(x(a),x(b),u) . Cb) [-p(t) ,-q(t),x(t)] e 3tf(t,x(t),u,p(t)) a.e. on [a,b] . Co) [ p ( a ) , - p ( b ) , - q ( b ) ] e A | [ v ^ _ g ] | [g»n,n'3 + N g(x(a),x(b),u) . W " q ( a ) = A |[vI-B]| ' PROOF Since V(u).:< a < V(0) + E , Lemma 4.2 assures that P(u) has a :. so l u t i o n x(.) admissible f o r P(u) . Now f o r any u' i n 6B, every 33. F - t r a j e c t o r y yC') admissible f o r P(u') obeys V(u') < f(y(a),y(b),u') < f(y(a),y(b),u') + a - f(x(a),x(b),u) . Hence [u',f(y(a),y(b),u')+a-f ( x(a) , x(b),u)] e epi V , and Proposition 1.2.4 implies that f(y(a),y(b),u') - <v,u'> + %|[u'-u,f(y(a),y(b),u')-f ( x(a) , x(b),u)]| 2 > f (x(a) ,x(b),u) - <v,u> . Equality holds when . y = x and u' = u , so we deduce that [x("),u] provides a l o c a l s o l u t i o n for the (unperturbed) d i f f e r e n t i a l i n c l u s i o n problem whose data are f (x,x1,y,y1) := fCx.y.y^ -<v,x±> + %|[ y i-u,f ( x,y, y i)-f ( x(a ) , x(b),u)]| 2 , F(t , x , x 1 ) := F(t ,x,x.) x {0} , and S := { [x.x^y.y^ : [x.y.y.^ e S , x;L e SB } . Note that H(t ,x ,x 1,p,q) = tf(t,x,x^,p) . A l l the hypotheses of item 2.2 hold for t h i s problem, so we may apply Theorem 2.4. It provides an arc [p,q] , a sc a l a r A i n {0,1} , and a vector [£,n.»n'] i n 3f(x(a) ,x(b),u) such that conditions ( i ) - ( i i i ) below hold. (D e[5,0,Ti,n'] + [0,-v,0,0] l i e s i n 3f(x(a),u ,x(b),u) . ( i i ) [-p,-q,x,0](t) e 3H(t , x(t),u,p(t) ,q(t)) a.e. on [a,b].' This implies [-p,-q ,x](t) e 3tf(t , x(t),u,p(t)) a.e. on [a,b].. ( i i i ) [p(a),q(a),-p(b),-q(b)] e A( 3[?,0,n,n'] + [0,-v,0,0] ) + Ns(x(a),u,xCb),u) . Now u l i e s i n <5B by assumption, so the second component of every vector i n N g(x(a),u ,x(b),u) i s zero.. Condition ( i i i ) therefore reduces to -q(.a) = Av and [p(a),-pCb),-q(b)] e Xgte.n.n'] + N s (x(a) ,x(b),u) . 34. To complete the proof, we simply divide the arc [p,q] by |[v,-3]| i n ( i i ) and ( i i i ) , and take the scaled arc [p,q] / J[v,-$]| f o r the adjoint t r a j e c t o r y i n conclusions (a)-(d). Suppose now that a sequence [v^,-3^] of vectors perpendicular to epi V at corresponding points [u^,a^] i s given, where [v^,-f3^] -*• [0,0] , [u ±,a ] -* [0,V(0)] , and the l i m i t of [v^-B^.] / J [v ±,-3±] | exists and equals (say) t vo' -^0'' * Item'1-3.1 t e l l s us that N e p ^ y(0,V(0)) i s pre c i s e l y the closed convex cone generated by vectors [ V Q , — ^ Q ^ obtained t h i s way. So the desired i n c l u s i o n involving ^ ^ ̂ (0,V(0)) w i l l be established i f we only prove [VQ ,-3Q] e u . This i s a consequence of the following lemma. 4.5 Lemma Let [ V Q , - 3 Q ] be the unit vector introduced above. Then there is a solution x (0 to P:(0) 3 an arc [p,q] y. and a vector [5,n,n'] ^ n 3f(x(a),x(b) ,0 ) such that Ca) [-p,-q,x](t) e- 3 H(t,x(t) , 0,p(t)) a.e. on [a,b] , Cb) [p(a) ,-p(b) ,-q(b)] e 0oU,n,n'] + N g(x(a) ,x(b) ,0) , and Cc) -q(a) = v Q . PROOF For a l l i s u f f i c i e n t l y l arge, Lemma 4.4 applies to the perpendicular vectors [v-̂ >~3̂ ] to generate solutions x^(') f o r P(u^) and corresponding quantities , [p^,q^] , and' [?^»i"|^,r)!J s a t i s f y i n g 4 .4(a)-(d). Note that f(x.(a),x.(b),u.) = V(u.) < a. + V (0) . I i i l I 35. Now we observe that \^ * 0 f o r a l l s u f f i c i e n t l y large i . To see t h i s , suppose a subsequence of the " m u l t i p l i e r s " above (which we do not relabel) has = 0 f o r a l l i . Then 4.4(d) implies that q^(a) = 0 , whence p^(a) * 0 f o r a l l i by the n o n t r i v i a l i t y condition. We may therefore scale the adjoint arc by 1 / |p_j,(a)| : the r e s u l t i s a sequence of arcs [p^,q^,x^] on [a,b] such that [-P i,-q i,x i] (t) e 8H.(t,x i(t),u 1,p i(t)) a.e. on [a,b] , [p (a),-p (b),-q (b)] e N (x (a),x (b),u ) , and 1 1 1 O 1 1 1 |p.^(.a)| = 1 while q^(a) = 0 . The sequence {[p^(a),q^(a),x^(a)]} of i n i t i a l points of these arcs i s bounded, and 9f/ s a t i s f i e s the hypotheses of Theorem 1.6. Therefore a further subsequence converges uniformly to an arc [p,q,x] such that x(") i s admissible for P(0) and [-p,-q\x](t) e 8f/(t,x(t) ,0,p(t)) a.e. on [a,b] , [p(a),-p(b),0] e N s(x(a),x(b),0) , and |p(a)| = 1 while q(a) = 0 . (To obtain the second conclusion, we use Hypothesis 3.2(e).) But by the note above, f(x(a),x(b),0) = l i m i t f(x.(a),x.(b),u.) < l i m i t a. = V(0) , so the i-x» l i m i t arc x(-) solves P(0) . This cannot be supported: the three conclusions j u s t derived contradict the nondegeneracy of problem P . A s i m i l a r argument establishes that the sequence {p_^(a)} i s bounded. For i f t h i s were not the case, then s c a l i n g the i - t h m u l t i p l i e r by 1 .' 1 / |p^(a)| leads to a family of m u l t i p l i e r s and solutions with q^(a) -»• 0 and { [p (a) , 1. (a) ,x. (a) ] } bounded. Applying Theorem 1.6 allows the : . 36. extraction of a subsequence of these m u l t i p l i e r s along which q^(a) converges to zero, p^ to some nonzero arc (for |p^(a.) | = 1 always), and x^(-) to a s o l u t i o n f o r P(0) . Once again, the nondegeneracy of problem P i s compromised. This i s absurd: the sequence {p^(a)} must be bounded. Thus the sequence of i n i t i a l points {[p (a).,q^(a) ,x (a) ] } i s bounded as i t stands, and A = 1 for a l l large i . A f i n a l a p p l i c a t i o n of Theorem 1.6 y i e l d s a subsequence of {[p^(•),q^(*),x^(•)]} which converges uniformly to the s o l u t i o n x(') and the adjoint arc [p('),q(')] described i n the conclusions of the lemma. (Note: t h i s l a s t l i m i t i n g argument uses the f a c t that 3f i s closed, which i s j u s t i f i e d by Proposition 1.6.4.) • Aided by Lemma 4.5, we may now prove that [ v ^ , - ^ ] l i e s i n N^ u N 2 . Suppose f i r s t that *''0 . Upon d i v i d i n g the arc [p,q] by i n conclusions (a)-(c) and renaming the r e s u l t i n g adjoint arcs as [p,q] , we f i n d that the s o l u t i o n x(-) has a m u l t i p l i e r of index 1 with -q(a) = v Q / e 0 . But 3Q [^,-1] = [v 0,-B Q] e N e p . V(0,V(0)) by construction, so -q(.a) = v Q / 3 0 6 9V(0) . In other words, V 0 -1 -p- e Q[M (Y)] n 3V(0) . eo This implies that [VQ , ~ 3Q] l i e s i n N^ . Second, assume 3Q = 0 . Then [p,q] i s an adjoint arc associated with an index 0 m u l t i p l i e r f o r the s o l u t i o n x(*) , and -q(a) = v^ . Of course, [v „ , 0 ] e 3V(0) because [v „ , 0 ] e N . „('0,V(.0)') by construction. Therefore U U epi V v Q-e Q[M°CY)_] n 3VC0) and [v Q ,0] l i e s i n N We have f i n a l l y established that "N V(0,V(0)) c co" (t^ u N 2) . Since the reverse i n c l u s i o n i s obvious, equality holds. Only one step remains i n the proof of Theorem 4.1. 4.6 .Lemma The set Q[M^(Y)] n 3°°V(0) contains the recession cone of the set Q[M 1(Y)] n 3V(0) . PROOF Recall that the recession cone of a set C i n :.Rm i s the cone 0 + C := { l i m i t 6.y. : y . e C , 6. + 0 } . i i l l 1 ->- oo CO + Since 3 V(0) always contains 0 3V(0) (Proposition 1.4.3), the lemma w i l l be established once we show that Q[M^(Y)] contains 0 + Q[M"*"(Y)] . Zero l i e s i n the former set, so we examine a nonzero element q of the l a t t e r . This element must be obtained as q = l i m i t -S.q.(a) for 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 scalars 6^ + 0 . When we write [p^,q^] f o r ^1Pi»^icli-l ^ n t' i e conditions defining a m u l t i p l i e r , the Hamiltonian i n c l u s i o n i s unchanged and the t r a n s v e r s a l i t y condition assumes the form [p,(a),-p.(b),-q (b)] £ 6 U ,n n'] + N (x (a),x (b),0) . 1 1 1 1 X 1 1 o l 1 Under t h i s s c a l i n g , we now have q = l i m i t -q.(a) . In p a r t i c u l a r , (q.(a)} i oo i s a bounded sequence. The sequence {x^(a)} i s bounded by Hypothesis 3.2(a), and the sequence (p^(a)} must also be bounded by an argument i d e n t i c a l to that of Lemma 4.5. Hence the arcs { [p^-( *) ,q^( *) >x^( •) ] } have a convergent 38. subsequence by Theorem 1.6. As , 8 AO and the subsequence of arcs converges uniformly to a further s o l u t i o n x(*) i n Y and an adjoint pair [p(*),q(*)] s a t i s f y i n g the Hamiltonian i n c l u s i o n and the t r a n s v e r s a l i t y condition [p(a),-p(b),-q(b)] £ N s(x(a),x(b),0) . Moreover, one has q = l i m i t -q.(a) = -q(a) . That i s , q l i e s i n i ->- co Q[M°(Y)] . • The proof of Theorem 4.1 i s complete. 5 A P P L I C A T I O N : ACCURATE DYNAMICS Certain 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 involve no perturbations i n t h e i r dynamics. In t h i s section, we investigate two such cases. The f i r s t involves only a perturbation of the objective function f ; i n the second, perturbations t r a n s l a t e the terminal set i n Rn.. 5.1 Reduced Conditions When the multifunction F has no u-dependence, the Hamiltonian K(t,x,x^,p) of sections 3 and 4 reduces to H(t,x,p) = sup{ <p,v>: v e F ( t , x ) } . With H now independent of x^ , the Hamiltonian i n c l u s i o n implies that q must be a constant arc. A m u l t i p l i e r [p,q,£,A] corresponding to an admissible arc x(*) must s a t i s f y 3.3(a) and the following reduced conditions. (b) p:[a,b] R n i s an arc obeying the i n c l u s i o n [-p(t),x(t)] e 3H(t,x(t),p(t)) a.e.; q i s constant. (c) [p(a),-p(b),-q] £ A[£,n,n'] + N g(x(a),x(b),0) . Further reduction i s possible i n the s p e c i a l case i n which the endpoint constraint set S i s also independent of u . Let us abuse our notation s l i g h t l y and think of _S as a subset of R n > <R n i n our discussion of t h i s p o s s i b i l i t y . 5.2 Theorem Let the function V:R m R u {+«>} be defined by V(u) := inf{ f(x(a),x(b),u) : i e F(t,x) , [x(a),x(b)] e S } , where the data obey Hypotheses 3.2(a)-(e) and 3.4, Then 9°°V(0) = {0} and 9V(0) = co{ n' e 3V(0) : U.n.n'] e 9f (x(a),x(b) ,0) f o r x e Y } . PROOF When S i s independent of u , the t h i r d component of every vector i n N (x(a),x(b),0) i s zero. Condition 5.1(c) implies that -q = An' , therefore. Now when A=0, q=0 — t h u s Q[M°(Y)] = {0} . Theorem 4.1 asserts that 9V(0) = co{ Q[M 1(Y)] n 9V(0) } . This i s p r e c i s e l y the desired conclusion. • Note that the value function defined i n the theorem i s L i p s c h i t z of rank CO near 0 by Hypothesis 3.2(c). We may therefore obtain 9 V(0) = {0} d i r e c t l y from Proposition 1.6.2 without recourse to Theorem 4.1. Also, when the function f i s regular (see [1], e s p e c i a l l y Propositions 2.3.15 and . 2.3.16)—for example, when f i s smooth or convex—the conclusion of Theorem 5.2 s i m p l i f i e s because { n' : U,n,n'l e 9f (x(a) ,x(b) ,0) } = 9g(0) , where g(u) := f(x(a),x(b),u) . Corollary 1 ext 9V(0) c { n' : [£,n,n'] e 9f(x(a),x(b),0) f o r xeY } . PROOF Apply the following well-known converse of the Krein-Milman Theorem: i f C c R m i s compact, then co C i s also compact and ext( co C ) c c . • The perturbation discussed by Theorem 5.2 has such a simple structure that a completely d i f f e r e n t approach w i l l also y i e l d a formula f o r 8V(0) . We d i r e c t the interested reader to section 2.8 of [1], where Clarke develops the theory of pointwise maxima and t h e i r generalized gradients. That theory leads to the formula 3V(0) c co{ n' : U,n,n'] e 3 f(x(a),x(b),0) f o r x(-) e Y } . ([1], Theorem 2.8.3.) This formula i s weaker than that given by Theorem 5.2 because i t s right-hand side does not involve the r e s t r i c t i o n n' e 3V(0) . It therefore f a i l s to eliminate the p o s s i b i l i t y that the set whose convex h u l l i s computed on the right-hand side contains no points of 3V(0) at a l l , but that i t s members are s u f f i c i e n t l y well d i s t r i b u t e d that t h e i r convex h u l l includes 3V(0) . Thus Corollary 1 o f f e r s a s i g n i f i c a n t refinement of the conventional theory. The geometric approach of Theorem 4.1 i s d i r e c t l y responsible f o r t h i s i n c i s i v e new estimate, a f a c t which suggests that the techniques of section 4 might be p r o f i t a b l y applied to other basic problems of the generalized c a l c u l u s . Pursuit of t h i s p o s s i b i l i t y would lead us f a r from the main track of t h i s exposition, but we can note the following improvement of Proposition 1.6.7. Coroll a r y 2 Let g 1 , g 2 > - • •,g k:R m R i>e functions Lipschitz on pB for some p >0 . Then the pointwise minimum function g(u') := min{ g ^ u 1 ) : i = 1,2,.'."..:.. . ,k } is L i p s c h i t z on pB and ext 3g(0) o.: u £3g (0). : i e 1(0) } , where 1(0) := { i : g ± ( 0 ) = g(0) } . 41. PROOF Set C := { 1, 2, . . ., k } . The conclusion follows immediately from Corollary 1, f o r g may be expressed as the value function of a problem where n=l , F(t,x,u) := {0} , ft := [0,1] x (-l,n+l)::x PB , S : = { 0 } x C x { l } x C x p B , and f i s a L i p s c h i t z function f o r which f(x,y,u) equals g^(u) whenever x=y=i . • 5.3 Endpoint Perturbations F. H. Clarke [1] derives the necessary conditions presented i n section 2 from a close study of the d i f f e r e n t i a l i n c l u s i o n problem's s e n s i t i v i t y to a d d i t i v e endpoint perturbations. (See h i s Theorem 3.4.3.) R e f l e c t i o n on t h i s s p e c i a l case w i l l help us assess the r e l a t i v e strength of Theorem 4.1 and determine the p l a u s i b i l i t y of i t s hypotheses. Let the function V:R n -> R u {+«>} be defined by V(u) := inf{ f(x(b)) : x e F(t,x) , x(a) e C Q , x(b) e C^u } . (The s l i g h t change to the argument l i s t of f should not be confusing.) Here CQ i s compact and C^ i s closed: the set S of sections 3 and 4 may be written : S = u n ( C Q x (C-j+u) x {u}) = C Q x (C 1x{0> + D) , ueR where D := { [u,u] : u e R n } . According to item 5.1, a m u l t i p l i e r [p>q»C»A] corresponding to some admissible arc x(") reduces as follows. (a) z = [0 ,n,0] , where n l i e s i n 3f(x(b)) . (b) [-p,x](t) e 3H(t,x(t),p(t)) a.e. on [a,b] ; q i s constant. (c) [p(a),-p(b),-q] ;e A[0,n,0] + N g(x(a),x(b),0) . But N s(x(a),x(b),u) = N c (x(a)) x N c x { Q } + D(x(b),0) , and t h i s reduces to N (x(a)) x { [v,-v] : v e N (x(b)) } by the C0 C l arguments of section SE-..7. Thus condition (c) implies that p(a) e N (x(a)) and L0 q ---= -p(b) - An e N_ (x(b)) . L l Combining these observations, we f i n d that for any admissible arc x(*) , Q[M\X)] = { An+p(b) : p:[a,b] R n i s an arc s a t i s f y i n g t-p,x] e 3H(t,x,p) a.e., p(a) e N (x(a)), c o and -p(b) e \r\ + N (x(b)) , where Ll n l i e s i n 9f(x(b)) } . 5.4 Conclusions The above expression f o r the sets Q throws the assertions of Theorem 4.1 into a form very s i m i l a r to those of Clarke's Theorem 3.4.3 ( [ 1 ] ) . That theorem adduces formulas i d e n t i c a l to those of 4.1, with the sets Q[M X(Y)] replaced by E[M*(Y)] f o r any r > r := (2K f+2)(l+K&n K) . The sets E[M^(Y)] can only be distinguished from Q[M X(Y)] by t h e i r s l i g h t l y stronger t r a n s v e r s a l i t y conditions, which read p(a) e r | [ A , E ] | 3 d (x(a)) and (la) L0 -p(b) e An + r | [ A , E ] | 3 d r (x(b)) , (lb) C l where E := An + p(b) . According to C o r o l l a r y 1.6.9, the t r a n s v e r s a l i t y conditions d e f i n i n g Q may be recovered from these by formally s e t t i n g r = +°° and taking the closure of the r e s u l t i n g right-hand sides. For values of ..r i n (r,-H>°) , we have E[M^(Y)] c Q[M A(Y)] . Thus Clarke's estimate of 3V(0) appears more precise than that of Theorem 4.1, e s p e c i a l l y as r+r . However, i t i s d i f f i c u l t to e s t a b l i s h that the estimate i n v o l v i n g E i s s u b s t a n t i a l l y sharper than that of 4.1 without p r i o r knowledge of the sets CQ and .C^ . To see t h i s , consider any n o n t r i v i a l m u l t i p l i e r [p,?,A] i n M^(Y) . If we l e t Q denote An + p(b) , then c e r t a i n l y Q / | [ A , Q ] | e B- Thus the second t r a n s v e r s a l i t y condition defining M^(Y) may be replaced by T U T Q T T € 1 N N C L ( X ( A ) ) • ( 2 A ) The i n e q u a l i t y |Q[ < | [ A , Q ] | also implies that |p(b) | < A | C | + | . U , Q ] | > so P(b) |[A,Q1 According to Gronwall's i n e q u a l i t y (compare Appendix 1), |p(a) | < (1 + K £n K)|p(b) |. Together with the previous i n e q u a l i t y , t h i s implies that the f i r s t trans- v e r s a l i t y condition defining M^(Y) may be replaced by T u f t l T e r * n V x ( a ) ) ( 2 b ) f o r any r > r := (1+K^)(1+K£n K) . In short, the t r a n s v e r s a l i t y conditions obtained from Theorem 4.1 may be replaced by p(a) e r|[A,Q]|B n N r (x(a)) (3a) -p(b) e An + |[A,Q]|B n N p (x(b)) (3b) Ll f o r any 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 (1) i s e s p e c i a l l y s t r i k i n g . Not only do the right-hand sides of (3) specify e s s e n t i a l l y the same di r e c t i o n s as do those of (1) ( c f . Corollary 1.6.9), but they also involve magnitude r e s t r i c t i o n s of i d e n t i c a l form. Indeed, the values of r permit- ted i n (1) must exceed r = 2r > 2 , while any r > r 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 stringent than those i n (1) i n some instances. In other cases, of course, conditions ( 1 ) are s t r i c t e r . But regardless of which s i t u a t i o n i s imposed by a s p e c i f i c s e l e c t i o n of the sets CQ and , we can be sure that the conclusions of Theorem 4 . 1 are i d e n t i c a l i n s p i r i t to those of [ 1 ] , Theorem 3 . 4 . 3 , and are not substan- t i a l l y weaker. 5 . 5 Hypotheses The hypotheses Theorem 4 . 1 imposes on t h i s s p e c i a l case also acquit themselves when compared to those of the standard r e s u l t . Additive endpoint perturbations are automatically nondegenerate, for example. The analysis above shows c l e a r l y that i f A and q vanish simultaneously, then -p(b) = An + q i s zero also, whence p i s the zero arc. Hypotheses 3 . 2 ( a ) - ( c ) are s t r i c t l y analogous to the basic hypotheses i n [ 1 ] , and require no further defense. Hypothesis 3.2(d) has been discussed above: i t amounts to the assumption that the state constraints defining the problem P ( 0 ) are i n a c t i v e along every s o l u t i o n to P(.O) . Active state constraints, even i n the more general form g ( t , x ( t ) ) < 0 f o r a l l t i n [a,b] , permit a treatment very s i m i l a r to that i n section 4 . We have ignored them to ease the notational burden i n t h i s thesis at l i t t l e conceptual expense. The only hypothesis of Theorem 4 . 1 which has no analogue i n Clarke's work i s 3 . 2 ( e ) , which requires ( i n t h i s case) that the multifunctions N (•) and N (') must be closed at x(a) and x(b) whenever the arc C 0 ° 1 x(') solves P ( 0 ) . This a d d i t i o n a l assumption represents the p r i c e we must pay for our imprecise knowledge of the perturbation's structure i n Theorem 4 . 1 . The standard r e s u l t uses the a d d i t i v e form of the perturbations to reduce the a u x i l i a r y problem ( c f . Lemma 4 . 4 ) to a free-endpoint problem f o r which no other hypotheses are required. This s p e c i a l i z e d approach i s unavailable i n the general setting of section 4 . Nonetheless, Hypothesis 3.2(e) i s not a serious flaw i n our theory. As noted i n section 3.2, i t holds automatically i f i n t T (x(a)) * 0 and i n t T (x(b)) * 0 for a l l C0 C l x(-) i n Y . The l a t t e r hypotheses are very mild: as Lemma III.5.2 (below) shows, they can only f a i l i f N (x(a)) or N (x(b)) contains a l i n e : the C0 C l d e f i n i t i o n of item 1.3.1 indicates that the only closed plane sets C with i n t T r(x) = 0 bear a close resemblance to one of the sets shown i n Figure 1. Figure 1. Typical sets C f o r which i n t T (x) = 0 . Similar geometric, features are required to obtain i n t T (x) = 0 for Li higher-dimensional sets C . A more de t a i l e d discussion of t h i s hypothesis i s offered i n section III.5. For the present, i t s u f f i c e s to note that i t holds f o r a l l convex sets CQ and , and f o r a l l sets whose boundaries are smooth, and f o r the great many other sets which do not di s p l a y the pathologies i l l u s t r a t e d i n Figure 1. Our theory i s not s u b s t a n t i a l l y weakened by excluding from consideration those problems whose solutions end at i n f i n i t e l y sharp points of the constraint sets. In short, both the hypotheses and the conclusions of Theorem 4.1 compare well with those of the standard theory. CHAPTER I I I THE FREE TIME PROBLEM 1 FORMULATION I. 1 Free Time The predetermined time i n t e r v a l [a,b] assumed throughout Chapter II 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 . I t a r i s e s , f o r example, when s e l e c t i n g an optimal investment p o l i c y f o r a five-year economic plan. However, not a l l problems permit t h i s assumption. Realigning the o r b i t of a space s a t e l l i t e using minimum f u e l , f o r instance, requires a c a r e f u l choice of the planning period. The free time problem studied i n t h i s chapter allows t h i s a d d i t i o n a l complication. It reads as follows: P(u) inf{ f(a,x(a),b,x(b),u) : x(t) e F(t,x(t),u) a.e. on [a,b] , [a,x(a),b,x(b),u] £ S } . Since the i n i t i a l and terminal times a and b must now be determined as part of the s o l u t i o n , the objective function f and endpoint constraint set S depend on them e x p l i c i t l y . Here, as i n Chapter I I , u represents a perturbation vector i n R m which introduces small deviations into the nominal problem P(.O) . We w i l l study the s e n s i t i v i t y of P(0) to such perturbations by i n v e s t i g a t i n g the generalized gradient at 0 of i t s value function V(u) := i n f P(u) . Clarke [1] derives necessary conditions for optimality i n the (unper^ turbed) free time problem by reducing i t to the fixed-time case of Theorem I I . 2.4. This f a c t explains the s l i g h t l y stronger hypotheses introduced below, and corroborates the s p i r i t of Theorem 3.3: known fixed-time r e s u l t s allow extensions to free-time theorems. I. 2 Hypotheses Throughout Chapter I I I , the data of problem P must s a t i s f y hypotheses ( a ) - ( e ) . (a) The constraint set S c RxR nxRxR nxR m i s closed and nonempty. Its projec t i o n { [s,x] : [s,x,t,y,u] e S } i s compact. This implies that SQ := inf{ s : [s,x,t,y,u] e S } i s f i n i t e ; we assume that t ^ := sup{ t : [s,x,t,y,u] e S } i s also f i n i t e . (b) The multifunction F(t,x,u) i s defined on some tube ft c RxR nxR m on [ S Q , ^ ] ; i t s values are nonempty compact convex subsets of R n . F i s integrably bounded on ft , where i t i s also j o i n t l y L i p s c h i t z of (constant) rank k i n [t,x,u] . (Recall that t h i s condition defines k(t -s ) another constant . K := e 0 0 .) We assume that ft has the form ft°xpB for some tube ft° c RxR n on [ s ^ j t ^ ] and some p>0 , and that F has an extension to some tube containing ft which retains these properties. (c) The objective function f i s L i p s c h i t z of rank on the set S c (ft^xft^xpB) . (d) Problem P(0) has a sol u t i o n ; a l l solutions of P(0) l i e i n ft , and hence solve . P(0) . Here problem P(u) i s a vers i o n of P(u) i n which the admissible arcs are confined to ft , j u s t as i n item II.2.2. (e) For every arc x(*) with domain [a,b] providing a s o l u t i o n f o r P(0) , the multifunction [s,x,t,y,u] ->- Ng(s,x,t,y,u) i s closed at the point [a,x(a),b,x(b),0] . 2 MULTIPLIER RULES FOR PCO) Every s o l u t i o n to the unperturbed free time problem P(0) must obey c e r t a i n necessary c o n d i t i o n s — t h e free-time conterparts of those i n Theorem I I . 2.4. These conditions are presented i n Clarke [1], but we o f f e r s l i g h t l y more general statements here. The standard hypotheses governing an unper- turbed free time problem are simply the obvious reductions of Hypotheses 1.2(a)-(d) i n the event that u does not appear. Note that no form of (e) i s required. The argument l i s t s of f and F and the dimension of the set S change s l i g h t l y i n the discussion to follow, but new notation would only obscure what the context renders p e r f e c t l y transparent. The f i r s t r e s u l t deals with the case when the problem has no e x p l i c i t time-dependence. Its conclusions c l o s e l y resemble those of Theorem II.2.4, and w i l l help e s t a b l i s h a general m u l t i p l i e r r u l e . 2.1 Theorem (Necessary Conditions—Autonomous Case) Suppose that the arc x(*) on [a,b] solves the free-time problem (P) min{ f(x(a),x(b)) : x ( t ) e F(x(t)) a.e. , [x(a),x(b)] e S } . Then for any r exceeding r := (2K f + 2)(1 + K an K) , there is a scalar X in {0,1} j an arc p , and a vector £ such that conditions (a)-(c) hold with X + ||p| > 0 . (a) £ = [£,n] lies in 3f(x(a),x(b)) . (b) p:[a,b] -> R n is an arc obeying the Hamiltonian inclusion [-p(t),x(t)] e 3H(x(t),p(t)) a.e. on [a,b] , and H(x(t),p(t)) = 0 a.e. on [a,b] . (c) [p(a),-p(b)] e X[5,n] + r 3 d s ( x ( a ) , x ( b ) ) . PROOF Although both terminal times a and b may vary i n p r i n c i p l e , we observe that the value of an arc depends only upon i t s shape: any admissible arc y(') on [a',b'] has the same value as the r e l a t e d arc y'(t) := y ( t - t ) defined on [a'+T,b'+x] . In short, only the duration b-a i s a s i g n i f i c a n t choice v a r i a b l e . We therefore lose no generality i n assuming that time a i s f i x e d . Under t h i s assumption, the very same bookkeeping device used to prove Theorem II.2.4 reduces problem P to an autonomous free time problem for which a m u l t i p l i e r r u l e i s given i n [1], Cor o l l a r y to Theorem 3.6.1. We argue j u s t as we did i n Theorem II.2.4 to deduce the present theorem from t h i s m u l t i p l i e r r u l e . • 2.2 Theorem (Necessary Conditions) Suppose that the arc x(*) on [a,b] solves the free-time problem (P) min{ f(a,x(a),b,x(b)) : x eF(t,x) a.e., [a,x(a),b,x(b)] e S } . Then for any r exceeding v := (2K^ + 2) (1 + K £n K) there exist an arc p:[a,b] -> R n , a vector t, , and. a scalar X in {0,1} such that conditions (a)-(c) hold with X + | | p | | > 0 . (a) £ = [a,5,x ,n ] lies in 3f(a,x(a),b,x(b)) . (b) [ h ( t ) , - p ( t ) , x ( t ) ] e 9H(t,x(t),p(t)) a.e. on [a,b], where h:[a,b] -> R is an arc such that h(t) = H(t , x ( t ) , p ( t ) ) a.e. on [a,b] . (Here, and throughout Chapter III, the generalized gradient of H refers to all its arguments,) (c) t-h(a),p(a),h(b),-p(b)] e A[a,£,T,n] + r3d g(a,x(a),b,x(b)) . PROOF Problem P i s c l e a r l y equivalent to the following autonomous f r e e - time problem: min{ f ( x Q ( a ) , x ( a ) , x Q ( b ) , x ( b ) ) : [x Q,x] e { l } x F ( x Q , x ) , [ x 0 ( a ) , x ( a ) , x 0 ( b ) , x ( b ) j e S } , whose Hamiltonian i s H ( X Q , X , P Q , P ) = p^ + H ( X Q , X , P ) . This problem obeys the standard hypotheses, and the arc [ x ^ ( t ) , x ( t ) ] := [ t , x ( t ) ] i s one of i t s s o lutions. Consequently there exist an arc [pQ,p]:[a,b] -> R x R n , a vector C, , and a s c a l a r X i n {0,1} such that conditions 2.1(a)-(c) hold. In p a r t i c u l a r , 2.1(b) implies that PgCt) + H(t , x ( t ) , p ( t ) ) = 0 a.e. Upon defining h(t) := -p^(t) , conclusions (a)-(c) of the present theorem follow immediately. To see that A + |p|| must be p o s i t i v e , note that i t cannot be zero. For i f p i s the zero arc, then 0 = H(t rx(t),p<t)) = - P Q ( t ) a.e. , which implies the absurd conclusion that A + | [ P Q , P ] | = 0 . The theorem stands. • 3 SE N S I T I V I T Y ANALYSIS 3.1 M u l t i p l i e r Sets The reader who has endured the s l i g h t abuses of notation i n section 2 w i l l undoubtedly fo r g i v e another small concession of pe r f e c t i o n - ism to r e a d a b i l i t y . Conditions (a)-(c) below define a m u l t i p l i e r set f o r the perturbed version of the free-time problem introduced i n section 1. Though these conditions 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 c a l l i n g the present set M \ X ) a l s o . We are permitted to do so because the contexts i n which the d i f f e r e n t sets a r i s e are easy to d i s t i n g u i s h ; we exercise the option 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 of Theorem II.4.1 and those of Theorem 3.3 below. For any sca l a r A>0 and arc x ( - ) on [a,b] admissible f o r P (0) , the index A multiplier set (corresponding to x(*) ) M \ X ) consists of a l l quadruples [p,q,£, A] s a t i s f y i n g conditions ( a ) - ( c ) . . (a) C. = [a, 5, x, n, n'] l i e s i n 8f (a,x(a) ,b,x(b) ,0) . Cb) [p,q] : [a,b] R nxR m i s an arc obeying the i n c l u s i o n [h(t) , - p C t ),-q(t),x(t)] e 3 H ( t , x ( t ) , 0 , p ( t ) ) a.e. on [a,b] , L where H(t,x,u,p) := sup{ <p,v> : v £ F(t,x,u) } and h:[a,b] -> R i s an arc such that h(t) = ff(t,x(t) , 0,p(t)) a.e. on [a,b] . (c) [-h(a),p(a),h(b),-p(b),-q(b)] e A[a,5»T,n»n'1 + Ng(a,x(a) ,b ,x (b),0) . For the given arc x(') , Q[M A(x)] denotes the set of a l l vectors -q(a) obtained from m u l t i p l i e r s [p,q»?,A] corresponding to x ( - ) . We also define Q[M A(Y)] = u Q[M A(x)] , x eY where Y i s the set of solutions to P(0) . 3.2 Nondegeneracy Just as i n item II.3.4, the free-time problem P i s nondegenerate i f \=0 and q(a)=0 imply p=0 whenver [p,q,?,A] i s a m u l t i p l i e r i n M A(Y) . The notation established i n item 3.1 allows us to transcribe the s e n s i t i v i t y r e s u l t s of Theorem II.4.1 into the free-time case. 3.3 Theorem Under Hypotheses 1.2(a)-(e) and 3.2, one has 3V(0) = c!7{ QjNp'CY) ] n 3V(0) + Q[M°(Y)] n 3°°V(0) } If the oone Q[M^(Y)] is pointed, the closure operation is superfluous and one also has co „ —r\ co 3 V(0) = co{ Q[tT(Y)] n 3 V(0) } . The proof of Theorem 3.3, l i k e i t s statement,is nothing but a trans- p o s i t i o n of the arguments i n section II.4. A very l i g h t sketch w i l l convey i t s content j u s t as well as a r e p e t i t i v e account of the d e t a i l s . Limiting techniques l i e at the core of Theorem 3.3, j u s t as they do i n Theorem II.4.1. The proof of Theorem II.4.1 deals with sequences of arcs defined on a given i n t e r v a l [a,b] , and invokes Theorem II.1.6,repeatedly. 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 sets A^ give to that technical r e s u l t . For the free-time problem, the sequences of arcs which a r i s e i n the proof carry along sequences of corresponding i n t e r v a l s of d e f i n i t i o n ^ i ' ^ ^ • According to Hypothesis 1.2(a), we may immediately extract subsequences i f necessary and assume that a. -*• a and b_. -> b f o r some S Q < a < b < . If we then extend each arc i n the sequence to [a,b] so that i t s a t i s f i e s I I . 1 . 6 ( i ) , the Theorem may be applied d i r e c t l y with A. := [a.,b.] n [a,b] . This small modification j u s t i f i e s a l l the 1 1 1 J applications of Theorem II.1.6 i n the free-time case. Free to apply the l i m i t i n g arguments introduced i n Chapter I I , we do so with abandon. In conjunction with Hypothesis 1.2(d), such an argument implies that epl'V'is I d e a l l y closed near [6:,V(0) ] and that an analogue of Hypothesis 1.2(d) holds i n a neighbourhood of 0 (compare Lemma II.4.2). We may therefore c a l c u l a t e the generalized gradients of V . at 0 s t r a i g h t from t h e i r d e f i n i t i o n s . Rockafellar's proposition (II.4.3) aids i n t h i s task i t s t e c h n i cal hypothesis follows j u s t as i n Lemma II.4.6. A l l that remains i s to investigate the properties of a normal vector '•vo,~^0'' 0 D t a l n e d from a sequence of perpendiculars [v.^,-8^] ± epi V at [u^,^] -* [0,V(0)] , [0,0]., as f v 0'~^0'' = i " " ^ ! J f v ^ - B j | ' E x a m i n i n 8 J u s t o n e such perpendicular [v^,-g ] leads to an a u x i l i a r y free-time problem without perturbation through Proposition 1.2.4; the necessary conditions 2.2 y i e l d a corresponding quadruple [p^>q^»£^,A^] which strongly resembles the multipV. l i e f we require (compare Lemma II.4.4). Several a p p l i c a t i o n s of Theorem II.1.6 serve to recover s i m i l a r m u l t i p l i e r conditions involving the l i m i t vector [VQ,~BQ] (Lemma I I . 4 . 5 ) — t h i s i s where nondegeneracy i s e s s e n t i a l . The formulas i n the theorem merely restate these conditions. Here ends our overview of the proof. 4 APPLICATION: THE MINIMUM TIME PROBLEM To solve the minimum time problem, one must i s o l a t e an F-tr a j e c t o r y which transfers a given i n i t i a l 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 ries with the s t a r t i n g p o s i t i o n , thereby defining the function T:Rn -> R y {+°°} v i a T(v) := inf{ T : x(t) € F ( t , x ( t ) ) a.e. on [0,T], x(0) = v , x(T) = 0 } . In a p p l i c a t i o n s , the o r i g i n of R n often represents the operating point of an e l e c t r i c a l or mechanical system i n which deviations from the nominal state must be corrected as quickly as possible. The generalized gradient 3T(v) re l a t e s the s e n s i t i v i t y of the minimum time-value to small changes i n the i n i t i a l deviation v . For f i x e d nonzero v , Theorem 3.3 allows us to evaluate 3T(v) as 9V(0) , where the data de f i n i n g V are f(a,x(a),b,x(b),u) := b , S := [ 0,v,0 , 0 , 0 ] + u ({0}x{u}xRx{0}x{ u}) , u eR and a multifunction F(t,x) independent of u . For any F- t r a j e c t o r y x(«) on [0,T] with x(0)=v and x(T)=0 , the conditions defining a m u l t i p l i e r [Pjq,?»A] i n M A(x) r e a d i l y imply (a) r, = [ 0 , 0 , 1 , 0 , 0 ] , (b) [h,-p,x](t) 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] + Ns(0,v,.T,0,0) . The analysis of section 1.7 allows us to compute N = u t,(Rx{u}x{0}xRx{-u}) U£R for any base point i n S . Thus N i s a closed multifunction (Hypothesis 1..2(e)). Also, condition (c) implies q=p(0) so the perturbation defining V i s nondegenerate (Hypothesis 3.2). These conditions lead to the expression Q[M A(x)] = { -p(0) : [h,-p,x] e 9H(t,x,p) a.e. on [0,T] , h(t) =H(t,x(t),p(t)) a.e. on [0,T] , h(T) = X } . Under Hypotheses 1.2(a)-(d) we may apply Theorem 3.3 to derive the expression 9T(v) = 9V(0) = ô~{ Q[M 1(Y)]n9V(0) + Q[M°(Y) ] n9°°V(0) ;, } . If the data of the problem are such that X=0 implies p=0 ( t h i s w i l l be the case i f , f o r example, 0 e i n t F(T(v),0)), then Q[M°(Y)] = {0} and we f i n d that T i s L i p s c h i t z near v , with 9T(v) = co{ Q[M 1(Y)]n9T(v) } . This implies (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 i n c l u s i o n ext 9T(v) c { -p(0) : f o r some s o l u t i o n x on [0,T(v)] with x(0) = v, p:[a,b] -»• R n obeys • • • [h,-p,x] e 9H(t,x,p) for.some a r c : .h/:s.t. h(t) = H ( t , x ( t ) , p ( t ) ) a.e., h(T(v)) = 1 } . Note that the theory of s e n s i t i v i t y developed here cannot provide any information about 9T(0) , since the " s o l u t i o n arcs" required to define Q[M A(Y)] are defined on the degenerate i n t e r v a l [0,0] . 5 ENDPOINT PERTURBATIONS AND NORMAL CONES Each of the three s p e c i f i c perturbation analyses above (sections II.5 and III.4) presents endpoint constraints i n the form [a,x(a),b,x(b)] e C(u) f o r some given multifunction C:Rm RxR nxRxR n . Such constraints f i t into the mold of problem P i f we take S to be the graph of C : S • := u (C(u) x {u}) . u e R m The reverse approach i s possible too: i f the set S i s given, the endpoint constraints may be recast as [a,x(a) ,b,x(b) ] e C(u) := { [a,x,g,y] : [;a,x,g,y,u] e S } ; S i s the graph of the m u l t i f u n c t i o n so defined. Hence the formulation of endpoint constraints i n terms of a multifunction, which a r i s e s n a t u r a l l y i n the examples studied above, retains a l l the generality inherent i n the formulation of problem P . The s p e c i f i c multifunctions analysed above a l l have such simple structures that N g ( - ) i s either closed automatically (section 4) or by mild a u x i l i a r y hypotheses (item II.5.5). This section reverses the s p i r i t of our previous studies: instead of t r y i n g to prove that a preassigned endpoint perturbation scheme S has a well-behaved normal cone, i t seeks to impose conditions on C which w i l l guarantee that N g i s a closed m u l t i f u n c t i o n . To s i m p l i f y the notation, we investigate an upper semlcontinuous multifunction T:R m -> R n, whose graph i s G := { [x,y] : y e F'(x) }j instead of C . modulo an i n s i g n i f i c a n t permutation of components 56. 5.1 Example Here i s a L i p s c h i t z multifunction r:R R whose values are compact convex sets, but whose graph G has a normal cone which f a i l s to be closed at the o r i g i n . We define r(u) := [0,f(u)] , where f:R -> R i s the piecewise l i n e a r function which l i n e a r l y interpolates the following values: f ( t ) { 0 i f t e ( - 0,0] u {2 n an integer} 4" n i f t = 3.2~ n" 2 f o r n = 1, 2, 3, . . The multifunction r i s evidently L i p s c h i t z ; i t s graph i s the region bounded by the x-axis and the graph of f as shown i n Figure 2. Figure 2. The graph of r Now the d e f i n i t i o n i n item 1.3.1 shows that N (2 n,0) = R 2 for a l l n>2 , but that N G(0,0) = {0}xR . Worse yet, i f the set G i s rotated through IT/4 radians, i t defines (at l e a s t near [0,0]) the graph of a multifunction which i s compact-convex-valued 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 "Inverse," but whose normal cone s t i l l defines a multifunction which i s not closed at [0,0] . (The "inverse" of a m u l t i - function r i s the multifunction r ^(y) := { x : y e r(x) } .) • Example 5.1 shows that a multifunction may obey several strong hypotheses, but stubbornly refuse to generate a graph with a well-behaved normal cone. It does not, however, unearth a serious shortcoming i n our theory. For no perturbation problems of in t e r e s t involve a constraint multifunction l i k e T . Why? Loosely speaking, r - i s unacceptable because i t has, to f i r s t order, no u-dependence near zero. To see t h i s , observe that the L i p s c h i t z rank of r can be made a r b i t r a r i l y small by r e s t r i c t i n g the domain of r to ever smaller neighbourhoods of 0 . The flaws of r w i l l become even more apparent as our study proceeds. 5.2 Lemma Let G be a closed subset of R m + n 3 and let zeG . Then conditions (a) and (b) ave equivalent. Moreover, either of them implies that the multifunction N (•) is closed at z . G (a) i n t T (z) * 0 . G Cb) N (z) is pointed. G PROOF According to Theorem 2.5.8 (Corollary 2) of [1], condition (a) implies that N (•) i s closed at z . We need only show (a) <=> (b). G (a => b) If i n t T (z) * 0 , then the assertion that <v,w> = 0 for a l l w i n T (z) must imply v=0 . (Otherwise T (z) l i e s i n a proper subspace of (j G R m + n, which i s absurd.) Hence <v,w> < 0 f o r a l l w i n T (z) — t h a t i s , G v e N (z) — i m p l i e s -v i N (z) unless v=0 . In.other words, N (z) G G (J contains no l i n e : by d e f i n i t i o n , N r(z) i s pointed. (b => a) If i n t T (z) = 0 , then T n(z) l i e s i n a proper subspace of R m + n G G Every l i n e i n the orthogonal complement of t h i s subspace l i e s i n N (z) , so G N (z) i s not pointed. Contrapose. • G Corollary If G is either a convex set with nonempty interior or a smooth set with nonempty interior, then N (•) is closed at z . G PROOF Either hypothesis implies that N (z) i s pointed. • G The conditions of Lemma 5.2 have an appealing geometric s i g n i f i c a n c e . The following r e s u l t of Rockafellar's (reported i n [1]) adds even more ins i g h t into the shape of a set s a t i s f y i n g these c r i t e r i a . I t t e l l s us that condition 5.2(a) holds i f and only i f G has the same form ( l o c a l l y ) as the epigraph of a L i p s c h i t z function. To s i m p l i f y the notation, we consider a closed subset C of R n and a point x i n C . The set C i s . - epi-Lipschitzian at x i f there are an i n v e r t i b l e l i n e a r transformation A:Rn -»- R n "'"xR , a neighbourhood U of x , and a function <Ji:Rn ^ -> R such that U n C = U n A _ 1 ( e p i <f>) and ij) i s L i p s c h i t z hear the R n ''"-component of A(x) . 5.3 Theorem Let C be a closed subset of R n , and let xeC . Then the following two assertions are equivalent. (a) i n t T c(x) * 0 . (b) C is epi-Lipschitzian at x . More s p e c i f i c r e s u l t s ensuring that N_, i s a closed multifunction-seem G e l u s i v e . Substantial progress i s possible, however, i n the very common s i t u a t i o n where the constraint set i s determined by a system of i n e q u a l i t i e s . Consider the multifunction r defined by r(u) := { y : f 1( u,y)<0, f 2(u,y)<0, . . f k(u,y)<0 } , where each f^:RmxRn -> R is Lipschitz. The graph of r is simply the set G := { [u,y] : f^u.y^O, f 2(u,y)<0, . . ., f k(u,y)<0 } . If a point [0,y] in G is given, we define 1(0,y) : = ' { i : f^(0,y)=0 } . 5.4 Theorem Let r be given as above, with y e 1(0) . If the set of vectors { 9f^(0,y) : i e 1(0,y) } is positively linearly independent, then N (•) is closed at [0,y] . G A PROOF If l(0,y) = 0 , then the indicated set of vectors i s empty and t r i v i a l l y positively linearly independent. But also f i(0,y) < 0 for a l l i , so [0,y] e int G and N (*,•) reduces to {0} on a neighbourhood of " G f0,y] . The conclusion follows. We therefore assume 1(0,y) * 0 . Define f(u,y) := max( f^(u,y) : i=l,2,...,k }. It is easy to see that f is Lipschitz near [0,y] , and that G = ' { [u,y] : f(u,y) < 0 = f(0,y) } . Now by Proposition I". 6. 7, 3f(0,y) c C O{ 9f ±(0,y) : i e 1(0,y) } . By assumption, the right-hand side of this inclusion is positively linearly independent: i t follows that 9f(0,y) is too, and in particular that 0 i 9f(0,y) . Theorem 2.4.7 (Corollary 1) of [1] therefore applies; i t asserts that N„(0,y) c u r9f(0,y) . G r>0 But the right-hand side contains no line, because 3f(0,y) is positively linearly independent. Hence N (0,y) is pointed, and the desired conclusion G follows from Lemma 5.2. D Corollary N (0,y) c u r co{ 8f,(0,^) : 1 e 1(0,y) } . G r£0 1 The p o s i t i v e l i n e a r independence required by Proposition 5.4 may be expressed as follows: there i s a vector v i n R m + n such that whenever i e KO,y) , <v,s> < 0 f o r a l l £ i n 8^(0,^) . This i s very c l o s e l y r e l a t e d to the well-known Mangasarian-Fromowitz constraint qualification of (unperturbed) mathematical programming. Indeed, i t reduces to t h i s condition i f each function f ^ i s smooth and independent of u . Of course, u-dependence i s t h i s thesis's raison d'etre, but t h i s reduction serves to show that the hypothesis of Proposition 5.4 i s even weaker than the standard constraint q u a l i f i c a t i o n . For the many d i f f e r e n t u-dependences possible i n the constraint functions make the p o s i t i v e l i n e a r independence of { Vf^(0,y) : i e 1(0,y) } even more l i k e l y than that of { V f.(0,y) : i e 1(0,y) } . In p a r t i c u l ar, i f the unperturbed constraint set 1(0) s a t i s f i e s the (unperturbed) Mangasarian-Fromowitz condition, then the hypothesis of the proposition holds automatically. Mathematical programmers invoke the constraint q u a l i f i c a t i o n to ensure that the constraints defining the f e a s i b l e set are not somehow degenerate: the hypothesis of Proposition 5.4 seeks only to avoid degeneracy i n the combination of con-:, s t r a i n t s and perturbations. The constraint sets of Example 5.1 i l l u s t r a t e the degeneracy which must be avoided. The multifunction V defined there has the form treated by Proposition 5.4, with .k=2 . To see t h i s , take f^(u,y) := -y and f2(u,y) := y - f(u) , where f i s the function constructed i n Example 5.1. It i s a simple matter to compute 3f 1(0,0) = {[0,-1]} and 8f 9(0,p)={[0,+l]}. These sets 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 independent quantitative i n d i c a t i o n that the multifunction T of Example involves an unacceptable perturbation structure. CHAPTER I V APPLICATIONS 1 CONTROLLABILITY 1.1 Admissible Arcs Small changes i n the data 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 induce v a r i a t i o n s i n the problem's f a m i l y of admi s s i b l e a r c s . In t h i s s e c t i o n , we i n v e s t i g a t e the admissible sets A(u) : = ' { x e AC[a,b] : x ( t ) e F ( t , x ( t ) , u ) a.e. on [a,b] , [x(a),x(b),u] e S } . We as sume that F and S s a t i s f y Hypotheses I I . 3 . 2 ( a ) ( b ) . I f A(u) i s empty, then no F - t r a j e c t o r y j o i n s an acceptable p a i r of i n i t i a l and t e r m i n a l s t a t e s . Systems and c o n t r o l engineers express t h i s unhappy occurrence by saying that the dynamical 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 which ensures t h a t A(u) i s n o n v o i d — t h a t i s , that the system d e f i n i n g A(u) is c o n t r o l l a b l e — f o r u near 0 . The b a s i c approach i s due to Clarke ( [ 1 ] , see s e c t i o n 3.5). I t r e l i e s h e a v i l y on the s e n s i t i v i t y a n a l y s i s of Chapter I I . Corresponding _ r e s u l t s f o r problems w i t h f r e e time permit a c l o s e l y analogous treatment, but r e q u i r e more n o t a t i o n . - 62 - 1.2 Normality An arc x(.) i n A(0) i s normal i f Hypotheses 11.3.2(e) and II.3.4 hold when Y i s replaced by {x(.)} , and i f the two conditions (a) [ - p ( t ) , - q ( t ) , x ( t ) ] e g H ( t , x ( t ) , 0 , p ( t ) ) a.e. on [a,b] and (b) [p(a),-p(b),-q(b)] e N g(x(a),x(b),0) imply that q(a)=0 . (By II.3.4, i t follows that p=0 and q=0 .) When an objective function f i s given, i t defines a value function V(u) := i n f { f(x(a),x(b),u) : x ( 0 e A(u) } and a corresponding optimization problem P . We say that P i s normal i f Hypothesis 11.3.4(d) holds and each of the arcs solving P(0) i s normal. 1.3 Lemma If problem P is normal, then V is Lipschitz near zero. PROOF I f P i s normal, then Q[M°(Y)] = {0}.. Apply Theorem 4.1, Coroll a r y 1. • 1.4 Proposition Suppose the arc x(«) in A(0) is normal. Then there are positive constants z and M such that for each u in eB , there is an arc x(») in A(u) such that [x - x ^ =. |x(t) - x(t) I dt < M|u| . PROOF Consider the function V:Rm'->- R u" {+»} defined by V(u) := inf{ / b |x(t) - x ( t ) | dt : x(-) e A(u) } . Its values are c l e a r l y nonnegative. When u=0 , the unique solution..to the problem defining V(0) i s x(«) ; i t forces V(0) = 0 . The function V may also be expressed as the value function of the perturbed d i f f e r e n t i a l i n c l u s i o n problem P whose data incorporate a scalar arc x n(*) as follows. f(x 0,x,y 0,y,u) := y Q F(t,x 0,x,u) := {|x - x(t)|} x F(t,x,u) S := { [0,x,r,y,u] : [x,y,u] e S , r e R } The arc [0,x(*)]_ i s the unique s o l u t i o n to problem P(0) . Hypotheses II.3.2(a)-(d) evidently hold for problem P ; the analysis below w i l l e s t a b l i s h Hypothesis 11.3.2(e). Any m u l t i p l i e r [pQ>P»q,C,A] corresponding to [0,x(«)l must obey the t r a n s v e r s a l i t y condition [p Q(a),p(a),-p Q(b) -,-p(b),-q(b)] e A[0,0,1,0,0,0] + Ns(0,x(a),0,x(b),0) . Upon computing N g(0,x,y,r,u) = { [s,£,0,n,n' ] : U,n,n'] e Ng(x,y,u), seR } , we f i n d that t h i s implies P Q ( ° ) = -X and (i) [p(a),- P(b),-q(b)] £ N s(x(a),x(b),0) . The Hamiltonian f o r problem P i s H(t,x 0,x,u,p 0,p) = p Q|x - x ( t ) j + H(t,x,u,p) . By Proposition 1.6.6, 3H(t,0,x(t),0,p 0(t),p(t)) c {0} x p Q ( t ) B x {[0,0,0]} + { [0,5, Y,0,ri] : U,Y,u] e 3H(t,x(t),0,p(t)) } . The Hamiltonian i n c l u s i o n implies PQ(*) = _ A A N C * ( i i ) [ - p ( t ) , - q ( t ) ,x(t)] e ABx{[0,0]} + 3H(t,x(t),0,p(t)) a.e. Now i f A=0 , conditions ( i ) and ( i i ) above exhibit [p,q] as the adjoint component of a m u l t i p l i e r i n M^(x) . Since the arc x i s non-. degenerate by assumption, Hypothesis II.3.4 holds for the problem P introduced here. Moreover, x i s a normal arc as defined i n item 1.2, and hence [0,x(«)l i s normal f o r problem P . Thus P i s a normal problem, and V i s L i p s c h i t z near zero by Lemma 1.3. In p a r t i c u l a r , there are p o s i t i v e constants M and e such that M|u| > |v(u) - V(0)| = V(u) f o r a l l u i n eB . Thus f o r any u i n eB , there i s some arc x(*) i n A(u) such that fx - = fl |x(t) - £<t)| dt < M|u| . 2 EXAMPLE: A ONE-SECTOR ECONOMY Consider a factory manager's problem as he s i t s down to plan h i s corporate strategy f o r the f i x e d time period [0,T] . The state of h i s factory i s measured by i t s productive capacity x(t) at time t . At each instant, a c e r t a i n f r a c t i o n u(t) of the factory's productive e f f o r t may be applied toward increasing i t s capacity f o r production: the r e s u l t i s that the capacity grows according to the law x(t) = u ( t ) x ( t ) . The remaining output i s to be sold at a f i x e d p r i c e : 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 to ( l - u ( t ) ) x ( t ) dt . The manager's objective i s to choose the f r a c t i o n u(t) i n [0,1] to maximize his company's p r o f i t : i t can be posed as the following optimization problem. max{ / J ( l - u ( t ) ) x ( t ) dt : x(t) = u ( t ) x ( t ) , 0 < u(t) < 1 , x(0) = c > 0 } This problem i s a s i m p l i f i e d version of the Ramsey model for a one-sector economy presented i n Fleming and Rishel [2], Example II.2.2. It can be solved d i r e c t l y i n several ways; Pontryagin's maximum p r i n c i p l e w i l l y i e l d a unique candidate for the s o l u t i o n , f o r example. Suppose now that the factory manager revises h i s objective: he no longer wants to maximize his t o t a l p r o f i t s , but rather seeks to maximize the present value of the revenue he w i l l gain during the planning period. If the discount rate i s 6 , he seeks max{ / Q e ( l - u ( t ) ) x ( t ) dt : x(t) = u ( t ) x ( t ) , 0 < u(t) < 1 , x(0) = c > 0 } . We propose to estimate the s e n s i t i v i t y of h i s expected return as <5 varies near zero. To do so, we define the value function V(6) := min{ -/J e _ < S t ( l - u ( t ) ) x ( t ) dt : x(t) = u ( t ) x ( t ) , 0 < u(t) < 1 , x(0) = c > 0 } . (V measures the negative of the firm's maximum p r o f i t . ) Our study w i l l show how t h i s optimal control problem can be cast as a d i f f e r e n t i a l i n c l u s i o n problem, and how Theorem II.4.1 applies to c a l c u l a t e 9V(0) . To make the problem i n t e r e s t i n g , we assume T>1 . Note f i r s t that the control problem defining V(.S) can be solved d i r e c t l y by applying, say, Pontryagin's p r i n c i p l e . A f t e r some c a l c u l a t i o n , one can define a switching time x := T + -̂ £n(l-6) and discover the optimal strategy u(t) = 1 j.^ ^ - j ^ • T h e productive capacity obeys {ce~ on [0,x] c ( l - 6 ) 1 / 6 e T on [x,T] The adjoint t r a j e c t o r y comes to r u-6)/6 a-syi, - t r n L(l-o) e ] e on [0,x] P ( t > = * 1 t " 6 t " ^ r T I j (e - e ) on [ T , T ] ; (1—(5)/6 (1—6)T the (negative) present value i s V(5) = -c(l-<5) e '. L'Hospital's rules give V(0) = - c e T - 1 and V'(0) = - c ( ^ - T ) e T _ 1 . To express V as the value function of a d i f f e r e n t i a l i n c l u s i o n problem, define f(x 0,x,y 0,y,S) := - y Q , F(t,x ,x,6) := { [e~ x(l-v),xv] : 0 < v < 1 } , and S := {[0,c]}xRxRxR . Then V(fi) = min{ f ( X ( )(0) ,x(0) ,x Q(T) ,x(T)) : [x Q,x] e F(t,x Q,x,6) , [x 0(0),x(0),x 0(T),x(T)]£S } . The Hamiltonian i s —St f/(t,x Q,x, <S,pQ,p) = max{ p Qe x(l-v) + pxv : 0 < v < 1 } —<5t —St = p^e x + max{ v(px - p^e x) : 0 < v < 1 } = p^e x + max{px - p^e x , 0} r —6t , , _ S t , = max{px , PQ£ X} = x«max{p , p^e } It i s even easier to compute N g = RxRx{[0,0,0]} at any base point i n S and 9f = {[0,0,-1,0,0]} everywhere. Now to compute 8V(0) using Theorem 4.1, we need only consider solutions to prohl 6m P(0) — t h a t , i s , the easy pirobXem i n which no discount rate appears. And any arc solving P(0) has a n o n t r i v i a l m u l t i p l i e r [pQ»P sq,?»A] by Corol l a r y 2 of Theorem I I . 4 . 1 . So suppose [XQ(«),X(«)] i s ah admissible arc and [pQ,p,q,C,A] the corresponding n o n t r i v i a l m u l t i p l i e r . Then since H has no x^-dependence, -p^ = 0 . The t r a n s v e r s a l i t y condition [p 0,p(0),-p 0,-p(T),-q(T)] e A[0,0,1,0,0] + RxRx{[0,0,0]} implies that p^ i s the constant arc A. , and that p(T) = q(T) = 0 . With the a i d of Proposition 1.6.7, we f i n d that the Hamiltonian i n c l u s i o n implies [0,A,-Atx,x,0] i f p <;A • • • • [0>-p 5-q,x 0,x] e 3n(t,x 0,x,0,p 0,p) = < [0,p, 0 ,0,x] i f p > A convex h u l l of these i f p = A » Now when A=0 , -q=0 implies q=0 . The m u l t i p l i e r i s t r i v i a l and Q[M°(Y)] = {0} . We may therefore take A=l . Then p(T) = 0 < 1 = A implies that p = -1 on [T-1,T] , while -p = p on [0,T-1] . Consequently x = x on [0,T-1] and x = 0 on [T-1,T] , while x Q = 0 on [0,T-1] and x Q = x(T) on [T-1,T] . We also obtain q = 0 on [0,T-1] and q = tx(t) on [T-1,T] . Upon integr a t i n g these equations, we f i n d the unique multt- i p l i e r of index 1 ..for problem P(0) . { e ^ 1 ^ on [0.T-1] P(t) T - t on [T-1,T] on [0,T-1] T - l x(t) = I ce on [T-1,T] 69. x 0 ( t ) = l T - l . V. ce ( t - on [0,T-1] T+l) on [T-1,T] {c e T ^ ( ^ - T ) T 1 W ( t 2 - T 2 ) on [0,T-1] on [T-1,T] T - l —1 Hence -q(0) = -ce (h-T) i s the only point i n Q[M (Y)] . I t follows T - l that 8V(0) = {-c(^-T)e } . The analysis of t h i s case i s much simpler, than that required to f i n d V(6) d i r e c t l y and then compute 9V(0) . BIBLIOGRAPHY 1. Clarke, Frank H. Optimization and Nonsmooth Analysis. New York: Wiley-Interscience, 1983. 2. Fleming, Wendell H., and Raymond W. R i s h e l . Deterministic and Stochastic Optimal Control. New York: Springer-Verlag, 1975. 3. Fr a n k l i n , J o e l . Methods. of Mathematical Economics: Linear and Nonlinear Programming, Fixed Point Theorems. New York: Springer- Verlag, 1980. 4. Legge, J. The Chinese Classics. V o l . I. London: 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 Value Functions i n Nonlinear Programming." Mathematical Programming Study, 17 (1982), 28-66. - 70 - APPENDIX AN APPLICATION OF GRONWALL'S INEQUALITY Let the multifunction F s a t i s f y the hypotheses of Chapter I I . We may then compute H(t,x,p) := sup{<p,F(t,x) >} . Proposition 3.2.4 of [1] avers that f o r any given [t,x,p] , the map x' ->H(t,x',p) i s L i p s c h i t z of rank |p|k(t) near p . Thus the f i r s t component of 8H(t,x,p) i s (by Theorem 1.6.3) a convex combination of vectors i n |p[k(t)B . If [p,x](-) i s an arc such that [-p,x] e 8H(t,x,p) a.e., we must have -p(t) e |p(t)|k(t)B a.e. Hence | |p(t) | - |p(a)| | < |p(t) - p(a)| < |/fcpCs) ds| a < / f c |p(s)| ds < / f c |p(s)|k(s) ds , and a a |p(t) | < |p( a) | + fl |p(s) |k(s) ds . a By Gronwall's i n e q u a l i t y (Fleming and Rishel [2], p. 198), |p(t)| < |p(a)| + |p(a)| / f c k(s) exp(/^ k(x) dx} ds . a s In p a r t i c u l a r , p(a) = 0 implies p(t) = 0 f o r t>a . In l i k e manner, p(b) = 0 implies p(t) = 0 for t<b . We summarize. Lemma 1 If the adjoint trajectory for a Hamiltonian system ever vanishes, i t is the zero arc. Corollary If [p,q,?,A] e M A(x) is a multiplier for a perturbed problem and the arc [p,q] vanishes somewhere, then i t is the zero arc. - 71 -

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 1 0
United States 1 0
City Views Downloads
Beijing 1 0
Ashburn 1 0

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

Share

Share to:

Comment

Related Items