VARIATIONAL ANALYSIS
R. Tyrrell Rockafellar & Roger J-B Wets
Springer Verlag, Vol. 317 Grundlehren der mathematischen Wissenschaften
PREFACE
In this book we aim to present, in a unified framework, a broad spectrum of mathematical theory that has grown in connection with the study of problems of optimization, equilibrium, control, and stability of linear and nonlinear systems. The title Variational Analysis reflects this breadth.
For a long time, `variational' problems have been identified mostly with the `calculus of variations'. In that venerable subject, built around the minimization of integral functionals, constraints were relatively simple and much of the focus was on infinite-dimensional function spaces. A major theme was the exploration of variations around a point, within the bounds imposed by the constraints, in order to help characterize solutions and portray them in terms of `variational principles'. Notions of perturbation, approximation and even generalized differentiability were extensively investigated. Variational theory progressed also to the study of so-called stationary points, critical points, and other indications of singularity that a point might have relative to its neighbors, especially in association with existence theorems for differential equations.
With the advent of computers, there has been a tremendous expansion of interest in new problem formulations that similarly demand such modes of analysis but are far from being covered by classical concepts, not to speak of classical results. For those problems, finite-dimensional spaces of arbitrary dimensionality are important alongside of function spaces, and theoretical concerns go hand in hand with the practical ones of mathematical modeling and the design of numerical procedures.
It is time to free the term `variational' from the limitations of its past and to use it to encompass this now much larger area of modern mathematics. We see `variations' as referring not only to movement away from a given point along rays or curves, and to the geometry of tangent and normal cones associated with that, but also to the forms of perturbation and approximation that are describable by set convergence, set-valued mappings and the like. Subgradients and subderivatives of functions, convex and nonconvex, are crucial in analyzing such `variations', as are the manifestations of Lipschitzian continuity that serve to quantify rates of change.
Our goal is to provide a systematic exposition of this broader subject as a coherent branch of analysis that, in addition to being powerful for the problems that have motivated it so far, can take its place now as a mathematical discipline ready for new applications.
Rather than detailing all the different approaches that researchers have been occupied with over the years in the search for the right ideas, we seek to reduce the general theory to its key ingredients as now understood, so as to make it accessible to a much wider circle of potential users. But within that consolidation, we furnish a thorough and tightly coordinated exposition of facts and concepts.
Several books have already dealt with major components of the subject. Some have concentrated on convexity and kindred developments in realms of nonconvexity. Others have concentrated on tangent vectors and subderivatives more or less to the exclusion of normal vectors and subgradients, or vice versa, or have focused on topological questions without getting into generalized differentiability. Here, by contrast, we cover set convergence and set-valued mappings to a degree previously unavailable and integrate those notions with both sides of variational geometry and subdifferential calculus. We furnish a needed update in a field that has undergone many changes, even in outlook. In addition, we include topics such as maximal monotone mappings, generalized second derivatives, and measurable selections and integrands, which have not in the past received close attention in a text of this scope. (For lack of space, we say little about the general theory of critical points, although we see that as a close neighbor to variational analysis.)
Many parts of this book contain material that is new not only in its manner of presentation but also in research. Each chapter provides motivations at the beginning and throughout, and each concludes with extensive notes, which furnish credits, and references together with historical perspective on how the ideas gradually took shape. These notes also explain the reasons for some of the decisions about notation and terminology that we felt were expedient in streamlining the subject so as to prepare it for wider use.
Because of the large volume of material and the challenge of unifying it properly, we had to draw the line somewhere. We chose to keep to finite-dimensional spaces so as not to cloud the picture with the many complications that a treatment of infinite-dimensional spaces would bring. Another reason for this choice was the fact that many of the concepts have multiple interpretations in the infinite-dimensional context, and more time may still be needed for them to be sorted out. Significant progress continues, but even in finite-dimensional spaces it is only now that the full picture is emerging with clarity. The abundance of applications in finite-dimensional spaces makes it desirable to have an exposition that lays out the most effective patterns in that domain, even if, in some respects, such patterns are not able go further without modification.
We envision that this book will be useful to graduate students, researchers and practitioners in a range of mathematical sciences, including some front-line areas of engineering and statistics that draw on optimization. We have aimed at making available a handy reference for numerous facts and ideas that cannot be found elsewhere except in technical papers, where the lack of a coordinated terminology and notation is currently a formidable barrier. At the same time, we have attempted to write this book so that it is helpful to readers who want to learn the field, or various aspects of it, step by step. We have provided many figures and examples, along with exercises accompanied by guides.
We have divided each chapter into a main part followed by sections marked by *, so as to signal to the reader a stage at which it would be reasonable, in a first run, to skip ahead to the next chapter. The results placed in the * sections are often important as well as necessary for the completeness of the theory, but they can suitably be addressed at a later time, once other developments begin to draw on them.
Acknowledgment. We are grateful for all the assistance we have received in the course of this project. The figures were computer-drawn and fine-tuned by Maria Wets, who also in numerous other ways generously gave technical and logistical support. Help with references was provided by Alexander Ioffe, Boris Mordukhovich, and Rene Poliquin, in particular. Lisa Korf was extraordinarily diligent in reading parts of the manuscript for possible glitches. Useful feedback came not only from these individuals but many others, including Hedy Attouch, Jean-Pierre Aubin, Gerald Beer, Michael Dong, Asen Dontchev, Rafal Goebel, Grant Galbraith, Rene Henrion, Adam Levy, Roberto Lucchetti, Werner Roemisch, Thomas Stromberg, and Kathleen Wets. The chapters on set convergence and epi-convergence benefited from the scrutiny of a seminar group consisting of Gul Gurkan, Douglas Lepro, Yonca Ozge, and Stephen Robinson. Various conversations we had over the years with our students and colleagues contributed significantly to the final form of the book as well. Grants from the National Science Foundation were essential in sustaining the long effort.
April 1997
-------------------------------------------------------------
CONTENTS
- Chapter 1. Max and Min ..... 1
- A. Penalties and Constraints ..... 2
- B. Epigraphs and Semicontinuity ..... 7
- C. Attainment of a Minimum ..... 11
- D. Continuity, Closure and Growth ..... 12
- E. Extended Arithmetic ..... 15
- F. Parametric Dependence ..... 16
- G. Moreau Envelopes ..... 19
- H. Epi-Addition and Epi-Multiplication ..... 23
- I* Auxiliary Facts and Principles ..... 27
- Commentary ..... 34
- Chapter 2. Convexity ..... 38
- A. Convex Sets and Functions ..... 38
- B. Level Sets and Intersections ..... 42
- C. Derivative Tests ..... 45
- D. Convexity in Operations ..... 49
- E. Convex Hulls ..... 53
- F. Closures and Continuity..... 57
- G* Separation ..... 62
- H* Relative Interiors ..... 64
- I* Piecewise Linear Functions ..... 67
- J* Other Examples ..... 71
- Commentary ..... 74
- Chapter 3. Cones and Cosmic Closure ..... 77
- A. Direction Points ..... 77
- B. Horizon Cones ..... 80
- C. Horizon Functions ..... 86
- D. Coercivity Properties ..... 90
- E* Cones and Orderings ..... 95
- F* Cosmic Convexity ..... 97
- G* Positive Hulls ..... 99
- Commentary ..... 105
- Chapter 4. Set Convergence ..... 108
- A. Inner and Outer Limits ..... 109
- B. Painlev\'e-Kuratowski Convergence ..... 111
- C. Pompeiu-Hausdorff Distance ..... 117
- D. Cones and Convex Sets ..... 118
- E. Compactness Properties ..... 120
- F. Horizon Limits ..... 122
- G* Continuity of Operations ..... 125
- H* Quantification of Convergence ..... 131
- I* Hyperspace Metrics ..... 138
- Commentary ..... 144
- Chapter 5. Set-Valued Mappings ..... 148
- A. Domains, Ranges and Inverses ..... 149
- B. Continuity and Semicontinuity ..... 152
- C. Local Boundedness ..... 157
- D. Total Continuity ..... 163
- E. Pointwise and Graphical Convergence ..... 166
- F. Equicontinuity of Sequences ..... 173
- G. Continuous and Uniform Convergence ..... 175
- H* Metric Descriptions of Convergence ..... 181
- I* Operations on Mappings ..... 183
- J* Generic Continuity and Selections ..... 186
- Commentary ..... 192
- Chapter 6. Variational Geometry ..... 196
- A. Tangent Cones ..... 196
- B. Normal Cones and Clarke Regularity ..... 199
- C. Smooth Manifolds and Convex Sets ..... 202
- D. Optimality and Lagrange Multipliers ..... 205
- E. Proximal Normals and Polarity ..... 212
- F. Tangent-Normal Relations ..... 217
- G* Recession Properties ..... 222
- H* Irregularity and Convexification ..... 225
- I* Other Formulas ..... 227
- Commentary ..... 232
- Chapter 7. Epigraphical Limits ..... 238
- A. Pointwise Convergence ..... 239
- B. Epi-Convergence ..... 240
- C. Continuous and Uniform Convergence ..... 249
- D. Generalized Differentiability ..... 255
- E. Convergence in Minimization ..... 262
- F. Epi-Continuity of Function-Valued Mappings..... 270
- G* Continuity of Operations ..... 275
- H* Total Epi-Convergence ..... 278
- I* Epi-Distances ..... 282
- J* Solution Estimates ..... 286
- Commentary ..... 293
- Chapter 8. Subderivatives and Subgradients ..... 298
- A. Subderivatives of Functions..... 299
- B. Subgradients of Functions ..... 300
- C. Convexity and Optimality ..... 308
- D. Regular Subderivatives ..... 311
- E. Support Functions and Subdifferential Duality ..... 317
- F. Calmness ..... 322
- G. Graphical Differentiation of Mappings ..... 324
- H* Proto-Differentiability and Graphical Regularity ..... 329
- I* Proximal Subgradients ..... 333
- J* Other Results ..... 336
- Commentary ..... 343
- Chapter 9. Lipschitzian Properties ..... 349
- A. Single-Valued Mappings ..... 349
- B. Estimates of the Lipschitz Modulus ..... 354
- C. Subdifferential Characterizations ..... 358
- D. Derivative Mappings and Their Norms ..... 365
- E. Lipschitzian Concepts for Set-Valued Mappings ..... 368
- F. Aubin Property and Mordukhovich Criterion ..... 377
- G. Metric Regularity and Openness ..... 386
- H* Semiderivatives and Strict Graphical Derivatives ..... 391
- I* Other Properties ..... 399
- J* Rademacher's Theorem and Consequences ..... 403
- K* Mollifiers and Extremals ..... 408
- Commentary ..... 415
- Chapter 10. Subdifferential Calculus ..... 421
- A. Optimality and Normals to Level Sets ..... 421
- B. Basic Chain Rule and Consequences ..... 426
- C. Parametric Optimality ..... 432
- D. Rescaling ..... 438
- E. Piecewise Linear-Quadratic Functions ..... 440
- F. Amenable Sets and Functions ..... 442
- G. Semiderivatives and Subsmoothness ..... 446
- H* Coderivative Calculus ..... 452
- I* Extensions ..... 458
- Commentary ..... 469
- Chapter 11. Dualization ..... 473
- A. Legendre-Fenchel Transform ..... 473
- B. Special Cases of Conjugacy ..... 476
- C. The Role of Differentiability ..... 480
- D. Piecewise Linear-Quadratic Functions ..... 484
- E. Polar Sets and Gauges ..... 490
- F. Dual Operations ..... 493
- G. Duality in Convergence ..... 499
- H. Dual Problems of Optimization ..... 502
- I. Lagrangian Functions ..... 508
- J* Minimax Problems ..... 514
- K* Augmented Lagrangians and Nonconvex Duality ..... 518
- L* Generalized Conjugacy ..... 525
- Commentary ..... 529
- Chapter 12. Monotone Mappings ..... 533
- A. Monotonicity Tests and Maximality ..... 533
- B. Minty Parameterization ..... 537
- C. Connections with Convex Functions ..... 542
- D. Graphical Convergence ..... 550
- E. Domains and Ranges ..... 552
- F* Preservation of Maximality ..... 556
- G* Monotone Variational Inequalities ..... 558
- H* Strong Monotonicity and Strong Convexity ..... 562
- I* Continuity and Differentiability ..... 567
- Commentary ..... 574
- Chapter 13. Second-Order Theory ..... 579
- A. Second-Order Differentiability ..... 579
- B. Second Subderivatives ..... 582
- C. Calculus Rules ..... 591
- D. Convex Functions and Duality ..... 603
- E. Second-Order Optimality ..... 606
- F. Prox-Regularity ..... 609
- G. Subgradient Proto-Differentiability ..... 618
- H. Subgradient Coderivatives and Perturbation ..... 622
- I* Further Derivative Properties ..... 625
- J* Parabolic Subderivatives ..... 633
- Commentary ..... 638
- Chapter 14. Measurability ..... 642
- A. Measurable Mappings and Selections ..... 642
- B. Preservation of Measurability ..... 651
- C. Limit Operations ..... 655
- D. Normal Integrands ..... 660
- E. Operations on Integrands ..... 669
- F. Integral Functionals ..... 675
- Commentary ..... 679
References ..... 684
Index of Statements ..... 709
Index of Notation ..... 724
Index of Topics ..... 725