# Projective splitting with backward, half-forward and proximal-Newton steps

M. Marques Alves  Departamento de Matemática, Universidade Federal de Santa
Catarina, Florianópolis, Brazil, 88040-900 (maicon.alves@ufsc.br). This work
was partially supported by CNPq grant 308036/2021-2.

###### Abstract

We propose and study the weak convergence of a projective splitting algorithm
[2, 30] for solving multi-term composite monotone inclusion problems involving
the finite sum of $n$ maximal monotone operators, each of which having an
inner four-block structure: sum of maximal monotone, Lipschitz continuous,
cocoercive and smooth differentiable operators. We show how to perform
backward and half-forward [18] steps with respect to the maximal monotone and
Lipschitz$+$cocoercive components, respectively, while performing proximal-
Newton steps with respect to smooth differentiable blocks.

2000 Mathematics Subject Classification: 47H05, 49M27, 47N10.

Key words: projective splitting algorithm, monotone inclusions, operator-
splitting, proximal-Newton.

##  1 Introduction

Consider the multi-term composite monotone inclusion problem

$\displaystyle
0\in\sum_{i=1}^{n}\,G_{i}^{*}(\underbrace{A_{i}+B_{i}+C_{i}+D_{i}}_{T_{i}})G_{i}(z),$
(1)

where, for each $i=1,\dots,n$, $G_{i}$ is bounded linear, $A_{i}$ is (set-
valued) maximal monotone, $B_{i}$ is (point-to-point) monotone and Lipschitz,
$C_{i}$ is (point-to-point) cocoercive and $D_{i}$ is (point-to-point)
monotone and continuously differentiable (more details later in Section 3).
Problem (1) appears in different fields of applied mathematics and
optimization, including inverse problems and machine learning (see, e.g., [2,
37, 50]).

In this paper, we present and study a new version of the projective splitting
(PS) algorithm (see, e.g., [2, 30, 31, 40]) for solving (1). Our main
algorithm (Algorithm 2 below) splits (1) into its $n$ pieces, by evaluating
each linear operator $G_{i}$, as well as the Lipschitz and cocoercive
operators $B_{i}$ and $C_{i}$, respectively, and by computing the resolvent of
$A_{i}$ plus a linearization of the continuously differentiable operator
$D_{i}$, which we refer to as a proximal-Newton step. Since PS algorithms are
of high interest nowadays, it follows that special instances of (1) have been
previously considered by other authors (more details later in this section),
but up to our knowledge none of them considered proximal-Newton steps with
respect to the smooth differentiable mappings $D_{i}$ in (1).

The extended-solution set. PS algorithms can be derived by noting that (under
the additional assumption that $G_{n}=I$), a vector $z$ is a solution of
problem (1) if and only if there exist $w_{1},\dots,w_{n-1}$ such that the
$n$-tuple $(z,w_{1},\dots,w_{n-1})$ belongs to the _extended-solution set_ [2,
31]:

$\displaystyle\mathcal{S}:=\left\\{(z,w_{1},\dots,w_{n-1})\mid w_{i}\in
T_{i}(G_{i}z),\;i=1,\dots,n,\;w_{n}:=-\sum_{i=1}^{n-1}\,G_{i}^{*}w_{i}\right\\}.$
(2)

Since $\mathcal{S}$ is a closed and convex subset of a product space (more
details in Section 3), one can approximate points in $\mathcal{S}$ by
successive projections onto separating hyperplanes. The basic idea consists in
giving a current point $p^{k}=(z^{k},w_{1}^{k},\dots,w_{n-1}^{k})$, find an
affine functional/separator, say $\varphi_{k}(\cdot)$, such that
$\varphi_{k}(p^{k})>0$ and $\varphi_{k}(p)\leq 0$ for all
$p=(z,w_{1},\dots,w_{n-1})\in\mathcal{S}$, and then define the next iterate
$p^{k+1}$ as the projection of $p^{k}$ (which can be explicitly computed) onto
the semi-space $\\{p\;|\;\varphi_{k}(p)\leq 0\\}$ containing $\mathcal{S}$.
For example, at a current iterate $k\geq 0$, a separator $\varphi_{k}(\cdot)$
can be constructed by choosing in an appropriate way $(x_{i}^{k},y_{i}^{k})$
in the graph of $T_{i}$ ($1\leq i\leq n$) and letting

$\displaystyle\varphi_{k}(p):={\sum_{i=1}^{n}\,}\,\langle
G_{i}z-x_{i}^{k}\,|\,y_{i}^{k}-w_{i}\rangle,$ (3)

where $p=(z,w_{1},\dots,w_{n-1})$ and $w_{n}$ is as in (2).

Sufficient conditions for separation. One may ask under what conditions the
affine functional $\varphi_{k}(\cdot)$ as in (3) produces good separators,
i.e., under what conditions we have $\varphi_{k}(p^{k})>0$ and
$\varphi_{k}(p)\leq 0$ for all $p\in\mathcal{S}$, while ensuring the resulting
projective algorithm has good convergence properties. Since the definition of
$\varphi_{k}(\cdot)$ depends on the points $(x_{i}^{k},y_{i}^{k})$ ($1\leq
i\leq n$), all we need to do is to provide rules for picking these points in
an appropriate way. Some of the strategies from the current literature on the
subject are as follows:

  1. 1.

Assume that the resolvent $(T_{i}+I)^{-1}$ of each $T_{i}$ ($1\leq i\leq n$)
is computable and let, for $i=1,\dots,n$,

$x_{i}^{k}=(\rho_{i}^{k}T_{i}+I)^{-1}(G_{i}z^{k}+\rho_{i}^{k}w_{i}^{k})\;\;\mbox{and}\;\;y_{i}^{k}=\dfrac{G_{i}z^{k}-x_{i}^{k}}{\rho_{i}^{k}}+w_{i}^{k},$

where $\rho_{i}^{k}>0$ is a proximal parameter. This appears, for instance, in
the works [2, 30, 31].

  2. 2.

Set, for all $i=1,\dots,n$, $B_{i}$ and $D_{i}$ as zero in (1), and then
compute single-forward steps for the cocoercive operators $C_{i}$ ($1\leq
i\leq n$) and backward steps for the maximal monotone operators $A_{i}$, i.e.,

$x_{i}^{k}=(\rho_{i}^{k}A_{i}+I)^{-1}\left(G_{i}z^{k}+\rho_{i}^{k}w_{i}^{k}-\rho_{i}^{k}C_{i}(G_{i}z^{k})\right)\;\;\mbox{and}\;\;y_{i}^{k}=\dfrac{G_{i}z^{k}-x_{i}^{k}}{\rho_{i}^{k}}+w_{i}^{k}.$

This appears in the works [20, 39].

  3. 3.

Set, for all $i=1,\dots,n$, $C_{i}$ and $D_{i}$ as zero in (1), and then
compute forward steps for the Lipschitz operators $B_{i}$ ($1\leq i\leq n$),
in the spirit of the seminal work of P. Tseng [59], and backward steps for
$A_{i}$, i.e.,

$x_{i}^{k}=(\rho_{i}^{k}A_{i}+I)^{-1}\left(G_{i}z^{k}+\rho_{i}^{k}w_{i}^{k}-\rho_{i}^{k}B_{i}(G_{i}z^{k})\right)\;\mbox{and}\;\;y_{i}^{k}=\dfrac{G_{i}z^{k}-x_{i}^{k}}{\rho_{i}^{k}}+w_{i}^{k}+\left[B_{i}(x_{i}^{k})-B_{i}(G_{i}z^{k})\right].$

Note that, when compared to $y_{i}^{k}$ as in item 2 above, $y_{i}^{k}$ as in
the latter displayed equation requires two more evaluations of the Lipschitz
operator $B_{i}$. This approach appeared, e.g., in the works [20, 40].

Main contributions of this work. As was already mentioned, the main
contribution of this work is the incorporation of proximal-Newton steps in the
PS framework with respect to the smooth differentiable mappings $D_{i}$
($1\leq i\leq n$) in (1). More precisely, to define the separator
$\varphi_{k}(\cdot)$, we will compute pairs $(x_{i}^{k},y_{i}^{k})$ ($1\leq
i\leq n$) as described in lines 2 and 2-2 of Algorithm 2, where, in
particular, we use a linearization $D_{i\,(G_{i}z^{k})}$ of $D_{i}$ at a
(current) point $G_{i}z^{k}$ ($1\leq i\leq n$); this is exactly what we refer
to as a proximal-Newton step. We also mention that a line-search procedure
(see line 2 of Algorithm 2) may be needed to choose the proximal parameter
$\rho_{i}^{k}>0$ ($1\leq i\leq n$), as described in Algorithm 3. The weak
convergence of our main algorithm, namely Algorithm 2, will be presented in
Theorem 4.7. For more details, we also refer the reader to the various
comments/remarks following Algorithm 2.

Next we review some related works on projective- and operator-splitting
algorithms. As we already mentioned, none of the variants of PS algorithm
mentioned below considered differentiable operators $D_{i}$ in $T_{i}$ \- as
in (1) - and, consequently, none of them performed proximal-Newton steps as in
the present work.

Projective- and operator-splitting algorithms. To the best of our knowledge,
the basic idea of PS algorithms originates in [30], with $n=2$ in (1),
$G_{i}=I$ and $T_{i}$ general maximal monotone operators ($i=1,2$), i.e., for
solving the two-operator monotone inclusion $0\in T_{1}(z)+T_{2}(z)$.
Subsequently, the method was extended in [31] for $n>2$, but still under the
above mentioned assumptions on $G_{i}$ and $T_{i}$ ($i=1,\dots,n$).
Compositions with linear operators $G_{i}$ ($i=1,\dots,n$) as in (1) appeared
for the first time in [2] (see also [3, 19, 20, 24]). Asynchronous and block-
iterative versions of the PS framework were developed and studied for the
first time in [23]. Forward and single-forward steps for Lipschitz and
cocoercive operators, respectively, were introduced and studied in [39, 40]
(see also [38]). Stochastic and inertial versions of the PS algorithm were
also studied in [37] and [5], respectively.

The literature on operator-splitting algorithms for monotone inclusions is
huge. The modern treatise [13] is quite helpful in presenting, among other
results on convex analysis and monotone operator theory, the basic theory of
some of the most important operator-splitting algorithms like the celebrated
Douglas-Rachford [29, 45] and Forward-Backward [45, 53] splitting algorithms.
In the last decades, with a growing interest in applications in inverse
problems and machine learning, many other variants of operator splitting
algorithms have emerged. We mention the Davis–Yin splitting [27], new variants
of the alternating direction method of multipliers (ADMM) algorithm (see,
e.g., [17, 35, 51]) and the hybrid proximal-extragradient (HPE) method and its
many variants (see, e.g., [4, 6, 7, 12, 42, 49, 50] and references there in).
Many other researchers and research groups have contributed to the subject in
different directions, as for instance [8, 9, 10, 14, 15, 16, 26, 32, 33, 22,
34, 41, 46, 47, 57, 58]. The monographs [17, 56] can also be quite useful to
many of the above mentioned algorithms and results.

Organization of the paper. The material is organized as follows. In Section 2,
we present some basic results. In Section 3, we present our main algorithm,
namely Algorithm 2. In Section 4, Theorem 4.7, we study the weak convergence
of Algorithm 2. Section 5 is devoted to present and study the
bracketing/bisection procedure called during the execution of Algorithm 2; see
Algorithm 3.

General notation. Let ${\mathcal{H}}$ be a real Hilbert space. The weak
convergence of a sequence $(z^{k})$ in ${\mathcal{H}}$ to $z\in{\mathcal{H}}$
will be denoted by $z^{k}\rightharpoonup z$. A set-valued map
$T:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$ is said to be a _monotone
operator_ if $\langle z-z^{\prime}\,|\,v-v^{\prime}\rangle\geq 0$ for all
$v\in T(z)$ and $v^{\prime}\in T(z^{\prime})$. On the other hand,
$T:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$ is _maximal monotone_ if $T$
is monotone and its _graph_
$\mbox{Gr}(T):=\\{(z,v)\in{\mathcal{H}}\times{\mathcal{H}}\,|\,v\in T(z)\\}$
is not properly contained in the graph of any other monotone operator on
${\mathcal{H}}$. The _domain_ of
$T:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$ is
$\mbox{Dom}(T):=\\{z\in{\mathcal{H}}\;|\;T(z)\neq\emptyset\\}$. The _inverse_
of $T:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$ is
$T^{-1}:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$, defined at any
$z\in{\mathcal{H}}$ by $v\in T^{-1}(z)$ if and only if $z\in T(v)$. The
_resolvent_ of a maximal monotone operator
$T:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$ is $J_{T}:=(T+I)^{-1}$; note
that $z=(T+I)^{-1}x$ if and only if $x-z\in T(z)$. The operator $\gamma
T:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$, where $\gamma>0$, is defined
by $(\gamma T)z:=\gamma T(z):=\\{\gamma v\,|\,v\in T(z)\\}$. The sum of
$T:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$ and
$S:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$ is defined via the usual
Minkowski sum $T(z)+S(z):=\\{u+v\;|\;u\in T(z)\;\;\mbox{and}\;\;v\in S(z)\\}$.

The _adjoint_ of a bounded linear operator $G:{\mathcal{H}}\to{\mathcal{H}}$
is denoted by $G^{*}$. A (point-to-point) operator
$C:{\mathcal{H}}\to{\mathcal{H}}$ is said to be $\beta$-_coercive_ if
$\beta\geq 0$ and $\langle
z-z^{\prime}\,|\,C(z)-C(z^{\prime})\rangle\geq\beta\|{C(z)-C(z^{\prime})}\|^{2}$
for all $z,z^{\prime}\in{\mathcal{H}}$. On the other hand, a (point-to-point)
operator $B:{\mathcal{H}}\to{\mathcal{H}}$ is said to be $\ell$-Lipschitz
continuous if $\ell\geq 0$ and
$\|{B(z)-B(z^{\prime})}\|\leq\ell\|{z-z^{\prime}}\|$ for all
$z,z^{\prime}\in{\mathcal{H}}$. The _subdifferential_ of a convex function
$f:{\mathcal{H}}\to(-\infty,\infty]$ is $\partial
f:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$, defined at any
$z\in{\mathcal{H}}$ as $\partial
f(z):=\\{u\in{\mathcal{H}}\;|\;f(z^{\prime})\geq f(z)+\langle
u\,|\,z^{\prime}-z\rangle\;\;\;\forall z^{\prime}\in{\mathcal{H}}\\}$. For
additional details on standard notation on convex analysis and monotone
operators we refer the reader to the books [13, 54].

The derivative of a continuously differentiable mapping
$D:{\mathcal{H}}\to{\mathcal{H}}$ will be denoted by $D^{\prime}(\cdot)$. The
norm of $D^{\prime}(z)$ is $\|{D^{\prime}(z)}\|:=\sup_{\|{x}\|\leq
1}\,\|{D^{\prime}(z)x}\|$. We will also frequently use the notation

$\displaystyle D_{(u)}(z):=D(u)+D^{\prime}(u)(z-u)\qquad\forall
z,u\in{\mathcal{H}}.$ (4)

Now let ${\mathcal{H}}_{0},{\mathcal{H}}_{1},\ldots,{\mathcal{H}}_{n-1}$ be
real Hilbert spaces, let ${\mathcal{H}}_{n}:={\mathcal{H}}_{0}$ and let
$\langle\cdot\,|\,\cdot\rangle$ and
$\|\cdot\|=\sqrt{\langle\cdot\,|\,\cdot\rangle}$ denote the inner product and
norm (respectively) in ${\mathcal{H}}_{i}$ ($i=0,\dots,n$). Let
$\bm{{\mathcal{H}}}:={\mathcal{H}}_{0}\times{\mathcal{H}}_{1}\times\dots\times{\mathcal{H}}_{n-1}$
be endowed with the inner product and norm defined, respectively, as follows
(for some $\gamma>0$):

$\displaystyle\langle p\,|\,\tilde{p}\rangle_{\gamma}=\gamma\langle
z\,|\,\tilde{z}\rangle+\sum_{i=1}^{n-1}\langle
w_{i}\,|\,\tilde{w}_{i}\rangle,\quad\|{p}\|_{\gamma}=\sqrt{\langle
p\,|\,p\rangle_{\gamma}},$ (5)

where $p=(z,w)$, $\tilde{p}=(\tilde{z},\tilde{w})$, with
$z,\tilde{z}\in{\mathcal{H}}_{0}$ and
$w:=(w_{1},\dots,w_{n-1}),\tilde{w}:=(\tilde{w}_{1},\dots,\tilde{w}_{n-1})\in{\mathcal{H}}_{1}\times\ldots\times{\mathcal{H}}_{n-1}$.
Elements in $\bm{{\mathcal{H}}}$ will be denoted either by
$p=(z,w_{1},\dots,w_{n-1})$ or simply $p=(z,w)$, where
$w=(w_{1},\dots,w_{n-1})$, and we will use the notation

$\displaystyle w_{n}=-\sum_{i=1}^{n-1}\,G_{i}^{*}w_{i}$ (6)

whenever $p\in\bm{{\mathcal{H}}}$ and $G_{i}$ is bounded linear
($i=1,\dots,n-1$).

We will also adopt the following conventions: $0\cdot\infty=0$, $1/\infty=0$,
$1/0=\infty$ and $r\cdot\infty=\infty$ for all $r\in(0,\infty)$. By
$\mathbb{R}_{++}$ we denote the set of strictly positive real numbers.

##  2 Basic results

In this section, we present a general separator-projection framework
(Algorithm 1) for finding a point in a nonempty closed and convex subset of a
Hilbert space, along with other basic results we will need in this paper. The
main reason to consider Algorithm 1 here comes from the fact (as previously
discussed in Section 1) that the monotone inclusion problem (1) can be
reformulated as the problem of finding a point in the extended solution set
$\mathcal{S}$ as in (2). Algorithm 1 will be used in Section 4 to analyze the
convergence of the main algorithm proposed in this paper, namely Algorithm 2
below.

Throughout this section, ${\mathcal{H}}$ and $\mathcal{K}$ denote real Hilbert
spaces with inner product $\langle\cdot\,|\,\cdot\rangle$ and norm
$\|\cdot\|=\sqrt{\langle\cdot\,|\,\cdot\rangle}$. We denote the gradient of an
affine function $\varphi:{\mathcal{H}}\to\mathbb{R}$ by the standard notation
$\nabla\varphi$ and we also write
$\varphi(z)=\langle\nabla\varphi\,|\,z\rangle+\varphi(0)$ for all
$z\in{\mathcal{H}}$.

Input: $p^{0}\in{\mathcal{H}}$, $0<\underline{\tau}<\overline{\tau}<2$

1 for  _$k=0,1,2,\dots$_ do

2 Find an affine function $\varphi_{k}$ in ${\mathcal{H}}$ such that
$\mathcal{S}\subset\\{p\in{\mathcal{H}}\;|\;\varphi_{k}(p)\leq 0\\}$

3 if  _$\varphi_{k}(p^{k}) >0$_ then

4 Choose $\tau_{k}\in[\underline{\tau},\overline{\tau}]$

5 [2mm]
$\alpha_{k}=\tau_{k}\dfrac{\varphi_{k}(p^{k})}{\|{\nabla\varphi_{k}}\|^{2}}$

6 [3mm] $p^{k+1}=p^{k}-\alpha_{k}\nabla\varphi_{k}$

7 else

8 $p^{k+1}=p^{k}$

9 end if

10

11 end for

Algorithm 1 Generic linear separation-projection method for finding a point in
a nonempty closed and convex set $\mathcal{S}\subset{\mathcal{H}}$

Next lemma is about the weak convergence of Algorithm 1.

######  Lemma 2.1.

_([2])_ The following holds for any sequence $(p^{k})$ generated by _Algorithm
1_.

  * _(a)_

$(p^{k})$ is bounded.

  * _(b)_

If all weak cluster points of $(p^{k})$ are in $\mathcal{S}$, then $(p^{k})$
converges weakly to some point in $\mathcal{S}$.

  * _(c)_

If there exists $\xi>0$ such that $\|{\nabla\varphi_{k}}\|\leq\xi$, for all
$k\geq 0$, then $\overline{\lim}\,\varphi_{k}(p^{k})\leq 0$.

Next lemma will be useful in the convergence analysis of Algorithm 2.

######  Lemma 2.2.

_([1, Lemma 3.1])_ Let $G:{\mathcal{H}}\to\mathcal{K}$ be a bounded linear
operator let $V$ be the graph of $G$, i.e.,
$V:=\\{(z,Gz)\in{\mathcal{H}}\times\mathcal{K}\;|\;z\in{\mathcal{H}}\\}$. Let
$P$ and $P^{\perp}$ denote the orthogonal projections onto $V$ and $V^{\perp}$
(the orthogonal complement of $V$), respectively. Then, for all
$(z,w)\in{\mathcal{H}}\times\mathcal{K}$, we have

$\displaystyle P(z,w)=((I+G^{*}G)^{-1}(z+G^{*}w),G(I+G^{*}G)^{-1}(z+G^{*}w)),$
$\displaystyle
P^{\perp}(z,w)=(G^{*}(I+GG^{*})^{-1}(Gz-w),-(I+GG^{*})^{-1}(Gz-w)).$

A proof of the lemma below in finite-dimensional spaces can be found in [28,
Lemma 4.1.12]. A proof in general Hilbert spaces follows the same outline as
in the finite-dimensional case.

######  Lemma 2.3.

Let $D:{\mathcal{H}}\to{\mathcal{H}}$ be a continuously differentiable mapping
with an $m$-Lipschitz continuous derivative $D^{\prime}(\cdot)$, i.e., let $D$
be such that there exits $m\geq 0$ satisfying

$\displaystyle\|{D^{\prime}(x)-D^{\prime}(y)}\|\leq m\|{x-y}\|\qquad\forall
x,y\in{\mathcal{H}}.$ (7)

Then,

$\|{D(z)-D_{(u)}(z)}\|\leq\dfrac{m}{2}\|{z-u}\|^{2}\qquad\forall
z,u\in{\mathcal{H}},$

where $D_{(u)}(z)$ is as in (4).

######  Lemma 2.4.

Let $T:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$ be a maximal monotone
operator. Let $(s^{k})$ and $(u^{k})$ be bounded sequences in ${\mathcal{H}}$,
let $(\rho^{k})$ be a bounded sequence in $\mathbb{R}_{++}$ and let
$D_{(u^{k})}(\cdot)$ be as in (4) with $u=u^{k}$. Then the sequence $(x^{k})$
defined by

$\displaystyle
x^{k}=J_{\rho^{k}\left(T+D_{(u^{k})}\right)}(s^{k})\qquad\forall k\geq 0$ (8)

is bounded.

###### Proof.

Let $w\in\mbox{Dom}(T)$ and, for each $k\geq 0$, choose
$r^{k}\in{\mathcal{H}}$ such that $r^{k}\in(T+D_{(u^{k})})(w)$, i.e., take
$a\in T(w)$ and let, for each $k\geq 0$, $r^{k}=a+D_{(u^{k})}(w)$. Since
$(u^{k})$ is bounded, it follows from Lemma 2.3 that $(r^{k})$ is also
bounded. Note now that the inclusion $r^{k}\in(T+D_{(u^{k})})(w)$ is clearly
equivalent to $w=J_{\rho^{k}\left(T+D_{(u^{k})}\right)}(\rho^{k}r^{k}+w)$,
which combined with (8) and the nonexpansiveness of
$J_{\rho^{k}(T+D_{u^{k}})}(\cdot)$ yields

$\|{x^{k}-w}\|\leq\|{s^{k}-\rho^{k}r^{k}-w}\|\leq\|{s^{k}-w}\|+\rho^{k}\|{r^{k}}\|.$

The desired result now follows from the boundedness of $(s^{k})$, $(\rho^{k})$
and $(r^{k})$. ∎

##  3 The problem and the main algorithm

In this section, we present our main algorithm, namely Algorithm 2, for
solving the multi-term monotone inclusion problem (1). In some cases,
Algorithm 2 may need a bracketing/bisection procedure, which we discuss in
Section 5 (see Algorithm 3). The main result on the weak convergence of
Algorithm 2 will be presented in Section 4 (Theorem 4.7). We also refer the
reader to the comments and remarks following Algorithms 2 and 3.

Consider the monotone inclusion problem (1), i.e., the problem of finding
$z\in{\mathcal{H}}_{0}$ such that

$\displaystyle
0\in\sum_{i=1}^{n}\,G_{i}^{*}(\underbrace{A_{i}+B_{i}+C_{i}+D_{i}}_{T_{i}})G_{i}(z),$
(9)

where the following assumptions are assumed to hold for all $i=1,\dots,n$:

  * (A1)

$G_{i}:{\mathcal{H}}_{0}\to{\mathcal{H}}_{i}$ is a bounded linear operator and
$G_{n}=I$ (the identity operator).

  * (A2)

$A_{i}:{\mathcal{H}}_{i}\rightrightarrows{\mathcal{H}}_{i}$ is a (set-valued)
maximal monotone operator.

  * (A3)

$B_{i}:{\mathcal{H}}_{i}\to{\mathcal{H}}_{i}$ is a (point-to-point) monotone
and $\ell_{i}$-Lipschitz continuous operator, i.e., there exists
$\ell_{i}\in[0,\infty)$ such that

$\displaystyle\|{B_{i}(x)-B_{i}(y)}\|\leq\ell_{i}\|{x-y}\|\qquad\forall
x,y\in{\mathcal{H}}_{i}.$ (10)

  * (A4)

$C_{i}:{\mathcal{H}}_{i}\to{\mathcal{H}}_{i}$ is a (point-to-point)
$\beta_{i}$-cocoercive operator, i.e., there exists $\beta_{i}\in(0,\infty]$
such that

$\displaystyle\langle
x-y\,|\,C_{i}(x)-C_{i}(y)\rangle\geq\beta_{i}\|{C_{i}(x)-C_{i}(y)}\|^{2}\qquad\forall
x,y\in{\mathcal{H}}_{i}.$ (11)

  * (A5)

$D_{i}:{\mathcal{H}}_{i}\to{\mathcal{H}}_{i}$ is a (point-to-point)
continuously differentiable monotone operator with an $m_{i}$-Lipschitz
continuous derivative $D^{\prime}_{i}(\cdot)$, i.e., there exists
$m_{i}\in[0,\infty)$ such that

$\displaystyle\|{D^{\prime}_{i}(x)-D^{\prime}_{i}(y)}\|\leq
m_{i}\|{x-y}\|\qquad\forall x,y\in{\mathcal{H}}_{i}.$ (12)

  * (A6)

The solution set of (9) is nonempty.

We also assume the following regarding the family of operators $D_{i}(\cdot)$
($i=1,\dots,n$):

  * (A7)

There exists a subset of indexes
$\mathcal{I}_{\mathcal{D}}\subset\\{1,\dots,n\\}$ such that $m_{i}>0$ whenever
$i\in\mathcal{I}_{\mathcal{D}}$, and $m_{i}=0$ and $D_{i}=0$ for all
$i\in\\{1,\dots,n\\}\backslash\mathcal{I}_{\mathcal{D}}$ ($m_{i}=0$ in (12)
implies that $D_{i}$ is affine and, as a consequence, it can be incorporated
to either $B_{i}$ or $C_{i}$ and so ignored in (9), i.e., set to be zero).

An important instance (under appropriate qualification conditions) of (9) is
the minimization problem

$\displaystyle\min_{z\in{\mathcal{H}}_{0}}\,\sum_{i=1}^{n}\,\Big{\\{}f_{i}(G_{i}z)+g_{i}(G_{i}z)+h_{i}(G_{i}z)\Big{\\}},$
(13)

where, for $i=1,\dots,n$, $f_{i}:{\mathcal{H}}_{i}\to(-\infty,\infty]$ is
proper, convex and lower semicontinuous,
$g_{i}:{\mathcal{H}}_{i}\to\mathbb{R}$ is convex differentiable with a
$\beta^{-1}_{i}$-Lipschitz continuous gradient $\nabla g_{i}$ and
$h_{i}:{\mathcal{H}}\to\mathbb{R}$ is convex and twice-continuously
differentiable with an $m_{i}$-Lipschitz continuous second derivative
$\nabla^{2}h_{i}$, in which case we have, in the general setting of (9):

$\displaystyle A_{i}=\partial f_{i},\quad B_{i}=0,\quad C_{i}=\nabla
g_{i}\;\;\mbox{and}\;\;D_{i}=\nabla h_{i}.$ (14)

We mention that several problems of interest in Machine Learning, including
_logistic regression problems_ , are special instances of (13) – see, e.g.,
[11, 48].

Our main Algorithm (see Algorithm 2 below) for solving (9) will, in
particular, be conformed to the following set of rules (for $i=1,\dots n$):

  1. 1.

Evaluation of each linear operator $G_{i}$.

  2. 2.

Explicit evaluation of the Lipschitz and cocoercive components $B_{i}$ and
$C_{i}$, respectively.

  3. 3.

Computation and evaluation of the first-order approximation of $D_{i}$:

$\displaystyle
D_{i\;(u)}(z):=D_{i}(u)+D_{i}^{\prime}(u)(z-u)\qquad(z,u\in{\mathcal{H}}_{i}).$
(15)

  4. 4.

Implicit computation of the resolvent
$J_{\rho(A_{i}+D_{i\;(u)})}:=\left(\rho(A_{i}+D_{i\;(u)})+I\right)^{-1}$ of
the operator $A_{i}+D_{i\;(u)}$, where $\rho>0$ (see the third remark
following Algorithm 2 for additional details).

Recall that we assumed the solution set of (9) to be nonempty, i.e., we
assumed that there exists at least one $z\in{\mathcal{H}}_{0}$ satisfying the
inclusion in (9). We also note that, under assumptions (A2)–(A5) above,
$T_{i}$ as defined in (9) is maximal monotone for all $i=1,\dots,n$.

Before presenting our algorithm, recall the _extended-solution set_ as
previously presented in (2):

$\displaystyle\mathcal{S}:=\left\\{p\in\bm{{\mathcal{H}}}\mid
w_{i}\in(\underbrace{A_{i}+B_{i}+C_{i}+D_{i}}_{T_{i}})(G_{i}z),\;i=1,\dots,n,\;w_{n}:=-\sum_{i=1}^{n-1}\,G_{i}^{*}w_{i}\right\\},$
(16)

where by $p$ we denote $(z,w_{1},\dots,w_{n-1})$. One can prove that
$\mathcal{S}$ is closed and convex (see, e.g., [2]).

Next is our main algorithm.

Input: $(z^{0},w_{1}^{0},\dots,w_{n-1}^{0})\in\bm{{\mathcal{H}}}$,
$0<\underline{\tau}<\overline{\tau}<2$,
$0<\underline{\theta}<\overline{\theta}<2$, $\hat{\rho}>0$, $\hat{\delta}>0$,
$\gamma>0$ and $w_{n}^{0}:=-\sum_{i=1}^{n-1}\,G_{i}^{*}w_{i}^{0}$

1 for  _$k=0,1,2,\dots$_ do

2 for  _$i=1,\dots,n$_ do

3 if  _$w_{i}^{k}\in(A_{i}+B_{i}+C_{i}+D_{i})(G_{i}z^{k})$_ then

4 $\rho_{i}^{k}=\hat{\rho}$, $x_{i}^{k}=G_{i}z^{k}$ and $y_{i}^{k}=w_{i}^{k}$

5

6 else

7 if  _$i\in\mathcal{I}_{\mathcal{D}}$_ then

8 Let
$(\rho_{i}^{k},x_{i}^{k},y_{i}^{k})\leftarrow\textnormal{{BrackBisecProc(}}\textnormal{\emph{$A_{i},B_{i},C_{i},D_{i},G_{i},z^{k},w_{i}^{k},\ell_{i},\beta_{i},m_{i}$}}\textnormal{{)}}$,
i.e.,

9 [3mm]
$x_{i}^{k}=J_{\rho_{i}^{k}\left(A_{i}+D_{i\,(G_{i}z^{k})}\right)}\left(G_{i}z^{k}+\rho_{i}^{k}w_{i}^{k}-\rho_{i}^{k}(B_{i}+C_{i})(G_{i}z^{k})\right)$

10 [3mm]
$y_{i}^{k}=\dfrac{G_{i}z^{k}-x_{i}^{k}}{\rho_{i}^{k}}+w_{i}^{k}+\left[B_{i}(x_{i}^{k})-B_{i}(G_{i}z^{k})\right]+\left[D_{i}(x_{i}^{k})-D_{i\,(G_{i}z^{k})}(x_{i}^{k})\right]$

11 [3mm] $\underline{\theta}\leq
4\,\ell_{i}^{2}(\rho_{i}^{k})^{2}+\left(\beta_{i}^{-1}+\hat{\delta}\right)\rho_{i}^{k}+\left(m_{i}\rho_{i}^{k}\|{x_{i}^{k}-G_{i}z^{k}}\|\right)^{2}\leq\overline{\theta}$

12

13 else

14 Choose $\rho_{i}^{k}>0$

15 [3mm]
$x_{i}^{k}=J_{\rho_{i}^{k}A_{i}}\left(G_{i}z^{k}+\rho_{i}^{k}w_{i}^{k}-\rho_{i}^{k}(B_{i}+C_{i})(G_{i}z^{k})\right)$

16 [3mm]
$y_{i}^{k}=\dfrac{G_{i}z^{k}-x_{i}^{k}}{\rho_{i}^{k}}+w_{i}^{k}+\left[B_{i}(x_{i}^{k})-B_{i}(G_{i}z^{k})\right]$

17

18 end if

19

20 end if

21 $u_{i}^{k}=x_{i}^{k}-G_{i}x_{n}^{k}$

22

23 end for

24 $v^{k}=\sum_{i=1}^{n-1}\,G_{i}^{*}y_{i}^{k}+y_{n}^{k}$

25 [3mm] $\varphi_{k}=\langle z^{k}\,|\,v^{k}\rangle+\sum_{i=1}^{n-1}\,\langle
w_{i}^{k}\,|\,u_{i}^{k}\rangle-\sum_{i=1}^{n}\,\left[\langle
x_{i}^{k}\,|\,y_{i}^{k}\rangle+\dfrac{1}{4\beta_{i}}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}\right]$

26 [3mm]
$\pi_{k}=\gamma^{-1}\|{v^{k}}\|^{2}+\sum_{i=1}^{n-1}\|{u_{i}^{k}}\|^{2}$

27 [3mm] if  _$\varphi_{k} >0$_ then

28 Choose $\tau_{k}\in[\underline{\tau},\overline{\tau}]$

29 [3mm] $\alpha_{k}=\tau_{k}\dfrac{\varphi_{k}}{\pi_{k}}$

30 [3mm] $z^{k+1}=z^{k}-\gamma^{-1}\alpha_{k}v^{k}$

31 [3mm] for  _$i=1,\dots,n-1$_ do

32 $w_{i}^{k+1}=w_{i}^{k}-\alpha_{k}u_{i}^{k}$

33

34 end for

35

36 else

37 $z^{k+1}=z^{k}$

38 [3mm] for  _$i=1,\dots,n-1$_ do

39 $w_{i}^{k+1}=w_{i}^{k}$

40

41 end for

42

43 end if

44 $w_{n}^{k+1}=-\sum_{i=1}^{n-1}\,G_{i}^{*}w_{i}^{k+1}$

45

46 end for

Algorithm 2 Projective splitting with backward, half-forward and proximal-
Newton steps for solving problem (9)

Next we make some remarks regarding Algorithm 2:

  * (i)

If one is lucky enough to find $(G_{i}z^{k},w_{i}^{k})$ in the graph of
$T_{i}$, as in line 2, then one simply set $x_{i}^{k}$ and $y_{i}^{k}$ as
$G_{i}z^{k}$ and $w_{i}^{k}$, respectively, and keep $\rho_{i}^{k}$ equal to
the constant $\hat{\rho}>0$.

  * (ii)

Note that if $i\in\mathcal{I}_{\mathcal{D}}$ we may need a
bracketing/bisection procedure to find a triple
$(\rho_{i}^{k},x_{i}^{k},y_{i}^{k})$ satisfying the conditions in lines
(2)-(2). As we will prove in Section 5, the bracketing/bisection procedure
(Algorithm 3) terminates after a finite number of steps - see Proposition 5.8.
On the other hand, if $i\notin\mathcal{I}_{\mathcal{D}}$, in which case
$D_{i}=0$, no bracketing/bisection procedure is required, and the computation
of $(\rho_{i}^{k},x_{i}^{k},y_{i}^{k})$ will depend only on the evaluation of
$J_{A_{i}}$, $G_{i}$, $B_{i}$ and $C_{i}$ (see lines 2-2). We also mention
that the problem of removing this bracketing/bisection (in the context of
monotone inclusions for a single operator) has been posed as a challenging and
difficult open problem (see, e.g., [21, 36, 42, 43, 44, 52]).

  * (iii)

Now we discuss the computation of resolvent
$J_{\rho(A_{i}+D_{i\;(u)})}:=\left(\rho(A_{i}+D_{i\;(u)})+I\right)^{-1}$, as
in line 2. Note that computing $x^{+}=J_{\rho(A_{i}+D_{i\;(u)})}(y)$ is
equivalent to solving the regularized inclusion problem

$\displaystyle 0\in\rho(A_{i}(x)+D_{i\;(u)}(x))+x-y,$

which, in the setting of the optimization problem (13) (see also (14)), gives
$x^{+}$ as the solution of the following (second-order in $h_{i}$) regularized
model

$\displaystyle\min_{x\in{\mathcal{H}}_{i}}\,\left\\{f_{i}(x)+h_{i}(u)+\langle\nabla
h_{i}(u)\,|\,x-u\rangle+\dfrac{1}{2}\langle\nabla^{2}h_{i}(u)(x-u)\,|\,x-u\rangle+\dfrac{1}{2\rho}\|{x-y}\|^{2}\right\\}.$
(17)

Hence, in the optimization setting (13), the execution of Algorithm 2 will be,
in particular, supported on the assumption that one knows how to solve (17)
efficiently, for any given $y,u\in{\mathcal{H}}_{i}$ and $\rho>0$.

More precisely, still in the optimization setting, $x_{i}^{k}$ as in line 2 is
given as

$\displaystyle
x_{i}^{k}=\mbox{arg}\min_{x\in{\mathcal{H}}_{i}}\,\Bigg{\\{}f_{i}(x)+h_{i}(G_{i}z^{k})+\langle\nabla
h_{i}(G_{i}z^{k})\,|\,x-G_{i}z^{k}\rangle+$
$\displaystyle\dfrac{1}{2}\langle\nabla^{2}h_{i}(G_{i}z^{k})(x-G_{i}z^{k})\,|\,x-G_{i}z^{k}\rangle+\dfrac{1}{2\rho_{i}^{k}}\left\|x-\left[G_{i}z^{k}+\rho_{i}^{k}w_{i}^{k}-\rho_{i}^{k}(B_{i}+C_{i})(G_{i}z^{k})\right]\right\|^{2}\Bigg{\\}},$
(18)

which, if $\mathcal{I}_{\mathcal{D}}\neq\emptyset$, represents the
computational burden of Algorithm 2. In this case, $y_{i}^{k}$ in line 2 is
given explicitly as (recall that $B_{i}=0$; see (14)):

$\displaystyle
y_{i}^{k}=\dfrac{G_{i}z^{k}-x_{i}^{k}}{\rho_{i}^{k}}+w_{i}^{k}+\left[\nabla
h_{i}(x_{i}^{k})-\nabla
h_{i}(G_{i}z^{k})-\nabla^{2}h_{i}(G_{i}z^{k})(x_{i}^{k}-G_{i}z^{k})\right].$

Note that problem ((iii)) can be solved by first-order methods, for example,
under the standard assumption that the proximal operator $(\lambda\partial
f_{i}+I)^{-1}$ of each $f_{i}$ ($1\leq i\leq n$) can be efficiently computed
(see, e.g., [25, 52]).

  * (iv)

The condition in line 2, namely

$\underline{\theta}\leq
4\,\ell_{i}^{2}(\rho_{i}^{k})^{2}+\left(\beta_{i}^{-1}+\hat{\delta}\right)\rho_{i}^{k}+\left(m_{i}\rho_{i}^{k}\|{x_{i}^{k}-G_{i}z^{k}}\|\right)^{2}\leq\overline{\theta},$

will be important in the proof of Proposition 4.5 below (see Eq. (39)).

  * (v)

If $\mathcal{I}_{\mathcal{D}}=\emptyset$, that is, if there is no
differentiable components $D_{i}$ ($1\leq i\leq n$) in (9), then it follows
that Algorithm 2 is closely related to the main algorithms in [20, 39, 40]. On
the other hand, as we have already discussed, none of these works have
considered the framework given by problem (9), under the Assumptions (A1)-(A7)
above (see also Assumption (A8) below).

##  4 Convergence analysis of Algorithm 2

The main result in this section is Theorem 4.7 on the weak convergence of
Algorithm 2. The main result in Proposition 4.2 is given in item (e), which
says that Algorithm 2 is a special instance of the separator-projection
framework given in Algorithm 1. Next, under the additional Assumption (A8) -
see (26) below- on the proximal parameters $\rho_{i}^{k}$ ($1\leq i\leq n$) we
prove, in Lemma 4.3, several results on the boundedness of some of the
sequences evolved by Algorithm 2. Lemma 4.4 is an auxiliary result and
Proposition 4.5 will be useful while proving our main theorem in this section,
namely Theorem 4.7. Lemma 4.6 yields a boundedness result on the gradients of
the sequence of separators $\varphi_{k}(\cdot)$ \- see (21) - and some
asymptotic results involving the sequences $(x_{i}^{k})$, $(y_{i}^{k})$ and
$(w_{i}^{k})$ ($1\leq i\leq n$).

We begin with the following technical lemma, which will be useful in the
proofs of Proposition 4.2 and Theorem 4.7.

######  Lemma 4.1.

Let $(x_{i}^{k})$, $(y_{i}^{k})$ _(_ $i=1,\dots,n$_)_ and $(z^{k})$ be
generated by _Algorithm 2_. For any $(r_{i},a_{i})\in\emph{Gr}(A_{i})$,
$i=1,\dots,n$, we have

$\displaystyle\langle
r_{i}-x_{i}^{k}\,|\,y_{i}^{k}-(B_{i}+C_{i}+D_{i})(r_{i})-a_{i}\rangle\leq\dfrac{1}{4\beta_{i}}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}\qquad(i=1,\dots,n).$
(19)

###### Proof.

First note that if $(x_{i}^{k},y_{i}^{k})$ is as in line 2 of Algorithm 2,
then we obtain that the right-hand side of (19) is equal to zero and that the
inclusion $y_{i}^{k}\in(A_{i}+B_{i}+C_{i}+D_{i})(x_{i}^{k})$ hold. The latter
combined with the inclusion $a_{i}\in A_{i}(r_{i})$ and the monotonicity of
$A_{i}+B_{i}+C_{i}+D_{i}$ yields the desired inequality in (19) (since the
right-hand side of (19), in this case, is zero).

Assume now that $(\rho_{i}^{k},x_{i}^{k},y_{i}^{k})$ is as in lines 2-2 (resp.
2-2) of Algorithm 2. From lines 2 and 2 (resp. 2 and 2), the definition of
$J_{\rho_{i}^{k}\left(A_{i}+D_{i\,(G_{i}z^{k})}\right)}$ (resp.
$J_{\rho_{i}^{k}A_{i}}$) and some simple algebra we find
$y_{i}^{k}-(B_{i}+D_{i})(x_{i}^{k})-C_{i}(G_{i}z^{k})\in A_{i}(x_{i}^{k})$ (By
Assumption (A7) in Section 3, we have $D_{i}=0$ whenever
$i\notin\mathcal{I}_{\mathcal{D}}$.), i.e.,

$\displaystyle(x_{i}^{k},y_{i}^{k}-(B_{i}+D_{i})(x_{i}^{k})-C_{i}(G_{i}z^{k}))\in\mbox{Gr}(A_{i}),$

which, in turn, when combined with the assumption that
$(r_{i},a_{i})\in\mbox{Gr}(A_{i})$ and the monotonicity of $A_{i}$ yields

$\displaystyle\langle
r_{i}-x_{i}^{k}\,|\,y_{i}^{k}-(B_{i}+D_{i})(x_{i}^{k})-C_{i}(G_{i}z^{k})-a_{i}\rangle\leq
0.$

The latter inequality combined with the monotonicity of $B_{i}+D_{i}$ gives

$\displaystyle\langle
r_{i}-x_{i}^{k}\,|\,y_{i}^{k}-(B_{i}+C_{i}+D_{i})(r_{i})-a_{i}\rangle$
$\displaystyle=\langle
r_{i}-x_{i}^{k}\,|\,y_{i}^{k}-(B_{i}+D_{i})(x_{i}^{k})-C_{i}(G_{i}z^{k})-a_{i}\rangle$
$\displaystyle\hskip 28.45274pt+\langle
r_{i}-x_{i}^{k}\,|\,(B_{i}+D_{i})(x_{i}^{k})-(B_{i}+D_{i})(r_{i})\rangle$
$\displaystyle\hskip 28.45274pt+\langle
r_{i}-x_{i}^{k}\,|\,C_{i}(G_{i}z^{k})-C_{i}(r_{i})\rangle$
$\displaystyle\leq\langle
r_{i}-x_{i}^{k}\,|\,C_{i}(G_{i}z^{k})-C_{i}(r_{i})\rangle.$ (20)

If $\beta_{i}<\infty$, using Assumption (A4), the Cauchy-Schwarz inequality
and some algebraic manipulations, we obtain

$\displaystyle\langle
r_{i}-x_{i}^{k}\,|\,C_{i}(G_{i}z^{k})-C_{i}(r_{i})\rangle$
$\displaystyle=\langle
r_{i}-G_{i}z^{k}\,|\,C_{i}(G_{i}z^{k})-C_{i}(r_{i})\rangle+\langle
G_{i}z^{k}-x_{i}^{k}\,|\,C_{i}(G_{i}z^{k})-C_{i}(r_{i})\rangle$
$\displaystyle\leq-\beta_{i}\|{C_{i}(G_{i}z^{k})-C_{i}(r_{i})}\|^{2}+\|{x_{i}^{k}-G_{i}z^{k}}\|\|{C_{i}(G_{i}z^{k})-C_{i}(r_{i})}\|,$

which combined with (20) and the fact that the maximum of the quadratic real
function $t\mapsto-\beta_{i}t^{2}+\|{G_{i}z^{k}-x_{i}^{k}}\|\,t$ is
$\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}/(4\beta_{i})$ yields exactly (19).

On the other hand, if $\beta_{i}=\infty$, then using the conventions
$r\cdot\infty=\infty$ if $r>0$ and $1/\infty=0$ (see “General notation” in
Section 1) and (11) with $x=G_{i}z^{k}$ and $y=r_{i}$, we obtain
$C_{i}(G_{i}z^{k})=C_{i}(r_{i})$. Hence, from (20),

$\displaystyle\langle
r_{i}-x_{i}^{k}\,|\,y_{i}^{k}-(B_{i}+C_{i}+D_{i})(r_{i})-a_{i}\rangle\leq
0=\dfrac{1}{4\beta_{i}}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2},$

which finishes the proof of the lemma. ∎

Consider now the sequences evolved by Algorithm 2 and define
$\varphi_{k}:\bm{{\mathcal{H}}}\to\mathbb{R}$ by

$\displaystyle\varphi_{k}(\underbrace{z,w_{1},\dots,w_{n-1}}_{p})=\langle
z\,|\,v^{k}\rangle+\sum_{i=1}^{n-1}\,\langle
w_{i}\,|\,u_{i}^{k}\rangle-\sum_{i=1}^{n}\,\left[\langle
x_{i}^{k}\,|\,y_{i}^{k}\rangle+\dfrac{1}{4\beta_{i}}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}\right].$
(21)

Define also $(p^{k})$ by

$\displaystyle p^{k}=(z^{k},w_{1}^{k},\dots,w_{n-1}^{k}),\qquad\forall k\geq
0.$ (22)

Next we prove, in particular, that Algorithm 2 is a special instance of
Algorithm 1.

######  Proposition 4.2.

Let $\varphi_{k}(\cdot)$ and $p^{k}$ be as (21) and (22), respectively, and
let the nonempty closed and convex set $\mathcal{S}$ be as in (16). The
following holds for all $k\geq 0$:

  * _(a)_

We have

$\displaystyle\nabla\varphi_{k}=\left(\gamma^{-1}v^{k},u_{1}^{k},u_{2}^{k},\dots,u_{n-1}^{k}\right)\;\;\mbox{and}\;\;\|{\nabla\varphi_{k}}\|_{\gamma}^{2}=\pi_{k}$
(23)

where $\nabla\varphi_{k}$ is taken with respect to the inner product
$\langle\cdot\,|\,\cdot\rangle_{\gamma}$ as in (5).

  * _(b)_

For all $p\in\bm{{\mathcal{H}}}$,

$\displaystyle\varphi_{k}(p)=\sum_{i=1}^{n}\,\left[\langle
G_{i}z-x_{i}^{k}\,|\,y_{i}^{k}-w_{i}\rangle-\dfrac{1}{4\beta_{i}}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}\right],$
(24)

where $w_{n}$ is as in (6).

  * _(c)_

$\varphi_{k}(\cdot)$ is an affine function in $\bm{{\mathcal{H}}}$ and
$\mathcal{S}\subset\\{p\in\bm{{\mathcal{H}}}\;|\;\varphi_{k}(p)\leq 0\\}$.

  * _(d)_

We have

$\displaystyle
p^{k+1}=p^{k}-\tau_{k}\dfrac{\varphi_{k}(p^{k})}{\|{\nabla\varphi_{k}}\|_{\gamma}^{2}}\nabla\varphi_{k}\;\;\;\mbox{if}\;\;\;\varphi_{k}(p^{k})>0\;\;\;\mbox{else}\;\;\;p^{k+1}=p^{k}.$
(25)

  * _(e)_

_Algorithm 2_ is a special instance of _Algorithm 1_ for finding a point in
$\mathcal{S}$ as in (16).

  * _(f)_

The sequences $(z^{k})$ and $(w_{i}^{k})$ _(_ $i=1,\dots,n$_)_ are bounded.

###### Proof.

(a) This follows directly from (21), lines 2–2 of Algorithm 2 and the
definitions of $\langle\cdot\,|\,\cdot\rangle_{\gamma}$ and
$\|\cdot\|_{\gamma}$ in (5).

(b) This follows from (21), lines 2 and 2 of Algorithm 2, (6) and some simple
algebraic manipulations.

(c) The fact that $\varphi_{k}(\cdot)$ is affine also follows directly from
(21). To finish the proof of (c), take any
$p=(z,w_{1},\dots,w_{n-1})\in\mathcal{S}$ and let $w_{n}$ be as in (6). From
the inclusions in the definition of $\mathcal{S}$ we obtain
$w_{i}-(B_{i}+C_{i}+D_{i})(G_{i}z)\in A_{i}(G_{i}z)$ ($i=1,\dots,n$). Hence,
using Lemma 4.1 with
$(r_{i},a_{i})=(G_{i}z,w_{i}-(B_{i}+C_{i}+D_{i})(G_{i}z))$ ($i=1,\dots,n$) we
find

$\displaystyle\langle
G_{i}z-x_{i}^{k}\,|\,y_{i}^{k}-w_{i}\rangle-\dfrac{1}{4\beta_{i}}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}\leq
0\qquad(i=1,\dots,n).$

The fact that $\varphi_{k}(p)\leq 0$ for all $p\in\mathcal{S}$ now follows by
adding the above inequalities from $i=1$ to $i=n$ and using (24).

(d) Using (21), (22), (23) and lines 2, 2, 2, 2, 2 and 2 of Algorithm 2 we
obtain (25).

(e) This follows from items (c), (d) and Algorithm 1’s definition.

(f) This is a consequence of item (e), Lemma 2.1(a), (22) and (6). ∎

From now on we also assume the following regarding the parameter
$\rho_{i}^{k}>0$ as in line 2 of Algorithm 2:

  * (A8)

For $i\in\\{1,\dots,n\\}\backslash\mathcal{I}_{\mathcal{D}}$,

$\displaystyle
0<\underline{\rho}_{\,i}\leq\rho_{i}^{k}\leq\overline{\rho}_{i}<\dfrac{1}{\dfrac{1}{4\beta_{i}}+\ell_{i}}\qquad\forall
k\geq 0,$ (26)

where $\ell_{i}\in[0,\infty)$ and $\beta_{i}\in(0,\infty]$ are as in
Assumptions (A3) and (A4), respectively.

######  Lemma 4.3.

Let $(x_{i}^{k})$, $(y_{i}^{k})$ and $(\rho_{i}^{k})$ _(_ $1\leq i\leq n$_)_
be generated by _Algorithm 2_. The following holds for $i=1,\dots,n$:

  * _(a)_

The sequence $(\rho_{i}^{k})$ is bounded.

  * _(b)_

The sequence $(x_{i}^{k})$ is bounded.

  * _(c)_

There exist $\rho_{\emph{min}},\rho_{\emph{max}}>0$ such that
$0<\rho_{\emph{min}}\leq\rho_{i}^{k}\leq\rho_{\emph{max}}<\infty$ $\forall
k\geq 0$.

  * _(d)_

The sequence $(y_{i}^{k})$ is bounded.

###### Proof.

(a) If $(\rho_{i}^{k},x_{i}^{k},y_{i}^{k})$ is as in line 2 of Algorithm 2,
then $\rho_{i}^{k}=\hat{\rho}$. On the other hand, if
$(\rho_{i}^{k},x_{i}^{k},y_{i}^{k})$ is as in lines 2–2, then using the second
inequality in line 2 we obtain,
$\rho_{i}^{k}\leq\overline{\theta}/\hat{\delta}$. Now, if
$i\in\\{1,\dots,n\\}\backslash\mathcal{I}_{\mathcal{D}}$, then it follows from
(26) that $\rho_{i}^{k}\leq\overline{\rho}:=\max\,\overline{\rho}_{i}$.
Altogether, we proved that, for $i=1,\dots,n$,

$\displaystyle
0<\rho_{i}^{k}\leq\rho_{\mbox{max}}:=\max\left\\{\hat{\rho},\dfrac{\overline{\theta}}{\hat{\delta}},\overline{\rho}\right\\}\qquad\forall
k\geq 0.$ (27)

(b) Take $i\in\\{1,\dots,n\\}$ and let $u^{k}:=G_{i}z^{k}$ and
$s^{k}:=G_{i}z^{k}+\rho_{i}^{k}w_{i}^{k}-\rho_{i}^{k}(B_{i}+C_{i})(G_{i}z^{k})$.
From Proposition 4.2(f), the (Lipschitz) continuity of $B_{i}$, $C_{i}$ and
$G_{i}$, and (27) we obtain that $(u^{k})$ and $(s^{k})$ are bounded
sequences. Using item (a), Lemma 2.4 with
$(T,{\mathcal{H}},D,m):=(A_{i},{\mathcal{H}}_{i},D_{i},m_{i})$ and $(u^{k})$
and $(s^{k})$ as above, we conclude that $(x_{i}^{k})$ as in line 2 of
Algorithm 2 is bounded. On the other hand, using item (a) and Lemma 2.4 with
$(T,{\mathcal{H}},D,m):=(A_{i},{\mathcal{H}}_{i},0,0)$, we find that
$(x_{i}^{k})$ as in line 2 of Algorithm 2 is bounded as well. Moreover,
$(x_{i}^{k})$ as in line 2 of Algorithm 2 is trivially bounded by Proposition
4.2(f) and the boundedness of $G_{i}$.

(c) By (27), it remains to prove that there exists $\rho_{\mbox{min}}>0$ such
that $\rho_{i}^{k}\geq\rho_{\mbox{min}}>0$ ($i=1,\dots,n$) for all $k\geq 0$.
If $i\in\\{1,\dots,n\\}\backslash\mathcal{I}_{\mathcal{D}}$, then it follows
from (26) that
$\rho_{i}^{k}\geq\underline{\rho}:=\min\,\underline{\rho}_{\,i}>0$ for all
$k\geq 0$. If $(\rho_{i}^{k},x_{i}^{k},y_{i}^{k})$ is as in line 2 of
Algorithm 2, then $\rho_{i}^{k}=\hat{\rho}$. For
$(\rho_{i}^{k},x_{i}^{k},y_{i}^{k})$ is as in lines 2–2, let
$c_{i}^{2}:=m_{i}^{2}\,\sup_{k}\,\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}$ and note that
from the first inequality in line 2 we obtain
$(4\ell_{i}^{2}+c_{i}^{2})(\rho_{i}^{k})^{2}+\left(\beta_{i}^{-1}+\hat{\delta}\right)\rho_{i}^{k}-\underline{\theta}\geq
0$, which gives $\rho_{i}^{k}\geq
2\underline{\theta}/\Big{(}\beta_{i}^{-1}+\hat{\delta}+\sqrt{(\beta_{i}^{-1}+\hat{\delta})^{2}+4(4\ell_{i}^{2}+c_{i}^{2})\underline{\theta}}\;\Big{)}$.
Altogether, we proved that, for $k\geq 0$,

$\displaystyle\rho_{i}^{k}\geq\rho_{\mbox{min}}:=\min\left\\{\underline{\rho},\hat{\rho},\dfrac{2\underline{\theta}}{\max\left\\{\beta_{i}^{-1}+\hat{\delta}+\sqrt{(\beta_{i}^{-1}+\hat{\delta})^{2}+4(4\ell_{i}^{2}+c_{i}^{2})\underline{\theta}}\right\\}_{i\in\mathcal{I}_{\mathcal{D}}}}\right\\}>0,$
(28)

which yields the desired lower bound on the sequence $(\rho_{i}^{k})$
($i=1,\cdots,n$).

(d) The boundedness of $(y_{i}^{k})$ (see lines 2, 2 and 2 of Algorithm 2)
follows from Proposition 4.2(f), items (b) and (c) above, the (Lipschitz)
continuity of $G_{i}$, $B_{i}$ and Lemma 2.3. ∎

######  Lemma 4.4.

Consider the sequences evolved by _Algorithm 2_. For
$i\in\\{1,\dots,n\\}\backslash\mathcal{I}_{\mathcal{D}}$,

$\displaystyle(1-\rho_{i}^{k}\ell_{i})\|{x_{i}^{k}-G_{i}z^{k}}\|\leq\|{\rho_{i}^{k}(y_{i}^{k}-w_{i}^{k})}\|\leq(1+\rho_{i}^{k}\ell_{i})\|{x_{i}^{k}-G_{i}z^{k}}\|.$
(29)

###### Proof.

First note that if $(\rho_{i}^{k},x_{i}^{k},y_{i}^{k})$ is as in line 2 of
Algorithm 2, then (29) holds trivially. On the other hand, using line 2 of
Algorithm 2 and Assumption (A3), we find

$\displaystyle\|{x_{i}^{k}-G_{i}z^{k}+\rho_{i}^{k}(y_{i}^{k}-w_{i}^{k})}\|$
$\displaystyle=\|{\rho_{i}^{k}(B_{i}(x_{i}^{k})-B_{i}(G_{i}z^{k}))}\|$
$\displaystyle\leq\rho_{i}^{k}\ell_{i}\|{x_{i}^{k}-G_{i}z^{k}}\|,$ (30)

which after using the triangle inequality and some algebraic manipulations
gives the desired result. ∎

Next proposition will be important in the convergence proof of Algorithm 2.

######  Proposition 4.5.

Consider the sequences evolved by _Algorithm 2_, let $\varphi_{k}(\cdot)$ and
$p^{k}$ be as in (21) and (22), respectively, let
$\rho_{\emph{min}},\rho_{\emph{max}}>0$ be as in _Lemma 4.3(c)_ and let
$\underline{\rho}:=\min\,\underline{\rho}_{\,i}$ and
$\overline{\rho}:=\max\,\overline{\rho}_{\,i}$, where
$\underline{\rho}_{\,i},\overline{\rho}_{\,i}>0$ _(_ $1\leq i\leq n$_)_ are as
in (26). Define, for $i=1,\dots,n$,

$\displaystyle\Delta_{i}^{k}:=\langle
G_{i}z^{k}-x_{i}^{k}\,|\,y_{i}^{k}-w_{i}^{k}\rangle-\dfrac{1}{4\beta_{i}}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}.$
(31)

The following holds:

  * _(a)_

For $i\in\\{1,\dots,n\\}\backslash\mathcal{I}_{\mathcal{D}}$,

$\displaystyle\Delta_{i}^{k}\geq\dfrac{1}{2}\left[\dfrac{1}{\overline{\rho}}-\left(\dfrac{1}{4\beta_{i}}+\ell_{i}\right)\right]\left(\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}+\left(\dfrac{\underline{\rho}}{1+\overline{\rho}\ell_{i}}\right)^{2}\|{y_{i}^{k}-w_{i}^{k}}\|^{2}\right)\quad\forall
k\geq 0.$ (32)

  * _(b)_

For $i\in\mathcal{I}_{\mathcal{D}}$,

$\displaystyle\Delta_{i}^{k}\geq\dfrac{(2-\overline{\theta})}{4\rho_{\emph{max}}}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}+\dfrac{\rho_{\emph{min}}}{2}\|{y_{i}^{k}-w_{i}^{k}}\|^{2}\qquad\forall
k\geq 0,$ (33)

where $0<\overline{\theta}<2$ is as in the input of Algorithm 2.

  * _(c)_

There exist $c_{1},c_{2}>0$ such that, for $i=1,\dots,n$,

$\displaystyle\Delta_{i}^{k}\geq
c_{1}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}+c_{2}\|{y_{i}^{k}-w_{i}^{k}}\|^{2}\qquad\forall
k\geq 0.$ (34)

  * _(d)_

There exists $c>0$ such that

$\displaystyle\varphi_{k}(p^{k})\geq
c\sum_{i=1}^{n}\,\left[\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}+\|{y_{i}^{k}-w_{i}^{k}}\|^{2}\right]\qquad\forall
k\geq 0.$ (35)

###### Proof.

First note that from the identity $\langle
a\,|\,b\rangle=(1/2)(\|{a+b}\|^{2}-\|{a}\|^{2}-\|{b}\|^{2})$ we find

$\displaystyle\langle\underbrace{x_{i}^{k}-G_{i}z^{k}}_{a}\,|\,\underbrace{\rho_{i}^{k}(y_{i}^{k}-w_{i}^{k})}_{b}\rangle+\dfrac{\rho_{i}^{k}}{4\beta_{i}}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}$
$\displaystyle=\dfrac{1}{2}\|{x_{i}^{k}-G_{i}z^{k}+\rho_{i}^{k}(y_{i}^{k}-w_{i}^{k})}\|^{2}$
$\displaystyle\hskip
2.84544pt+\left(\dfrac{\rho_{i}^{k}}{4\beta_{i}}-\dfrac{1}{2}\right)\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}-\dfrac{1}{2}\|{\rho_{i}^{k}(y_{i}^{k}-w_{i}^{k})}\|^{2}.$
(36)

(a) If $(\rho_{i}^{k},x_{i}^{k},y_{i}^{k})$ is as in line 2 of Algorithm 2,
then the result is trivial. Take
$i\in\\{1,\dots,n\\}\backslash\mathcal{I}_{\mathcal{D}}$. From line 2 of
Algorithm 2, (31), (36), Assumption (A3) and the first inequality in (29),

$\displaystyle-\rho_{i}^{k}\Delta_{i}^{k}$
$\displaystyle=\dfrac{1}{2}\|{\rho_{i}^{k}[B_{i}(x_{i}^{k})-B_{i}(G_{i}z^{k})]}\|^{2}+\left(\dfrac{\rho_{i}^{k}}{4\beta_{i}}-\dfrac{1}{2}\right)\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}-\dfrac{1}{2}\|{\rho_{i}^{k}(y_{i}^{k}-w_{i}^{k})}\|^{2}$
$\displaystyle\leq\left[\dfrac{(\rho_{i}^{k}\ell_{i})^{2}}{2}+\left(\dfrac{\rho_{i}^{k}}{4\beta_{i}}-\dfrac{1}{2}\right)\right]\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}-\dfrac{1}{2}\|{\rho_{i}^{k}(y_{i}^{k}-w_{i}^{k})}\|^{2}\qquad\mbox{[by
Assumption (A3)]}$
$\displaystyle\leq\left[\dfrac{(\rho_{i}^{k}\ell_{i})^{2}}{2}+\left(\dfrac{\rho_{i}^{k}}{4\beta_{i}}-\dfrac{1}{2}\right)\right]\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}-\dfrac{(1-\rho_{i}^{k}\ell_{i})^{2}}{2}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}\qquad\mbox{[by
\eqref{eq:conway} and \eqref{eq:carmo}]}$
$\displaystyle=\left[\rho_{i}^{k}\left(\dfrac{1}{4\beta_{i}}+\ell_{i}\right)-1\right]\|{x_{i}^{k}-G_{i}z^{k}}\|^{2},$

which in turn (after division by $-\rho_{i}^{k}$) yields

$\displaystyle\Delta_{i}^{k}$
$\displaystyle\geq\left[\dfrac{1}{\rho_{i}^{k}}-\left(\dfrac{1}{4\beta_{i}}+\ell_{i}\right)\right]\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}$
$\displaystyle\geq\left[\dfrac{1}{\overline{\rho}}-\left(\dfrac{1}{4\beta_{i}}+\ell_{i}\right)\right]\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}.$
(37)

On the other hand, using Assumption (A8), (37) combined with the second
inequality in (29) gives

$\displaystyle\Delta_{i}^{k}\geq\left[\dfrac{1}{\overline{\rho}}-\left(\dfrac{1}{4\beta_{i}}+\ell_{i}\right)\right]\left(\dfrac{\underline{\rho}}{1+\overline{\rho}\ell_{i}}\right)^{2}\|{y_{i}^{k}-w_{i}^{k}}\|^{2}.$
(38)

Note now that (32) follows by adding the inequalities in (37) and (38).

(b) Note first that if $(\rho_{i}^{k},x_{i}^{k},y_{i}^{k})$ is as in line 2,
then, in particular, $x_{i}^{k}=G_{i}z^{k}$ and $y_{i}^{k}=w_{i}^{k}$, which
gives that (33) follows trivially from (31) (in this case, both sides of (33)
are equal to zero). In what follows in this proof we assume that
$(\rho_{i}^{k},x_{i}^{k},y_{i}^{k})$ is as in lines 2–2 of Algorithm 2.

Note that using line 2 of Algorithm 2, the inequality
$\dfrac{1}{2}\|{a+b}\|^{2}\leq\|{a}\|^{2}+\|{b}\|^{2}$, Assumptions (A3) and
(A5), and Lemma 2.3 we obtain

$\displaystyle\dfrac{1}{2}\|{x_{i}^{k}-G_{i}z^{k}+\rho_{i}^{k}(y_{i}^{k}-w_{i}^{k})}\|^{2}$
$\displaystyle=\dfrac{1}{2}(\rho_{i}^{k})^{2}\|[B_{i}(x_{i}^{k})-B_{i}(G_{i}z^{k})]+[D_{i}(x_{i}^{k})-D_{i\,(G_{i}z^{k})}(x_{i}^{k})]\|^{2}$
$\displaystyle\leq(\rho_{i}^{k})^{2}\left(\|{B_{i}(x_{i}^{k})-B_{i}(G_{i}z^{k})}\|^{2}+\|{D_{i}(x_{i}^{k})-D_{i\,(G_{i}z^{k})}(x_{i}^{k})}\|^{2}\right)$
$\displaystyle\leq(\rho_{i}^{k})^{2}\left(\ell_{i}^{2}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}+\dfrac{m_{i}^{2}}{4}\|{x_{i}^{k}-G_{i}z^{k}}\|^{4}\right)$
$\displaystyle=\left(\ell_{i}^{2}(\rho_{i}^{k})^{2}+\dfrac{m_{i}^{2}(\rho_{i}^{k})^{2}}{4}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}\right)\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}.$
(39)

From (36), (39), line 2 of Algorithm 2 (discarding the term $\hat{\delta}>0$)
and (31),

$\displaystyle-\rho_{i}^{k}\Delta_{i}^{k}$
$\displaystyle\leq\left[\ell_{i}^{2}(\rho_{i}^{k})^{2}+\dfrac{m_{i}^{2}(\rho_{i}^{k})^{2}}{4}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}+\left(\dfrac{\rho_{i}^{k}}{4\beta_{i}}-\dfrac{1}{2}\right)\right]\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}$
$\displaystyle\hskip
28.45274pt-\dfrac{1}{2}\|{\rho_{i}^{k}(y_{i}^{k}-w_{i}^{k})}\|^{2}$
$\displaystyle=\dfrac{1}{4}\left[4\ell_{i}^{2}(\rho_{i}^{k})^{2}+\beta_{i}^{-1}\rho_{i}^{k}+m_{i}^{2}(\rho_{i}^{k})^{2}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}-2\right]\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}$
$\displaystyle\hskip
28.45274pt-\dfrac{1}{2}\|{\rho_{i}^{k}(y_{i}^{k}-w_{i}^{k})}\|^{2}$
$\displaystyle\leq-\dfrac{2-\overline{\theta}}{4}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}-\dfrac{1}{2}\|{\rho_{i}^{k}(y_{i}^{k}-w_{i}^{k})}\|^{2}.$

The desired result follows by dividing the latter inequality by
$-\rho_{i}^{k}$ and using Lemma 4.3(c).

(c) This follows trivially from items (a) and (b).

(d) This follows from (c), (31) and Proposition 4.2(b). ∎

######  Lemma 4.6.

Consider the sequences evolved by _Algorithm 2_ and let $\varphi_{k}(\cdot)$
and $p^{k}$ be as in (21) and (22), respectively. The following holds:

  * _(a)_

There exists $\xi>0$ such that $\|{\nabla\varphi_{k}}\|_{\gamma}\leq\xi$ for
all $k\geq 0$.

  * _(b)_

$G_{i}z^{k}-x_{i}^{k}\to 0$ and $w_{i}^{k}-y_{i}^{k}\to 0$ _(_
$i=1,\dots,n$_)_.

  * _(c)_

$\sum_{i=1}^{n}\,G_{i}^{*}y_{i}^{k}\to 0$ and $x_{i}^{k}-G_{i}x_{n}^{k}\to 0$
_(_ $i=1,\dots,n-1$_)_.

###### Proof.

(a) From (23), (5) and lines 2–2 of Algorithm 2,

$\displaystyle\|{\nabla\varphi_{k}}\|_{\gamma}^{2}$
$\displaystyle=\gamma^{-1}\|{v^{k}}\|^{2}+\sum_{i=1}^{n-1}\|{u_{i}^{k}}\|^{2}$
$\displaystyle=\gamma^{-1}\left\|\sum_{i=1}^{n}\,G_{i}^{*}y_{i}^{k}\right\|^{2}+\sum_{i=1}^{n-1}\|{x_{i}^{k}-G_{i}x_{n}^{k}}\|^{2}$
$\displaystyle\leq
n\gamma^{-1}\sum_{i=1}^{n}\,\|{G_{i}^{*}}\|^{2}\|{y_{i}^{k}}\|^{2}+2\sum_{i=1}^{n-1}\,\left(\|{x_{i}^{k}}\|^{2}+\|{G_{i}}\|^{2}\|{x_{n}^{k}}\|^{2}\right),$

which combined with Lemma 4.3(items (b) and (d)) yields the desired result.

(b) Using Proposition 4.2(e), item (a) and Lemma 2.1(c) we obtain
$\overline{\lim}\varphi_{k}(p^{k})\leq 0$, which, in turn, combined with
Proposition 4.5(d) yields the desired result.

(c) Using the fact that $\sum_{i=1}^{n}G_{i}^{*}w_{i}^{k}=0$ (see line 2 in
Algorithm 2) we obtain

$\displaystyle\left\|\sum_{i=1}^{n}\,G_{i}^{*}y_{i}^{k}\right\|=\left\|\sum_{i=1}^{n}\,G_{i}^{*}(w_{i}^{k}-y_{i}^{k})\right\|\leq\sum_{i=1}^{n}\,\|{G_{i}^{*}}\|\|{w_{i}^{k}-y_{i}^{k}}\|.$
(40)

Moreover,

$\displaystyle\|{x_{i}^{k}-G_{i}x_{n}^{k}}\|$
$\displaystyle=\|{x_{i}^{k}-G_{i}z^{k}+G_{i}(z^{k}-x_{n}^{k})}\|$
$\displaystyle\leq\|{x_{i}^{k}-G_{i}z^{k}}\|+\|{G_{i}}\|\|{z^{k}-x_{n}^{k}}\|.$
(41)

The desired result now follows form (40), (4), item (b) and the fact that
$G_{n}=I$ (see Assumption (A1)). ∎

######  Theorem 4.7 (Weak convergence of Algorithm 2).

Consider the sequences evolved by _Algorithm 2_, let $\mathcal{S}$ be as in
(16) and assume that Assumptions _(A1)-(A8)_ hold. Let
$p^{k}:=(z^{k},w_{1}^{k},\dots,w_{n-1}^{k})$ and let, for all $k\geq 0$,

$\displaystyle w_{n}^{k}:=-\sum_{i=1}^{n-1}\,G_{i}^{*}w_{i}^{k}.$ (42)

Then $(p^{k})$ converges weakly to some element
$\overline{p}=(\overline{z},\overline{w}_{1},\dots\overline{w}_{n-1})\in\mathcal{S}$,
i.e.,

$\displaystyle
z^{k}\rightharpoonup\overline{z}\;\;\mbox{and}\;\;w_{i}^{k}\rightharpoonup\overline{w}_{i}\quad(i=1,\dots,n),$
(43)

where $\overline{w}_{n}:=-\sum_{i=1}^{n-1}\,G_{i}^{*}\overline{w}_{i}$, and

$\displaystyle\overline{w}_{i}\in
T_{i}(G_{i}\overline{z})\qquad(i=1,\dots,n).$ (44)

Moreover,

$\displaystyle x_{i}^{k}\rightharpoonup
G_{i}\overline{z}\;\;\mbox{and}\;\;y_{i}^{k}\rightharpoonup\overline{w}_{i}\qquad(i=1,\dots,n).$
(45)

###### Proof.

We will apply Proposition 4.2(e) and Lemma 2.1(b). Hence, we have to show that
every weak cluster point of $p^{k}=(z^{k},w_{1}^{k},\dots,w_{n-1}^{k})$
belongs to $\mathcal{S}$. Let
$p^{\infty}=(z^{\infty},w_{1}^{\infty},\dots,w_{n-1}^{\infty})$ be a weak
cluster point of $(p^{k})$ and define

$\displaystyle
w^{\infty}=(w_{1}^{\infty},\dots,w_{n-1}^{\infty})\;\;\mbox{and}\;\;w_{n}^{\infty}=-\sum_{i=1}^{n-1}\,G_{i}^{*}w_{i}^{\infty}.$
(46)

Our goal is to show that $p^{\infty}\in\mathcal{S}$, i.e.,

$\displaystyle w_{i}^{\infty}\in T_{i}(G_{i}z^{\infty})\qquad(i=1,\dots,n).$
(47)

(recall that $G_{n}=I$). To this end, first consider
$R:{\mathcal{H}}_{n}={\mathcal{H}}_{0}\rightrightarrows{\mathcal{H}}_{n}={\mathcal{H}}_{0}$
and
$S:{\mathcal{H}}_{1}\times\dots\times{\mathcal{H}}_{n-1}\rightrightarrows{\mathcal{H}}_{1}\times\dots\times{\mathcal{H}}_{n-1}$
the maximal monotone operators defined as

$\displaystyle R=T_{n}\;\;\mbox{and}\;\;S=T_{1}\times\dots\times T_{n-1}.$
(48)

Consider also the (bounded) linear operator
$G:{\mathcal{H}}_{n}={\mathcal{H}}_{0}\to{\mathcal{H}}_{1}\times\dots\times{\mathcal{H}}_{n-1}$
defined by

$\displaystyle
Gz=(G_{1}z,\dots,G_{n-1}z)\qquad(z\in{\mathcal{H}}_{n}={\mathcal{H}}_{0})$
(49)

and let
$G^{*}:{\mathcal{H}}_{1}\times\dots\times{\mathcal{H}}_{n-1}\to{\mathcal{H}}_{n}={\mathcal{H}}_{0}$,

$\displaystyle
G^{*}(w_{1},\dots,w_{n-1})=\sum_{i=1}^{n-1}\,G_{i}^{*}w_{i}\qquad\left((w_{1},\dots,w_{n-1})\in{\mathcal{H}}_{1}\times\dots\times{\mathcal{H}}_{n-1}\right)$
(50)

be its adjoint operator. In view of (48), (46), (50) and the fact that
$G_{n}=I$, we have that our goal (47) is clearly equivalent to

$\displaystyle-G^{*}w^{\infty}\in R(z^{\infty})\;\;\mbox{and}\;\;w^{\infty}\in
S(Gz^{\infty})\;\;\mbox{i.e.}\;\;(-G^{*}w^{\infty},w^{\infty})\in(R\times
S)(z^{\infty},Gz^{\infty}).$ (51)

Since $R\times S$ is maximal monotone [13], to prove (51) (and hence our goal
(47)) it suffices to show that

$\displaystyle\langle(r,s)-(z^{\infty},Gz^{\infty})\,|\,(u,v)-(-G^{*}w^{\infty},w^{\infty})\rangle\geq
0\qquad\forall(u,v)\in(R\times S)(r,s).$ (52)

Hence, in what follows in this proof, we will focus on proving that (52)
holds. Let us start by proving that

$\displaystyle\langle(r,s)-(r^{k},s^{k})\,|\,(u,v)-(u^{k},v^{k})\rangle+\sum_{i=1}^{n}\,\dfrac{1}{4\beta_{i}}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2}\geq
0\qquad\forall(u,v)\in(R\times S)(r,s),$ (53)

where, for all $k\geq 0$,

$\displaystyle r^{k}:=x_{n}^{k},\quad u^{k}:=y_{n}^{k},\quad
s^{k}:=(x_{1}^{k},\dots,x_{n-1}^{k})\;\;\mbox{and}\;\;v^{k}:=(y_{1}^{k},\dots,y_{n-1}^{k}).$
(54)

To this end, take

$\displaystyle(u,v)\in(R\times S)(r,s),\;\;\mbox{i.e.}\;\;u\in
R(r)\;\;\mbox{and}\;\;v\in S(s),$ (55)

where $r,u\in{\mathcal{H}}_{0}$ and $s:=(s_{1},\dots,s_{n-1})$,
$v:=(v_{1},\dots,v_{n-1})\in{\mathcal{H}}_{1}\times\dots\times{\mathcal{H}}_{n-1}$.
Using the latter definitions and (54) we obtain, for all $k\geq 0$,

$\displaystyle\langle(r,s)-(r^{k},s^{k})\,|\,(u,v)-(u^{k},v^{k})\rangle$
$\displaystyle=\langle r-r^{k}\,|\,u-u^{k}\rangle+\langle
s-s^{k}\,|\,v-v^{k}\rangle$ $\displaystyle=\langle
r-x_{n}^{k}\,|\,u-y_{n}^{k}\rangle+\sum_{i=1}^{n-1}\,\langle
s_{i}-x_{i}^{k}\,|\,v_{i}-y_{i}^{k}\rangle.$ (56)

In view of (55), (48) and the fact that $T_{i}=A_{i}+B_{i}+C_{i}+D_{i}$
($i=1,\dots,n$) we have

$\displaystyle u-B_{n}(r)-C_{n}(r)-D_{n}(r)\in
A_{n}(r)\;\;\mbox{and}\;\;v_{i}-B_{i}(s_{i})-C_{i}(s_{i})-D_{i}(s_{i})\in
A_{i}(s_{i})\quad(i=1,\dots,n-1).$

Hence, using Lemma 4.1 with
$(r_{i},a_{i}):=(s_{i},v_{i}-B_{i}(s_{i})-C_{i}(s_{i})-D_{i}(s_{i}))$
($i=1,\dots,n-1$) and $(r_{n},a_{n}):=(r,u-B_{n}(r)-C_{n}(r)-D_{n}(r))$ and
some simple algebra we find

$\displaystyle\langle
r-x_{n}^{k}\,|\,u-y_{n}^{k}\rangle\geq-\dfrac{1}{4\beta_{n}}\|{x_{n}^{k}-G_{n}z^{k}}\|^{2}\;\;\mbox{and}\;\;\sum_{i=1}^{n-1}\,\langle
s_{i}-x_{i}^{k}\,|\,v_{i}-y_{i}^{k}\rangle\geq-\sum_{i=1}^{n-1}\,\dfrac{1}{4\beta_{i}}\|{x_{i}^{k}-G_{i}z^{k}}\|^{2},$

which, in turn, when combined with (4) yields exactly (53).

Next we will take limit in (53) (up to a subsequence) to prove (52) (and hence
our goal (47)). To this end, let $(p^{k_{j}})$ be a subsequence of
$p^{k}=(z^{k},w_{1}^{k},\dots,w_{n-1}^{k})$ such that
$p^{k_{j}}\rightharpoonup
p^{\infty}=(z^{\infty},w_{1}^{\infty},\dots,w_{n-1}^{\infty})$. (Recall that
$p^{\infty}$ is a weak cluster point of $(p^{k})$.) Using (42) and (46)
combined with the assumption that $p^{k_{j}}\rightharpoonup p^{\infty}$ we
obtain

$\displaystyle z^{k_{j}}\rightharpoonup
z^{\infty}\;\;\;\mbox{and}\;\;\;w_{i}^{k_{j}}\rightharpoonup
w_{i}^{\infty}\qquad(i=1,\dots,n).$ (57)

From Lemma 4.6(b) and the first limit in (57) we obtain
$x_{i}^{k_{j}}-G_{i}z^{k_{j}}\to 0$ and $G_{i}z^{k_{j}}\rightharpoonup
G_{i}z^{\infty}$, respectively, and so

$\displaystyle
x_{i}^{k_{j}}=\left(x_{i}^{k_{j}}-G_{i}z^{k_{j}}\right)+G_{i}z^{k_{j}}\rightharpoonup
G_{i}z^{\infty}\qquad(i=1,\dots,n).$ (58)

Analogously, using now the second limit in (57) and Lemma 4.6(b) again we also
find

$\displaystyle
y_{i}^{k_{j}}=\left(y_{i}^{k_{j}}-w_{i}^{k_{j}}\right)+w_{i}^{k_{j}}\rightharpoonup
w_{i}^{\infty}\qquad(i=1,\dots,n).$ (59)

Using the definitions of $r^{k}$ and $s^{k}$ in (54) combined (58) for $i=n$
and for $i=1,\dots,n-1$ (respectively), the fact that $G_{n}=I$ and (49) we
also find

$\displaystyle r^{k_{j}}\rightharpoonup
z^{\infty}\;\;\mbox{and}\;\;s^{k_{j}}\rightharpoonup
Gz^{\infty}\;\;\mbox{i.e.}\;\;(r^{k_{j}},s^{k_{j}})\rightharpoonup(z^{\infty},Gz^{\infty}).$
(60)

Likewise, using now the definitions of $u^{k}$ and $v^{k}$ in (54) combined
with (59) for $i=n$ and for $i=1,\dots,n-1$ (respectively), (46) and (50) we
obtain

$\displaystyle
u^{k_{j}}\rightharpoonup-G^{*}w^{\infty}\;\;\mbox{and}\;\;v^{k_{j}}\rightharpoonup
w^{\infty}\;\;\mbox{i.e.}\;\;(u^{k_{j}},v^{k_{j}})\rightharpoonup(-G^{*}w^{\infty},w^{\infty}).$
(61)

Note now that, from the definitions of $u^{k}$ and $v^{k}$ in (54), (50) and
the fact that $G_{n}=I$ we have
$u^{k}+G^{*}v^{k}=y_{n}^{k}+\sum_{i=1}^{n-1}\,G_{i}^{*}y_{i}^{k}=\sum_{i=1}^{n}\,G_{i}^{*}y_{i}^{k}$
and so, from Lemma 4.6(c),

$\displaystyle u^{k}+G^{*}v^{k}\to 0.$ (62)

Analogously, from the definitions of $r^{k}$ and $s^{k}$ in (54) and the
definition of $G$ in (49) we also find
$Gr^{k}-s^{k}=(G_{1}x_{n}^{k}-x_{1}^{k},\dots,G_{n-1}x_{n}^{k}-x_{n-1}^{k})$
and so, from Lemma 4.6(c),

$\displaystyle Gr^{k}-s^{k}\to 0.$ (63)

Now consider $V$ the closed linear subspace of $\bm{{\mathcal{H}}}$ defined as
$V=\\{(z,Gz)\,|z\in{\mathcal{H}}_{0}\\}$, i.e, $V$ is the graph of the linear
operator $G$, and let $P=P_{V}$ and $P^{\perp}=P_{V^{\perp}}$ denote the
projection operators onto $V$ and $V^{\perp}$, respectively. From Lemma 2.2 we
know that, for all $(z,w)\in\bm{{\mathcal{H}}}$, with $z\in{\mathcal{H}}_{0}$,

$\displaystyle\begin{aligned}
&P(z,w)=((I+G^{*}G)^{-1}(z+G^{*}w),G(I+G^{*}G)^{-1}(z+G^{*}w)),\\\
&P^{\perp}(z,w)=(G^{*}(I+GG^{*})^{-1}(Gz-w),-(I+GG^{*})^{-1}(Gz-w)).\end{aligned}$
(64)

Hence, using (62), (63) as well as the continuity of $(I+G^{*}G)^{-1}$,
$(I+GG^{*})^{-1}$ and $G^{*}$ we find

$\displaystyle P(u^{k},v^{k})\to 0\;\;\mbox{and}\;\;P^{\perp}(r^{k},s^{k})\to
0.$ (65)

On the other hand, using the fact that $P$ and $P^{\perp}$ are weakly
continuous combined with (60) and (61) we also find

$\displaystyle\begin{aligned} &P(r^{k_{j}},s^{k_{j}})\rightharpoonup
P(z^{\infty},Gz^{\infty})=(z^{\infty},Gz^{\infty}),\\\
&P^{\perp}(u^{k_{j}},v^{k_{j}})\rightharpoonup
P^{\perp}(-G^{*}w^{\infty},w^{\infty})=(-G^{*}w^{\infty},w^{\infty}),\end{aligned}$
(66)

where the latter identities follow from the fact that
$(z^{\infty},Gz^{\infty})\in V$ and $(-G^{*}w^{\infty},w^{\infty})\in
V^{\perp}$.

Now, using the fact that $V$ is orthogonal to $V^{\perp}$ and some algebraic
manipulations we find that the first term in the right-hand side of (53) can
be decomposed as

$\displaystyle\begin{aligned}
\langle(r,s)-(r^{k},s^{k})\,|\,(u,v)-(u^{k},v^{k})\rangle&=\underbrace{\langle
P(r,s)-P(r^{k},s^{k})\,|\,P(u,v)-P(u^{k},v^{k})\rangle}_{=:\mu^{k}}\\\\[5.69054pt]
&+\underbrace{\langle
P^{\perp}(r,s)-P^{\perp}(r^{k},s^{k})\,|\,P^{\perp}(u,v)-P^{\perp}(u^{k},v^{k})\rangle}_{=:\nu^{k}}.\end{aligned}$
(67)

Direct use of (65) with $k=k_{j}$ and (66) yields

$\displaystyle\mu^{k_{j}}\to\langle
P(r,s)-P(z^{\infty},Gz^{\infty})\,|\,P(u,v)\rangle\;\;\mbox{and}\;\;\nu^{k_{j}}\to\langle
P^{\perp}(r,s)\,|\,P^{\perp}(u,v)-P^{\perp}(-G^{*}w^{\infty},w^{\infty})\rangle$

and so

$\displaystyle\mu^{k_{j}}+\nu^{k_{j}}\to\langle
P(r,s)-P(z^{\infty},Gz^{\infty})\,|\,P(u,v)\rangle+\langle
P^{\perp}(r,s)\,|\,P^{\perp}(u,v)-P^{\perp}(-G^{*}w^{\infty},w^{\infty})\rangle=:\eta.$
(68)

On the other hand, using the facts that $V$ is orthogonal to $V^{\perp}$ and
$P+P^{\perp}=I$ we find that the right-hand side of (68) can be written as

$\displaystyle\eta$ $\displaystyle=\langle
P(r,s)-P(z^{\infty},Gz^{\infty})+P^{\perp}(r,s)\,|\,P(u,v)+P^{\perp}(u,v)-P^{\perp}(-G^{*}w^{\infty},w^{\infty})\rangle$
$\displaystyle=\langle(r,s)-P(z^{\infty},Gz^{\infty})\,|\,(u,v)-P^{\perp}(-G^{*}w^{\infty},w^{\infty})\rangle$
$\displaystyle=\langle(r,s)-(z^{\infty},Gz^{\infty})\,|\,(u,v)-(-G^{*}w^{\infty},w^{\infty})\rangle,$

where in the last identity we used that $(z^{\infty},Gz^{\infty})\in V$ and
$(-G^{*}w^{\infty},w^{\infty})\in V^{\perp}$. Hence, from (68),

$\displaystyle\mu^{k_{j}}+\nu^{k_{j}}\to\langle(r,s)-(z^{\infty},Gz^{\infty})\,|\,(u,v)-(-G^{*}w^{\infty},w^{\infty})\rangle.$
(69)

Note now that we obtain (52) as a direct consequence of (53), (67) with
$k=k_{j}$, (69) and Lemma 4.6(b). ∎

##  5 Bracketing/bisection procedure

In this section, we present and justify the bracketing/bisection routine
(Algorithm 3) called in line 2 of Algorithm 2.

Motivation. The main motivation for introducing a bracketing/bisection
procedure in Algorithm 2 is as follows: for each
$i\in\mathcal{I}_{\mathcal{D}}$, at an iteration $k\geq 0$, we may need to
find $\rho_{i}^{k}>0$ and $x_{i}^{k}$ (see lines 2 and 2 of Algorithm 2)
satisfying

$\displaystyle
x_{i}^{k}=J_{\rho_{i}^{k}\left(A_{i}+D_{i\,(G_{i}z^{k})}\right)}\left(G_{i}z^{k}+\rho_{i}^{k}w_{i}^{k}-\rho_{i}^{k}(B_{i}+C_{i})(G_{i}z^{k})\right),$
(70) $\displaystyle\underline{\theta}\leq
4\,\ell_{i}^{2}(\rho_{i}^{k})^{2}+\left(\beta_{i}^{-1}+\hat{\delta}\right)\rho_{i}^{k}+\left(m_{i}\rho_{i}^{k}\|{x_{i}^{k}-G_{i}z^{k}}\|\right)^{2}\leq\overline{\theta}.$
(71)

While the computation of $x_{i}^{k}$ as in (70) follows essentially from the
assumption that the resolvent
$J_{\rho_{i}^{k}\left(A_{i}+D_{i\,(G_{i}z^{k})}\right)}$ is computable, the
requirement of $\rho_{i}^{k}$ and $x_{i}^{k}$ satisfying the coupled system
(70)-(71) makes the task much more challenging.

To begin with, let’s put (70)-(71) in a more general framework. The task then
is (cf. (70)-(71)):

Problem A Let ${\mathcal{H}}$ be a real Hilbert space,
$A:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$ be maximal monotone,
$B:{\mathcal{H}}\to{\mathcal{H}}$ be monotone and $\ell$-Lipschitz continuous,
$C:{\mathcal{H}}\to{\mathcal{H}}$ be $\beta$-cocoercive,
$D:{\mathcal{H}}\to{\mathcal{H}}$ be monotone and continuously differentiable
with an $m$-Lipschitz continuous derivative $D^{\prime}(\cdot)$, and
$G:{\mathcal{H}}\to{\mathcal{H}}$ be a bounded linear operator.

Given $z,w\in{\mathcal{H}}$, find $\rho>0$ and $x\in{\mathcal{H}}$ satisfying

$\displaystyle x=J_{\rho\left(A+D_{(Gz)}\right)}\left(Gz+\rho
w-\rho(B+C)(Gz)\right),$ (72) $\displaystyle\underline{\theta}\leq
4\,\ell^{2}\rho^{2}+\left(\beta^{-1}+\hat{\delta}\right)\rho+(m\rho\|{x-Gz}\|)^{2}\leq\overline{\theta},$
(73)

where $\hat{\delta}>0$, $0<\underline{\theta}<\overline{\theta}$ and
$D_{(Gz)}(x):=D(Gz)+D^{\prime}(Gz)(x-Gz)$, for all $x\in{\mathcal{H}}$.

Next lemma and corollary will be helpful.

######  Lemma 5.1.

Let $A(\cdot)$, $B(\cdot)$, $C(\cdot)$, $D(\cdot)$ and $G(\cdot)$, and
$z,w\in{\mathcal{H}}$ and $\rho>0$, be as described in _Problem A_ above and
define $\widehat{T}:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$ as

$\displaystyle\widehat{T}(x)=A(x)+D_{(Gz)}(x)+(B+C)(Gz)-w,\qquad\forall
x\in{\mathcal{H}}.$ (74)

The following holds:

  * _(a)_

$\widehat{T}$ is maximal monotone.

  * _(b)_

$0\in\widehat{T}(Gz)$ if and only if $w\in(A+B+C+D)(Gz)$.

  * _(c)_

$J_{\rho\widehat{T}}(Gz)=J_{\rho(A+D_{(Gz)})}(Gz+\rho w-\rho(B+C)(Gz))$.

###### Proof.

(a) The result follows from the definition of $\widehat{T}$ as in (74) and the
maximality of the sum of maximal monotone operators [55] (see also [13]).

(b) This follows trivially from (74) and (4).

(c) This is a direct consequence of (74) and the definition of resolvents of
$\widehat{T}$ and $A+D_{(Gz)}$. ∎

######  Corollary 5.2.

Let the maximal monotone operator $\widehat{T}$ be as in (74). For
$z,w\in{\mathcal{H}}$, we have that $\rho>0$ and $x\in{\mathcal{H}}$ solve
_Problem A_ , i.e., they satisfy (72)-(73) if and only if

$\displaystyle\underline{\theta}\leq
4\,\ell^{2}\rho^{2}+\left(\beta^{-1}+\hat{\delta}\right)\rho+(m\rho\|{J_{\rho\widehat{T}}(Gz)-Gz}\|)^{2}\leq\overline{\theta}$
(75)

and $x=J_{\rho\widehat{T}}(Gz)$. Consequently, _Problem A_ is equivalent to
find $\rho>0$ satisfying condition (75).

###### Proof.

The proof follows from Lemma 5.1(c) and (72)-(73). ∎

As a direct consequence of Corollary 5.2, we have that Problem A can be posed
in a more general framework as described next .

Problem B Given a maximal monotone operator $T$ in a real Hilbert space
${\mathcal{H}}$, scalars $a,b\geq 0$, $0<\theta_{-}<\theta_{+}<\infty$ and
$z\in{\mathcal{H}}$, find $\rho>0$ such that

$\displaystyle\theta_{-}\leq\psi(\rho,z)\leq\theta_{+},$ (76)

where

$\displaystyle\psi(\rho,z):=a\rho^{2}+b\rho+(\rho\|{J_{\rho T}(z)-z}\|)^{2}.$
(77)

######  Proposition 5.3.

_Problem A_ is a special case of _Problem B_. As a consequence, any solution
method designed to solve _Problem B_ can also be applied to solve _Problem A_.

###### Proof.

Indeed, by Corollary 5.2 we know that Problem A is equivalent to the problem
of finding $\rho>0$ satisfying (75). Now, note that by simply dividing (75) by
$m^{2}$, we see that it is clearly equivalent to (76)-(77) with
$T=\widehat{T}$ and

$\displaystyle\theta_{-}\leftarrow\underline{\theta}/m^{2},\quad a\leftarrow
4\ell^{2}/m^{2},\quad b\leftarrow(\beta^{-1}+\hat{\delta})/m^{2},\quad
z\leftarrow Gz\;\;\mbox{and}\quad\theta_{+}\leftarrow\overline{\theta}/m^{2}.$

∎

_Based on the discussion in the first paragraph of this section (see
“Motivation”) and Proposition 5.3, we conclude that it is sufficient for our
purposes to consider _Problem B_._

In order to achieve (76), we need to study the function $\psi(\cdot,\cdot)$ as
in (77) in more details. The following lemma of Monteiro and Svaiter will be
helpful to us.

######  Lemma 5.4.

_([50, Lemma 4.3])_ Let ${\mathcal{H}}$ be a real Hilbert space and
$T:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$ be maximal monotone. The
following holds for $\varphi(\rho,z):=\rho\|{J_{\rho T}(z)-z}\|$, where
$\rho>0$ and $z\in{\mathcal{H}}$.

  * _(a)_

$0<\rho\mapsto\varphi(\rho,z)$ is a continuous function.

  * _(b)_

For every $0<\mu<\rho$,

$\displaystyle\dfrac{\rho}{\mu}\varphi(\mu,z)\leq\varphi(\rho,z)\leq\left(\dfrac{\rho}{\mu}\right)^{2}\varphi(\mu,z).$
(78)

Next we prove a similar result for the function $\psi(\cdot,\cdot)$.

######  Lemma 5.5.

Let $\psi(\cdot,\cdot)$ be as in (77), i.e., let
$\psi(\rho,z):=a\rho^{2}+b\rho+\left[\varphi(\rho,z)\right]^{2}$, where
$\rho>0$, $z\in{\mathcal{H}}$, $a,b\geq 0$ and $\varphi(\rho,z)$ is as in
_Lemma 5.4_. If $0<\mu<\rho$, then

$\displaystyle\dfrac{\rho}{\mu}\psi(\mu,z)\leq\psi(\rho,z)\leq\left(\dfrac{\rho}{\mu}\right)^{4}\psi(\mu,z).$
(79)

###### Proof.

Note first that

$\displaystyle\dfrac{\psi(\mu,z)}{\mu}-b$
$\displaystyle=a\mu+\mu\left(\dfrac{\varphi(\mu,z)}{\mu}\right)^{2}$
$\displaystyle\leq
a\rho+\rho\left(\dfrac{\varphi(\mu,z)}{\mu}\right)^{2}\qquad[\mu<\rho]$
$\displaystyle\leq
a\rho+\rho\left(\dfrac{\varphi(\rho,z)}{\rho}\right)^{2}\qquad[\mbox{by the
first inequality in \eqref{eq:1300}}]$
$\displaystyle=\dfrac{\psi(\rho,z)}{\rho}-b,$

which clearly gives the first inequality in (79). Note now that it is trivial
to check the inequality

$\displaystyle
a\rho^{2}+b\rho\leq\left(\dfrac{\rho}{\mu}\right)^{4}(a\mu^{2}+b\mu).$ (80)

Hence,

$\displaystyle\psi(\rho,z)$
$\displaystyle=a\rho^{2}+b\rho+\left[\varphi(\rho,z)\right]^{2}$
$\displaystyle\leq\left(\dfrac{\rho}{\mu}\right)^{4}\left(a\mu^{2}+b\mu\right)+\left[\varphi(\rho,z)\right]^{2}\qquad\mbox{[by
\eqref{eq:1305}]}$
$\displaystyle\leq\left(\dfrac{\rho}{\mu}\right)^{4}\left(a\mu^{2}+b\mu+\left[\varphi(\mu,z)\right]^{2}\right)\qquad\mbox{[by
the second inequality in \eqref{eq:1300}]}$
$\displaystyle=\left(\dfrac{\rho}{\mu}\right)^{4}\psi(\mu,z).$

∎

######  Lemma 5.6.

Let $\psi(\cdot,\cdot)$ be as in (77) and let $z\in{\mathcal{H}}$ be such that
$0\notin T(z)$. The following holds:

  * _(a)_

$\psi(\rho,z)>0$ for every $\rho>0$.

  * _(b)_

$0<\rho\mapsto\psi(\rho,z)$ is a strictly increasing and continuous function,
which goes to $0$ or $\infty$, as $\rho$ tends to $0$ or $\infty$,
respectively.

  * _(c)_

For any $0<\theta_{-}<\theta_{+}<\infty$, the set of all $\rho>0$ satisfying

$\theta_{-}\leq\psi(\rho,z)\leq\theta_{+}$

is a closed interval $[\rho_{-},\rho_{+}]$, where

$\displaystyle\theta_{-}=\psi(\rho_{-},z)\;\;\mbox{and}\;\;\theta_{+}=\psi(\rho_{+},z),$
(81)

such that

$\dfrac{\rho_{+}}{\rho_{-}}\geq\sqrt[4]{\dfrac{\theta_{+}}{\theta_{-}}}.$

###### Proof.

The proof follows the same outline of [50, Lemma 4.4]’s proof, using Lemma 5.5
instead of [50, Lemma 4.3]. ∎

Next lemma, which is motivated by [50, Lemma 4.6], justifies the
bracketing/bisection procedure as presented in Algorithm 3 in the light of
Problem B - see (76) and (77).

######  Lemma 5.7.

Let $\psi(\cdot,\cdot)$ be as in (77) and let $\rho_{-},\rho_{+}>0$ be as in
(81). Let $z\in{\mathcal{H}}$ be such that $0\notin T(z)$ and let
$0<\theta_{-}<\theta_{+}<\infty$. The following holds:

  * _(a)_

If $\psi(\rho,z)<\theta_{-}$, then $\rho<\rho_{-}$ and
$\rho_{+}\leq\dfrac{\rho\theta_{+}}{\psi(\rho,z)}$.

  * _(b)_

If $\psi(\rho,z)>\theta_{+}$, then
$\dfrac{\rho\theta_{-}}{\psi(\rho,z)}\leq\rho_{-}$ and $\rho_{+}<\rho$.

###### Proof.

(a) If $\psi(\rho,z)<\theta_{-}$, using the fact that
$\theta_{-}=\psi(\rho_{-},z)$ \- see (81) - and Lemma 5.6(b) we obtain
$\rho<\rho_{-}$. Moreover, since we now know that $\rho<\rho_{-}<\rho_{+}$,
one can use Lemma 5.5 with $(\mu,\rho)\leftarrow(\rho,\rho_{+})$ to conclude
that $\dfrac{\rho_{+}}{\rho}\psi(\rho,z)\leq\psi(\rho_{+},z)$ and hence, since
$\theta_{+}=\psi(\rho_{+},z)$, that
$\rho_{+}\leq\dfrac{\rho\theta_{+}}{\psi(\rho,z)}$.

(b) The proof follows the same outline of the proof of item (a). ∎

We now make a few remarks about Lemma 5.7 (see also Figure 1).

  * (i)

Lemma 5.7(a) says that if (76) fails, for some $\rho>0$, because
$\psi(\rho,z)<\theta_{-}$, then it follows that $t_{-}:=\rho$ and
$t_{+}:=\dfrac{\rho\theta_{+}}{\psi(\rho,z)}$ define a closed interval
$[t_{-},t_{+}]$ which contains the interval $[\rho_{-},\rho_{+}]$ of all
possible $\rho>0$ satisfying (76). A similar observation also applies to Lemma
5.7(b). This is what we refer to in Algorithm 3 as Bracketing.

  * (ii)

Since, as we pointed out in item (i) above,
$[t_{-},t_{+}]\supset[\rho_{-},\rho_{+}]$, a simple bisection procedure on the
interval $[t_{-},t_{+}]$ will finish with some $\rho>0$ in
$[\rho_{-},\rho_{+}]$, i.e., some $\rho>0$ satisfying Problem B. This is what
we refer to in Algorithm 3 as Bisection.

Figure 1: See Problem B, Lemma 5.7 and the remarks following it.
$\rho$$\psi(\cdot,z)$0$t\\_$$t_{+}$$\rho\\_$$\rho_{+}$$\rho\\_$$\theta\\_$$\theta_{+}$

Global Variables for Function: $0<\underline{\theta}<\overline{\theta}<2$,
$\hat{\rho}>0$ and $\hat{\delta}>0$

1 Function  _BrackBisecProc(_$A,B,C,D,G,z,w,\ell,\beta,m$_)_:

2 Choose $\rho^{0}>0$ and compute
$x^{0}=J_{\rho^{0}\left(A+D_{(Gz)}\right)}\left(Gz+\rho^{0}w-\rho^{0}(B+C)(Gz)\right)$

3 if  _$\underline{\theta}\leq
4\ell^{2}(\rho^{0})^{2}+(\beta^{-1}+\hat{\delta})\rho^{0}+(m\rho^{0}\|{x^{0}-Gz}\|)^{2}\leq\overline{\theta}$_
then

4 return $\rho\leftarrow\rho^{0}$, $x\leftarrow x^{0}$ and

5
$y\leftarrow(Gz-x^{0})/\rho^{0}+w+\left[B(x^{0})-B(Gz)\right]+\left[D(x^{0})-D_{(Gz)}(x^{0})\right]$

6 end if

7 if
_$4\ell^{2}(\rho^{0})^{2}+(\beta^{-1}+\hat{\delta})\rho^{0}+(m\rho^{0}\|{x^{0}-Gz}\|)^{2}
<\underline{\theta}$_ then

8 $t_{-}\leftarrow\rho^{0}$ and
$t_{+}\leftarrow\dfrac{\rho^{0}\overline{\theta}}{4\ell^{2}(\rho^{0})^{2}+(\beta^{-1}+\hat{\delta})\rho^{0}+(m\rho^{0}\|{x^{0}-Gz}\|)^{2}}$

9 end if

10 if
_$4\ell^{2}(\rho^{0})^{2}+(\beta^{-1}+\hat{\delta})\rho^{0}+(m\rho^{0}\|{x^{0}-Gz}\|)^{2}
>\overline{\theta}$_ then

11
$t_{-}\leftarrow\dfrac{\rho^{0}\underline{\theta}}{4\ell^{2}(\rho^{0})^{2}+(\beta^{-1}+\hat{\delta})\rho^{0}+(m\rho^{0}\|{x^{0}-Gz}\|)^{2}}$
and $t_{+}\leftarrow\rho^{0}$

12 end if

13 Set $\tilde{\rho}=\sqrt{t_{-}t_{+}}$ and compute
$\tilde{x}=J_{\tilde{\rho}\left(A+D_{(Gz)}\right)}\left(Gz+\tilde{\rho}w-\tilde{\rho}(B+C)(Gz)\right)$

14 [1mm] if  _$\underline{\theta}\leq
4\ell^{2}(\tilde{\rho})^{2}+(\beta^{-1}+\hat{\delta})\tilde{\rho}+(m\tilde{\rho}\|{\tilde{x}-Gz}\|)^{2}\leq\overline{\theta}$_
then

15 return $\rho\leftarrow\tilde{\rho}$, $x\leftarrow\tilde{x}$ and

16
$y\leftarrow(Gz-\tilde{x})/\tilde{\rho}+w+\left[B(\tilde{x})-B(Gz)\right]+\left[D(\tilde{x})-D_{(Gz)}(\tilde{x})\right]$

17 end if

18 if
_$4\ell^{2}(\tilde{\rho})^{2}+(\beta^{-1}+\hat{\delta})\tilde{\rho}+(m\tilde{\rho}\|{\tilde{x}-Gz}\|)^{2}
>\overline{\theta}$_ then

19 $t_{+}\leftarrow\tilde{\rho}$

20 end if

21 if
_$4\ell^{2}(\tilde{\rho})^{2}+(\beta^{-1}+\hat{\delta})\tilde{\rho}+(m\tilde{\rho}\|{\tilde{x}-Gz}\|)^{2}
<\underline{\theta}$_ then

22 $t_{-}\leftarrow\tilde{\rho}$

23 end if

24 Go to line 3

25

return $(\rho,x,y)$

Algorithm 3 Bracketing/Bisection procedure for solving Problem A

Note that Algorithm 3 is nothing but a bracketing/bisection procedure
specialized to Problem A (see Proposition 5.3, Lemma 5.7 and Figure 1).

Next we show that Algorithm 3 finishes with $\rho>0$ and $x\in{\mathcal{H}}$
solving Problem A.

######  Proposition 5.8.

Consider the setting of _Problem A_ above and assume that
$w\notin(A+B+C+D)(Gz)$. Then, the bracketing/bisection procedure, as presented
in _Algorithm 3_, terminates with a triple $(\rho,x,y)$ with $\rho>0$ and
$x\in{\mathcal{H}}$ satisfying (72)-(73) and

$y=(Gz-x)/\rho+w+\left[B(x)-B(Gz)\right]+\left[D(x)-D_{(Gz)}(x)\right].$

###### Proof.

The proof follows from Proposition 5.3 and Lemmas 5.6 and 5.7. ∎

## References

  * [1] M. A. Alghamdi, A. Alotaibi, P. L. Combettes, and N. Shahzad.  A primal-dual method of partial inverses for composite inclusions.  Optim. Lett., 8(8):2271–2284, 2014.
  * [2] A. Alotaibi, P. L. Combettes, and N. Shahzad.  Solving coupled composite monotone inclusions by successive Fejér approximations of their Kuhn-Tucker set.  SIAM J. Optim., 24(4):2076–2095, 2014.
  * [3] A. Alotaibi, P. L. Combettes, and N. Shahzad.  Best approximation from the Kuhn-Tucker set of composite monotone inclusions.  Numer. Funct. Anal. Optim., 36(12):1513–1532, 2015.
  * [4] M. M. Alves.  Variants of the A-HPE and large-step A-HPE algorithms for strongly convex problems with applications to accelerated high-order tensor methods.  _Optim. Methods Softw._ , 37(6):2021–2051, 2022.
  * [5] M. M. Alves, M. Geremia, and R.T. Marcavillaca.  A relative-error inertial-relaxed inexact projective splitting algorithm.  J. Convex Anal., 31(1):1–24, 2024.
  * [6] M. M. Alves and R. T. Marcavillaca.  On inexact relative-error hybrid proximal extragradient, forward-backward and Tseng’s modified forward-backward methods with inertial effects.  Set-Valued Var. Anal., 28(2):301–325, 2020.
  * [7] H. Attouch, M. M. Alves, and B. F. Svaiter.  A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity $\mathcal{O}(1/n^{2})$.  J. Convex Anal., 23(1):139–180, 2016.
  * [8] H. Attouch and A. Cabot.  Convergence of a relaxed inertial proximal algorithm for maximally monotone operators.  Math. Program., 184(1-2, Ser. A):243–287, 2020.
  * [9] H. Attouch, A. Cabot, Z. Chbani, and H. Riahi.  Inertial forward-backward algorithms with perturbations: application to Tikhonov regularization.  J. Optim. Theory Appl., 179(1):1–36, 2018.
  * [10] H. Attouch and J. Peypouquet.  Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators.  Math. Program., 174(1-2, Ser. B):391–432, 2019.
  * [11] F. Bach.  Self-concordant analysis for logistic regression.  Electron. J. Stat., 4:384–414, 2010.
  * [12] M. Barré, A. Taylor, and F. Bach.  A note on approximate accelerated forward-backward methods with absolute and relative errors, and possibly strongly convex objectives.  _OJMO, Open J. Math. Optim._ , 3, article no. 1 (15 pages), 2022.
  * [13] H. H. Bauschke and P. L. Combettes.  Convex analysis and monotone operator theory in Hilbert spaces.  CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York, 2011.
  * [14] H. H. Bauschke and W. M. Moursi.  On the behavior of the Douglas-Rachford algorithm for minimizing a convex function subject to a linear constraint.  SIAM J. Optim., 30(3):2559–2576, 2020.
  * [15] A. Beck and M. Teboulle.  A fast iterative shrinkage-thresholding algorithm for linear inverse problems.  SIAM J. Imaging Sci., 2(1):183–202, 2009.
  * [16] R. I. Boţ and E. R. Csetnek.  ADMM for monotone operators: convergence analysis and rates.  Adv. Comput. Math., 45(1):327–359, 2019.
  * [17] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  Found. Trends Mach. Learn., 3(1):1–122, 2011.
  * [18] L. M. Briceño Arias and D. Davis.  Forward-backward-half forward algorithm for solving monotone inclusions.  SIAM J. Optim., 28(4):2839–2871, 2018.
  * [19] M. N. Bùi and P. L. Combettes.  Warped proximal iterations for monotone inclusions.  J. Math. Anal. Appl., 491(1):124315, 21, 2020.
  * [20] M. N. Bùi and P. L. Combettes.  Multivariate monotone inclusions in saddle form.  Math. Oper. Res., 47(2):1082–1109, 2022.
  * [21] B. Bullins and K. A. Lai.  Higher-order methods for convex-concave min-max optimization and monotone variational inequalities.  SIAM J. Optim., 32(3):2208–2229, 2022.
  * [22] L. Chen, X. Li, D. Sun, and K.-C. Toh.  On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming.  Math. Program., 185(1-2, Ser. A):111–161, 2021.
  * [23] P. L. Combettes and J. Eckstein.  Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions.  Math. Program., 168(1-2, Ser. B):645–672, 2018.
  * [24] P. L. Combettes and Q. V. Nguyen.  Solving composite monotone inclusions in reflexive Banach spaces by constructing best Bregman approximations from their Kuhn-Tucker set.  J. Convex Anal., 23(2):481–510, 2016.
  * [25] P. L. Combettes and J.-C. Pesquet.  Proximal splitting methods in signal processing.  In Fixed-point algorithms for inverse problems in science and engineering, volume 49 of Springer Optim. Appl., pages 185–212. Springer, New York, 2011.
  * [26] L. Condat.  A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms.  J. Optim. Theory Appl., 158(2):460–479, 2013.
  * [27] D. Davis and W. Yin.  A three-operator splitting scheme and its optimization applications.  Set-Valued Var. Anal., 25(4):829–858, 2017.
  * [28] J. E. Dennis, Jr. and R. B. Schnabel.  Numerical methods for unconstrained optimization and nonlinear equations, volume 16 of Classics in Applied Mathematics.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996.  Corrected reprint of the 1983 original.
  * [29] J. Eckstein and D. P. Bertsekas.  On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators.  Math. Program., 55(3):293–318, 1992.
  * [30] J. Eckstein and B. F. Svaiter.  A family of projective splitting methods for the sum of two maximal monotone operators.  Math. Program., 111(1-2, Ser. B):173–199, 2008.
  * [31] J. Eckstein and B. F. Svaiter.  General projective splitting methods for sums of maximal monotone operators.  SIAM J. Control Optim., 48(2):787–811, 2009.
  * [32] P. Giselsson.  Nonlinear forward-backward splitting with projection correction.  SIAM J. Optim., 31(3):2199–2226, 2021.
  * [33] R. Glowinski, S. J. Osher, and W. Yin, editors.  Splitting methods in communication, imaging, science, and engineering.  Scientific Computation. Springer, Cham, 2016.
  * [34] W. W. Hager and H. Zhang.  Convergence rates for an inexact ADMM applied to separable convex optimization.  Comput. Optim. Appl., 77(3):729–754, 2020.
  * [35] B. He and X. Yuan.  On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method.  SIAM J. Numer. Anal., 50(2):700–709, 2012.
  * [36] R. Jiang and A. Mokhtari.  Generalized optimistic methods for convex-concave saddle point problems.  Technical report (arxiv:2202.09674 [math.oc]), 2022.
  * [37] P. Johnstone, J. Eckstein, T. Flynn, and S. Yoo.  Stochastic projective splitting.  Comput. Optim. Appl., 87(4):397-437 (2024).
  * [38] P. R. Johnstone and J. Eckstein.  Convergence rates for projective splitting.  SIAM J. Optim., 29(3):1931–1957, 2019.
  * [39] P. R. Johnstone and J. Eckstein.  Single-forward-step projective splitting: exploiting cocoercivity.  Comput. Optim. Appl., 78(1):125–166, 2021.
  * [40] P. R. Johnstone and J. Eckstein.  Projective splitting with forward steps.  Math. Program., 191(2, Ser. A):631–670, 2022.
  * [41] A. Lenoir and P. Mahey.  A survey on operator splitting and decomposition of convex programs.  RAIRO Oper. Res., 51(1):17–41, 2017.
  * [42] T. Lin and M. I. Jordan.  A control-theoretic perspective on optimal high-order optimization.  _Math. Program._ , 195, No. 1-2 (A), 929-975 (2022).
  * [43] T. Lin and M. I. Jordan.  Perseus: A simple and optimal high-order method for variational inequalities.  _Math. Program._ , 2024, https://doi.org/10.1007/s10107-024-02075-2
  * [44] T. Lin and M.I. Jordan.  Monotone inclusions, acceleration, and closed-loop control.  Math. Oper. Res., 48(4):2353-2382, 2023.
  * [45] P.-L. Lions and B. Mercier.  Splitting algorithms for the sum of two nonlinear operators.  SIAM J. Numer. Anal., 16(6):964–979, 1979.
  * [46] D. A. Lorenz and T. Pock.  An inertial forward-backward algorithm for monotone inclusions.  J. Math. Imaging Vision, 51(2):311–325, 2015.
  * [47] D. A. Lorenz and Q. Tran-Dinh.  Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence.  Comput. Optim. Appl., 74(1):67–92, 2019.
  * [48] U. Marteau-Ferey, F. Bach, and A. Rudi.  Globally convergent newton methods for ill-conditioned generalized self-concordant losses.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019.
  * [49] R. D. C. Monteiro and B. F. Svaiter.  On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean.  SIAM J. Optim., 20(6):2755–2787, 2010.
  * [50] R. D. C. Monteiro and B. F. Svaiter.  Iteration-Complexity of a Newton Proximal Extragradient Method for Monotone Variational Inequalities and Inclusion Problems.  SIAM J. Optim., 22(3):914–935, 2012.
  * [51] R. D. C. Monteiro and B. F. Svaiter.  Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers.  SIAM J. Optim., 23(1):475–507, 2013.
  * [52] Y. Nesterov.  Lectures on convex optimization, volume 137 of Springer Optimization and Its Applications.  Springer, Cham, 2018.  Second edition of [ MR2142598].
  * [53] G. B. Passty.  Ergodic convergence to a zero of the sum of monotone operators in Hilbert space.  J. Math. Anal. Appl., 72(2):383–390, 1979.
  * [54] R. T. Rockafellar.  Convex Analysis.  Princeton University Press, Princeton, NJ, 1970.
  * [55] R. T. Rockafellar.  On the maximality of sums of nonlinear monotone operators.  Trans. Amer. Math. Soc., 149:75–88, 1970.
  * [56] E. Ryu and W. Yin.  Large-Scale Convex Optimization: Algorithms and Analyses via Monotone Operators.  2022\.
  * [57] S. Salzo and S. Villa.  Inexact and accelerated proximal point algorithms.  J. Convex Anal., 19(4), 2012.
  * [58] S. Salzo and S. Villa.  Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis.  Math. Program., 193(1, Ser. A):225–269, 2022.
  * [59] P. Tseng.  A modified forward-backward splitting method for maximal monotone mappings.  SIAM J. Control Optim., 38(2):431–446 (electronic), 2000.