Grundlehren der mathematischen Wissenschaften 330 ASeriesofComprehensiveStudies inMathematics Serieseditors M.Berger B.Eckmann P.delaHarpe F.Hirzebruch N.Hitchin L.Hörmander M.-A.Knus A.Kupiainen G. Lebeau M.Ratner D.Serre Ya.G.Sinai N.J.A.Sloane B.Totaro A.Vershik M.Waldschmidt Editor-in-Chief A.Chenciner J.Coates S.R.S.Varadhan Boris S. Mordukhovich Variational Analysis and Generalized Differentiation I Basic Theory ABC BorisS.Mordukhovich DepartmentofMathematics WayneStateUniversity CollegeofScience Detroit,MI48202-9861,U.S.A. E-mail:[email protected] LibraryofCongressControlNumber:2005932550 MathematicsSubjectClassification(2000):49J40,49J50,49J52,49K24,49K27,49K40, 49N40,58C06,58C20,58C25,65K05,65L12,90C29,90C31,90C48,93B35 ISSN0072-7830 ISBN-10 3-540-25437-4SpringerBerlinHeidelbergNewYork ISBN-13 978-3-540-25437-9SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation,broadcasting, reproductiononmicrofilmorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9, 1965,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsare liableforprosecutionundertheGermanCopyrightLaw. SpringerisapartofSpringerScience+BusinessMedia springeronline.com (cid:1)c Springer-VerlagBerlinHeidelberg2006 PrintedinTheNetherlands Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply, evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotectivelaws andregulationsandthereforefreeforgeneraluse. Typesetting:bytheauthorandTechBooksusingaSpringerLATEXmacropackage Coverdesign:design&productionGmbH,Heidelberg Printedonacid-freepaper SPIN:10922989 41/TechBooks 543210 To Margaret, as always Preface Namely, because the shape of the whole universe is most perfect and, in fact, designed by the wisest creator, nothing in all of the world will occur in which no maximum or minimum rule is somehow shining forth. LeonhardEuler(1744) We can treat this firm stand by Euler [411] (“...nihil omnino in mundo con- tingint, in quo non maximi minimive ratio quapiam eluceat”) as the most fundamental principle of Variational Analysis. This principle justifies a va- riety of striking implementations of optimization/variational approaches to solving numerous problems in mathematics and applied sciences that may notbeofavariationalnature.Rememberthatoptimizationhasbeenamajor motivation and driving force for developing differential and integral calculus. Indeed, the very concept of derivative introduced by Fermat via the tangent slope to the graph of a function was motivated by solving an optimization problem;itled towhatisnowcalled theFermat stationary principle. Besides applications to optimization, the latter principle plays a crucial role in prov- ing the most important calculus results including the mean value theorem, theimplicitandinversefunctiontheorems,etc.Thesamelineofdevelopment can be seen in the infinite-dimensional setting, where the Brachistochrone was the first problem not only of the calculus of variations but of all func- tionalanalysisinspiring,inparticular,avarietyofconceptsandtechniquesin infinite-dimensional differentiation and related areas. Modernvariationalanalysiscanbeviewedasanoutgrowthofthecalculus ofvariationsandmathematicalprogramming,wherethefocusisonoptimiza- tion of functions relative to various constraints and on sensitivity/stability of optimization-relatedproblemswithrespecttoperturbations.Classicalnotions of variations such as moving away from a given point or curve no longer play VIII Preface acriticalrole,whileconceptsofproblemapproximationsand/orperturbations become crucial. One of the most characteristic features of modern variational analysis is the intrinsic presence of nonsmoothness, i.e., the necessity to deal with nondifferentiable functions, sets with nonsmooth boundaries, and set-valued mappings. Nonsmoothness naturally enters not only through initial data of optimization-relatedproblems(particularlythosewithinequalityandgeomet- ric constraints) but largely via variational principles and other optimization, approximation, and perturbation techniques applied to problems with even smooth data. In fact, many fundamental objects frequently appearing in the framework of variational analysis (e.g., the distance function, value functions in optimization and control problems, maximum and minimum functions, so- lution maps to perturbed constraint and variational systems, etc.) are in- evitablyofnonsmoothand/orset-valuedstructuresrequiringthedevelopment of new forms of analysis that involve generalized differentiation. Itisimportanttoemphasizethateventhesimplestandhistoricallyearliest problems of optimal control are intrinsically nonsmooth, in contrast to the classical calculus of variations. This is mainly due to pointwise constraints on controlfunctionsthatoftentakeonlydiscretevaluesasintypicalproblemsof automaticcontrol,aprimarymotivationfordevelopingoptimalcontroltheory. Optimal control has always been a major source of inspiration as well as a fruitful territory for applications of advanced methods of variational analysis and generalized differentiation. Key issues of variational analysis in finite-dimensional spaces have been addressedinthebook“VariationalAnalysis”byRockafellarandWets[1165]. The development and applications of variational analysis in infinite dimen- sions require certain concepts and tools that cannot be found in the finite- dimensional theory. The primary goals of this book are to present basic con- cepts and principles of variational analysis unified in finite-dimensional and infinite-dimensional space settings, to develop a comprehensive generalized differentialtheoryatthesamelevelofperfectioninbothfiniteandinfinitedi- mensions, and to provide valuable applications of variational theory to broad classes of problems in constrained optimization and equilibrium, sensitivity and stability analysis, control theory for ordinary, functional-differential and partial differential equations, and also to selected problems in mechanics and economic modeling. Generalized differentiation lies at the heart of variational analysis and its applications. We systematically develop a geometric dual-space approach to generalized differentiation theory revolving around the extremal principle, which can be viewed as a local variational counterpart of the classical convex separationinnonconvexsettings.Thisprincipleallowsustodealwithnoncon- vex derivative-like constructions for sets (normal cones), set-valued mappings (coderivatives), and extended-real-valued functions (subdifferentials). These constructionsaredefineddirectlyindualspacesand,beingnonconvex-valued, cannotbegeneratedbyanyderivative-likeconstructionsinprimalspaces(like Preface IX tangent cones and directional derivatives). Nevertheless, our basic nonconvex constructions enjoy comprehensive calculi, which happen to be significantly better than those available for their primal and/or convex-valued counter- parts. Thus passing to dual spaces, we are able to achieve more beauty and harmony in comparison with primal world objects. In some sense, the dual viewpoint does indeed allow us to meet the perfection requirement in the fundamental statement by Euler quoted above. Observe to this end that dual objects (multipliers, adjoint arcs, shadow prices, etc.) have always been at the center of variational theory and applica- tionsused,inparticular,forformulatingprincipaloptimalityconditionsinthe calculus of variations, mathematical programming, optimal control, and eco- nomicmodeling.Theusageofvariationsofoptimalsolutionsinprimalspaces can be considered just as a convenient tool for deriving necessary optimality conditions. There are no essential restrictions in such a “primal” approach in smooth and convex frameworks, since primal and dual derivative-like con- structions are equivalent for these classical settings. It is not the case any more in the framework of modern variational analysis, where even nonconvex primal space local approximations (e.g., tangent cones) inevitably yield, un- der duality, convex sets of normals and subgradients. This convexity of dual objects leads to significant restrictions for the theory and applications. More- over, there are many situations particularly identified in this book, where primal space approximations simply cannot be used for variational analysis, while the employment of dual space constructions provides comprehensive results. Nevertheless, tangentially generated/primal space constructions play an important role in some other aspects of variational analysis, especially in finite-dimensional spaces, where they recover in duality the nonconvex sets of our basic normals and subgradients at the point in question by passing to the limit from points nearby; see, for instance, the afore-mentioned book by Rockafellar and Wets [1165] Among the abundant bibliography of this book, we refer the reader to the monographsbyAubinandFrankowska[54],BardiandCapuzzoDolcetta[85], Beer[92],BonnansandShapiro[133],Clarke[255],Clarke,Ledyaev,Sternand Wolenski [265], Facchinei and Pang [424], Klatte and Kummer [686], Vinter [1289],andtothecommentsgivenaftereachchapterforsignificantaspectsof variational analysis and impressive applications of this rapidly growing area that are not considered in the book. We especially emphasize the concur- rent and complementing monograph “Techniques of Variational Analysis” by BorweinandZhu[164],whichprovidesaniceintroductiontosomefundamen- tal techniques of modern variational analysis covering important theoretical aspects and applications not included in this book. The book presented to the reader’s attention is self-contained and mostly collects results that have not been published in the monographical literature. Itissplitintotwovolumesandconsistsofeightchaptersdividedintosections and subsections. Extensive comments (that play a special role in this book discussing basic ideas, history, motivations, various interrelations, choice of X Preface terminology and notation, open problems, etc.) are given for each chapter. We present and discuss numerous references to the vast literature on many aspects of variational analysis (considered and not considered in the book) including early contributions and very recent developments. Although there are no formal exercises, the extensive remarks and examples provide grist for further thought and development. Proofs of the major results are complete, while there is plenty of room for furnishing details, considering special cases, and deriving generalizations for which guidelines are often given. Volume I“BasicTheory”consistsoffourchaptersmostlydevotedtobasic constructions of generalized differentiation, fundamental extremal and varia- tionalprinciples,comprehensivegeneralizeddifferentialcalculus,andcomplete dualcharacterizationsoffundamentalpropertiesinnonlinearstudyrelatedto Lipschitzian stability and metric regularity with their applications to sensi- tivity analysis of constraint and variational systems. Chapter 1concernsthegeneralizeddifferentialtheoryinarbitraryBanach spaces.Ourbasicnormals,subgradients,andcoderivativesaredirectlydefined in dual spaces via sequential weak∗ limits involving more primitive ε-normals andε-subgradientsoftheFr´echettype.Weshowthattheseconstructionshave a variety of nice properties in the general Banach spaces setting, where the usage of ε-enlargements is crucial. Most such properties (including first-order and second-order calculus rules, efficient representations, variational descrip- tions, subgradient calculations for distance functions, necessary coderivative conditions for Lipschitzian stability and metric regularity, etc.) are collected in this chapter. Here we also define and start studying the so-called sequen- tial normal compactness (SNC) properties of sets, set-valued mappings, and extended-real-valued functions that automatically hold in finite dimensions while being one of the most essential ingredients of variational analysis and its applications in infinite-dimensional spaces. Chapter2containsadetailedstudyoftheextremalprincipleinvariational analysis,whichisthemainsingletoolofthisbook.Firstwegiveadirectvari- ationalproofoftheextremalprincipleinfinite-dimensionalspacesbasedona smoothing penalization procedure via the method of metric approximations. Then we proceed by infinite-dimensional variational techniques in Banach spaces with a Fr´echet smooth norm and finally, by separable reduction, in the larger class of Asplund spaces. The latter class is well-investigated in the geometric theory of Banach spaces and contains, in particular, every reflexive spaceandeveryspacewithaseparabledual.Asplundspacesplayaprominent role in the theory and applications of variational analysis developed in this book. In Chap. 2 we also establish relationships between the (geometric) ex- tremalprincipleand(analytic)variationalprinciplesinbothconventionaland enhanced forms. The results obtained are applied to the derivation of novel variational characterizations of Asplund spaces and useful representations of the basic generalized differential constructions in the Asplund space setting similar to those in finite dimensions. Finally, in this chapter we discuss ab- stract versions of the extremal principle formulated in terms of axiomatically Preface XI defined normal and subdifferential structures on appropriate Banach spaces and also overview in more detail some specific constructions. Chapter 3 is a cornerstone of the generalized differential theory developed in this book. It contains comprehensive calculus rules for basic normals, sub- gradients,andcoderivativesintheframeworkofAsplundspaces.Wepaymost ofourattentiontopointbasedrulesviathelimitingconstructionsatthepoints inquestion,forbothassumptionsandconclusions,havinginmindthatpoint- based results indeed happen to be of crucial importance for applications. A number of the results presented in this chapter seem to be new even in the finite-dimensional setting, while overall we achieve the same level of perfec- tion and generality in Asplund spaces as in finite dimensions. The main issue that distinguishes the finite-dimensional and infinite-dimensional settings is the necessity to invoke sufficient amounts of compactness in infinite dimen- sions that are not needed at all in finite-dimensional spaces. The required compactness is provided by the afore-mentioned SNC properties, which are included in the assumptions of calculus rules and call for their own calcu- lus ensuring the preservation of SNC properties under various operations on sets and mappings. The absence of such a SNC calculus was a crucial obsta- cle for many successful applications of generalized differentiation in infinite- dimensionalspacestoarangeofinfinite-dimensions problemsincludingthose in optimization, stability, and optimal control given in this book. Chapter 3 contains a broad spectrum of the SNC calculus results that are decisive for subsequent applications. Chapter4isdevotedtoathoroughstudyofLipschitzian,metricregularity, and linear openness/covering properties of set-valued mappings, and to their applications to sensitivity analysis of parametric constraint and variational systems. First we show, based on variational principles and the generalized differentiationtheorydevelopedabove,thatthenecessarycoderivativecondi- tionsforthesefundamentalpropertiesderivedinChap.1inarbitraryBanach spaces happen to be complete characterizations of these properties in the As- plundspacesetting.Moreover,theemployedvariationalapproachallowsusto obtain verifiable formulas for computing the exact bounds of the correspond- ing moduli. Then we present detailed applications of these results, supported by generalized differential and SNC calculi, to sensitivity and stability analy- sis of parametric constraint and variational systems governed by perturbed sets of feasible and optimal solutions in problems of optimization and equi- libria, implicit multifunctions, complementarity conditions, variational and hemivariational inequalities as well as to some mechanical systems. Volume II “Applications” also consists of four chapters mostly devoted to applications of basic principles in variational analysis and the developed generalized differential calculus to various topics in constrained optimization andequilibria,optimalcontrolofordinaryanddistributed-parametersystems, and models of welfare economics. Chapter 5 concerns constrained optimization and equilibrium problems with possibly nonsmooth data. Advanced methods of variational analysis XII Preface based on extremal/variational principles and generalized differentiation hap- pentobeveryusefulforthestudyofconstrainedproblemsevenwithsmooth initial data, since nonsmoothness naturally appears while applying penaliza- tion, approximation, and perturbation techniques. Our primary goal is to de- rivenecessaryoptimalityandsuboptimalityconditionsforvariousconstrained problems in both finite-dimensional and infinite-dimensional settings. Note that conditions of the latter – suboptimality – type, somehow underestimated inoptimizationtheory,don’tassumetheexistenceofoptimalsolutions(which isespeciallysignificantininfinitedimensions)ensuringthat“almost”optimal solutions “almost” satisfy necessary conditions for optimality. Besides con- sidering problems with constraints of conventional types, we pay serious at- tention to rather new classes of problems, labeled as mathematical problems with equilibrium constraints (MPECs) and equilibrium problems with equilib- rium constraints(EPECs),whichareintrinsicallynonsmoothwhileadmitting a thorough analysis by using generalized differentiation. Finally, certain con- cepts of linear subextremality and linear suboptimality are formulated in such awaythatthenecessaryoptimalityconditionsderivedaboveforconventional notions are seen to be necessary and sufficient in the new setting. In Chapter 6 we start studying problems of dynamic optimization and op- timal control that, as mentioned, have been among the primary motivations for developing new forms of variational analysis. This chapter deals mostly with optimal control problems governed by ordinary dynamic systems whose statespacemaybeinfinite-dimensional.Themainattentioninthefirstpartof the chapter is paid to the Bolza-type problem for evolution systems governed by constrained differential inclusions. Such models cover more conventional control systems governed by parameterized evolution equations with control regions generally dependent on state variables. The latter don’t allow us to use control variations for deriving necessary optimality conditions. We de- velop the method of discrete approximations, which is certainly of numerical interest, while it is mainly used in this book as a direct vehicle to derive op- timality conditions for continuous-time systems by passing to the limit from their discrete-time counterparts.Inthis way weobtain, strongly based on the generalizeddifferentialandSNCcalculi,necessaryoptimalityconditionsinthe extended Euler-Lagrange formfor nonconvex differential inclusions in infinite dimensions expressed via our basic generalized differential constructions. ThesecondpartofChap.6dealswithconstrainedoptimalcontrolsystems governedbyordinaryevolutionequationsofsmoothdynamicsinarbitraryBa- nachspaces.Suchproblemshaveessentialspecificfeaturesincomparisonwith thedifferentialinclusionmodelconsideredabove,andtheresultsobtained(as wellasthemethodsemployed)inthetwopartsofthischapteraregenerallyin- dependent.Anothermajorthemeexploredhereconcernsstabilityofthemax- imum principle under discrete approximations of nonconvex control systems. We establish rather surprising results on the approximate maximum principle for discrete approximations that shed new light upon both qualitative and