Asymmetric forward–backward–adjoint splitting for solving monotone inclusions involving three operators

Abstract

In this work we propose a new splitting technique, namely Asymmetric Forward–Backward–Adjoint splitting, for solving monotone inclusions involving three terms, a maximally monotone, a cocoercive and a bounded linear operator. Our scheme can not be recovered from existing operator splitting methods, while classical methods like Douglas–Rachford and Forward–Backward splitting are special cases of the new algorithm. Asymmetric preconditioning is the main feature of Asymmetric Forward–Backward–Adjoint splitting, that allows us to unify, extend and shed light on the connections between many seemingly unrelated primal-dual algorithms for solving structured convex optimization problems proposed in recent years. One important special case leads to a Douglas–Rachford type scheme that includes a third cocoercive operator.

Appendix

The proofs omitted in the main text are listed below.

Proof of Propostition 4.1

(i): Let us start by noting that P and S defined in (57) are special cases of (65) and (75) when $L=\mathrm{Id}$, $\gamma _1=\gamma _2^{-1}=\gamma$ and, as such, are strongly positive if $\theta \in [0,2[$ (see Lemma 5.1 and 5.3). Next, consider step 3 of Algorithm 1 and Substitute the parameters defined in (57), to derive

$$\begin{aligned} \frac{\alpha _{n}}{\lambda _n}&= \frac{\Vert \tilde{z}_{n}\Vert _{P}^{2}}{\Vert \tilde{z}_{n}\Vert _{D}^{2}} = \frac{\gamma ^{-1}\Vert \tilde{x}_{n}\Vert ^{2}+\gamma \Vert \tilde{y}_{n}\Vert ^{2}-\theta \langle \tilde{x}_{n},\tilde{y}_{n}\rangle }{\gamma ^{-1}(\theta ^2-3\theta +3)\Vert \tilde{x}_n\Vert ^2+\gamma \Vert \tilde{y}_n\Vert ^2+2(1-\theta )\langle \tilde{x}_n,\tilde{y}_n \rangle }, \end{aligned}$$

(92)

where D is defined in (5) and by construction is strongly positive. Let $\lambda _n$ be equal to the inverse of the right hand side in (92) multiplied by $\rho _n$, where $(\rho _n)_{n\in \mathrm{{I}}\!\mathrm{{N}}}$ is uniformly bounded in the interval ]0, 2[. This would result in $\alpha _n=\rho _n$ and simplify the iterations. Our goal is to establish the convergence using Theorem 3.1. Therefore, we must show that the condition (7) is satisfied when the sequence $(\lambda _{n})_{n\in \mathrm{{I}}\!\mathrm{{N}}}$ is selected as described. We do this by showing that $(\lambda _{n})_{n\in \mathrm{{I}}\!\mathrm{{N}}}\subseteq [\nu _1,2-\frac{1}{2\beta }-\nu _2]$, for some $\nu _1,\nu _2>0$.

From strong positivity of D, boundedness of P and the fact that $(\rho _n)_{n\in \mathrm{{I}}\!\mathrm{{N}}}$ is uniformly bounded above 0, it follows that $(\lambda _{n})_{n\in \mathrm{{I}}\!\mathrm{{N}}}\subseteq [\nu _1,\infty [$ for some positive $\nu _1$. Consider C defined in (56c), we have $\Vert Cz-Cz^{\prime }\Vert ^2_{P^{-1}} = \gamma \left( 1-\tfrac{1}{4}\theta ^2\right) ^{-1}\Vert Cz-Cz^{\prime }\Vert ^2$. Therefore, it follows that C is $\beta$-cocoercive with respect to $\Vert \cdot \Vert _P$, with $\beta =\eta \gamma ^{-1}(1-\frac{1}{4}\theta ^2)$. Let $\nu _2$ be a positive parameter such that

$$\begin{aligned} \nu _2<2-\frac{1}{2\beta }-\frac{2\rho _n(2+\sqrt{2-\theta })}{2+\theta }, \end{aligned}$$

(93)

holds for all $n\in \mathrm{{I}}\!\mathrm{{N}}$. It’s easy to verify that such $\nu _2$ exists as long as $(\rho _n)_{n\in \mathrm{{I}}\!\mathrm{{N}}}$ is uniformly bounded in the interval (59). For brevity, we define $\beta ^\prime$ such that $\frac{1}{2\beta ^\prime }=\frac{1}{2\beta }+\nu _2$. Additionally, introduce the notation $\upsilon =\rho _n^{-1}(2-\frac{1}{2\beta ^\prime })$, $\omega _{1}=\upsilon \theta +2(1-\theta )$, $\omega _{2}=\theta ^2-3\theta +3$. We proceed by showing that $(\lambda _n)_{n\in \mathrm{{I}}\!\mathrm{{N}}}$ is bounded above by $2-\frac{1}{2\beta }-\nu _2$. A sufficient condition for this to hold is

$$\begin{aligned} \xi =\gamma ^{-1}(\upsilon -\omega _2)\Vert \tilde{x}_{n}\Vert ^{2}+\gamma (\upsilon -1)\Vert \tilde{y}_{n}\Vert ^{2}-\omega _{1}\langle \tilde{x}_{n},\tilde{y}_{n}\rangle \ge 0. \end{aligned}$$

(94)

Apply the Fenchel-Young inequality for $\frac{\epsilon }{2}\Vert \cdot \Vert ^2$ to lower bound $\xi$:

$$\begin{aligned} \xi \ge \left( \gamma ^{-1}(\upsilon -\omega _2)-|\omega _{1}|\tfrac{\epsilon }{2}\right) \Vert \tilde{x}_{n}\Vert ^{2}+\left( \gamma (\upsilon -1)-|\omega _1|\tfrac{1}{2\epsilon }\right) \Vert \tilde{y}_{n}\Vert ^{2}, \end{aligned}$$

(95)

where $|\cdot |$ is the absolute value. It follows from (93) that $\upsilon >1$ for all $n\in \mathrm{{I}}\!\mathrm{{N}}$. Let $\epsilon =\frac{|\omega _{1}|}{2\gamma (\upsilon -1)}$ so that the term involving $\Vert \tilde{y}_n\Vert ^2$ in (95) disappears. Therefore, we obtain that

$$\begin{aligned}&\gamma ^{-1}\left( \upsilon -\omega _2-\tfrac{\omega _1^2}{4(\upsilon -1)}\right) \Vert \tilde{x}_{n}\Vert ^{2}\ge 0, \end{aligned}$$

(96)

is sufficient for (94) to hold. By substituting $\omega _{1}$ and $\omega _{2}$ and after some algebraic manipulations we find that (93) is sufficient for the right hand side in (96) to be positive. Consequently, Theorem 3.1 completes the proof of convergence. We showed that we can set $\alpha _n=\rho _n$ by choosing $(\lambda _{n})_{n\in \mathrm{{I}}\!\mathrm{{N}}}$ appropriately. Algorithm 2 follows by setting $\alpha _n=\rho _n$, a change of variables $s_n=x_n-\gamma y_n$, substituting $x_{n+1}$ and application of Moreau’s identity.

(ii): Mimic the proof of (i), but use Theorem 3.1 with $C\equiv 0$, by showing that $\lambda _n$ is uniformly bounded between 0 and 2.

(iii): When $\theta =2$, we have $P\in \mathscr {S}(\mathscr {K})$, $P\succeq 0$. It follows from (56a), (58) and Lemma 3.1 that $(H+A)^{-1}P$ is continuous. Therefore, since $F\equiv 0$, by appealing to Theorem 3.4 and following the same change of variables as in previous parts the assertion is proved. $\square$

Proof of Proposition 4.2

Building upon the argument in the proof of Proposition 4.1(iii) and Theorem 3.4(ii) we have

$$\begin{aligned} \Vert {P}z_{n+1}-Pz_n\Vert ^{2}\le \tfrac{\Vert P\Vert }{\tau (n+1)}\Vert Qz_{0}-Qz^{\star }\Vert _{R}^{2}, \end{aligned}$$

(97)

and $\Vert Pz_{n+1}-Pz_n\Vert ^{2}=o(1/(n+1))$, where $z_n= \left( x_n,\gamma ^{-1}(x_n-s_n)\right)$. Combine this with definition of P,  (57a) with $\theta =2$, to derive

$$\begin{aligned} \Vert {P}z_{n+1}-Pz_n\Vert ^{2}= (1+\gamma ^{-2})\Vert s_{n+1}-s_n\Vert ^2. \end{aligned}$$

(98)

Furthermore, simple calculation shows that $P^2=(\gamma +\gamma ^{-1})P$. Hence for all $z\in \mathscr {K}$

$$\begin{aligned} \Vert Pz\Vert ^2= (\gamma +\gamma ^{-1})\left( \gamma ^{-1}\Vert x\Vert ^2+\gamma \Vert y\Vert ^2-2\langle x,y \rangle \right) \le (\gamma +\gamma ^{-1})^2\Vert z\Vert ^2, \end{aligned}$$

(99)

where we used Fenchel-Young inequality for $\frac{\gamma }{2}\Vert \cdot \Vert ^2$. It follows from (99) that $\Vert P\Vert \le (\gamma +\gamma ^{-1})$. Combining this with (97) and (98) completes the proof. $\square$

Proof of Lemma 5.2

For every z and $z_1$ in $\mathscr {K}$ we have

$$\begin{aligned} \langle Cz-Cz^{\prime },z-z^{\prime }\rangle&= \langle \nabla h(x)-\nabla h(x^{\prime }),x-x^\prime \rangle + \langle \nabla l^*(y)-\nabla l^*(y^{\prime }),y-y^\prime \rangle \nonumber \\&\ge \frac{1}{\beta _{h}}\Vert \nabla h(x)-\nabla h(x^{\prime })\Vert ^{2} +\frac{1}{\beta _{l}}\Vert \nabla l^*(y)-\nabla l^*(y^{\prime })\Vert ^{2} \nonumber \\&\ge \min \{\beta _{l}^{-1},\beta _{h}^{-1}\}\Vert Cz-Cz^{\prime } \Vert ^{2}. \end{aligned}$$

(100)

It follows from Lemma 5.1 that $P\in \mathscr {S}_\tau (\mathscr {K})$ with $\tau$ defined in (69). Therefore, we have $\Vert P^{-1}\Vert \le \tau ^{-1}$. Using (100), we have

$$\begin{aligned} \langle Cz-Cz^{\prime },z-z^{\prime }\rangle&\ge \min \{\beta _{l}^{-1},\beta _{h}^{-1}\}\Vert Cz-Cz^{\prime } \Vert ^{2} \\&\ge \Vert P^{-1}\Vert ^{-1}\min \{\beta _{l}^{-1},\beta _{h}^{-1}\}\Vert Cz-Cz^{\prime } \Vert _{P^{-1}}^{2} \\&\ge \tau \min \{\beta _{l}^{-1},\beta _{h}^{-1}\}\Vert Cz-Cz^{\prime } \Vert _{P^{-1}}^{2}. \end{aligned}$$

Hence, C is $\beta$-cocoercive with respect to $\Vert \cdot \Vert _P$, where $\beta =\tau \min \{\beta _{l}^{-1},\beta _{h}^{-1}\}$. In the case when $l=\iota _{\{0\}}$, we have $\nabla l^{*}=0$ and it is possible to derive less conservative parameters. Define the linear operator $Q:(x,y)\rightarrow (x,0)$, then,

$$\begin{aligned} \Vert Qz\Vert _{P^{-1}}^{2}&=\langle x,(\gamma _{1}^{-1}\mathrm{Id}-\frac{\gamma _{2}}{4}\theta ^{2}L^{*}L)^{-1}x\rangle \le \Vert x\Vert ^{2}\Vert (\gamma _{1}^{-1}\mathrm{Id}-\frac{\gamma _{2}}{4}\theta ^{2}L^{*}L)^{-1}\Vert \\&\le \Vert Qz\Vert ^{2}(\gamma _{1}^{-1}-\frac{\gamma _{2}}{4}\theta ^{2}\Vert L\Vert ^{2})^{-1}, \end{aligned}$$

where we used (65). For $\beta _{h}\in ]0,+\infty [$, considering the above inequality and the fact that $Cz=(\nabla h(x),0)$ we obtain

$$\begin{aligned} \Vert Cz-Cz^{\prime }\Vert _{P^{-1}}^{2}&\le (\gamma _{1}^{-1}-\frac{\gamma _{2}}{4}\theta ^{2}\Vert L\Vert ^{2})^{-1}\Vert \nabla h(x)-\nabla h(x^{\prime })\Vert ^{2}\\&\le \beta _{h}(\gamma _{1}^{-1}-\frac{\gamma _{2}}{4}\theta ^{2}\Vert L\Vert ^{2})^{-1}\langle \nabla h(x)-\nabla h(x^{\prime }),x-x^\prime \rangle \\&=\beta _{h}(\gamma _{1}^{-1}-\frac{\gamma _{2}}{4}\theta ^{2}\Vert L\Vert ^{2})^{-1}\langle Cz-Cz^{\prime },z-z^\prime \rangle , \end{aligned}$$

where the last inequality follows from the Baillon-Haddad theorem [1, Corollary 18.16]. This shows that C is $\beta$-cocoercive with respect to $\Vert \cdot \Vert _P$, with $\beta$ defined in (72).

Proof of Lemma 5.3

We start by showing that $S_2$ is strongly positive. Lemma 5.1 asserts that $P\in \mathscr {S}_\tau (\mathscr {K})$ with $\tau$ defined in (69). Simple calculations show that $\tau \le \min \{\gamma _1^{-1},\gamma _2^{-1}\}$. If $\theta \in [2,\infty [$ define a constant c, such that $0<c<\tau$, otherwise if $\theta \in [0,2[$ set c such that $0<c<\min \left\{ \tau ,\frac{(2-\theta )\gamma _{2}^{-1}}{4}\right\}$. Then for all $z=(x,y)\in \mathscr {K}$, $\langle (P-c\mathrm{Id})z,z \rangle >0$ which implies

$$\begin{aligned} (\gamma _{1}^{-1}-c)\Vert x\Vert ^2-\tfrac{\theta ^{2}}{4(\gamma _{2}^{-1}-c)}\Vert Lx\Vert ^2 > 0. \end{aligned}$$

(101)

It follows from (74b) that

$$\begin{aligned} \langle z,S_{2}z\rangle&= \gamma _{1}^{-1}\Vert x\Vert ^{2}-2\langle Lx,y\rangle +\gamma _{2}^{-1}\Vert y\Vert ^{2}+\gamma _{2}(2-\theta )\Vert Lx\Vert ^{2} \\&= c\Vert z\Vert ^{2}+(\gamma _{1}^{-1}-c)\Vert x\Vert ^{2}-2\langle Lx,y\rangle +(\gamma _{2}^{-1}-c)\Vert y\Vert ^{2}+\gamma _{2}(2-\theta )\Vert Lx\Vert ^{2} \\&\ge c\Vert z\Vert ^{2}{+}(\gamma _{1}^{-1}-c)\Vert x\Vert ^{2}{+}(\gamma _{2}^{-1}-c-\epsilon )\Vert y\Vert ^{2}{+}(\gamma _{2}(2-\theta )-\epsilon ^{-1})\Vert Lx\Vert ^{2}, \end{aligned}$$

where the last line follows from Fenchel-Young inequality for $\frac{\epsilon }{2}\Vert \cdot \Vert ^2$. Let $\epsilon =\gamma _{2}^{-1}-c$ so that the term involving $\Vert y\Vert ^2$ disappears, and use (101) to derive

$$\begin{aligned} \langle z,S_{2}z\rangle&\ge \ c\Vert z\Vert ^{2}+(\gamma _{1}^{-1}-c)\Vert x\Vert ^{2}+\left( \gamma _{2}\left( 2-\theta \right) -\tfrac{1}{\gamma _{2}^{-1}-c}\right) \Vert Lx\Vert ^{2} \nonumber \\&> c\Vert z\Vert ^{2}+\left( \gamma _{2}(2-\theta )+\left( \tfrac{\theta ^{2}}{4}-1\right) \tfrac{1}{\gamma _{2}^{-1}-c}\right) \Vert Lx\Vert ^{2}. \end{aligned}$$

(102)

It follows from the choice of c for both $\theta \in [0,2[$ and $\theta \in [2,\infty [$ that the last term in (102) is nonnegative and hence, $S_{2}\in \mathscr {S}_c(\mathscr {K})$. The analysis for $S_1$ is similar and therefore has been omitted. Hence, it follows that $S_1^{-1}$ and $S_2^{-1}$ are strongly positive and so is their convex combination and its inverse, S. Furthermore, it was shown in (6) that if S and P are strongly positive, K skew-adjoint and M monotone, then $D\in \mathscr {S}_\nu (\mathscr {K})$ for some $\nu \in ]0,\infty [$, where D was defined in (5). We conclude by noting that D in (76) can be derived by substituting S in (5).$\square$

Proof of Proposition 5.2

Algorithm 4 is a special case of Algorithm 3 and consequently of Algorithm 1. Let us establish the proof by directly showing that Theorem 3.1 is applicable with $(\lambda _n)_{n\in \mathrm{{I}}\!\mathrm{{N}}}$ selected such that $\alpha _{n}=1$, while satisfying (7). For all (i)–(iii), strong positivity of the operators P, S, and D follow from Lemma 5.1 and 5.3. Set

$$\begin{aligned} \lambda _{n} = \frac{\Vert \tilde{z}_{n}\Vert _{D}^{2}}{\Vert \tilde{z}_{n}\Vert _{P}^{2}}= 1+\frac{\gamma _{2}\Vert L\tilde{x}_{n}\Vert ^{2}+\gamma _{1}\Vert L^{*}\tilde{y}_{n}\Vert ^{2}}{\gamma _{1}^{-1}\Vert \tilde{x}_{n}\Vert ^{2}+\gamma _{2}^{-1}\Vert \tilde{y}_{n}\Vert ^{2}}. \end{aligned}$$

(103)

Such a choice would yield $\alpha _n=1$. A sufficient condition for (7) to hold is to show that $(\lambda _n)_{n\in \mathrm{{I}}\!\mathrm{{N}}}$ is uniformly bounded between 0 and $\delta$. From strong positivity of D and boundedness of P it follows that $(\lambda _{n})_{n\in \mathrm{{I}}\!\mathrm{{N}}}\subseteq [\nu _1,\infty [$ for some positive $\nu _1$. Denote by $\beta$ the cocoercivity constant of C with respect to $\Vert \cdot \Vert _P$. We proceed by showing that $(\lambda _{n})_{n\in \mathrm{{I}}\!\mathrm{{N}}}\subseteq [\nu _1,2-\frac{1}{2\beta }-\nu _2]$. Assume that

$$\begin{aligned} 0<1-\gamma _1\gamma _2\Vert L\Vert ^2-\tfrac{1}{2\beta }. \end{aligned}$$

(104)

Then, there exists a positive constant $\nu _2$ such that

$$\begin{aligned} \nu _2<1-\gamma _1\gamma _2\Vert L\Vert ^2-\tfrac{1}{2\beta }. \end{aligned}$$

(105)

It follows from (103) that

$$\begin{aligned} \lambda _{n} \le 1+\frac{\gamma _{2}\Vert L\Vert ^2\Vert \tilde{x}_{n}\Vert ^{2}+\gamma _{1}\Vert L\Vert ^2\Vert \tilde{y}_{n}\Vert ^{2}}{\gamma _{1}^{-1}\Vert \tilde{x}_{n}\Vert ^{2}+\gamma _{2}^{-1}\Vert \tilde{y}_{n}\Vert ^{2}} < 2-\tfrac{1}{2\beta }-\nu _2, \end{aligned}$$

where in the second inequality we used (105) to upper bound both $\gamma _{2}\Vert L\Vert ^2$ and $\gamma _{1}\Vert L\Vert ^2$. We showed that (104) is sufficient for (7) to hold. Consequently, Theorem 3.1 completes the proof of convergence.

• (i) : By Lemma 5.2, substitute $\beta$ in (104) with (71) to derive (83). The algorithm follows by substituting $\alpha _{n}=1$ in Algorithm 3 when $\theta =0$ and $\mu =\frac{1}{2}$.

• (ii) : Similar to (i), since $l=\iota _{\{0\}}$, substitute $\beta$ in (104) with (72), i.e. $\beta =\beta _{h}^{-1}\gamma _{1}^{-1}$. This choice of $\beta$ results in (84) and the algorithm follows.

• (iii) : The proof is similar to previous parts, but we show that $(\lambda _n)_{n\in \mathrm{{I}}\!\mathrm{{N}}}$ is uniformly bounded between 0 and 2, and then use Theorem 3.1 with $C\equiv 0$.$\square$