Convex Analysis and Monotone Operator Theory in Hilbert Spaces

Frontmatter

Chapter 1. Background

Abstract

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

Heinz H. Bauschke, Patrick L. Combettes

Chapter 2. Hilbert Spaces

Abstract

Throughout this book, \(\mathcal{H}\) is a real Hilbert space with scalar (or inner) product \(\langle \cdot | \cdot \rangle\). The associated norm is denoted by \(\parallel \cdot \parallel\) and the associated distance by d, i.e.,

$$(\forall x \in \mathcal{H}) (\forall y \in \mathcal{H}) \quad \parallel x \parallel = \sqrt {\langle x | x \rangle} \ {\rm and} \ d(x, y) = \parallel x-y \parallel.$$

(2.1)

Heinz H. Bauschke, Patrick L. Combettes

Chapter 3. Convex Sets

Abstract

In this chapter we introduce the fundamental notion of the convexity of a set and establish various properties of convex sets. The key result is Theorem 3.14, 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 Nonexpansiveness

Abstract

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

Abstract

A sequence is Fejér monotone with respect to a set C if each point in the sequence is not strictly farther from any point in C than its predecessor. Such sequences possess very attractive properties that greatly simplify the analysis of their asymptotic behavior. In this chapter, we provide the basic theory for Fejér monotone sequences and apply it to obtain in a systematic fashion convergence results for various classical iterations involving nonexpansive operators.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 6. Convex Cones and Generalized Interiors

Abstract

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

Abstract

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

Abstract

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

Abstract

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

Abstract

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 Variational Problems

Abstract

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

Abstract

This chapter is devoted to a fundamental convexity-preserving operation for functions: the infimal convolution. Its properties are investigated, with special emphasis on the Moreau envelope, which is obtained by convolving a function with the halved squared norm.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 13. Conjugation

Abstract

In classical analysis, functional transforms make it possible to investigate problems from a different perspective and sometimes simplify their analysis. 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

Abstract

In 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 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 the difference.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 15. Fenchel–Rockafellar Duality

Abstract

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 Br9zis. In turn, it gives rise to the Fenchel–Rockafellar duality framework for convex optimization problems. The applications we discuss include von Neumann’s minimax theorem as well as several results on the closure of the sum of linear subspaces.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 16. Subdifferentiability

Abstract

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

Abstract

Fr9chet 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

Abstract

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 of this chapter 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

Abstract

A convex optimization problem can be paired with a dual problem involving the conjugates of the functions appearing it 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.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 20. Monotone Operators

Abstract

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 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

Abstract

In this chapter, we deepen our study of (maximally) 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–Motzkin result concerning 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

Abstract

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

Abstract

Two quite useful single-valued, Lipschitz continuous operators can be 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 parametrization. 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. Sums of Monotone Operators

Abstract

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. Consideration is also given to the parallel sum of two set-valued operators.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 25. Zeros of Sums of Monotone Operators

Abstract

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. These are called splitting algorithms in the sense that they involve the operators individually.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 26. Fermat’s Rule in Convex Optimization

Abstract

Fermat’s rule (Theorem 16.2) provides a simple characterization of the minimizers of a function as the zeros of its subdifferential. This chapter explores various consequences of this fact. Throughout, K is a real Hilbert space.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 27. Proximal Minimization

Abstract

As seen in Chapter 26, the solutions to variational problems can be characterized by fixed point equations involving proximity operators. Since proximity operators are firmly nonexpansive, they can be used to devise efficient algorithms to solve minimization problems. Such algorithms, called proximal algorithms, are investigated in this chapter. Throughout, K is a real Hilbert space.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 28. Projection Operators

Abstract

Let C be a nonempty closed convex subset of \(\mathcal{H}\). The projection \( P_{c}x \)of a point \( x\, \in \, \mathcal{H} \) onto C is characterized by (see Theorem 3.14)

$$P_{c}x \in C \quad {\rm and} \quad (\forall y \in C) \quad \langle y-P_{c}x | x-P_{c}x \rangle \leq 0$$

or, equivalently, by (see Proposition 6.46) \( x - {P_{c}x } \in N_c\left( {P_{c}x } \right)\)). In this chapter, we investigate further the properties of projectors and provide a variety of examples.

Heinz H. Bauschke, Patrick L. Combettes

Chapter 29. Best Approximation Algorithms

Abstract

Best approximation algorithms were already discussed in Corollary 5.28, in Example 27.17, and in Example 27.18. In this chapter we provide further approaches for computing the projection onto the intersection of finitely many closed convex sets, employing the individual projectors, namely, Dykstra’s algorithm and Haugazeau’s algorithm. Applications of the latter to solving monotone inclusion and minimization problems with strongly convergent algorithms are given.

Heinz H. Bauschke, Patrick L. Combettes

Backmatter