Skip to main content
main-content

Über dieses Buch

This reference text, now in its second edition, offers a modern unifying presentation of three basic areas of nonlinear analysis: convex analysis, monotone operator theory, and the fixed point theory of nonexpansive operators. Taking a unique comprehensive approach, the theory is developed from the ground up, with the rich connections and interactions between the areas as the central focus, and it is illustrated by a large number of examples. The Hilbert space setting of the material offers a wide range of applications while avoiding the technical difficulties of general Banach spaces. The authors have also drawn upon recent advances and modern tools to simplify the proofs of key results making the book more accessible to a broader range of scholars and users. Combining a strong emphasis on applications with exceptionally lucid writing and an abundance of exercises, this text is of great value to a large audience including pure and applied mathematicians as well as researchers in engineering, data science, machine learning, physics, decision sciences, economics, and inverse problems. The second edition of Convex Analysis and Monotone Operator Theory in Hilbert Spaces greatly expands on the first edition, containing over 140 pages of new material, over 270 new results, and more than 100 new exercises. It features a new chapter on proximity operators including two sections on proximity operators of matrix functions, in addition to several new sections distributed throughout the original chapters. Many existing results have been improved, and the list of references has been updated.

Heinz H. Bauschke is a Full Professor of Mathematics at the Kelowna campus of the University of British Columbia, Canada.

Patrick L. Combettes, IEEE Fellow, was on the faculty of the City University of New York and of Université Pierre et Marie Curie – Paris 6 before joining North Carolina State University as a Distinguished Professor of Mathematics in 2016.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Background

This chapter reviews basic definitions, facts, and notation from topology and set-valued analysis that will be used throughout the book.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 2. Hilbert Spaces

Throughout this book, ℋ $$\mathcal{H}$$ is a real Hilbert space with scalar (or inner) productscalar product⋅∣⋅ $$\left \langle \cdot \mid \cdot \right \rangle$$ . The associated normnorm is denoted by ∥ ⋅ ∥ and the associated distancedistance by d.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 3. Convex Sets

In this chapter we introduce the fundamental notion of the convexity of a set and establish various properties. The key result is Theorem 3.16, which asserts that every nonempty closed convex subset C of ℋ $$\mathcal{H}$$ is a Chebyshev set, i.e., that every point in ℋ $$\mathcal{H}$$ possesses a unique best approximation from C, and which provides a characterization of this best approximation.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 4. Convexity and Notions of Nonexpansiveness

Nonexpansive operators are Lipschitz continuous operators with Lipschitz constant 1. They play a central role in applied mathematics because many problems in nonlinear analysis reduce to finding fixed points of nonexpansive operators. In this chapter, we discuss nonexpansiveness and several variants. The properties of the fixed point sets of nonexpansive operators are investigated, in particular in terms of convexity.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 5. Fejér Monotonicity and Fixed Point Iterations

A sequence is Fejér monotone with respect to a set C if no point of the sequence is strictly farther from any point in C than its predecessor.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 6. Convex Cones and Generalized Interiors

The notion of a convex cone, which lies between that of a linear subspace and that of a convex set, is the main topic of this chapter. It has been very fruitful in many branches of nonlinear analysis. For instance, closed convex cones provide decompositions analogous to the well-known orthogonal decomposition based on closed linear subspaces. They also arise naturally in convex analysis in the local study of a convex set via the tangent cone and the normal cone operators, and they are central in the analysis of various extensions of the notion of an interior that will be required in later chapters.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 7. Support Functions and Polar Sets

In this chapter, we develop basic results concerning support points, including the Bishop–Phelps theorem and the representation of a nonempty closed convex set as the intersection of the closed half-spaces containing it. Polar sets are also studied.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 8. Convex Functions

Convex functions, which lie at the heart of modern optimization, are introduced in this chapter. We study operations that preserve convexity and the interplay between various continuity properties.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 9. Lower Semicontinuous Convex Functions

The theory of convex functions is most powerful in the presence of lower semicontinuity. A key property of lower semicontinuous convex functions is the existence of a continuous affine minorant, which we establish in this chapter by projecting onto the epigraph of the function.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 10. Convex Functions: Variants

In this chapter we present variants of the notion of convexity for functions. The most important are the weaker notion of quasiconvexity and the stronger notions of uniform and strong convexity.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 11. Convex Minimization Problems

Convex optimization is one of the main areas of application of convex analysis. This chapter deals with the issues of existence and uniqueness in minimization problems and investigates properties of minimizing sequences.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 12. Infimal Convolution

infimal convolutionThis chapter is devoted to a fundamental convexity-preserving operation for functions: the infimal convolution. Special attention is given to the Moreau envelope and the proximity operator.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 13. Conjugation

Functional transforms make it possible to investigate problems from a different perspective and sometimes simplify their investigation. In convex analysis, the most suitable notion of a transform is the Legendre transform, which maps a function to its Fenchel conjugate. This transform is studied in detail in this chapter. In particular, it is shown that the conjugate of an infimal convolution is the sum of the conjugates. The key result of this chapter is the Fenchel–Moreau theorem, which states that the proper convex lower semicontinuous functions are precisely those functions that coincide with their biconjugates.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 14. Further Conjugation Results

conjugationIn this chapter, we exhibit several deeper results on conjugation. We first discuss Moreau’s decomposition principle, whereby a vector is decomposed in terms of the proximity operator of a lower semicontinuous convex function and that of its conjugate. This powerful nonlinear principle extends the standard linear decomposition with respect to a closed linear subspace and its orthogonal complement. Basic results concerning the proximal average and positively homogeneous functions are also presented. Also discussed are the Moreau–Rockafellar theorem, which characterizes coercivity in terms of an interiority condition, and the Toland–Singer theorem, which provides an appealing formula for the conjugate of a difference.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 15. Fenchel–Rockafellar Duality

Of central importance in convex analysis are conditions guaranteeing that the conjugate of a sum is the infimal convolution of the conjugates. The main result in this direction is a theorem due to Attouch and Brézis. In turn, it gives rise to the Fenchel–Rockafellar duality framework for convex optimization problems.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 16. Subdifferentiability of Convex Functions

The subdifferential is a fundamental tool in the analysis of nondifferentiable convex functions. In this chapter we discuss the properties of subdifferentials and the interplay between the subdifferential and the Legendre transform.Moreover, we establish the Brøndsted–Rockafellar theorem, which asserts that the graph of the subdifferential operator is dense in the domain of the separable sum of the function and its conjugate.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 17. Differentiability of Convex Functions

Fréchet differentiability, Gâteaux differentiability, directional differentiability, subdifferentiability, and continuity are notions that are closely related to each other. In this chapter, we provide fundamental results on these relationships, as well as basic results on the steepest descent direction, the Chebyshev center, and the max formula that relates the directional derivative to the support function of the subdifferential at a given point.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 18. Further Differentiability Results

Further results concerning derivatives and subgradients are collected in this chapter. The Ekeland–Lebourg theorem gives conditions under which the set of points of Fréchet differentiability is a dense G δ subset of the domain of the function. Formulas for the subdifferential of a maximum and of an infimal convolution are provided, and the basic duality between differentiability and strict convexity is presented. Another highlight is the Baillon–Haddad theorem, which states that nonexpansiveness and firm nonexpansiveness are identical properties for gradients of convex functions. Finally, the subdifferential operator of the distance to a convex set is analyzed in detail.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 19. Duality in Convex Optimization

A convex optimization problem can be paired with a dual problem involving the conjugates of the functions appearing in its (primal) formulation. In this chapter, we study the interplay between primal and dual problems in the context of Fenchel–Rockafellar duality and, more generally, for bivariate functions. The latter approach leads naturally to saddle points and Lagrangians. Special attention is given to minimization under equality constraints and under inequality constraints. We start with a discussion of instances in which all primal solutions can be recovered from an arbitrary dual solution.duality

Heinz H. Bauschke, Patrick L. Combettes

Chapter 20. Monotone Operators

The theory of monotone set-valued operators plays a central role in many areas of nonlinear analysis. A prominent example of a monotone operator is the subdifferential operator investigated in Chapter 16 Single-valued monotone operators will be seen to be closely related to the firmly nonexpansive operators studied in Chapter 4 Our investigation of monotone operators will rely heavily on the Fitzpatrick function.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 21. Finer Properties of Monotone Operators

In this chapter, we deepen our study of monotone operators. The main results are Minty’s theorem, which conveniently characterizes maximal monotonicity, and the Debrunner–Flor theorem, which concerns the existence of a maximally monotone extension with a prescribed domain localization. Another highlight is the fact that the closures of the range and of the domain of a maximally monotone operator are convex, which yields the classical Bunt–Kritikos–Motzkin result on the convexity of Chebyshev sets in Euclidean spaces. Results on local boundedness, surjectivity, and single-valuedness are also presented.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 22. Stronger Notions of Monotonicity

This chapter collects basic results on various stronger notions of monotonicity (para, strict, uniform, strong, and cyclic) and their relationships to properties of convex functions. A fundamental result is Rockafellar’s characterization of maximally cyclically monotone operators as subdifferential operators and a corresponding uniqueness result for the underlying convex function.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 23. Resolvents of Monotone Operators

Two quite useful single-valued Lipschitz continuous operators are associated with a monotone operator, namely its resolvent and its Yosida approximation. This chapter is devoted to the investigation of these operators. It exemplifies the tight interplay between firmly nonexpansive mappings and monotone operators. Indeed, firmly nonexpansive operators with full domain can be identified with maximally monotone operators via resolvents and the Minty parameterization. When specialized to subdifferential operators, resolvents become proximity operators. Numerous calculus rules for resolvents are derived. Finally, we address the problem of finding a zero of a maximally monotone operator, via the proximal-point algorithm and via approximating curves.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 24. Proximity Operators

Recall from Definition 12.23 and Proposition 12.28 that the proximity operator of f∈Γ0(ℌ) $$f \in \varGamma _{0}(\mathcal{H})$$ is the firmly nonexpansive operator defined by Proxf:ℌ→ℌ:x↦y∈ℌargminf(y)+12∥x−y∥2. $$\mathop{\mathrm{Prox}}\nolimits _{f}: \mathcal{H}\rightarrow \mathcal{H}: x\mapsto \mathop{\mathrm{argmin}}\limits_{\begin{array}{c}y\in \mathcal{H}\end{array}}\;\;\Big(f(y) + \tfrac{1} {2}\|x - y\|^{2}\Big).$$ In this chapter, we pursue our investigation of the properties of proximity operators and provide concrete examples of such operators.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 25. Sums of Monotone Operators

The sum of two monotone operators is monotone. However, maximal monotonicity of the sum of two maximally monotone operators is not automatic and requires additional assumptions. In this chapter, we provide flexible sufficient conditions for maximality. Under additional assumptions, conclusions can be drawn about the range of the sum, which is important for deriving surjectivity results. We also consider the parallel sum of two set-valued operators.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 26. Zeros of Sums of Monotone Operators

Properties of the zeros of a single monotone operator were discussed in Section 23.4 In this chapter, we first characterize the zeros of sums of monotone operators and then present basic algorithms to construct such zeros iteratively. Duality for monotone inclusion problems is also discussed. In the case of two operators A and B such that A + B is maximally monotone, a point in zer(A+B) $$\mathop{\mathrm{zer}}\nolimits (A + B)$$ could in principle be constructed via Theorem 23.41. However, this approach is numerically viable only when it is easy to compute J γ(A+B). A more widely applicable alternative is to devise an operator splitting algorithmoperator splitting algorithm, in which the operators A and B are employed in separate steps. Various such algorithms are discussed in this chapter. Splitting methods for finding a zero of composite monotone operators of the form A + L∗BL, where L is a linear operator, are also presented.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 27. Fermat’s Rule in Convex Optimization

Fermat’s rule (Theorem 16.3) provides a simple characterization of the minimizers of a function as the zeros of its subdifferential.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 28. Proximal Minimization

We saw in Chapter 27 that the solutions to minimization problems can be characterized by fixed point equations involving proximity operators. Since proximity operators are firmly nonexpansive, they can be used to devise efficient operator splitting operator splitting algorithm algorithms to solve minimization problems. Such algorithms, called proximal algorithms, are investigated in this chapter.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 29. Projection Operators

Let C be a nonempty closed convex subset of ℌ $$\mathcal{H}$$ . The projection P C x of a point x∈ℌ $$x \in \mathcal{H}$$ onto C is characterized by (see Theorem 3.16) or, equivalently, by (see Proposition 6.47) x − P C x ∈ N C (P C x). In this chapter, we investigate further the properties of projectors and provide a variety of examples.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 30. Best Approximation Algorithms

Best approximation algorithms were already discussed in Corollary 5.30, in Example 28.18, and in Example 28.19. In this chapter, we provide further approaches for computing the projection onto the intersection of finitely many closed convex sets. The methods we present, all of which employ the individual projectors onto the given sets, are Halpern’s algorithm, Dykstra’s algorithm, and Haugazeau’s algorithm. Applications to solving monotone inclusion and minimization problems with strongly convergent algorithms are also given.

Heinz H. Bauschke, Patrick L. Combettes

Backmatter

Weitere Informationen

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise