Monotone Operator Theory in Convex Optimization

Introduction and historical overview

In this paper, we examine various facets of the role of monotone operator theory in convex optimization and of the interplay between the two fields. Throughout, ${\mathcal{H}}$ is a real Hilbert space with scalar product ${\langle{{\cdot}\mid{\cdot}}\rangle}$, associated norm $\|\cdot\|$, and identity operator $\operatorname{Id}\,\!$. To put our discussion in proper perspective, we first provide an historical account and highlight some key results (see Section 2 for notation).

Monotone operator theory is a fertile area of nonlinear analysis which emerged in 1960 in independent papers by Kačurovskiĭ, Minty, and Zarantonello. Let $D$ be a nonempty subset of ${\mathcal{H}}$, let $A\colon D\to{\mathcal{H}}$, and let $B\colon D\to{\mathcal{H}}$. Extending the ordering of functions on the real line which results from the comparison of their increments, Zarantonello declared $B$ is slower than $A$ if

which is denoted by $A\succcurlyeq B$. He then called $A$ (isotonically) monotone if $A\succcurlyeq 0$, that is,

and supra-unitary if $A\succcurlyeq\operatorname{Id}\,$. An instance of the latter notion can be found in . In modern language, it corresponds to that of $1$-strong monotonicity. An important result of is the following.

Let $A\colon{\mathcal{H}}\to{\mathcal{H}}$ be monotone and Lipschitzian. Then $\text{\rm ran}\,(\operatorname{Id}\,+A)={\mathcal{H}}$.

The second connection is with linear functional analysis: if $A\colon{\mathcal{H}}\to{\mathcal{H}}$ is linear and bounded, then it is monotone if and only if it is positive, that is,

In particular, if a bounded linear operator $A\colon{\mathcal{H}}\to{\mathcal{H}}$ is skew, that is $A^{*}=-A$, then it is monotone since

In other words, $A$ is monotone and there exists no monotone operator $B\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}$ distinct from $A$ such that $\text{\rm gra}\,A\subset\text{\rm gra}\,B$. A key result of is the following theorem, which can be viewed as an extension of Theorem 1.1 since a continuous monotone operator $A\colon{\mathcal{H}}\to{\mathcal{H}}$ is maximally monotone.

Let $A\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}$ be a monotone operator. Then $A$ is maximally monotone if and only if $\text{\rm ran}\,(\operatorname{Id}\,+A)={\mathcal{H}}$.

The paper also establishes an important connection between monotonicity and nonexpansiveness, which we state in the following form.

[13, Prop. 4.4 and Cor. 23.9] Let $T\colon{\mathcal{H}}\to{\mathcal{H}}$. Then the following are equivalent:

$R=2T-\operatorname{Id}\,$ is nonexpansive, i.e., $(\forall x\in{\mathcal{H}})(\forall y\in{\mathcal{H}})\quad\|Rx-Ry\|\leqslant\|x-y\|$.

There exists a maximally monotone operator $A\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}$ such that $T$ is the resolvent of $A$, i.e.,

From the onset, monotone operator theory impacted areas such as partial differential equations, evolution equations and inclusions, and nonlinear equations; see for instance . In particular, in such problems, it turned out to provide efficient tools to derive existence results. Standard references on the modern theory of monotone operators are . From a modeling standpoint, monotone operator theory constitutes a powerful framework that reduces many problems in nonlinear analysis to the simple formulation

The most direct connection between monotone operator theory and optimization is obtained through the subdifferential of a proper function $f\colon{\mathcal{H}}\to\left]-\infty,+\infty\right]$, i.e., the operator

This operator is easily seen to be monotone. In addition, from the standpoint of minimization, a straightforward yet fundamental consequence of (1.10) is Fermat’s rule. It states that, for every proper function $f\colon{\mathcal{H}}\to\left]-\infty,+\infty\right]$,

The maximality of the subdifferential was first investigated by Minty for certain classes of convex functions, and then by Moreau in full generality.

Let $f\colon{\mathcal{H}}\to\left]-\infty,+\infty\right]$ be a proper lower semicontinuous convex function. Then $\partial f$ is maximally monotone.

One way to prove Moreau’s theorem is to use Theorem 1.2; see [13, Theorem 21.2] or [25, Exemple 2.3.4]. Interestingly, Moreau’s proof in did not rely on Theorem 1.2 but on proximal calculus. The proximity operator of a function $f\in\Gamma_{0}({\mathcal{H}})$ is

This operator is intimately linked to the subdifferential operator. Indeed, let $f\in\Gamma_{0}({\mathcal{H}})$. Then

which entails, using (1.10), that $\text{\rm prox}_{f}$ is firmly nonexpansive. Furthermore, (1.11) and (1.14) imply that $\text{Argmin}f=\text{\rm Fix}\,\text{\rm prox}_{f}$. Since fixed points of firmly nonexpansive operators can be constructed by successive approximations , a conceptual algorithm for finding a minimizer of $f$ is

This scheme was first studied by Martinet in the early 1970s , and a special case in the context of quadratic programming appeared in [19, Sect. 5.8]. Though of limited practical use, this so-called proximal point algorithm occupies nonetheless a central place in convex minimization schemes because it embraces many fundamental ideas and connections that have inspired much more efficient and broadly applicable minimization algorithms in the form of proximal splitting methods . The methodology underlying these algorithms is to solve structured convex minimization problems using only the proximity operators of the individual functions present in the model.

Moreau’s motivations for introducing the proximity operator (1.12) came from nonsmooth mechanics . In recent years proximity operators have become prominent in convex optimization theory. For instance, they play a central theoretical role in . On the application side, their increasing presence is particularly manifest in the broad area of data processing, where they were introduced in and have since proven very effective in the modeling and the numerical solution of a vast array of problems in disciplines such as signal processing, image recovery, machine learning, and computational statistics; see for instance .

At first glance, it may appear that the theory of subdifferentials and proximity operators forms a self-contained corpus of theoretical and algorithmic tools which is sufficient to deal with convex optimization problems, and that the broader concepts of monotone operators and resolvents play only a peripheral role in such problems. A goal of this paper is to show that monotone operator theory occupies a central position in convex optimization, and that many advances in the latter would not have been possible without it. Conversely, we shall see that some algorithmic developments in monotonicity methods have directly benefited from convex minimization methodologies. We shall also examine certain aspects of the gap that separates the two theories. Section 2 covers notation and background. Section 3 studies subdifferentials as maximally monotone operators and proximity operators as resolvents, discussing characterizations, new proximity-preserving transformations, and self-dual classes. Section 4 focuses on the use of monotone operator theory in analyzing and solving convex optimization problems, and it proposes new insights and developments.

Notation and background

We follow the notation of , where one will find a detailed account of the following notions. The direct Hilbert sum of ${\mathcal{H}}$ and a real Hilbert space ${\mathcal{G}}$ is denoted by ${\mathcal{H}}\oplus{\mathcal{G}}$. Let $A\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}$ be a set-valued operator. We denote by \text{\rm gra}\,A=\big{\{}{(x,u)\in{\mathcal{H}}\times{\mathcal{H}}}~{}\big{|}~{}{u\in Ax}\big{\}} the graph of $A$, by \text{\rm dom}\,A=\big{\{}{x\in{\mathcal{H}}}~{}\big{|}~{}{Ax\neq{\varnothing}}\big{\}} the domain of $A$, by \text{\rm ran}\,A=\big{\{}{u\in{\mathcal{H}}}~{}\big{|}~{}{(\exists\,x\in{\mathcal{H}})\;u\in Ax}\big{\}} the range of $A$, by \text{\rm zer}\,A=\big{\{}{x\in{\mathcal{H}}}~{}\big{|}~{}{0\in Ax}\big{\}} the set of zeros of $A$, and by $A^{-1}$ the inverse of $A$, i.e., the set-valued operator with graph \big{\{}{(u,x)\in{\mathcal{H}}\times{\mathcal{H}}}~{}\big{|}~{}{u\in Ax}\big{\}}. The parallel sum of $A$ and $B\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}$, and the parallel composition of $A$ by $L\in\mathcal{B}({\mathcal{H}},{\mathcal{G}})$ are, respectively,

The resolvent of $A$ is J_{A}=(\operatorname{Id}\,+A)^{-1}=A^{-1}\mbox{\small\,\square\,}\operatorname{Id}\,. The set of fixed points of an operator $T\colon{\mathcal{H}}\to{\mathcal{H}}$ is \text{\rm Fix}\,T=\big{\{}{x\in{\mathcal{H}}}~{}\big{|}~{}{Tx=x}\big{\}}. The set of global minimizers of a function $f\colon{\mathcal{H}}\to\left]-\infty,+\infty\right]$ is denoted by $\text{Argmin}f$ and, if it is a singleton, its unique element is denoted by $\text{argmin}\,f$. We denote by $\Gamma_{0}({\mathcal{H}})$ the class of lower semicontinuous convex functions $f\colon{\mathcal{H}}\to\left]-\infty,+\infty\right]$ such that \text{\rm dom}\,f=\big{\{}{x\in{\mathcal{H}}}~{}\big{|}~{}{f(x)<{+\infty}}\big{\}}\neq{\varnothing}. Now let $f\in\Gamma_{0}({\mathcal{H}})$. The conjugate of $f$ is the function $f^{*}\in\Gamma_{0}({\mathcal{H}})$ defined by $f^{*}\colon u\mapsto\sup_{x\in{\mathcal{H}}}({\langle{{x}\mid{u}}\rangle}-f(x))$. The subdifferential of $f$ is defined in (1.10), and its inverse is $(\partial f)^{-1}=\partial f^{*}$. The proximity operator $\text{\rm prox}_{f}$ of $f$ is defined in (1.12). We say that $f$ is $\nu$-strongly convex for some $\nu\in\left]0,+\infty\right[$ if $f-\nu\|\cdot\|^{2}/2$ is convex. The infimal convolution of $f$ and $g\in\Gamma_{0}({\mathcal{H}})$ is

Let $C$ be a convex subset of ${\mathcal{H}}$. The interior of $C$ is denoted by $\text{\rm int}\,C$, the boundary of $C$ by $\text{bdry}\,C$, the indicator function of $C$ by $\iota_{C}$, the distance function to $C$ by $d_{C}$, the support function of $C$ by $\sigma_{C}$ and, if $C$ is nonempty and closed, the projection operator onto $C$ by $\text{\rm proj}_{C}$, i.e., $\text{\rm proj}_{C}=\text{\rm prox}_{\iota_{C}}$. A point $x\in C$ is in the strong relative interior of $C$, denoted by $\text{\rm sri}\,C$, if the cone generated by $C-x$ is a closed vector subspace of ${\mathcal{H}}$. We define

\mathcal{B}({\mathcal{H}},{\mathcal{G}})=\big{\{}{T\colon{\mathcal{H}}\to{\mathcal{G}}}~{}\big{|}~{}{T\;\text{is linear and bounded}}\big{\}} and $\mathcal{B}({\mathcal{H}})=\mathcal{B}({\mathcal{H}},{\mathcal{H}})$.

\mathcal{N}({\mathcal{H}})=\big{\{}{T\colon{\mathcal{H}}\to{\mathcal{H}}}~{}\big{|}~{}{T\;\text{is nonexpansive}}\big{\}}.

\mathcal{F}({\mathcal{H}})=\big{\{}{T\colon{\mathcal{H}}\to{\mathcal{H}}}~{}\big{|}~{}{T\;\text{is firmly nonexpansive}}\big{\}}.

\mathcal{M}({\mathcal{H}})=\big{\{}{A\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}}~{}\big{|}~{}{A\;\text{is maximally monotone}}\big{\}}.

\mathcal{S}({\mathcal{H}})=\big{\{}{A\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}}~{}\big{|}~{}{(\exists\,f\in\Gamma_{0}({\mathcal{H}}))\;A=\partial f}\big{\}}.

\mathcal{J}({\mathcal{H}})=\big{\{}{T\colon{\mathcal{H}}\to{\mathcal{H}}}~{}\big{|}~{}{(\exists\,A\in\mathcal{M}({\mathcal{H}}))\;T=J_{A}}\big{\}}.

\mathcal{P}({\mathcal{H}})=\big{\{}{T\colon{\mathcal{H}}\to{\mathcal{H}}}~{}\big{|}~{}{(\exists\,f\in\Gamma_{0}({\mathcal{H}}))\;T=\text{\rm prox}_{f}}\big{\}}.

\mathcal{K}({\mathcal{H}})=\big{\{}{T\colon{\mathcal{H}}\to{\mathcal{H}}}~{}\big{|}~{}{T=\text{\rm proj}_{K}\;\text{for some nonempty closed convex cone}\;K\subset{\mathcal{H}}}\big{\}}.

\mathcal{V}({\mathcal{H}})=\big{\{}{T\colon{\mathcal{H}}\to{\mathcal{H}}}~{}\big{|}~{}{T=\text{\rm proj}_{V}\;\text{for some closed vector space}\;V\subset{\mathcal{H}}}\big{\}}.

Facts mentioned in Section 1 are summarized by the inclusions

Let $f\in\Gamma_{0}({\mathcal{H}})$ and set $q=\|\cdot\|^{2}/2$. Then f\mbox{\small\,\square\,}q+f^{*}\mbox{\small\,\square\,}q=q and \text{\rm prox}_{f}=J_{\partial f}=\nabla(f+q)^{*}=\nabla(f^{*}\mbox{\small\,\square\,}q)=(\partial f^{*})\mbox{\small\,\square\,}\operatorname{Id}\,=\operatorname{Id}\,-\text{\rm prox}_{f^{*}}.

The next result brings together ideas from and .

$h$ is Fréchet differentiable on ${\mathcal{H}}$ and $\nabla h\in\mathcal{N}({\mathcal{H}})$.

$h$ is Fréchet differentiable on ${\mathcal{H}}$ and $\nabla h\in\mathcal{F}({\mathcal{H}})$.

$f\in\Gamma_{0}({\mathcal{H}})$ and h=f^{*}\mbox{\small\,\square\,}q=q-f\mbox{\small\,\square\,}q.

$f\in\Gamma_{0}({\mathcal{H}})$ and $\text{\rm prox}_{f}=\nabla h=\operatorname{Id}\,-\text{\rm prox}_{f^{*}}$.

Subdifferentials as monotone operators

As seen in Section 1, from a convex optimization perspective, the subdifferential and the proximity operators of a function in $\Gamma_{0}({\mathcal{H}})$ constitute, respectively, prime examples of maximally monotone and firmly nonexpansive operators. In this section with discuss some structural differences between $\mathcal{S}({\mathcal{H}})$ and $\mathcal{M}({\mathcal{H}})$, and between $\mathcal{P}({\mathcal{H}})$ and $\mathcal{J}({\mathcal{H}})$.

In this case, $A$ is called maximally cyclically monotone if there exists no cyclically monotone operator $B\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}$ such that $\text{\rm gra}\,B$ properly contains $\text{\rm gra}\,A$.

\mathcal{S}({\mathcal{H}})=\big{\{}{A\in\mathcal{M}({\mathcal{H}})}~{}\big{|}~{}{A\;\text{is maximally cyclically monotone}}\big{\}}.

The question of representing a maximally monotone operator as the sum of a subdifferential and a remainder component is a challenging one. In the case of a monotone matrix $A$ such a decomposition is obtained by writing $A$ as the sum of its symmetric part (hence a gradient) and its antisymmetric part. This observation motivated Asplund to investigate the decomposition of $A\in\mathcal{M}({\mathcal{H}})$ as

Here, acyclic means that if $B=\partial g+C$ for some $g\in\Gamma_{0}({\mathcal{H}})$ and some $C\in\mathcal{M}({\mathcal{H}})$, then $g$ is affine on $\text{\rm dom}\,A$. A sufficient condition for Alspund’s cyclic+acyclic decomposition (3.2) to exist for $A\in\mathcal{M}({\mathcal{H}})$ is that $\text{int\,dom}\,A\neq{\varnothing}$ . Acyclic operators are not easy to apprehend, which shows that the notion of a maximally monotone operator remains only partially understood. A simpler decomposition was investigated in by imposing that $B$ in (3.2) be the restriction of a skew operator in $\mathcal{B}({\mathcal{H}})$. Thus, the so-called Borwein-Wiersma decomposition of $A\in\mathcal{M}({\mathcal{H}})$ is

If $A\in\mathcal{M}({\mathcal{H}})$ and $\text{\rm gra}\,A$ is a vector subspace, then $A$ admits a Borwein-Wiersma decomposition if and only if $\text{\rm dom}\,A\subset\text{\rm dom}\,A^{*}$ [17, Thm. 5.1]. Another viewpoint on the distinction between a general maximally monotone operator and a subdifferential is presented in .

2 Characterizations of proximity operators

Exploring a different facet of the discussion of Section 3.1, we focus in this section on some properties of the class of proximity operators as a subset of that of firmly nonexpansive operators. We first review characterization results and then study the closedness of $\mathcal{P}({\mathcal{H}})$ under various transformations.

Let $T\in\mathcal{F}({\mathcal{H}})$. Then $T\in\mathcal{P}({\mathcal{H}})$ if and only if, for every integer $n\geqslant 2$ and every $(x_{1},\ldots,x_{n+1})\in{\mathcal{H}}^{n+1}$ such that $x_{n+1}=x_{1}$, we have $\sum_{i=1}^{n}{\langle{{x_{i}-Tx_{i}}\mid{Tx_{i}-Tx_{i+1}}}\rangle}\geqslant 0$.

For our purposes, a more readily exploitable characterization is the following result due to Moreau (see also Theorem 2.2).

Let $T\in\mathcal{B}({\mathcal{H}})$ be such that $\|T\|\leqslant 1$. Then $T\in\mathcal{P}({\mathcal{H}})$ if and only if $T$ is positive and self-adjoint.

3 Proximity-preserving transformations

A transformation which preserves firm nonexpansiveness may not be proximity-preserving in the sense that it may not produce a proximity operator when applied to proximity operators. Here are two examples.

Transformations involving compositions are unlikely to be proximity-preserving for a simple reason: in the linear case, Corollary 3.4 imposes that such a transformation preserve self-adjointness. However, a product of symmetric matrices may not be symmetric. A standard example is the Douglas-Rachford splitting operator $T_{A,B}$ associated with two operators $A$ and $B$ in $\mathcal{M}({\mathcal{H}})$ , which will arise in (4.6). In general,

Let $A\in\mathcal{M}({\mathcal{H}})$ and let $V$ be a closed vector subspace of ${\mathcal{H}}$. The partial inverse of $A$ with respect to $V$ is the operator $A_{V}\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}$ with graph

This operator, which was introduced by Spingarn in , can be regarded as an intermediate object between $A$ and $A^{-1}$. As shown in , $A\in\mathcal{M}({\mathcal{H}})$ $\Leftrightarrow$ $A_{V}\in\mathcal{M}({\mathcal{H}})$. Therefore, by Theorem 1.3, $A\in\mathcal{M}({\mathcal{H}})$ $\Leftrightarrow$ $J_{A_{V}}\in\mathcal{J}({\mathcal{H}})$. However,

Thus $J_{A_{V}}^{*}\neq J_{A_{V}}$ and Corollary 3.4 implies that $J_{A_{V}}\notin\mathcal{P}({\mathcal{H}})$.

Let us start with some simple proximity-preserving transformations.

Let $T\in\mathcal{P}({\mathcal{H}})$. Then the following hold:

$\operatorname{Id}\,-T\in\mathcal{P}({\mathcal{H}})$.

Let $z\in{\mathcal{H}}$. Then $z+T(\cdot-z)\in\mathcal{P}({\mathcal{H}})$.

$-T\circ(-\operatorname{Id}\,)\in\mathcal{P}({\mathcal{H}})$.

Proof. Let $f\in\Gamma_{0}({\mathcal{H}})$ be such that $T=\text{\rm prox}_{f}$, and set $q=\|\cdot\|^{2}/2$.

(i): Set $g=f^{*}$. Then $g\in\Gamma_{0}({\mathcal{H}})$ and Theorem 2.1 states that $\text{\rm prox}_{g}=\operatorname{Id}\,-T$.

(ii): Set $g=f(\cdot-z)$. Then $g\in\Gamma_{0}({\mathcal{H}})$ and $\text{\rm prox}_{g}=z+T(\cdot-z)$ .

(iii): Set $g=f(-\cdot)$. Then $g\in\Gamma_{0}({\mathcal{H}})$ and $\text{\rm prox}_{g}=-T\circ(-\operatorname{Id}\,)$ .

(iv): Since $\mathcal{P}({\mathcal{H}})\subset\mathcal{J}({\mathcal{H}})\subset\mathcal{M}({\mathcal{H}})$, $J_{T}$ is well defined. Now set g=f^{*}\mbox{\small\,\square\,}q. Then $g\in\Gamma_{0}({\mathcal{H}})$ and $g=(f+q)^{*}$. Thus, by Theorem 2.1, J_{T}=T^{-1}\mbox{\small\,\square\,}\operatorname{Id}\,=(\operatorname{Id}\,+\partial f)\mbox{\small\,\square\,}\operatorname{Id}\,=\partial(f+q)\mbox{\small\,\square\,}\operatorname{Id}\,=(\partial g^{*})\mbox{\small\,\square\,}\operatorname{Id}\,=\text{\rm prox}_{g}.

Let $f\in\Gamma_{0}({\mathcal{H}})$, let ${\mathcal{G}}$ be a real Hilbert space, and let $M\in\mathcal{B}({\mathcal{H}},{\mathcal{G}})$ be such that $0\in\text{\rm sri}\,(\text{\rm ran}\,M^{*}-\text{\rm dom}\,f)$ and $MM^{*}-\operatorname{Id}\,_{\!\!{\mathcal{G}}}$ is positive. Set $q_{{\mathcal{H}}}=\|\cdot\|_{{\mathcal{H}}}^{2}/2$ and $q_{{\mathcal{G}}}=\|\cdot\|_{{\mathcal{G}}}^{2}/2$. Then M\mbox{\Large\,\triangleright\,}\text{\rm prox}_{f}\in\mathcal{P}({\mathcal{G}}). More specifically, M\mbox{\Large\,\triangleright\,}\text{\rm prox}_{f}=\text{\rm prox}_{\varphi}, where $\varphi=(f+q_{{\mathcal{H}}})\circ M^{*}-q_{{\mathcal{G}}}$.

We now describe a composite proximity-preserving transformation.

Let $I$ be a nonempty finite set and put $q=\|\cdot\|_{{\mathcal{H}}}^{2}/2$. For every $i\in I$, let $\omega_{i}\in\left]0,+\infty\right[$, let ${\mathcal{G}}_{i}$ be a real Hilbert space with identity operator $\operatorname{Id}_{i}\,$, put $q_{i}=\|\cdot\|_{{\mathcal{G}}_{i}}^{2}/2$, let ${\mathcal{K}}_{i}$ be a real Hilbert space, let $L_{i}\in\mathcal{B}({\mathcal{H}},{\mathcal{G}}_{i})\smallsetminus\{0\}$, let $M_{i}\in\mathcal{B}({\mathcal{K}}_{i},{\mathcal{G}}_{i})\smallsetminus\{0\}$, let $f_{i}\in\Gamma_{0}({\mathcal{G}}_{i})$, let $g_{i}\in\Gamma_{0}({\mathcal{G}}_{i})$, and let $h_{i}\in\Gamma_{0}({\mathcal{K}}_{i})$. Suppose that $\sum_{i\in I}\omega_{i}\|L_{i}\|^{2}\leqslant 1$ and that, for every $i\in I$,

Then $T\in\mathcal{P}({\mathcal{H}})$. More specifically,

Proof. The fact that $f\in\Gamma_{0}({\mathcal{H}})$ follows from standard convex analysis . Now let $i\in I$. We derive from (2.1), (3.9), [13, Cor. 16.30 and Thm. 16.47(i)], and Theorem 3.3 that

Since $\text{\rm prox}_{f_{i}+g_{i}^{*}+h_{i}^{*}\circ M_{i}^{*}}\in\mathcal{N}({\mathcal{H}})$,

has Lipschitz constant $\|L_{i}\|^{2}$. Altogether,

has Lipschitz constant $\sum_{i\in I}\omega_{i}\|L_{i}\|^{2}\leqslant 1$. In view of Theorem 3.3, the proof is complete.

Let us highlight some special cases of Proposition 3.9. ${\mathcal{G}}$ is a real Hilbert space.

Let $(T_{i})_{i\in I}$ be a finite family in $\mathcal{P}({\mathcal{H}})$ and let $(\omega_{i})_{i\in I}$ be a finite family in $\left]0,1\right]$ such that $\sum_{i\in I}\omega_{i}=1$. Then $\sum_{i\in I}\omega_{i}T_{i}\in\mathcal{P}({\mathcal{H}})$. This result is due to Moreau . Connections with the proximal average are discussed in .

In (i), taking $I=\{1,2\}$, $T_{1}=T$, $T_{2}=\operatorname{Id}\,$, and $\omega_{1}=\lambda\in\left]0,1\right[$ yields $\operatorname{Id}\,+\lambda(T-\operatorname{Id}\,)\in\mathcal{P}({\mathcal{H}})$. The fact that the under-relaxation of a proximity operator is a proximity operator appears in . More precisely, it is shown there that if $T=\text{\rm prox}_{h}$ for some $h\in\Gamma_{0}({\mathcal{H}})$, then $\operatorname{Id}\,+\lambda(T-\operatorname{Id}\,)=\text{\rm prox}_{f}$, where f=h\mbox{\small\,\square\,}(\lambda q)/(1-\lambda), which can now be seen as a consequence of (3.11).

Let $T_{1}$ and $T_{2}$ be in $\mathcal{P}({\mathcal{H}})$. Then $(T_{1}-T_{2}+\operatorname{Id}\,)/2\in\mathcal{P}({\mathcal{H}})$. Indeed, Proposition 3.7(i) asserts that $\operatorname{Id}\,-T_{2}\in\mathcal{P}({\mathcal{H}})$ and then (i) that the average of $T_{1}$ and $\operatorname{Id}\,-T_{2}$ is also in $\mathcal{P}({\mathcal{H}})$.

Let $T\in\mathcal{P}({\mathcal{G}})$ and let $L\in\mathcal{B}({\mathcal{H}},{\mathcal{G}})$ be such that $\|L\|\leqslant 1$. Then $L^{*}\circ T\circ L\in\mathcal{P}({\mathcal{H}})$.

Let $T\in\mathcal{P}({\mathcal{H}})$ and let $V$ be a closed vector subspace of ${\mathcal{H}}$. Then it follows from (iv) that $\text{\rm proj}_{V}\circ T\circ\text{\rm proj}_{V}\in\mathcal{P}({\mathcal{H}})$.

Let $M\in\mathcal{B}({\mathcal{G}},{\mathcal{H}})\smallsetminus\{0\}$, let $f\in\Gamma_{0}({\mathcal{H}})$, let $g\in\Gamma_{0}({\mathcal{H}})$, and let $h\in\Gamma_{0}({\mathcal{G}})$ be such that $0\in\text{\rm sri}\,(\text{\rm dom}\,h^{*}-M^{*}(\text{\rm dom}\,f\cap\text{\rm dom}\,g^{*}))$ and $0\in\text{\rm sri}\,(\text{\rm dom}\,f-\text{\rm dom}\,g^{*})$. Then \text{\rm prox}_{f}\mbox{\small\,\square\,}(\partial g\mbox{\small\,\square\,}(M\mbox{\Large\,\triangleright\,}\partial h))\in\mathcal{P}({\mathcal{H}}). More specifically, \text{\rm prox}_{f}\mbox{\small\,\square\,}(\partial g\mbox{\small\,\square\,}(M\mbox{\Large\,\triangleright\,}\partial h))=\text{\rm prox}_{f+g^{*}+h^{*}\circ M^{*}}.

In (vii), suppose that, in addition, g=\varphi^{*}\mbox{\small\,\square\,}q_{{\mathcal{H}}} and h=\psi^{*}\mbox{\small\,\square\,}q_{{\mathcal{G}}}, where $\varphi\in\Gamma_{0}({\mathcal{H}})$ and $\psi\in\Gamma_{0}({\mathcal{G}})$. Then $\partial g=\{\text{\rm prox}_{\varphi}\}$, $\partial h=\{\text{\rm prox}_{\psi}\}$, and we conclude that \text{\rm prox}_{f}\mbox{\small\,\square\,}(\text{\rm prox}_{\varphi}\mbox{\small\,\square\,}(M\mbox{\Large\,\triangleright\,}\text{\rm prox}_{\psi}))\in\mathcal{P}({\mathcal{H}}). More specifically,

In (vii), suppose that, in addition, ${\mathcal{G}}={\mathcal{H}}$, $M=\operatorname{Id}\,$, g=\varphi^{*}\mbox{\small\,\square\,}q, and $h=\iota_{\{0\}}$, where $\varphi\in\Gamma_{0}({\mathcal{H}})$. Then $\partial g=\{\text{\rm prox}_{\varphi}\}$, $\partial h=\{0\}^{-1}$, and we conclude that \text{\rm prox}_{f}\mbox{\small\,\square\,}\text{\rm prox}_{\varphi}\in\mathcal{P}({\mathcal{H}}). More specifically,

has Lipschitz constant $1/2$. This result appears in [13, Cor. 25.35].

Proposition 3.9 allows us to interpret some algorithms as simple instances of the standard proximal point algorithm (1.15) for convex minimization.

Let $K$ be a closed convex cone in ${\mathcal{H}}$ with polar cone $K^{\ominus}$, let $V$ be a closed vector subspace of ${\mathcal{H}}$, and set

Let $(C_{i})_{i\in I}$ be a finite family of nonempty closed convex subsets of ${\mathcal{H}}$. The convex feasibility problem is to find a point in $\bigcap_{i\in I}C_{i}$. When this problem has no solution, a situation that arises frequently in signal recovery due to inaccurate prior knowledge or measurement errors , one must find a surrogate minimization problem. Let us note that the standard method of periodic projections used in consistent problems is of little value here as the limit cycles it generates do not minimize any function . Let $x_{0}\in{\mathcal{H}}$ and $\varepsilon\in\left]0,1\right[$. In , it was proposed to minimize $(1/2)\sum_{i\in I}\omega_{i}d_{C_{i}}^{2}$, where $(\omega_{i})_{i\in I}$ are in $\left]0,1\right]$ and satisfy $\sum_{i\in I}\omega_{i}=1$, via the parallel projection method

Now set f=(\sum_{i\in I}\omega_{i}(\sigma_{C_{i}}\mbox{\small\,\square\,}q))^{*}-q and apply Proposition 3.9 with $(\forall i\in I)$ ${\mathcal{G}}_{i}={\mathcal{K}}_{i}={\mathcal{H}}$, $L_{i}=M_{i}=\operatorname{Id}\,$, $f_{i}=\iota_{C_{i}}$, and $g_{i}=h_{i}=\iota_{\{0\}}$. Then $\text{\rm prox}_{f}=\sum_{i\in I}\omega_{i}\text{\rm proj}_{C_{i}}$, and (3.18) therefore turns out to be just a relaxed instance of Martinet’s proximal point algorithm (1.15).

As noted in Example 3.5, a composition of proximity operators is usually not a proximity operator. Likewise, the sum of two proximity operators may not be in $\mathcal{N}({\mathcal{H}})$ and therefore not in $\mathcal{P}({\mathcal{H}})$. The following propositions provide some exceptions. We start with the identity $\text{\rm prox}_{f_{1}}\circ\text{\rm prox}_{f_{2}}=\text{\rm prox}_{f_{1}+f_{2}}$, which is also discussed in special cases in .

Let $T_{1}$ and $T_{2}$ be in $\mathcal{P}({\mathcal{H}})$, say $T_{1}=\text{\rm prox}_{f_{1}}$ and $T_{2}=\text{\rm prox}_{f_{2}}$ for some $f_{1}$ and $f_{2}$ in $\Gamma_{0}({\mathcal{H}})$. Suppose that $\text{\rm dom}\,f_{1}\cap\text{\rm dom}\,f_{2}\neq{\varnothing}$ and that one of the following holds:

$(\forall x\in\text{\rm dom}\,\partial f_{2})$ $\partial f_{2}(x)\subset\partial f_{2}(T_{1}x)$.

$(\forall(x,u)\in\text{\rm gra}\,\partial{f_{1}})$ $\partial f_{2}(x+u)\subset\partial f_{2}(x)$.

$0\in\text{\rm sri}\,(\text{\rm dom}\,{f_{1}}-\text{\rm dom}\,f_{2})$ and $(\forall(x,u)\in\text{\rm gra}\,\partial{f_{1}})$ $\partial f_{2}(x)\subset\partial f_{2}(x+u)$.

Then $T_{1}\circ T_{2}\in\mathcal{P}({\mathcal{H}})$. More specifically, in cases (ii)–(iv), $T_{1}\circ T_{2}=\text{\rm prox}_{f_{1}+f_{2}}$.

Proof. Let $x\in{\mathcal{H}}$. If $\phi$ is constant, then $T_{1}=\operatorname{Id}\,$ and the result is trivially true. We therefore assume otherwise, which allows us to derive from [27, Prop. 2.2] that

Since Theorem 2.1 yields $\operatorname{Id}\,-\text{\rm proj}_{C}=\text{\rm prox}_{\sigma_{C}}$, using (3.19) and (3.20), we get

Proposition 3.14 has important applications.

It follows from [46, Prop. 3.2(v)] that, if $\phi$ is differentiable at with $\phi^{\prime}(0)=0$, then $\text{\rm prox}_{\varphi}$, which can be implemented explicitly via (3.19), is a proximal thresholder on $C$: $(\forall x\in{\mathcal{H}})$ $\text{\rm prox}_{\varphi}x=0$ $\Leftrightarrow$ $x\in C$.

Let $\gamma\in\left]0,+\infty\right[$, let $K$ be a nonempty closed convex cone in ${\mathcal{H}}$, let $C$ be the polar cone of $K$, and let $x\in{\mathcal{H}}$. Upon setting $\phi=\gamma|\cdot|$ in Proposition 3.14 and using [13, Examp. 24.20], we obtain (see [44, Lemma 2.2] for a different derivation)

On the other hand, setting $\phi=\iota_{[-\gamma,\gamma]}$ in Proposition 3.14 and using [13, Examp. 3.18], we obtain (see [9, Sec. 7] for different derivations)

Set $q=\|\cdot\|^{2}/2$, and let $T_{1}$ and $T_{2}$ be in $\mathcal{P}({\mathcal{H}})$, say $T_{1}=\text{\rm prox}_{f_{1}}$ and $T_{2}=\text{\rm prox}_{f_{2}}$ for some $f_{1}$ and $f_{2}$ in $\Gamma_{0}({\mathcal{H}})$. Suppose that $0\in\text{\rm sri}\,(\text{\rm dom}\,f_{1}^{*}-\text{\rm dom}\,f_{2}^{*})$ and that

Then $T_{1}+T_{2}\in\mathcal{P}({\mathcal{H}})$. More specifically, T_{1}+T_{2}=\text{\rm prox}_{f_{1}\mbox{\small\,\square\,}f_{2}}.

Proof. It follows from [13, Prop. 15.7(i)] that f_{1}\mbox{\small\,\square\,}f_{2}\in\Gamma_{0}({\mathcal{H}}). In addition, we derive from Theorem 2.1, (3.24), and [13, Prop. 13.24(i)] that T_{1}+T_{2}=\nabla\big{(}f_{1}^{*}\mbox{\small\,\square\,}q\big{)}+\nabla\big{(}f_{2}^{*}\mbox{\small\,\square\,}q\big{)}=\nabla\big{(}f_{1}^{*}\mbox{\small\,\square\,}q+f_{2}^{*}\mbox{\small\,\square\,}q\big{)}=\nabla\big{(}(f_{1}^{*}+f_{2}^{*})\mbox{\small\,\square\,}q\big{)}=\nabla\big{(}(f_{1}\mbox{\small\,\square\,}f_{2})^{*}\mbox{\small\,\square\,}q\big{)}=\text{\rm prox}_{f_{1}\mbox{\small\,\square\,}f_{2}}, as claimed.

Let $C_{1}$ and $C_{2}$ be nonempty closed convex subsets of ${\mathcal{H}}$, and set $f_{1}=\iota_{C_{1}}$ and $f_{2}=\iota_{C_{2}}$. Then the conclusion of Proposition 3.16 is that $\text{\rm proj}_{C_{1}}+\text{\rm proj}_{C_{2}}=\text{\rm proj}_{C_{1}+C_{2}}$. This property is discussed in (for cones), in [13, Prop. 29.6], and in the recently posted paper .

4 Self-dual classes of firmly nonexpansive operators

Let us call a subclass $\mathcal{T}({\mathcal{H}})$ of $\mathcal{J}({\mathcal{H}})$ self-dual if $(\forall T\in\mathcal{T}({\mathcal{H}}))$ $\operatorname{Id}\,-T\in\mathcal{T}({\mathcal{H}})$. This property plays an important role in our paper.

It is clear from (1.7) that $\mathcal{J}({\mathcal{H}})$ is self-dual. This can also be recovered from Theorem 1.3 and (2.4). As seen in Proposition 3.7(i), $\mathcal{P}({\mathcal{H}})$ is also self-dual. Now let $T\in\mathcal{K}({\mathcal{H}})$. Then there exists a nonempty closed convex cone $K\subset{\mathcal{H}}$ such that $T=\text{\rm proj}_{K}$ and Moreau’s conical decomposition expresses the projector onto the polar cone $K^{\ominus}$ as $\text{\rm proj}_{K^{\ominus}}=\operatorname{Id}\,-\text{\rm proj}_{K}$ . This shows that $\mathcal{K}({\mathcal{H}})$ is self-dual. Likewise, it follows from the standard Beppo Levi orthogonal decomposition of ${\mathcal{H}}$ that the class $\mathcal{V}({\mathcal{H}})$ of projectors onto closed vector subspaces of ${\mathcal{H}}$ is self-dual. We thus obtain the nested self-dual classes

Self-duality properties were investigated in , where other classes were identified and studied in depth. In particular, let $A\colon{\mathcal{H}}\to 2^{{\mathcal{H}}}$ be maximally monotone. Then $A$ is paramonotone if and only if $A^{-1}$ is [13, Prop. 22.2(i)]. As a result, it follows from (2.4) that the class $\mathcal{J}_{\text{para}}({\mathcal{H}})$ of resolvents of paramonotone maximally monotone operators from ${\mathcal{H}}$ to $2^{{\mathcal{H}}}$ is self-dual and since subdifferentials are paramonotone, we have $\mathcal{P}({\mathcal{H}})\subset\mathcal{J}_{\text{para}}({\mathcal{H}})\subset\mathcal{J}({\mathcal{H}})$. Likewise, since $A$ is $3^{*}$ monotone if and only if $A^{-1}$ is [13, Prop. 25.19(i)], and since subdifferentials are $3^{*}$ monotone, the class $\mathcal{J}_{3^{*}}({\mathcal{H}})$ of resolvents of $3^{*}$ monotone maximally monotone operators from ${\mathcal{H}}$ to $2^{{\mathcal{H}}}$ is self-dual and satisfies $\mathcal{P}({\mathcal{H}})\subset\mathcal{J}_{3^{*}}({\mathcal{H}})\subset\mathcal{J}({\mathcal{H}})$.

Although our primary objective in Section 3.3 was to investigate transformations on the class $\mathcal{P}({\mathcal{H}})$, similar questions could be asked about other self-dual classes. In this spirit, Zarantonello has studied some transformations in $\mathcal{K}({\mathcal{H}})$. Let $T_{1}$ and $T_{2}$ be in $\mathcal{K}({\mathcal{H}})$, say $T_{1}=\text{\rm proj}_{K_{1}}$ and $T_{2}=\text{\rm proj}_{K_{2}}$. In connection with Proposition 3.13, he has shown that $\{T_{1}\circ T_{2},T_{2}\circ T_{1}\}\subset\mathcal{K}({\mathcal{H}})$ if and only if $T_{2}\circ T_{1}=T_{1}\circ T_{2}$, in which case $T_{1}\circ T_{2}=\text{\rm proj}_{K_{1}\cap K_{2}}$ . On the other hand, in this context, the conclusion of Proposition 3.16, which states that $T_{1}+T_{2}=\text{\rm proj}_{K_{1}+K_{2}}\in\mathcal{K}({\mathcal{H}})$, is discussed in .

The proximity-preserving transformations studied in Section 3.3 have natural resolvent-preserving counterparts. For instance, mimicking the pattern of Remark 3.10(vii) and using [13, Thm. 25.3], one shows that, if $T=J_{A}\in\mathcal{J}({\mathcal{H}})$, $B\in\mathcal{M}({\mathcal{H}})$, $M\in\mathcal{B}({\mathcal{G}},{\mathcal{H}})\smallsetminus\{0\}$, and $C\in\mathcal{M}({\mathcal{G}})$, then T\mbox{\small\,\square\,}(B\mbox{\small\,\square\,}(M\mbox{\Large\,\triangleright\,}C))=J_{A+B^{-1}+M\circ C^{-1}\circ M^{*}}\in\mathcal{J}({\mathcal{H}}) provided that the cones generated by $\text{\rm dom}\,C^{-1}-M^{*}(\text{\rm dom}\,A\cap\text{\rm dom}\,B^{-1})$ and by $\text{\rm dom}\,A-\text{\rm dom}\,B^{-1}$ are closed vector subspaces.

Monotone operators in convex optimization

In this section we present several examples of maximally monotone operators which are not subdifferentials and which play fundamental and indispensable roles in the analysis and the numerical solution of convex optimization problems. We preface these examples with a brief overview of classical splitting methods which depend less critically on monotone operator theory.

The proximal point algorithm (1.15) was first developed for convex optimization. It was extended in to solve the inclusion problem (1.9) for an operator $A\in\mathcal{M}({\mathcal{H}})$ such that $\text{\rm zer}\,A\neq{\varnothing}$ via the iteration

for a general $A\in\mathcal{M}({\mathcal{H}})$ while, when $A=\partial f$ for some $f\in\Gamma_{0}({\mathcal{H}})$, it can be sharpened to

Let $A\in\mathcal{M}({\mathcal{H}})$ and $B\in\mathcal{M}({\mathcal{H}})$ be such that $0\in\text{\rm ran}\,(A+B)$. Find a zero of $A+B$.

Generally speaking, when replacing monotone operators by subdifferentials in certain inclusion problems, one recovers a convex minimization problem provided some constraint qualification holds . In this regard, we shall also consider the following convex optimization problem.

Let $f$ and $g$ be functions in $\Gamma_{0}({\mathcal{H}})$ such that $0\in\text{\rm ran}\,(\partial f+\partial g)$. Find a minimizer of $f+g$ over ${\mathcal{H}}$.

Forward-backward splitting. In Problem 4.1, suppose that $B\colon{\mathcal{H}}\to{\mathcal{H}}$ and that $\beta^{-1}B\in\mathcal{F}({\mathcal{H}})$ for some $\beta\in\left]0,+\infty\right[$. Let $x_{0}\in{\mathcal{H}}$ and $\varepsilon\in\left]0,2/(\beta+1)\right[$, and iterate

Tseng’s forward-backward-forward splitting. In Problem 4.1, suppose that $B\colon{\mathcal{H}}\to{\mathcal{H}}$ is $\beta$-Lipschitzian for some $\beta\in\left]0,+\infty\right[$. Let $x_{0}\in{\mathcal{H}}$ and $\varepsilon\in\left]0,1/(\beta+1)\right[$, and iterate

Douglas-Rachford splitting. Let $x_{0}\in{\mathcal{H}}$ and $\gamma\in\left]0,+\infty\right[$, and iterate

Historically, the forward-backward method grew out of the projected gradient method in convex optimization , and the first version for Problem 4.1 was proposed in . Another example of a monotone operator splitting method that evolved from convex optimization is Dykstra’s method , which was first devised for indicator functions in . By contrast, the forward-backward-forward and Douglas-Rachford methods were developed directly for Problem 4.1, and then specialized to Problem 4.2. In principle, however, even though monotone inclusions provide a more synthetic and natural framework, it is possible (at least a posteriori) to derive their convergence in the scenario of Problem 4.2 from optimization concepts only, without invoking monotone operator theory. Nonetheless, non-subdifferential maximally monotone operators may still be at play. For instance, note that in the Douglas-Rachford algorithm (4.6), we have

Upon invoking (3.4) and Theorem 1.3, we see that $T\in\mathcal{J}({\mathcal{H}})$ and that there exists $C\in\mathcal{M}({\mathcal{H}})$ such that $T=J_{C}$, namely $C=T^{-1}-\operatorname{Id}\,$. Hence

For example, let us consider the forward-backward algorithm (4.4) with a fixed proximal parameter $\gamma\in\left]0,2/\beta\right[$. Then

Furthermore, $T$ is averaged with constant $\alpha=2/(4-\beta\gamma)$ . Altogether, the forward-backward iteration (4.10) is an instance of the relaxed proximal point algorithm

2 Rockafellar’s saddle function operator

The following result is due to Rockafellar (he actually used a somewhat more general notion of closedness, made precise in these papers, for the function $\mathcal{L}$).

Let ${\mathcal{H}}_{1}$ and ${\mathcal{H}}_{2}$ be real Hilbert spaces, let $\mathcal{L}\colon{\mathcal{H}}_{1}\oplus{\mathcal{H}}_{2}\to\left[-\infty,+\infty\right]$ be such that, for every $x_{1}\in{\mathcal{H}}_{1}$ and every $x_{2}\in{\mathcal{H}}_{2}$, $-\mathcal{L}(x_{1},\cdot)\in\Gamma_{0}({\mathcal{H}}_{2})$ and $\mathcal{L}(\cdot,x_{2})\in\Gamma_{0}({\mathcal{H}}_{1})$. Set

Then $\boldsymbol{A}\in\mathcal{M}({\mathcal{H}}_{1}\oplus{\mathcal{H}}_{2})$ and

is the set of saddle points of $\mathcal{L}$.

A geometrical interpretation of (4.12) is that $(u_{1},u_{2})\in\boldsymbol{A}(x_{1},x_{2})$ if and only if $(x_{1},x_{2})$ is a saddle point of the convex-concave function $(x^{\prime}_{1},x^{\prime}_{2})\mapsto\mathcal{L}(x^{\prime}_{1},x^{\prime}_{2})-{\langle{{x^{\prime}_{1}}\mid{u_{1}}}\rangle}+{\langle{{x^{\prime}_{2}}\mid{u_{2}}}\rangle}$. The maximally monotone operator $\boldsymbol{A}$ of (4.12) is deeply rooted in convex optimization due to the foundational role it plays in Lagrangian theory and duality schemes . Yet, as the following example shows, it is not a subdifferential.

The idea of using the proximal point algorithm (4.1) with the operator $\boldsymbol{A}$ of (4.12) to find a saddle point of $\mathcal{L}$ was proposed by Rockafellar in . In , he applied it to the concrete problem of minimizing a convex function subject to convex inequality constraints, using the ordinary Lagrangian as a saddle function. The resulting algorithm is known as the proximal method of multipliers.

3 Spingarn’s partial inverse operator

Let $A\in\mathcal{M}({\mathcal{H}})$, let $V$ be a closed vector subspace of ${\mathcal{H}}$, and let the partial inverse of $A$ with respect to $V$ be the operator $A_{V}\in\mathcal{M}({\mathcal{H}})$ defined in (3.5). As discussed in , problems of the form

can be solved by applying the proximal point algorithm (4.1) to $A_{V}$; this method is known as the method of partial inverses, and it has strong connections with the Douglas-Rachford algorithm . For instance, if $A=\partial f$ for some $f\in\Gamma_{0}({\mathcal{H}})$ such that $f$ admits a minimizer over $V$ and $0\in\text{\rm sri}\,(V-\text{\rm dom}\,f)$, (4.14) reduces to finding a solution of the Fenchel dual pair

In this case, given $x_{0}\in V$ and $u_{0}\in V^{\bot}$, the method of partial inverses iterates

Let $I$ be a nonempty finite set, and let $({\mathcal{H}}_{i})_{i\in I}$ and ${\mathcal{G}}$ be real Hilbert spaces. Let $r\in{\mathcal{G}}$, let $g\in\Gamma_{0}({\mathcal{G}})$, and, for every $i\in I$, let $z_{i}\in{\mathcal{H}}_{i}$, let $f_{i}\in\Gamma_{0}({\mathcal{H}}_{i})$, and let $L_{i}\in\mathcal{B}({\mathcal{H}}_{i},{\mathcal{G}})$. Solve the primal problem

It is shown in that, when applied to a version of (4.14) suitably reformulated in a product space, (4.16) yields a proximal splitting algorithm that solves Problem 4.5 and employs the operators $(\text{\rm prox}_{f_{i}})_{i\in I}$, $\text{\rm prox}_{g}$, $(L_{i})_{i\in I}$, and $(L^{*}_{i})_{i\in I}$ separately.

The backbone of all the above-mentioned applications of the method of partial inverses to convex optimization is the partial inverse of an operator in $\mathcal{S}({\mathcal{H}})$. As seen in Example 3.6, this maximally monotone operator is not in $\mathcal{S}({\mathcal{H}})$ in general.

4 Primal-dual algorithm for mixed composite minimization

We re-examine through the lens of the maximally monotone saddle function operator (4.12) a mixed composite minimization problem proposed and studied in with different tools.

From a numerical standpoint, solving (4.20) is challenging as it involves five objects (four functions, three of which are nonsmooth, and a linear operator), while traditional proximal splitting techniques are limited to two objects; see (4.4)–(4.6). In , Problem 4.6 was analyzed and solved as an instance of a more general primal-dual inclusion problem involving monotone operators, which was reformulated as that of finding a zero of the sum of two operators in $\mathcal{M}({\mathcal{H}}\oplus{\mathcal{G}})$. Let us stress that, even in the special case of Problem 4.6, this inclusion problem still involves operators which are not subdifferentials. To see this, we now propose an alternative derivation of the results of [49, Sect. 4] using the saddle function formalism of Theorem 4.3. Following the same pattern as in [105, Examp. 11] (with the conventions of [13, Prop. 19.20]), we define the Lagrangian of Problem 4.6 as

and observe that it satisfies the assumptions of Theorem 4.3. In turn, using standard subdifferential calculus , we deduce that the associated maximally monotone operator $\boldsymbol{A}$ of (4.12) is

It is noteworthy that this operator admits a Borwein-Wiersma decomposition (3.3), namely

Note that $\boldsymbol{f}\in\Gamma_{0}({\mathcal{H}}\oplus{\mathcal{G}})$ and that computing $J_{\partial\boldsymbol{f}}=\text{\rm prox}_{\boldsymbol{f}}=\text{\rm prox}_{f}\times\text{\rm prox}_{g^{*}}$ requires only the ability to compute $\text{\rm prox}_{f}$ and $\text{\rm prox}_{g^{*}}=\operatorname{Id}\,-\text{\rm prox}_{g}$. Furthermore ,

Let us make a few observations regarding Problem 4.6 and the iterative method (4.28).

Algorithm (4.28) achieves full splitting of the functions and of the linear operators. In addition, all the smooth functions are activated via explicit gradient steps, while the nonsmooth ones are activated via their proximity operator.

In , Problem 4.6 is also written as that of finding a zero of $\boldsymbol{A}$ in (4.25). However, it is then reformulated in a new Hilbert space obtained by suitably renorming ${\mathcal{H}}\times{\mathcal{G}}$. This formulation yields an equivalent inclusion problem for an operator which can be decomposed as the sum of two maximally monotone operators amenable to forward-backward splitting (see Problem 4.1 and (4.4)) and, in fine, an algorithm which also achieves full splitting (see for related work). A special case of this framework is the algorithm proposed in .

The construction of algorithm (4.28) revolves around the problem of finding a zero of the operator $\boldsymbol{A}\in\mathcal{M}({\mathcal{H}}\oplus{\mathcal{G}})\smallsetminus\mathcal{S}({\mathcal{H}}\oplus{\mathcal{G}})$ of (4.25). It is not clear how this, or any of the splitting algorithms mentioned in (i)–(iii), could have been devised using only subdifferential tools.

5 Lagrangian formulations of composite problems

We consider a special case of Problem 4.6 which corresponds to the standard Fenchel-Rockafellar duality framework.

Let $f\in\Gamma_{0}({\mathcal{H}})$, let ${\mathcal{G}}$ be a real Hilbert space, and let $g\in\Gamma_{0}({\mathcal{G}})$. Suppose that $0\neq L\in\mathcal{B}({\mathcal{H}},{\mathcal{G}})$ and that $0\in\text{\rm ran}\,(\partial f+L^{*}\circ\partial g\circ L)$. The objective is to solve the primal problem

We have already discussed in Remark 4.7(ii) monotone operator-based algorithms to solve (4.29)–(4.30). Alternatively, set $\boldsymbol{\mathcal{H}}={\mathcal{H}}\oplus{\mathcal{G}}$, $\boldsymbol{f}\colon\boldsymbol{\mathcal{H}}\to\left]-\infty,+\infty\right]\colon(x,y)\mapsto f(x)+g(y)$, and $\boldsymbol{L}\colon\boldsymbol{\mathcal{H}}\to{\mathcal{G}}\colon(x,y)\mapsto Lx-y$. Then (4.29) is equivalent to minimizing $\boldsymbol{f}$ over $\ker\boldsymbol{L}$. The Lagrangian for this type of problem is $\mathcal{L}\colon\boldsymbol{\mathcal{H}}\oplus{\mathcal{G}}\to\left]-\infty,+\infty\right]\colon(\boldsymbol{x},v)\mapsto\boldsymbol{f}(\boldsymbol{x})+{\langle{{\boldsymbol{Lx}}\mid{v}}\rangle}$ [105, Examp. 4’] (see also [13, Prop. 19.21]) and the associated maximally monotone operator $\boldsymbol{A}$ of (4.12) is defined at $(\boldsymbol{x},v)\in\boldsymbol{\mathcal{H}}\oplus{\mathcal{G}}$ to be $\boldsymbol{A}(\boldsymbol{x},v)=(\partial\boldsymbol{f}(\boldsymbol{x})+\boldsymbol{L}^{*}v,-\boldsymbol{Lx})$. Thus, solving (4.29)–(4.30) is equivalent to finding a zero of the operator $\boldsymbol{A}\in\mathcal{M}({\mathcal{H}}\oplus{\mathcal{G}}\oplus{\mathcal{G}})\smallsetminus\mathcal{S}({\mathcal{H}}\oplus{\mathcal{G}}\oplus{\mathcal{G}})$ defined by

In , this problem is approached by splitting $\boldsymbol{A}$ as

When $\mu_{1}=\mu_{2}=0$, this scheme corresponds to the alternating direction method of multipliers (ADMM) and, just like it, requires a potentially complex minimization involving $f$ and $L$ jointly to construct $x_{n+1}$ (see for connections between ADMM and the Douglas-Rachford algorithm). To circumvent this issue and obtain a method that does split $f$, $g$, and $L$, let us decompose $\boldsymbol{A}$ as $\boldsymbol{A}=\boldsymbol{M}+\boldsymbol{S}$, where

Applying (4.5) to this subdifferential+skew decomposition in ${\mathcal{H}}\oplus{\mathcal{G}}\oplus{\mathcal{G}}$, we obtain the following algorithm, which employs $\text{\rm prox}_{f}$, $\text{\rm prox}_{g}$, $L$, and $L^{*}$.

Consider the setting of Problem 4.8 and let $(x_{0},y_{0},v_{0})\in{\mathcal{H}}\oplus{\mathcal{G}}\oplus{\mathcal{G}}$. Iterate

Let us note that (4.35) bears a certain resemblance with the algorithm

proposed in a finite-dimensional setting in .

Closing remarks

The constant interactions between convex optimization and monotone operator theory have greatly benefited both fields. On the numerical side, spectacular advances have been made in the last years in the area of splitting algorithms to solve complex structured problems. While many methods have been obtained by recasting classical algorithms in product spaces, often with the help of duality arguments, recent proposals such as that of rely on different paradigms and make asynchronous and block-iterative implementations possible. Despite the relative maturity of the field, there remain plenty of exciting open problems, and we can mention only a few here. For instance, on the theoretical side, duality for monotone inclusions is based on rather rudimentary principles, whereby dual solutions exist if and only if primal solution exist, and it does not match the more subtle results from Fenchel-Rockafellar duality in classical convex optimization. On the algorithmic front, splitting based on Bregman distances is still in its infancy. This framework is motivated by the need to solve problems in Banach spaces, where standard notions of resolvent and proximity operators are no longer appropriate, but also by numerical considerations in basic Euclidean spaces since some proximity operators may be easier to implement in Bregman form or some functions may have more exploitable properties when examined through Bregman distances . As a final word, let us emphasize that a monumental achievement of Browder, Kačurovskiĭ, Minty, Moreau, Rockafellar, and Zarantonello was to build, within the unchartered field of nonlinear analysis, structured and fertile areas that extended ideas from classical linear functional analysis. It remains a huge challenge to delimit and construct such areas in the vast world of nonconvex/nonmonotone problems, that would preserve enough structure to support a solid and meaningful theory and, at the same time, lend itself to the development of powerful algorithms that would produce more than just local solutions.

References