Convex Analysis and Monotone Operator Theory in Hilbert Spaces

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

The original version of this book was inadvertently published without updating the following corrections in Chapters 1, 2, 3, 6–13, 17, 18, 20, 23, 24, 26, 29, 30 and back matter. These are corrected now.