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-J^ -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 {Y^ } obeying Y^ € 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 - 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) = o^~{ 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 -
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- The sensitivity of optimal value functions in differential...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
The sensitivity of optimal value functions in differential inclusion problems Loewen, Philip Daniel 1983
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | The sensitivity of optimal value functions in differential inclusion problems |
Creator |
Loewen, Philip Daniel |
Publisher | University of British Columbia |
Date Issued | 1983 |
Description | In many practical situations, the parameters of a control system are not known exactly. For this reason, much recent literature is concerned with the sensitivity of dynamic optimization problems to small perturbations of their basic character. This thesis discusses the sensitivity of a general differential inclusion problem to perturbations of its 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 in the problem's optimal value. After Chapter I reviews the calculus of generalized gradients, Chapter II provides a formula for a certain quantitative index of the problem's sensitivity to changes in u: the generalized gradient of V. The basic approach is that used by Clarke in "Optimization and Nonsmooth Analysis" (New York: Wiley-Interscience, 1983)., Theorem 3.4.3. The results presented in Chapter II compare well with Clarke's in the appropriate special case. Chapter III extends the sensitivity analysis of Chapter II to treat free time problems, in which the planning period is a further choice variable. A brief discussion of controllability and an example from mathematical economics constitute Chapter IV. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-04-21 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0095673 |
URI | http://hdl.handle.net/2429/23970 |
Degree |
Master of Science - MSc |
Program |
Statistics |
Affiliation |
Science, Faculty of Statistics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1983_A6_7 L63.pdf [ 3.68MB ]
- Metadata
- JSON: 831-1.0095673.json
- JSON-LD: 831-1.0095673-ld.json
- RDF/XML (Pretty): 831-1.0095673-rdf.xml
- RDF/JSON: 831-1.0095673-rdf.json
- Turtle: 831-1.0095673-turtle.txt
- N-Triples: 831-1.0095673-rdf-ntriples.txt
- Original Record: 831-1.0095673-source.json
- Full Text
- 831-1.0095673-fulltext.txt
- Citation
- 831-1.0095673.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0095673/manifest