nach oben

1998 | Buch

Kapitel lesen Erstes Kapitel lesen

Variational Analysis

verfasst von: R. Tyrrell Rockafellar, Roger J. B. Wets

Verlag: Springer Berlin Heidelberg

Buchreihe : Grundlehren der mathematischen Wissenschaften

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

From its origins in the minimization of integral functionals, the notion of 'variations' has evolved greatly in connection with applications in optimization, equilibrium, and control. It refers not only to constrained movement away from a point, but also to modes of perturbation and approximation that are best describable by 'set convergence', variational convergence of functions and the like. This book develops a unified framework and, in finite dimension, provides a detailed exposition of variational geometry and subdifferential calculus in their current forms beyond classical and convex analysis. Also covered are set-convergence, set-valued mappings, epi-convergence, duality, maximal monotone mappings, second-order subderivatives, measurable selections and normal integrands.

The changes in this 3rd printing mainly concern various typographical corrections, and reference omissions that came to light in the previous printings. Many of these reached the authors' notice through their own re-reading, that of their students and a number of colleagues mentioned in the Preface. The authors also included a few telling examples as well as improved a few statements, with slightly weaker assumptions or have strengthened the conclusions in a couple of instances.

Inhaltsverzeichnis

Frontmatter

1. Max and Min

Questions about the maximum or minimum of a function f relative to a set C are fundamental in variational analysis. For problems in n real variables, the elements of C are vectors x = (x₁,…, x_n) ∊ ℝⁿ. In any application, f or C are likely to have special structure that needs to be addressed, but we begin here with concepts associated with maximization and minimization as general operations.

2. Convexity

The concept of convexity has far-reaching consequences in variational analysis. In the study of maximization and minimization, the division between problems of convex or nonconvex type is as significant as the division in other areas of mathematics between problems of linear or nonlinear type. Furthermore, convexity can often be introduced or utilized in a local sense and in this way serves many theoretical purposes.

3. Cones and Cosmic Closure

An important advantage that the extended real line ℝ¯ has over the real line ℝ is compactness: every sequence of elements has a convergent subsequence. This property is achieved by adjoining to ℝ the special elements oo and −ø, which can act as limits for unbounded sequences under special rules. An analogous compactification is possible for ℝⁿ. It serves in characterizing basic ‘growth’ properties that sets and functions may have in the large.

Every vector x ≠ 0 in ℝⁿ has both magnitude and direction. The magnitude of x is ÀxÀ, which can be manipulated in familiar ways. The direction of x has often been underplayed as a mathematical entity, but our interest now lies in a rigorous treatment where directions are viewed as ‘points at infinity’ to be adjoined to ordinary space.

4. Set Convergence

The precise meaning of such basic concepts in analysis as differentiation, integration and approximation is dictated by the choice of a notion of limit for sequences of functions. In the past, pointwise limits have received most of the attention. Whether ‘uniform’ or invoked in an ‘almost everywhere’ sense, they underlie the standard definitions of derivatives and integrals as well as the very meaning of a series expansion. In variational analysis, however, pointwise limits are inadequate for such mathematical purposes. A different approach to convergence is required in which, on the geometric level, limits of sequences of sets have the leading role.

Motivation for the development of this geometric approach has come from optimization, stochastic processes, control systems and many other subjects. When a problem of optimization is approximated by a simpler problem, or a sequence of such problems, for instance, it's of practical interest to know what might be expected of the behavior of the associated sets of feasible or optimal solutions. How close will they be to those for the given problem? Related challenges arise in approximating functions that may be extended-real-valued and mappings that may be set-valued. The limiting behavior of a sequence of such functions and mappings, possibly discontinuous and not having the same effective domains, can't be well understood in a framework of pointwise convergence. And this fundamentally affects the question of how ‘differentiation’ might be extended to meet the demands of variational analysis, since that's inevitably tied to ideas of local approximation.

5. Set-Valued Mappings

6. Variational Geometry

In the study of ‘variations’, constraints can present a major complication. Before the effects of variations can be ascertained it may be necessary to determine the directions in which something can be varied at all. This may be difficult, whether the variations are aimed at tests of optimality or stability, or arise in trying to understand the consequences of perturbations in the data parameters on which a mathematical model might depend.

In maximizing or minimizing a function over a set C ⊂ ℝⁿ, for instance, properties of the boundary of C can be crucial in characterizing a solution. When C is specified by a system of constraints such as inequalities, however, the boundary may have all kinds of curvilinear facets, edges and corners. Standard methods of geometric analysis can't cope with such a lack of smoothness except in simple cases where the pieces making up the boundary of C are neatly laid out and can be dealt with one by one.

7. Epigraphical Limits

Familiar notions of convergence for real-valued functions on ℝ^? require a bit of rethinking before they can be applied to possibly unbounded functions that might take on oo and −ø as values. Even then, they may fall short of meeting the basic needs in variational analysis.

8. Subderivatives and Subgradients

Maximization and minimization are often useful in constructing new functions and mappings from given ones, but, in contrast to addition and composition, they commonly fail to preserve smoothness. These operations, and others of prime interest in variational analysis, fit poorly in the traditional environment of differential calculus. The conceptual platform for ‘differentiation’ needs to be enlarged in order to cope with such circumstances.

Notions of semidifferentiability and epi-differentiability have already been developed in Chapter 7 as a start to this project. The task is carried forward now in a thorough application of the variational geometry of Chapter 6 to epigraphs. ‘Subderivatives’ and ‘subgradients’ are introduced as counterparts to tangent and normal vectors and shown to enjoy various useful relationships. Alongside of general subderivatives and subgradients, there are ‘regular’ ones of more special character. These are intimately tied to the regular tangent and normal vectors of Chapter 6 and show aspects of convexity. The geometric paradigm of Figure 6–17 finds its reflection in Figure 8–9, which schematizes the framework in which all these entities hang together.

9. Lipschitzian Properties

The notion of Lipschitz continuity is useful in many areas of analysis, but in variational analysis it takes on a fundamental role. To begin with, it singles out a class of functions which, although not necessarily differentiable, have a property akin to differentiability in furnishing estimates of the magnitudes, if not the directions, of change. For such functions, real-valued and vector-valued, subdifferentiation operates on an especially simple and powerful level. As a matter of fact, subdifferential theory even characterizes the presence of Lipschitz continuity and provides a calculus of the associated constants. It thereby supports a host of applications in which such constants serve to quantify the stability of a problem's solutions or the rate of convergence in a numerical method for determining a solution.

But the study of Lipschitzian properties doesn't stop there. It can be extended from single-valued mappings to general set-valued mappings as a means of obtaining quantitative results about continuity that go beyond the topological results obtained so far. In that context, Lipschitz continuity can be captured by coderivative conditions, which likewise pin down the associated constants. What's more, those conditions can be applied to basic objects of variational analysis such as profile mappings associated with functions, and this leads to important insights. For instance, the very concepts of normal vector and subgradient turn out to represent ‘manifestations of singularity’ in the Lipschitzian behavior of certain set-valued mappings.

10. Subdifferential Calculus

Numerous facts about functions f:ℝⁿ → ℝ¯ and mappings F:ℝⁿ → ℝm and S:ℝⁿ ⇉ ℝ^m have been developed in Chapters 7, 8, and 9 by way of the variational geometry in Chapter 6 and characterized through subdifferentiation. In order to take advantage of this body of results, bringing the theory down from an abstract level to workhorse use in practice, one needs to have effective machinery for determining subderivatives, subgradients, and graphical derivatives and coderivatives in individual situations. Just as in classical analysis, contemplation of ε's and δ's only goes so far. In the end, the vitality of the subject rests on tools like the chain rule.

In variational analysis, though, calculus serves additional purposes. While classically the calculation of derivatives can't proceed without first assuming that the functions to be differentiated are differentiable, the subdifferentiation concepts of variational analysis require no such preconditions. Their rules of calculation operate in inequality or inclusion form with little more needed than closedness or semicontinuity, and they give a means of establishing whether a differentiability property or Lipschitzian property is present or not.

11. Dualization

In the realm of convexity, almost every mathematical object can be paired with another, said to be dual to it. The pairing between convex cones and their polars has already been fundamental in the variational geometry of Chapter 6 in relating tangent vectors to normal vectors. The pairing between convex sets and sublinear functions in Chapter 8 has served as the vehicle for expressing connections between subgradients and subderivatives. Both correspondences are rooted in a deeper principle of duality for ‘conjugate’ pairs of convex functions, which will emerge fully here.

On the basis of this duality, close connections between otherwise disparate properties are revealed. It will be seen for instance that the level boundedness of one function in a conjugate pair corresponds to the finiteness of the other function around the origin. A catalog of such surprising linkages can be put together, and lists of dual operations and constructions to go with them.

12. Monotone Mappings

A valuable tool in the study of gradient and subgradient mappings, solution mappings, and various other mappings of importance in variational analysis, both single-valued and set-valued, is the following concept of monotonicity.

13. Second-Order Theory

For functions f:ℝⁿ → ℝ¯, the notions of ‘subderivative’ and ‘subgradient’, along with semidifferentiability and epi-differentiability, have provided a broad and effective generalization of first-order differentiation. What can be said, though, on the level of generalized second-order differentiation? And what might the use of this be?

Classically, second derivatives carry forward the analysis of first derivatives and provide quadratic approximations of a given function, whereas first derivatives by themselves only provide linear approximations. They serve as an intermediate link in an endless chain of differentiation that proceeds to third derivatives, fourth derivatives, and so on. In optimization, derivatives of third order and higher are rarely of importance, but second derivatives help significantly in the understanding of optimality, especially the formulation of sufficient conditions for local optimality in the absence of convexity. Such conditions form the basis for numerical methodology and assist in studies of what happens to optimal solutions when the parameters on which a problem depends are perturbed.

14. Measurability

Problems involving ‘integration’ offer rich and challenging territory for vari-ational analysis, and indeed it's especially around such problems, under the heading of the calculus of variations, that the subject has traditionally been organized. Models in which expressions have to be integrated with respect to time are central to the treatment of dynamical systems and their optimal control. When the systems are ‘distributed’, with states that, like density distributions, are conceived as elements of a function space, integration with respect to spatial variables or other parameters can enter the picture as well. In economics, it may be desirable to integrate over a space of infinitesimal agents. Applications in stochastic environments often concern expected values that are defined by integration with respect to a probability measure, or may demand a sturdy platform for working with concepts like that of a ‘random set,’ a ‘random function’, or even a ‘random problem of optimization’.

Satisfactory handling of problem models in these categories usually requires an appeal to measure theory, and that inevitably raises questions about measurable dependence. This chapter is aimed at providing the technical machinery for answering such questions, so that analysis can go forward in full harmony with the ideas developed in the preceding chapters, where variable points are often replaced by variable sets, the geometry of graphs is replaced by that of epigraphs, and so forth.

Backmatter

Titel: Variational Analysis
verfasst von: R. Tyrrell Rockafellar
Roger J. B. Wets
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-02431-3
Print ISBN: 978-3-540-62772-2
DOI: https://doi.org/10.1007/978-3-642-02431-3

Springer Professional