On the complexity of the projective splitting and Spingarn's methods for the sum of two maximal monotone operators
Majela Pentón Machado
math.OC



Active and Passive Transport of Cargo in a Corrugated Channel: A Lattice Model Study
    Moumita Das
    December 30, 2023
====================================================================================



In this work, we study the pointwise and ergodic iteration-complexity of a family of projective splitting methods proposed by Eckstein and Svaiter, for finding a zero of the sum of two maximal monotone operators. As a consequence of the complexity analysis of the projective splitting methods, we obtain complexity bounds for the two-operator case of Spingarn's partial inverse method. We also present inexact variants of two specific instances of this family of algorithms and derive corresponding convergence rate results.


Keywords.
splitting algorithms; maximal monotone operators; complexity; Spingarn method.


AMS Classification: 47H05, 49M27, 90C60, 65K05.



§ INTRODUCTION


A wide variety of problems, such as optimization and min-max problems, 
complementarity problems and variational inequalities, can be posed as the monotone inclusion problem (MIP) associated to a maximal monotone point-to-set operator.
An important tool for the design and analysis of several implementable methods for solving MIPs is the
proximal point algorithm (PPA), proposed by Martinet <cit.> and generalized by Rockafellar 
<cit.>. 
Even though the PPA has good global and local convergence properties <cit.>,
its major drawback is that it requires the evaluation of the resolvent mappings (or proximal mappings) associated with the operator. The difficulty lies in the fact that evaluating a resolvent mapping, which is equivalent to solving a proximal
subproblem, can be as complicated as finding a root of the operator.
 
One alternative to surmount this difficulty is to decompose the operator as the sum of two maximal monotone operators such that their resolvents are considerably easier to evaluate. Then, one can devise methods that use independently these proximal mappings.

In this work, we are concerned with MIPs defined by the sum of two maximal monotone
operators. 
We are also interested in the case 
where the problems of finding zeros of these operators separately are easier than solving the MIP for the sum. 
A typical instance of this situation is the variational inequality problem associated with a maximal monotone operator A and a closed convex subset C, whose solutions are precisely the zeros of the sum of A and the normal operator associated with C, known to be maximal monotone.

Splitting methods (or decomposition methods) for problems of the above-mentioned type attempt to converge to
a solution of the MIP by solving, in each iteration, subproblems involving one of the operators, but not both.
Peaceman-Rachford and Douglas-Rachford methods are examples of this type of algorithms. These 
were first introduced in <cit.> and <cit.> for the particular case of 
linear mappings, and then generalized in <cit.> by Lions and Mercier to address MIPs.
Forward-backward methods <cit.>, 
which generalize standard gradient projection methods for variational inequalities and optimization 
problems, are also examples of splitting algorithms.

Recently, a new family of splitting methods for solving MIPs given by the sum of two maximal monotone operators was introduced in <cit.> by Eckstein and Svaiter. Through a generalized solution set in a product space, whose projection onto the first space is indeed the solution set of the problem, the authors constructed a class of decomposition methods with quite solid convergence properties.
These algorithms are
essentially projection methods, in the sense that in each
iteration a hyperplane is constructed separating the current iterate from the generalized solution
set, and then the next
iterate is taken as a relaxed projection of the current one onto this separating hyperplane. In order
to construct such hyperplanes, two proximal subproblems are solved,
each of which involves only one of the two maximal monotone operators,
which ensures the splitting nature of the methods.

In this work we study the iteration-complexity of the family of methods proposed
in <cit.>, to be referred as projective splitting methods (PSM) in the sequel. 
We start our analysis by introducing a projective algorithm that generalizes the PSM.
We then consider a termination criterion for this general algorithm in terms of the 
ϵ-enlargements of the operators, which allows us to obtain convergence rates for the 
PSM measured by the pointwise and ergodic iteration-complexities.

Using the complexity analysis developed for the PSM, we also study the complexity 
of Spingarn's splitting method 
for solving inclusion problems given by the sum of two maximal monotone operators. 
In <cit.>, Spingarn introduced a splitting method for finding a zero of the sum of m maximal monotone 
operators using the concept of partial inverses. For the two-operator case, Eckstein and Svaiter proved 
in <cit.> that Spingarn's method is a special case of a scaled variant of the PSM. This will allow us to establish iteration-complexity results for Spingarn's method for the case of the sum of two maximal monotone operators.

The general projective method that we introduce in this work is also used to construct inexact variants of two special cases of the family of PSM. For two specific instances of the PSM, we consider a relative error condition for 
approximately evaluating the resolvents. The error criterion considered in this work is different from the one 
used in <cit.>, where was generalized the projective splitting framework for MIPs given by the sum of m maximal 
monotone operators. Indeed, we will use the notion of approximate solutions of a proximal subproblem presented in 
<cit.>, which yields a more flexible error tolerance criterion and allows evaluation of the ϵ-enlargement. 
We also derive convergence rate results for these two novel algorithms. 

The remainder of this paper is organized as follows. Section <ref> reviews the definitions and some basic properties of a point-to-set maximal monotone operator and its ϵ-enlargements. Section <ref> presents a relaxed
projection method that extends the framework introduced in <cit.>. It also proves some properties regarding this general scheme and establishes the stopping criterion that will be considered for such method and its instances.
Section <ref> presents the PSM introduced in <cit.> and derives global convergence rate results for these methods. Subsection <ref> specializes these general complexity bounds for the case where global convergence for the family of PSM was obtained in <cit.>. Section <ref> studies the  iteration complexity of the two-operator case of Spingarn’s method of partial inverses <cit.>. Finally, sections <ref> and <ref> propose inexact versions of two special cases of the PSM and establish iteration-complexity results for them.




§ PRELIMINARIES



Throughout this paper, we let ^n denote an n-dimensional space with inner product and induced norm denoted by ·· and ·, respectively. We also define the spaces _+ and 𝔼 as _+:=x∈ : x≥0 and 𝔼:=^n×^n×_+.

In what follows in this section, we will review some material related to a point-to-set maximal monotone operator and its ϵ-enlargements that will be needed along this work. 

A point-to-set operator T:ℝ^n⇉ℝ^n is a relation T ⊆^n×^n and 

    T(z) := {v∈ℝ^n:(z,v)∈ T}     z∈ℝ^n.

Given T:ℝ^n⇉ℝ^n its graph is the set

    T:={(z,v)∈^n×^n:v∈ T(z)}.

An operator T:ℝ^n⇉ℝ^n is monotone, if 

    z-z'v-v'≥0        ∀ (z,v),(z',v')∈T,

and it is maximal monotone if it is monotone and maximal in the family of monotone operators of ℝ^n into ℝ^n, with respect to the partial order of inclusion. This is, if S:ℝ^n⇉ℝ^n is a monotone operator such that T⊆S, then S=T.

The resolvent mapping of a maximal monotone operator T with parameter λ>0 is (I+λ T)^-1, where I is the identity mapping. It follows directly from the definition that z'=(I+λ T)^-1(z), if and only if z' is the solution of the proximal subproblem 

    0∈λ T(z') + (z'-z).


The ϵ-enlargement of a maximal monotone operator was introduced in <cit.> by Burachik, Iusem and Svaiter. In <cit.>, Monteiro and Svaiter extended this notion to a generic point-to-set operator as follows. Given T:ℝ^n⇉ℝ^n and ϵ∈ℝ, define the operator ϵ-enlargement of T, T^ϵ:ℝ^n⇉ℝ^n, by

    T^ϵ(z) := {v∈ℝ^n:z'-zv'-v≥-ϵ,  ∀ (z',v') ∈ T},    ∀ z∈ℝ^n.

The following proposition presents some important properties of T^ϵ. Its proof can be found in <cit.>.


Let T:ℝ^n⇉ℝ^n. Then,


  (a) if ϵ'≤ϵ, we have T^ϵ'(z)⊆ T^ϵ(z) for all z∈ℝ^n;

  (b) T is monotone if and only if T⊆ T^0;

  (c) T is maximal monotone if and only if T=T^0.



Observe that items (a) and (c) above imply that, if T:^n⇉^n is maximal monotone, then T(z)⊆ T^ϵ(z) for all z∈^n and ϵ≥0.
Hence, T^ϵ(z) is indeed an enlargement of T(z).

We now state the weak transportation formula <cit.> for computing points in the graph of T^ϵ. This formula will be used in the complexity analysis of some ergodic iterates generated by the algorithms studied in this work (see subsection <ref>).


Assume that T:ℝ^n⇉ℝ^n is a maximal monotone operator. Let z_i,v_i∈ℝ^n and ϵ_i,α_i∈ℝ_+, for i=1,…,k, be such that

    v_i∈ T^ϵ_i(z_i),   i=1,…,k,         ∑_i=1^kα_i=1,

and define 

    z: = ∑_i=1^kα_iz_i,       v:=∑_i=1^kα_iv_i,       ϵ:=∑_i=1^kα_i(ϵ_i+z_i-zv_i).

Then, ϵ≥0 and v∈ T^ϵ(z).




§ THE GENERAL PROJECTIVE SPLITTING FRAMEWORK


The monotone inclusion problem (MIP) of interest in this work consists of finding
z∈ℝ^n such that

    0 ∈ A(z) + B(z),

where A,B:ℝ^n⇉ℝ^n are maximal
monotone operators. 

The framework presented in <cit.> reformulates problem (<ref>) in  terms  of  a  convex  
feasibility problem, which  is  defined  by  a certain closed convex extended solution set.
To solve the feasibility problem, the authors introduced successive projection 
algorithms that use, at each iteration, independent calculations involving each operator. Our goals in this section are to present a scheme that generalizes the methods in <cit.>, and to study its properties. This general framework will allow us to derive convergence rates for the family of PSM and Spingarn's method. In addition, using this general method, we construct inexact versions of two specific instances of the PSM and study their complexities.

Consider S_e(A,B)⊂^n×^n the extended solution set of (<ref>) defined in
<cit.> as

    S_e(A,B):=(z,w)∈^n×^n : w∈ B(z),  -w∈ A(z).

The following result establishes two important properties of AB. Its proof can be found in <cit.>.



  If A,B:ℝ^n⇉ℝ^n are maximal
  monotone operators, then the following statements hold.


  (a) A point z∈ℝ^n is a solution of (<ref>),
  if and only if there is w∈ℝ^n such that
  (z,w)∈AB.

  (b) S_e(A,B) is a closed and convex subset of ^n×^n.



According to the above lemma, problem (<ref>) is equivalent to the 
convex feasibility problem of finding a point in S_e(A,B).
In order to solve this feasibility problem by successive orthogonal projection methods, we need to construct hyperplanes separating points (z,w)∉ S_e(A,B) from S_e(A,B).
For this purpose, in <cit.> it was used points in the graph of A and B to define affine functions, which were called decomposable separators, such that
AB was contained in the non-positive half-spaces determined by
them. Here, we generalize this concept using points in
the ϵ-enlargements of A and B.


  
  Given two triplets (x,b,ϵ^x),
  (y,a,ϵ^y)∈𝔼 such that b∈ B^ϵ^x(x)
  and a∈ A^ϵ^y(y), the   decomposable   separator   associated   with   (x,b,ϵ^x)   and   (y,a,ϵ^y)   is   the   affine   function ϕ:^n×^n→ℝ
  
    ϕ(z,w) := z-xb-w + z-ya+w -ϵ^x - ϵ^y.

  The non-positive level set of ϕ is
  
    H_ϕ:=(z,w)∈^n×^n : ϕ(z,w) ≤ 0.





  If ϕ is the decomposable separator associated with (x,b,ϵ^x) and
  (y,a,ϵ^y)∈𝔼, where b∈ B^ϵ^x(x)
  and a∈ A^ϵ^y(y), and H_ϕ is its non-positive level set, then
  
  
  (a) S_e(A,B)⊆ H_ϕ;
  
  (b) either ∇ϕ≠ 0 or ϕ≤ 0 in ℝ^n×ℝ^n;
  
  (c) either H_ϕ is a closed half-space or H_ϕ=^n×^n.
  



Item (a) is a direct consequence of the definitions of the ϵ-enlargement of a point-to-set
operator and the set S_e(A,B). Rewriting ϕ(z,w)  as

    ϕ(z,w) = z-ya+b + w-bx-y -ϵ^x -ϵ^y    ∀(z,w)∈^n×^n,

and noting that ∇ϕ=(a+b,x-y) and ϵ^x, ϵ^y≥0, then (b) and (c) follow immediately.


We now present the general projection scheme for finding a point in S_e(A,B) that will be studied in this work. 
Algorithm <ref> below generalizes the framework introduced in <cit.>, since we use the notion of decomposable separator introduced in Definition <ref>. 



Note that the general form of Algorithm <ref> is not sufficient to guarantee convergence of the sequence {(z_k,w_k)} to a point in AB. 
For example, if the separation between the point (z_k-1,w_k-1)∉ S_e(A,B) and S_e(A,B) by ϕ_k is not strict, then the next iterate is in fact (z_k-1,w_k-1) itself, which
might lead to a constant sequence. 
Hence, to ensure convergence it is necessary to impose
additional conditions on the decomposable separators, see <cit.> and sections <ref>, <ref> and <ref> below. However, since Algorithm <ref> is a relaxed projection type method, it is possible to establish Fejér 
monotone convergence to S_e(A,B) and boundedness of its generated sequence, as well as other classical properties of this kind of algorithms (see for example <cit.>, <cit.>).





 §.§ The Generated Sequences



We will now analyze some properties of the sequences {(z_k,w_k)}, {ϕ_k}, {γ_k} and {ρ_k} generated by Algorithm <ref>, which will be needed in our complexity study.
To this end, let us first prove the following technical result.



For any (z,w)∈^n×^n and k≥1 we have

    12(z,w)-(z_k,w_k)^2 + 12∑_j=1^kρ_j(2-ρ_j)γ_j^2∇ϕ_j^2 = 12(z,w)-(z_0,w_0)^2 + ∑_j=1^kρ_jγ_jϕ_j(z,w).




First we observe that for j=1,2,…, and any (z,w)∈^n×^n it holds that

    12(z,w)-(z_j,w_j)^2  =     12(z,w)-(z_j-1,w_j-1)+ρ_jγ_j∇ϕ_j^2
    
     =     12(z,w)-(z_j-1,w_j-1)^2 + (z,w)-(z_j-1,w_j-1)ρ_jγ_j∇ϕ_j
          + 12ρ_j^2γ_j^2∇ϕ_j^2
    
    =     12(z,w)-(z_j-1,w_j-1)^2 + ρ_jγ_j(z,w)-(y_j,b_j)∇ϕ_j
          + ρ_jγ_j(y_j,b_j)-(z_j-1,w_j-1)∇ϕ_j + 12ρ_j^2γ_j^2∇ϕ_j^2,

where the first equality above follows from the update rule in step 3 of Algorithm <ref>.

Equation (<ref>) with ϕ=ϕ_j implies that

    ϕ_j(z,w) = (z,w)-(y_j,b_j)∇ϕ_j - ϵ^x_j - ϵ^y_j      ∀(z,w) ∈^n×^n.

Therefore, adding and subtracting ρ_jγ_j(ϵ^x_j + ϵ^y_j) on the right-hand side of the last equality in (<ref>) and combining with the identity above, we obtain 

    12(z,w)-(z_j,w_j)^2 =     12(z,w)-(z_j-1,w_j-1)^2 + ρ_jγ_jϕ_j(z,w)
            - ρ_jγ_jϕ_j(z_j-1,w_j-1) + 12ρ_j^2γ_j^2∇ϕ_j^2.


If we assume that γ_j>0, then the definition of γ_j in step 2 of Algorithm <ref> yields that ϕ_j(z_j-1,w_j-1)=γ_j∇ϕ_j^2. Hence, substituting this expression into the equality above and rearranging, we have

    12(z,w)-(z_j,w_j)^2 + 12ρ_j(2-ρ_j)γ_j^2∇ϕ_j^2 =   12(z,w)-(z_j-1,w_j-1)^2 + ρ_jγ_jϕ_j(z,w).

It is clear that this latter equality also holds if γ_j=0. Thus, adding equation above from j=1 to k we obtain (<ref>).


In what follows we assume that problem (<ref>) has at least one solution, which implies that S_e(A,B) is a non-empty set in view of Lemma <ref>.


Next theorem, which follows directly from Lemma <ref>, establishes boundedness of the sequence {(z_k,w_k)} calculated by Algorithm <ref>, and it also shows that the sum appearing on the left-hand 
side of (<ref>) is bounded by the distance of the initial point to the set S_e(A,B).



Take  (z_0,w_0)∈^n×^n and let 
{(z_k,w_k)}, {ϕ_k}, {γ_k} and {ρ_k}
be the sequences generated by Algorithm <ref>. Then, for every integer k≥1, we have

    ∑_j=1^kρ_j(2-ρ_j)γ_j^2∇ϕ_j^2≤ d_0^2    and    (z_k,w_k)-(z_0,w_0)≤ 2d_0,

where d_0 is the distance of (z_0,w_0) to AB.



Take (z^∗,w^∗) the orthogonal projection of (z_0,w_0) onto S_e(A,B). From Lemma <ref>(a) it follows that ϕ_j(z^∗,w^∗)≤0 for all integer j≥1. 
Hence, specializing equality (<ref>) with (z^∗,w^∗) we obtain the first bound in (<ref>) and the following inequality

    (z_k,w_k)-(z^∗,w^∗)≤ d_0.

Since (z_0,w_0)-(z^∗,w^∗)=d_0, the second estimate in (<ref>) follows from the latter two relations and the triangle inequality for norms.


It is important to say that Theorem <ref> can be proven using standard arguments of relaxed projection algorithms, see for instance <cit.>. 
We have chosen the above approach since it will be more convenient for our subsequent analysis.



 §.§ The Ergodic Sequences



Besides the pointwise complexity of specific instances of Algorithm <ref>,
we are also interested in deriving their convergence rates measured by the iteration 
complexity in an ergodic sense. To do this, we consider sequences obtained by weighted 
averages of the sequences {x_k} and {y_k}, generated by Algorithm <ref>, and study their properties.


Let {x_k}, {y_k}, {γ_k} and {ρ_k} be the sequences computed with Algorithm <ref>, for every integer k≥1 assume that γ_k>0 and 
define x_k and y_k as                                                                              

    x_k := 1/Γ_k∑_j=1^kρ_jγ_jx_j,    y_k := 1/Γ_k∑_j=1^kρ_jγ_jy_j,      whereΓ_k := ∑_j=1^kρ_jγ_j.

The following lemma is a direct consequence of the weak transportation formula, Theorem <ref>.



Let {(x_k,b_k,ϵ^x_k)}, {(y_k,a_k,ϵ^y_k)}, {γ_k} and {ρ_k} be the sequences generated by Algorithm <ref>. 
For every integer k≥1, suppose that γ_k>0 and consider x_k, y_k and Γ_k given as in (<ref>). Define also

    b_k := 1/Γ_k∑_j=1^kρ_jγ_jb_j,       ϵ^x_k := 1/Γ_k∑_j=1^kρ_jγ_j(ϵ^x_j+x_j-x_kb_j),
    a_k := 1/Γ_k∑_j=1^kρ_jγ_ja_j,       ϵ^y_k := 1/Γ_k∑_j=1^kρ_jγ_j(ϵ^y_j+y_j-y_ka_j).

Then, we have

    ϵ^x_k≥0,   b_k∈ B^ϵ^x_k(x_k),
    
    ϵ^y_k≥0,   a_k∈ A^ϵ^y_k(y_k).




The lemma follows from Theorem <ref> and the inclusions b_j∈ B^ϵ^x_j(x_j) and a_j∈ A^ϵ^y_j(y_j).


We will refer to the sequences {(x_k,b_k,ϵ^x_k)} and {(y_k,a_k,ϵ^y_k)}, defined in (<ref>)-(<ref>), as the ergodic sequences associated with Algorithm <ref>.

Next lemma presents alternative expressions for a_k+b_k, x_k-y_k and
ϵ^x_k+ϵ^y_k, which will be used for obtaining bounds on their sizes.


Let {(x_k,b_k,ϵ^x_k)}, {(y_k,a_k,ϵ^y_k)}, {γ_k} and {ρ_k} be the sequences generated by Algorithm <ref>. Assume that γ_k>0 for all k≥1, and define the sequences {x_k}, {y_k}, {Γ_k}, {b_k}, {a_k}, {ϵ^x_k} and {ϵ^y_k} as in (<ref>), (<ref>) and (<ref>). Then, for every integer k≥1, we have

    a_k+b_k = 1/Γ_k(z_0-z_k),
        x_k-y_k = 1/Γ_k(w_0-w_k),
        ϵ^x_k + ϵ^y_k = -1/Γ_k∑_j=1^kρ_jγ_jϕ_j(y_k,b_k).




Direct use of the definitions of  x_k, y_k, b_k and a_k yields

    (a_k+b_k,x_k-y_k) = 1/Γ_k∑_j=1^kρ_jγ_j(a_j+b_j,x_j-y_j).

Since ∇ϕ_j=(a_j+b_j,x_j-y_j) for all integer j≥1, in view of the update rule in step 3 of Algorithm <ref>, the definition of Γ_k and the equation above, we have

    (z_k,w_k) =     (z_0,w_0) - ∑_j=1^kρ_jγ_j(a_j+b_j,x_j-y_j)
    
     =      (z_0,w_0) - Γ_k(a_k+b_k,x_k-y_k).

The relation above clearly implies the first two identities in (<ref>).

To prove the last equality in (<ref>) we first note that

    ∑_j=1^kρ_jγ_jϕ_j(y_k,b_k)    = ∑_j=1^k ρ_jγ_j(y_k-x_jb_j-b_k+y_k-y_ja_j+b_k -ϵ^x_j -ϵ^y_j)
       = ∑_j=1^k ρ_jγ_j(y_kb_j + x_jb_k-b_j +y_k-y_ja_j -y_jb_k -ϵ^x_j -ϵ^y_j).

Next, we multiply the equation above by 1/Γ_k and use the definitions of y_k and b_k to obtain

    1/Γ_k∑_j=1^kρ_jγ_jϕ_j(y_k,b_k)    = 1/Γ_k∑_j=1^k ρ_jγ_j(x_jb_k-b_j+y_k-y_ja_j -ϵ^x_j -ϵ^y_j).

Now, we observe that ϵ^x_k can be rewritten as

    ϵ^x_k = 1/Γ_k∑_j=1^kρ_jγ_j(ϵ^x_j + x_jb_j-b_k).

Thus, adding ϵ^x_k and ϵ^y_k and combining with (<ref>) and the equation above, we deduce the third equality in (<ref>).


The following result establishes bounds for the quantities a_k+b_k, x_k-y_k and ϵ^x_k+ϵ_k^y.



Assume the hypotheses of Lemma <ref> and let d_0 be the distance of (z_0,w_0) to AB. Then, for all integer k≥1, we have

    a_k+b_k≤2d_0/Γ_k,        x_k-y_k≤2d_0/Γ_k,
       ϵ^x_k + ϵ^y_k≤1/Γ_k[1/Γ_k∑_j=1^kρ_jγ_j(y_j,b_j)-(z_j-1,w_j-1)^2+4d_0^2].




We combine the first two identities in (<ref>) with the second inequality in (<ref>) to obtain

    (a_k+b_k,x_k-y_k) = 1/Γ_k(z_0,w_0)-(z_k,w_k)≤2d_0/Γ_k.

Thus, the bounds in (<ref>) follow immediately from the equation above.

Now, taking (z,w)=(y_k,b_k) in equation (<ref>) and rearranging the terms we have

    -∑_j=1^kρ_jγ_jϕ_j(y_k,b_k) =      12(y_k,b_k)-(z_0,w_0)^2 - 12(y_k,b_k)-(z_k,w_k)^2
          - 1/2∑_j=1^kρ_j(2-ρ_j)γ_j^2∇ϕ_j^2.

Since ρ_j∈]0,2[ for all integer j≥1, the equation above implies

    -∑_j=1^kρ_jγ_jϕ_j(y_k,b_k) ≤  12(y_k,b_k)-(z_0,w_0)^2.

Next, we define (z_k,w_k):=1Γ_k∑_j=1^kρ_jγ_j(z_j-1,w_j-1) and use the triangle inequality for norms to obtain

    12(y_k,b_k)-(z_0,w_0)^2 ≤    (y_k,b_k)-(z_k,w_k)^2 + (z_k,w_k)-(z_0,w_0)^2
    ≤    1Γ_k∑_j=1^kρ_jγ_j(y_j,b_j)-(z_j-1,w_j-1)^2
           + 1Γ_k∑_j=1^kρ_jγ_j(z_j-1,w_j-1)-(z_0,w_0)^2
    ≤    1Γ_k∑_j=1^kρ_jγ_j(y_j,b_j)-(z_j-1,w_j-1)^2 + 4d_0^2,

where the second and the third inequalities above are due to the convexity of ·^2 and the second bound in (<ref>), respectively.

Combining (<ref>) with (<ref>) we deduce that 

    -∑_j=1^kρ_jγ_jϕ_j(y_k,b_k) ≤1Γ_k∑_j=1^kρ_jγ_j(y_j,b_j)-(z_j-1,w_j-1)^2 + 4d_0^2.

Relation above, together with the last equality in (<ref>), now yields (<ref>).





 §.§ Stopping Criterion


In order to analyze the complexity properties of instances of Algorithm <ref>, we define a termination condition for this general method in terms of the ϵ-enlargements of operators A and B. This criterion will enable the obtention of complexity bounds, proportional to the distance 
of the initial iterate to the extended solution set S_e(A,B), for all the schemes presented in this work.

We consider the following stopping criterion for Algorithm <ref>. Given an arbitrary pair of scalars δ, ϵ>0, Algorithm <ref> will stop when it finds a
pair of points (x,b,ϵ^x), (y,a,ϵ^y) ∈𝔼 such that 

    b ∈ B^ϵ^x(x),        a ∈ A^ϵ^y(y),       max{a+b,x-y}≤δ,       max{ϵ^x,ϵ^y}≤ϵ.

We observe that if δ=ϵ=0, in view of Proposition <ref>, the above termination criterion is reduced to b∈ B(x), a∈ A(y), x=y and b=-a, in which case (x,b)∈ S_e(A,B).

Based on the termination condition (<ref>) we can define the following notion of approximate solutions of problem (<ref>).


For a given pair of positive scalars (δ,ϵ), a pair (x,y)∈^n×^n is called a (δ,ϵ)-approximate solution (or (δ,ϵ)-solution) of problem (<ref>), if there exist b,a∈ℝ^n and ϵ^x,ϵ^y∈ℝ_+ such that the relations in (<ref>) hold. 




§ THE FAMILY OF PROJECTIVE SPLITTING METHODS


Our goal in this section is to establish the complexity analysis of the family of PSM developed in 
<cit.> for solving (<ref>). First, we will observe that the PSM is an instance of the general 
Algorithm <ref> with the feature of solving two proximal subproblems exactly, one involving only A and the other one only B, for obtaining the decomposable separator in step 2 of Algorithm <ref>. This will allow us to use the results of section <ref> to derive
general iteration-complexity bounds for the PSM. Such bounds will be expressed in terms of the parameter sequences {λ_k}, 
{μ_k}, {ρ_k} and {α_k}, calculated at each iteration of the method (see the PSM below). In 
subsection <ref>, we will specialize these results for the case where global convergence was obtained 
in <cit.>.


We start by stating the family of projective splitting methods (PSM).
[PSM]

Choose (z_0,w_0)∈^n×^n. For k=1,2,…


  1. Choose λ_k, μ_k>0 and α_k∈ℝ such that 

    μ_k/λ_k-(α_k/2)^2>0,

and find (x_k,b_k)∈B and (y_k,a_k)∈A such that

    λ_kb_k + x_k   = z_k-1 + λ_kw_k-1, 
    μ_ka_k + y_k   = (1-α_k)z_k-1 + α_kx_k - μ_kw_k-1.


  2. If a_k+b_k + x_k-y_k=0 stop. Otherwise, set

    γ_k = z_k-1-x_kb_k-w_k-1 + z_k-1-y_ka_k+w_k-1/a_k+b_k^2 + x_k-y_k^2.


  3. Choose a parameter ρ_k∈]0,2[ and set

    z_k =      z_k-1 - ρ_kγ_k(a_k+b_k),
    
    w_k =      w_k-1 - ρ_kγ_k(x_k-y_k).




Several remarks are in order. The PSM is the same as <cit.>, except for the stopping criterion in step 2 above and boundedness 
conditions imposed on the parameters ρ_k, λ_k and μ_k in <cit.>.  Note that if a_k+b_k+x_k-y_k=0 for some k, then x_k=y_k, b_k=-a_k and, since the points (x_k,b_k) and (y_k,a_k) are chosen in the graph of B and A, respectively, we have (x_k,b_k)∈AB. Therefore, when the PSM stops in step 2, it has found a point in the extended solution set.

Observe also that, since B is maximal monotone, Minty's theorem <cit.> implies that the resolvent mappings (I+λ_kB)^-1 are everywhere defined and single valued for all integer k≥1. Hence, by (<ref>) we have that the points x_k=(I+λ_k B)^-1(z_k-1+λ_kw_k-1) and b_k=(1/λ_k)(z_k-1-x_k)+w_k-1 exist and are unique. Similarly, the maximal monotonicity of A, together with (<ref>), guarantees the    existence    and    uniqueness    of    y_k=(I+μ_kA)^-1((1-α_k)z_k-1+α_kx_k-μ_kw_k-1)    and a_k=(1/μ_k)((1-α_k)z_k-1+α_kx_k)-w_k-1.

Moreover, if for k=1,2,…, we denote by ϕ_k the decomposable separator (see Definition <ref>) associated with the triplets (x_k,b_k,0) and (y_k,a_k,0), calculated in step 1 of the PSM, 
then the update rule in step 3 of the PSM can be restated as

    (z_k,w_k) = (z_k-1,w_k-1) - ρ_kγ_k∇ϕ_k.

Consequently, the family of PSM falls within the general framework of Algorithm <ref>, and the results of section <ref> apply.



Finally, note that the PSM generates, on each iteration, a pair (x_k,y_k) and vectors 
b_k, a_k∈^n such that the inclusions in (<ref>) hold with (x,b,ϵ^x)=(x_k,b_k,0) and (y,a,ϵ^y)=(y_k,a_k,0). Hence,
we can try to develop bounds for the quantities a_k+b_k and x_k-y_k to estimate when an iterate (x_k,y_k) is bound to satisfy the termination criterion (<ref>).

Before establishing the iteration-complexity results for the PSM, we need the following technical result.  

It presents two lower bounds for ϕ_k(z_k-1,w_k-1).



Let {(x_k,b_k)}, {(y_k,a_k)}, {(z_k,w_k)}, {λ_k}, {μ_k}, {α_k} and {ρ_k} be the sequences generated by the PSM, and {ϕ_k} be the 
sequence of decomposable separators associated with the PSM. Then, for all integer k≥1, the following inequalities hold

    ϕ_k(z_k-1,w_k-1) ≥θ_k/δ_k(a_k+b_k^2 + x_k-y_k^2),
       ϕ_k(z_k-1,w_k-1) ≥θ_k/μ_k(z_k-1-y_k^2 + w_k-1-b_k^2),

where δ_k:=μ_k+(1-α_k)λ_k>0 and θ_k>0 is the smallest eigenvalue of the matrix 

    ([           1 -λ_k|α_k|/2; -λ_k|α_k|/2      λ_kμ_k ]).




Inequality (<ref>) was obtained in <cit.> as part of the convergence proof of Algorithm 2 in <cit.>, as were the assertions that θ_k, δ_k>0 
under assumption (<ref>). Therefore, we only need to prove here relation (<ref>).

If we subtract y_k from both sides of (<ref>) and rearrange the terms we obtain

    x_k - y_k = z_k-1-y_k + λ_k(w_k-1-b_k).

Now, adding μ_kb_k to both sides of (<ref>) and rearranging we have

    μ_k(a_k+b_k)    = (1-α_k)z_k-1 + α_kx_k - y_k - μ_k(w_k-1-b_k)
       = α_k(x_k-y_k) + (1-α_k)(z_k-1-y_k) - μ_k(w_k-1-b_k).

Next, we substitute (<ref>) into (<ref>) and divide by μ_k to obtain

    a_k+b_k   = α_k/μ_k(z_k-1-y_k + λ_k(w_k-1-b_k)) + (1-α_k)/μ_k(z_k-1-y_k) - (w_k-1-b_k)
        = 1/μ_k(z_k-1-y_k) + (α_kλ_k/μ_k-1)(w_k-1-b_k).

Since

    ϕ_k(z_k-1,w_k-1) =    a_k+b_kz_k-1-y_k + x_k-y_kw_k-1-b_k,

equation above, together with (<ref>) and (<ref>), yields

    ϕ_k(z_k-1,w_k-1) =     1/μ_kz_k-1-y_k^2 + α_kλ_k/μ_kz_k-1-y_kw_k-1-b_k + λ_kw_k-1-b_k^2
    ≥    1/μ_kz_k-1-y_k^2 - |α_k|λ_k/μ_kz_k-1-y_kw_k-1-b_k + λ_kw_k-1-b_k^2
    
    =    1/μ_k([ z_k-1-y_k; w_k-1-b_k ])^T([           1 -λ_k|α_k|/2; -λ_k|α_k|/2      λ_kμ_k ])
    ([ z_k-1-y_k; w_k-1-b_k ]),

where the inequality in the above relation follows from the Cauchy-Schwartz inequality. Finally, (<ref>) follows from the expression above and the definition of θ_k.


For simplicity, the convergence rate results presented below suppose that the PSM never stops in step 2,
i.e. they are assuming that ∇ϕ_k>0 for all integer k≥1. However, they can easily be restated without assuming such condition by saying that either the conclusion stated below holds or  (x_k,b_k) is a point in AB.

Next result estimates the quality of the best iterate among (x_1,y_1),…,(x_k,y_k) in terms of the stopping criterion (<ref>). 
We refer to these estimates as pointwise complexity bounds for the PSM. 



Let {(x_k,b_k)}, {(y_k,a_k)}, {λ_k}, {μ_k}, {α_k}, {γ_k} and {ρ_k} be the sequences generated by the PSM. 
Then, for every integer k≥1, we have

    b_k∈ B(x_k),         a_k∈ A(y_k),

and there exists an index 1≤ i ≤ k such that

    a_i+b_i^2+x_i-y_i^2≤d_0^2/∑_j=1^kρ_j(2-ρ_j)(θ_j/δ_j)^2,

where d_0 is the distance of the first iterate (z_0,w_0) to AB, and θ_k and δ_k are defined in Lemma <ref>.



The assertions that b_k∈ B(x_k) and a_k∈ A(y_k) are direct consequences of step 1 in the PSM.
The definition of γ_j in step 2 of the method, together with the definition of ϕ_j  and inequality (<ref>), yields

    γ_j=ϕ_j(z_j-1,w_j-1)/∇ϕ_j^2≥θ_j/δ_j        for j=1,2,….

Therefore,

    γ_j^2≥(θ_jδ_j)^2          for j=1,2,….

Multiplying both sides of the inequality above by ρ_j(2-ρ_j)∇ϕ_j^2, adding from j=1 to k and using the first bound in (<ref>), we have

    d_0^2≥∑_j=1^k∇ϕ_j^2ρ_j(2-ρ_j)(θ_j/δ_j)^2.

Taking i such that

    i∈min_j=1,…,k(∇ϕ_j^2),

and using the previous inequality we obtain

    d_0^2≥∑_j=1^kρ_j(2-ρ_j)(θ_j/δ_j)^2∇ϕ_i^2.

Bound (<ref>) now follows from the above relation and noting that ∇ϕ_i=(a_i+b_i,x_i-y_i).


We will now derive alternative complexity bounds for the PSM. 
Using the sequences of ergodic iterates associated with the PSM, defined as in subsection <ref>, we will obtain convergence rates for the methods in the ergodic sense.  We refer to these kind of estimates as ergodic complexity bounds.

Define the sequences of ergodic means {(x_k,b_k,ϵ^x_k)} and {(y_k,a_k,ϵ^y_k)}, associated with
the sequences {(x_k,b_k,0)}, {(y_k,a_k,0)}, {γ_k} and {ρ_k} generated by the PSM, as in (<ref>), (<ref>) and (<ref>).
According to Lemma <ref>, we can attempt to bound the size of a_k+b_k, x_k-y_k, ϵ^x_k and 
ϵ^y_k, in order to know when the ergodic iterates {x_k} and {y_k} will meet the stopping condition (<ref>).



Assume the hypotheses of Theorem <ref>. In addition, consider the sequences of ergodic iterates {(x_k,b_k,ϵ^x_k)} and
{(y_k,a_k,ϵ^y_k)} associated with the sequences generated by the PSM, defined as in (<ref>), (<ref>) and (<ref>). Then, for every integer k≥1, we have

    b_k∈ B^ϵ^x_k(x_k),        a_k∈ A^ϵ^y_k(y_k),

and

    a_k+b_k≤2d_0/Γ_k,    x_k-y_k≤2d_0/Γ_k,      ϵ^x_k + ϵ^y_k≤d_0^2(ς_k+4)/Γ_k,

where 

    ς_k:=max_j=1,…,k{μ_j/θ_j(2-ρ_j)Γ_k}.




Inclusions in (<ref>) are a consequence of Lemma <ref>. The first two inequalities in (<ref>) are obtained by applying Theorem <ref>.

Now, we observe that relation (<ref>), together with the equality in (<ref>), implies

    μ_j/θ_j∇ϕ_j^2γ_j≥(y_j,b_j)-(z_j-1,w_j-1)^2      for  j=1,2,….

Multiplying the inequality above by 1Γ_kρ_jγ_j and adding from j=1 to k, we obtain

    1/Γ_k∑_j=1^kρ_jγ_j(y_j,b_j)-(z_j-1,w_j-1)^2≤    1/Γ_k∑_j=1^kμ_j/θ_jρ_jγ_j^2∇ϕ_j^2
    
    =     1/Γ_k∑_j=1^kμ_j/θ_j(2-ρ_j)ρ_j(2-ρ_j)γ_j^2∇ϕ_j^2
    ≤    (max_j=1,…,k{μ_j/θ_j(2-ρ_j)Γ_k})∑_j=1^kρ_j(2-ρ_j)γ_j^2∇ϕ_j^2
    ≤    (max_j=1,…,k{μ_j/θ_j(2-ρ_j)Γ_k})d_0^2,

where the last inequality above follows from the first estimate in (<ref>). We combine the relation above with (<ref>) and the definition 
of ς_k to deduce the last bound in (<ref>).




 §.§ Specialized Complexity Results

  
In this subsection, we will specialize the general pointwise and ergodic complexity bounds derived for the PSM in Theorems <ref> and <ref>, respectively, for the case where global convergence was obtained in <cit.>.

In <cit.>, it was proven convergence of the sequences {(x_k,b_k)}, {(y_k,-a_k)} and {(z_k,w_k)}, calculated by the PSM, to a point
of S_e(A,B) under the following assumptions:



  (A.1) there exist λ and λ such that, λ≥λ>0 and λ_k,μ_k∈[λ,λ] for all integer k≥1;

  (A.2) there exists ρ∈[0,1[ such that ρ_k∈[1-ρ,1+ρ] for all integer k≥1;

  (A.3) ν:=inf_k{μ_kλ_k-(α_k2)^2}>0.


Under hypotheses (A.1)-(A.3) we will show that the PSM has 𝒪(1/√(k)) pointwise convergence
rate, while the rate in the ergodic sense is 𝒪(1/k).



Let {(x_k,b_k)}, {(y_k,a_k)}, {λ_k}, {μ_k}, {α_k}, {γ_k} and {ρ_k} be the sequences generated by the PSM under assumptions (A.1)-(A.3).
If d_0 denote the distance of (z_0,w_0) to the extended solution set AB. Then, for all integer k≥1, we have

    b_k∈ B(x_k),         a_k∈ A(y_k),

and there exists an index 1≤ i≤ k such that

    a_i+b_i≤d_0υ/√(k)(1-ρ)      and      x_i-y_i≤d_0υ/√(k)(1-ρ),

where 

    υ:=2λ(1+λ^2)(1+√(λ/λ))/λ^2ν.




The inclusions in the statement of the theorem follow from (<ref>).
Now, we note that condition (A.2) implies

    ρ_j(2-ρ_j)≥(1-ρ)^2        for   j=1,2,….

Next, we observe that relation (<ref>) in step 1 of the PSM yields |α_j|≤2√(μ_j/λ_j). Hence, assumption (A.1) implies 

    |α_j|≤2√(λ/λ)          for   j=1,2,….

The inequality above, together with the definition of δ_j in Lemma <ref> and assumption (A.1), yields

    δ_j≤ 2λ(1+√(λ/λ)).

Moreover, in <cit.> it was proven that

    θ_j: =     1/2(1+λ_jμ_j-√((1+λ_jμ_j)^2-4(λ_jμ_j-(λ_jα_j/2)^2)))
    ≥    λ_j^2(μ_j/λ_j-(α_j/2)^2)/1+λ_jμ_j.

Thus, under hypotheses (A.1)-(A.3) we have 

    θ_j ≥λ^2ν/1+λ^2,

and combining (<ref>) with (<ref>) we obtain

    θ_j/δ_j≥λ^2ν/(1+λ^2)2λ(1+√(λ/λ))=1/υ        for   j=1,2,….

Now, from inequalities (<ref>) and (<ref>) we deduce that

    ρ_j(2-ρ_j)(θ_j/δ_j)^2≥(1-ρ)^2/υ^2

for j=1,…,k. Hence, adding equation above from j=1  to k we have

    ∑_j=1^kρ_j(2-ρ_j)(θ_j/δ_j)^2≥ k(1-ρ)^2/υ^2.

The theorem follows combining the above expression with inequality (<ref>).




Assume the hypotheses of Theorem <ref>. Consider the sequences of ergodic iterates {(x_k,b_k,ϵ^x_k)} and {(y_k,a_k,ϵ^y_k)} associated with the sequences generated by the PSM, defined as in (<ref>), (<ref>) and (<ref>). Then, for every integer k≥1, we have 

    b_k∈ B^ϵ^x_k(x_k),        a_k∈ A^ϵ^y_k(y_k),

and

    a_k+b_k≤2d_0υ/k(1-ρ),    x_k-y_k≤2d_0υ/k(1-ρ),    ϵ^x_k + ϵ^y_k≤d_0^2υ(υ'_k+4)/k(1-ρ),

where 
    υ'_k:=λ(1+λ^2)υ/λ^2ν(1-ρ)^2k.




The inclusions in (<ref>) follow from Lemma <ref>. The definition of Γ_k, together with assumption (A.2) and equation (<ref>), yields

    Γ_k≥ (1-ρ)∑_j=1^kθ_j/δ_j.

Therefore, by (<ref>) and the inequality above we have

    Γ_k≥(1-ρ)k/υ.

The first two bounds in (<ref>) now follow from (<ref>) and the first two inequalities in (<ref>).

To conclude the proof we observe that the definition of ς_k, hypothesis (A.1), (<ref>) and (<ref>) imply 

    ς_k ≤λ(1+λ^2)υ/λ^2ν(1-ρ)^2k.

Thus, combining the above relation with the last inequality in (<ref>), the definition of υ'_k and (<ref>), we obtain the last bound in (<ref>).



We emphasize here that the derived bounds obtained in Theorem <ref> are asymptotically better than the ones obtained in Theorem <ref>. Indeed, the bounds for x_k, y_k, a_k and b_k are 𝒪(1/√(k)), whereas for x_k, y_k, b_k, a_k, ϵ_k^x and ϵ_k^y the bounds are 𝒪(1/k). However, the iterates calculated by the PSM are points in the graph of A and B, while the ergodic iterates are in some outer approximation of the operators, namely they are points in an ϵ-enlargement of A and B.


The following result, which is an immediate consequence of Theorems <ref> and <ref>, presents complexity bounds for the PSM to obtain (δ,ϵ)-approximate solutions of problem (<ref>).


Assume the hypotheses of Theorem <ref>. Then, the following statements hold.

 
  (a) For every δ>0 there exists an index 
 
    i = 𝒪(d_0^2υ^2/δ^2)

such that the iterate (x_i,y_i) is a (δ,0)-solution of problem (<ref>). 
 
  (b) For every δ, ϵ>0 there exists an index
 
    k_0 = 𝒪(max{d_0υ/δ,d_0^2υ/ϵ})

 such that, for any k ≥ k_0, the ergodic iterate (x_k,y_k) is a (δ,ϵ)-solution of problem (<ref>). 
 




§ SPINGARN'S SPLITTING METHOD


In  this section, we study the iteration-complexity 
of the two-operator case of 
Spingarn's splitting algorithm. 
In <cit.>, Spingarn describes a partial inverse method for solving MIPs given by the sum of m maximal monotone operators.
Spingarn's method computes, at each iteration, 
independent proximal subproblems on each of the m operators involved in the problem and then finds the next iterate by essentially averaging the results. 
This algorithm is actually a special case of the Douglas-Rachford splitting method <cit.>, 
and it is also a particular instance of the general projective splitting methods for sums of m maximal monotone operators, which were introduced in <cit.>. 

Eckstein and Svaiter proved in <cit.> that the m=2 case of the Spingarn splitting method is a special case of a scaled variant of the PSM. 
Interpreting Spingarn's algorithm as an instance of the PSM allows us to use the analysis developed in the previous section for obtaining its complexity bounds. 

For this purpose, let us begin with a brief discussion of the reformulation of problem (<ref>) studied in <cit.>, obtained via including a scale factor.
If η>0 is a fixed scalar, multiplying both sides of (<ref>) by η gives the problem 

    0∈η A(z) + η B(z).

This simple reformulation leaves the solution set unchanged, but it transforms the set S_e(A,B). Indeed,
the extended solution set associated with operators η A and η B has the form

    η Aη B = {(z,η w):(z,w)∈AB}.


If we apply the PSM to η A and η B, and consider η a_k, η b_k and η w_k, respectively, in place of a_k, b_k and w_k, after some algebraic manipulations we obtain a scheme identical to the PSM, except that (<ref>)-(<ref>) are modified to

    λ_kη b_k + x_k = z_k-1 + λ_kη w_k-1,        b_k∈ B(x_k),
       μ_kη a_k + y_k = (1-α_k)z_k-1 + α_kx_k - μ_kη w_k-1,        a_k∈ A(y_k),
       γ_k=z_k-1-x_kb_k-w_k-1 + z_k-1-y_ka_k+w_k-1/ηa_k+b_k^2 + 1/ηx_k-y_k^2,
        z_k =  z_k-1 - ρ_kγ_kη(a_k+b_k),
        w_k =  w_k-1 - ρ_kγ_k/η(x_k-y_k).

The general pointwise and ergodic complexity bounds for the method above are obtained as a direct consequence of Theorems <ref> and <ref>, replacing a_i, b_i, a_k, b_k, ϵ^x_k and ϵ^y_k by η a_i, η b_i, ηa_k, ηb_k, ηϵ^x_k and ηϵ^y_k, respectively.

If η>0, in our notation, the Spingarn splitting method is reduced to the following set of recursions:

    η b_k + x_k = z_k-1 + η w_k-1,        b_k∈ B(x_k),
       η a_k + y_k = z_k-1 - η w_k-1,        a_k∈ A(y_k),
        z_k =  (1-ρ_k)z_k-1 + ρ_k/2(x_k+y_k),
        w_k = (1-ρ_k)w_k-1 + ρ_k/2(b_k-a_k).


Note that if we take λ_k=μ_k=1 and α_k=0 in (<ref>)-(<ref>) for all integer k≥1, then (<ref>)-(<ref>) and (<ref>)-(<ref>) are identical.
Moreover, the remaining calculations, (<ref>), (<ref>) and (<ref>), can be rewritten into the form (<ref>)-(<ref>), as it is established in the next result.



Assume that the following condition is satisfied:


  (B)    λ_k=μ_k=1 and α_k=0 in (<ref>)-(<ref>) for every integer k≥1.

Then, the recursions (<ref>)-(<ref>) and (<ref>)-(<ref>) are identical. Hence, Spingarn's method is a special case of the PSM.


This result was proven in <cit.>.


The following theorem derives the global convergence rate of Spingarn's splitting method in terms of the termination criterion (<ref>).


Let η>0 and let {(x_k,b_k)}, {(y_k,a_k)} and {ρ_k} be the sequences generated by Spingarn's splitting method (<ref>)-(<ref>). 
For every k≥1, define

    P_k := ∑_j=1^kρ_j,

and

    x_k := 1/P_k∑_j=1^kρ_jx_j,    b_k := 1/P_k∑_j=1^kρ_jb_j,    ϵ^x_k:=1/P_k∑_j=1^kρ_jx_j-x_kb_j,
       y_k := 1/P_k∑_j=1^kρ_jy_j,    a_k := 1/P_k∑_j=1^kρ_ja_j,    ϵ^y_k:=1/P_k∑_j=1^kρ_jy_j-y_ka_j.

Assume hypothesis (A.2) and set d_0:=(z_0,η w_0)η Aη B. Then, the following statements hold.


  (a) For every integer k≥1 we have

    b_k∈ B(x_k),         a_k∈ A(y_k),

and there exists an index 1≤ i≤ k such that 

    a_i+b_i≤2d_0/η√(k)(1-ρ),        x_i-y_i≤2d_0/√(k)(1-ρ).


  (b) For every integer k≥1 we have 

    b_k∈ B^ϵ^x_k(x_k),        a_k∈ A^ϵ^y_k(y_k),
 
and

    a_k+b_k≤4d_0/η k(1-ρ),            x_k-y_k≤4d_0/k(1-ρ),
    
       ϵ^x_k + ϵ^y_k≤2d_0^2/η k(1-ρ)(2/(1-ρ)^2+4).

 




  (a) By the definitions of δ_k and θ_k in the statement of Lemma <ref> and hypothesis (B), we have that δ_k=2 and θ_k=1 for every integer k≥1. 

Therefore, since Theorem <ref> gives that Spingarn's algorithm is a special case of (<ref>)-(<ref>) under assumption (B), the claims in (a) follow from assumption (A.2) and Theorem <ref> applied to (<ref>)-(<ref>) with α_k=0 and λ_k=μ_k=1.


  (b) The first assertions in (b) follow from the definitions of P_k, x_k, b_k, ϵ^x_k, y_k, a_k, ϵ^y_k in (<ref>), (<ref>) and (<ref>),
the inclusions in (<ref>), (<ref>) and Theorem <ref>.

Now, we observe that Theorem <ref> implies that the sequences {(x_k,η b_k)} and {(y_k, η a_k)} can be viewed as generated by the PSM applied to the operators 
η A and η B, with λ_k=μ_k=1 and α_k=0 for k=1,2,….
Moreover, in <cit.> it was proven under assumption (B) that γ_k, given in (<ref>), is equal to 1/2 for every integer k≥1. Therefore,  the sequences of ergodic iterates associated
with {(x_k,η b_k)}, {(y_k, η a_k)}, {ρ_k} and {γ_k}, which are obtained by equations (<ref>), (<ref>) and (<ref>) 
with Γ_k=(1/2)P_k, are exactly as defined in (<ref>) and (<ref>), but with ηb_k,
ηϵ^x_k, ηa_k and ηϵ^y_k instead of b_k,
ϵ^x_k, a_k and ϵ^y_k, respectively.

Hence, applying Theorem <ref> we have 

    η(a_k+b_k)≤2d_0/(1/2)P_k,    x_k-y_k≤2d_0/(1/2)P_k,      η(ϵ^x_k + ϵ^y_k) ≤d_0^2(ς_k+4)/(1/2)P_k,

where d_0 is the distance of (z_0,η w_0) to S_e(η A,η B) and ς_k=max_j=1,…,k{μ_jθ_j(2-ρ_j)(1/2)P_k}.

Next, we note that condition (A.2) yields ρ_j ≥ 1-ρ  for every j,
therefore by the definition of P_k we have 

    P_k≥ k(1-ρ).
 
Furthermore, since in this case μ_j=1, θ_j=1  and  2-ρ_j≥ 1-ρ  for all integer  j≥1, the definition of ς_k and (<ref>) imply

    ς_k≤2/(1-ρ)^2k≤2/(1-ρ)^2,        for    k=1,2,….

Hence, the remaining claims in (b) follow combining the bounds in (<ref>) with the inequality above and (<ref>).



Consider the sequences {x_k} and {y_k} generated by Spingarn's method and the sequences {x_k} and {y_k} defined in (<ref>) and (<ref>), respectively. Then, the following statements hold.

 
  (a) For every δ>0 there exists an index 
 
    i = 𝒪(max{d_0^2/η^2δ^2,d_0^2/δ^2})

such that the pair (x_i,y_i) is a (δ,0)-solution of problem (<ref>). 
 
  (b) For every δ, ϵ>0 there exists an index
 
    k_0 = 𝒪(max{d_0/ηδ, d_0/δ,d_0^2/ηϵ})

 such that, for any k ≥ k_0, the pair (x_k,y_k) is a (δ,ϵ)-solution of problem (<ref>). 
 




§ A PARALLEL INEXACT CASE



The PSM has to solve two proximal subproblems on each iteration, in order to construct decomposable separators.
Since finding the exact solution of subproblems (<ref>) and (<ref>) could be a challenging task, one might wish to allow approximate evaluations of
the resolvent mappings, while maintaining convergence of the method.

Our main goal in this section is to propose an inexact version of the PSM in the special case of taking α_k=0 for all iteration k, which possibly allows the subproblems to be performed in parallel. 

It is customary to appeal to the theory of approximation criteria for the PPA and related methods, when attempting to approximate solutions of proximal subproblems.
The first inexact versions of the PPA were introduced in <cit.> by Rockafellar and are based on absolute summable error criteria.
For instance, one of the approximation conditions proposed in <cit.> is

    z_k+1-(I+λ_kT)^-1(z_k)≤ s_k,         ∑_k=1^∞s_k<∞.

This kind of approximation criteria, which involves a theoretical sequence {s_k}⊂[0,∞[ 
such that ∑_k=1^∞s_k<∞, has as a practical disadvantage that there is no direct guidance as to how to select it when solving a specific problem.
Therefore, it is useful to construct error conditions for approximating
proximal subproblems that could be computable during the progress of the algorithm. 
Inexact versions of the PPA, which use relative error tolerance criteria of this kind, 
were developed in <cit.>. 

To solve subproblems (<ref>) and (<ref>) inexactly, we will use the notion of approximate solutions of a proximal subproblem proposed in <cit.> by Solodov and Svaiter.

The general projective splitting framework for the sum of m≥2 maximal monotone operators <cit.> admits a relative error condition for
approximately evaluating resolvents. 
The criterion used in <cit.> is a generalization for the case
of m maximal monotone operators of the relative error tolerance of the hybrid proximal extragradient method <cit.>. 
We have preferred the framework developed in <cit.> since it yields a more flexible error tolerance criterion and evaluation of the ϵ-enlargements of the operators.

We now present the notion of inexact solutions of a proximal subproblem introduced in <cit.>. Let T:ℝ^n⇉ℝ^n be a maximal monotone operator, 
λ>0 and z∈ℝ^n. Consider the proximal system

    {[       w∈ T(z'),; λ w + z' - z=0, ].

which is clearly equivalent to the proximal subproblem (<ref>).





Given σ∈[0,1[, a triplet (z',w,ϵ)∈𝔼 is called a σ-approximate solution of (<ref>) at (λ,z), if 

    w∈ T^ϵ(z'),
       λ w+z'-z^2 +2λϵ≤σ(λ w^2+z'-z^2).



We observe that if (z',w) is the exact solution of (<ref>) then, taking ϵ=0, the triplet (z',w,ϵ) satisfies the approximation criterion 
(<ref>) for all σ∈[0,1[. Conversely, if σ=0, only the exact solution of (<ref>), with ϵ=0, will satisfy (<ref>).

The method that will be studied in this section is as follows.



Note that for all iteration k, the triplet (x_k,b_k,ϵ^x_k) calculated in step 1 of Algorithm <ref> is a σ-approximate solution of (<ref>) at (λ_k,z_k-1),
where T=B-w_k-1. Similarly, (y_k,a_k,ϵ^y_k) is a σ-approximate solution of (<ref>) (with T=A+w_k-1) at point (μ_k,z_k-1).
Observe also that taking σ=0 in Algorithm <ref> yields exactly the PSM with α_k=0 for all integer k≥1, since condition (<ref>) is satisfied.

Let us denote by ϕ_k the decomposable separator associated with the pair (x_k,b_k,ϵ^x_k) and (y_k,a_k,ϵ^y_k), for every integer k≥1 (see Definition <ref>).
It will be shown in the following lemma that if Algorithm <ref> stops in step 2 at iteration k, then it has found a point in S_e(A,B). Otherwise we will have ∇ϕ_k>0, which gives
ϕ_k(z_k-1,w_k-1)>0. This clearly implies that Algorithm <ref> falls within the general framework of Algorithm <ref>. 



Let {(x_k,b_k,ϵ^x_k)}, {(y_k,a_k,ϵ^y_k)}, {(z_k,w_k)}, {λ_k}, {μ_k} and {ρ_k} be the sequences generated by Algorithm <ref>, and 
{ϕ_k} be the sequence of decomposable separators associated with Algorithm <ref>. Then, for every integer k≥1, we have

    ϕ_k(z_k-1,w_k-1)≥1-σ/4ξ_k(a_k+b_k^2+x_k-y_k^2)≥0,

where 

    ξ_k:=min{λ_k,1/λ_k,μ_k,1/μ_k}.

If ∇ϕ_k>0, then it follows that ϕ_k(z_k-1,w_k-1)>0. Furthermore, ∇ϕ_k=0 if and only if (x_k,b_k)=(y_k,-a_k)∈AB.



From the definition of ϕ_k and direct calculations it follows that

    ϕ_k(z_k-1,w_k-1) =      z_k-1-x_kb_k-w_k-1 + z_k-1-y_ka_k+w_k-1 - ϵ^x_k - ϵ^y_k
    
    =      1/2λ_k(z_k-1-x_k^2 + λ_k(b_k-w_k-1)^2 - r^x_k^2 - 2λ_kϵ^x_k)
          + 1/2μ_k(z_k-1-y_k^2 + μ_k(a_k+w_k-1)^2 - r^y_k^2 - 2μ_kϵ^y_k).

The identity above, together with the error criteria (<ref>) and (<ref>), implies 

    ϕ_k(z_k-1,w_k-1)≥    1-σ/2λ_k(z_k-1-x_k^2 + λ_k(b_k-w_k-1)^2)
         + 1-σ/2μ_k(z_k-1-y_k^2 + μ_k(a_k+w_k-1)^2).

If   we   interpret   this   last   expression   as   a   quadratic   form   applied   to   the   ℝ^4   vector

(z_k-1-x_k,b_k-w_k-1,z_k-1-y_k,a_k+w_k-1)^T, we obtain 

    ϕ_k(z_k-1,w_k-1) ≥    1-σ/2([ z_k-1-x_k; w_k-1-b_k; z_k-1-y_k; w_k-1+a_k ])^T([ 1/λ_k     0     0     0;     0   λ_k     0     0;     0     0 1/μ_k     0;     0     0     0   μ_k ])
    ([ z_k-1-x_k; w_k-1-b_k; z_k-1-y_k; w_k-1+a_k ])
    ≥    1-σ/2ξ_k(z_k-1-x_k^2+b_k-w_k-1^2+z_k-1-y_k^2+a_k+w_k-1^2),

where ξ_k, defined in (<ref>), is the smallest eigenvalue of the matrix in (<ref>).

Now, we combine the second inequality in (<ref>) with relations 

    z_k-1-x_k^2+z_k-1-y_k^2≥1/2x_k-y_k^2,
 
    b_k-w_k-1^2+a_k+w_k-1^2≥1/2a_k+b_k^2;

to obtain the first inequality in (<ref>). Since ξ_k>0 and σ∈[0,1[, the second inequality in (<ref>) follows directly. Furthermore, these last relations, together with equation (<ref>), clearly imply that ϕ_k(z_k-1,w_k-1)>0 whenever ∇ϕ_k>0.

To prove the last assertion of
the lemma we rewrite ϕ_k(z_k-1,w_k-1) as

    ϕ_k(z_k-1,w_k-1) = a_k+b_kz_k-1-y_k + x_k-y_kw_k-1-b_k - ϵ^x_k - ϵ^y_k.

Then, if ∇ϕ_k=0, it follows that x_k=y_k, b_k=-a_k and 

    ϕ_k(z_k-1,w_k-1)= - ϵ^x_k - ϵ^y_k.
 
From equation (<ref>), the equality above and the fact that ϵ^x_k, ϵ^y_k≥0, we obtain ϵ^x_k=ϵ^y_k=0. Hence,
b_k∈ B(x_k), a_k∈ A(y_k) and we conclude that (x_k,b_k)=(y_k,-a_k)∈AB.


For deriving complexity bounds for Algorithm <ref> we will assume, as was done in the preceding section,
that the method does not stop in a finite number of iterations. Thus, from now on we suppose that ∇ϕ_k>0 for all integer k≥1.

Next result establishes pointwise complexity bounds for Algorithm <ref>.



Take (z_0,w_0)∈^n×^n and let  {(x_k,b_k,ϵ^x_k)}, {(y_k,a_k,ϵ^y_k)}, {λ_k}, {μ_k}, {γ_k} and {ρ_k} be the sequences generated by Algorithm <ref>. 
Let d_0 be the distance of (z_0,w_0) to the set AB and, for all integer k≥1, define ξ_k by (<ref>). Then, for every integer k≥1, we have 

    b_k∈ B^ϵ^x_k(x_k),         a_k∈ A^ϵ^y_k(y_k),

and there exists an index 1≤ i≤ k such that 

    a_i+b_i^2 + x_i-y_i^2≤    16d_0^2/(1-σ)^2(1-ρ)^2ξ_i∑_j=1^kξ_j,
    
    ϵ^x_i + ϵ^y_i≤    4σ d_0^2/(1-σ)^2(1-ρ)^2∑_j=1^kξ_j.




The inclusions in (<ref>) are due to step 1 of Algorithm <ref>. Since γ_k=ϕ_k(z_k-1,w_k-1)∇ϕ_k^2, using (<ref>) we have 

    γ_k≥1-σ/4ξ_k      for  k=1,2,….

Thus, squaring both sides of (<ref>) and multiplying by ∇ϕ_k^2 we obtain

    γ_k^2∇ϕ_k^2≥(1-σ/4)^2ξ_k^2∇ϕ_k^2.

Now, we observe that the error criteria (<ref>) and (<ref>) imply

    ϵ^x_k≤σ/2λ_k(z_k-1-x_k^2 + λ_k(b_k-w_k-1)^2)

and

    ϵ^y_k≤σ/2μ_k(z_k-1-y_k^2 + μ_k(a_k+w_k-1)^2),

respectively. 
Adding these two inequalities and combining with relation (<ref>) we obtain 

    ϵ^x_k + ϵ^y_k≤σ/1-σϕ_k(z_k-1,w_k-1)= σ/1-σγ_k∇ϕ_k^2.

Multiplying the latter inequality by γ_k, using (<ref>) and multiplying both sides of the resulting expression by 1-σσ, we have

    (1-σ)^2/4σξ_k(ϵ^x_k + ϵ^y_k) ≤γ_k^2∇ϕ_k^2      for   k=1,2,….


Now, we define

    ψ_k := max{(1-σ/4)^2ξ_k∇ϕ_k^2,(1-σ)^2/4σ(ϵ^x_k+ϵ^y_k)},

and combine (<ref>) with (<ref>) to obtain

    ξ_kψ_k≤γ_k^2∇ϕ_k^2        for   k=1,2,….

Next, adding the inequality above from j=1 to k, using the assumption that ρ_k∈[1-ρ,1+ρ] for all integer k≥1 and the first inequality in (<ref>), we have

    ∑_j=1^kξ_jψ_j≤d_0^2/(1-ρ)^2,

 and consequently

    (min_j=1,…,k{ψ_j})∑_j=1^kξ_j≤d_0^2/(1-ρ)^2.

The theorem now follows from this last inequality and the definition of ψ_k.


If  {(x_k,b_k,ϵ^x_k)}, {(y_k,a_k,ϵ^y_k)}, {γ_k} and {ρ_k} are the sequences generated by Algorithm <ref>,
we consider their associated sequences of ergodic iterates {(x_k,b_k,ϵ^x_k)} and {(y_k,a_k,ϵ^y_k)}, defined as in (<ref>),
(<ref>) and (<ref>). Since Algorithm <ref> is a special instance of Algorithm <ref>, the results of subsection <ref> hold for its ergodic sequences. 
Thus, combining Theorem <ref> and Lemma <ref> we can derive ergodic complexity estimates for the method.



Let {(x_k,b_k,ϵ^x_k)}, {(y_k,a_k,ϵ^y_k)}, {γ_k} and {ρ_k} be the sequences generated by Algorithm <ref>. Let 
{(x_k,b_k,ϵ^x_k)} and {(y_k,a_k,ϵ^y_k)} be the sequences of ergodic iterates associated with 
Algorithm <ref>, defined as in (<ref>)-(<ref>), and consider ξ_k given by (<ref>). Then, for all integer k≥1, we have

    b_k∈ B^ϵ^x_k(x_k),        a_k∈ A^ϵ^y_k(y_k)

and

    a_k+b_k≤2d_0/Γ_k,    x_k-y_k≤2d_0/Γ_k,      ϵ^x_k + ϵ^y_k≤d_0^2(φ_k+4)/Γ_k,

where d_0 is the distance of (z_0,w_0) to AB and 

    φ_k:=(2/1-σ)max_j=1,…,k{1/ξ_j(2-ρ_j)Γ_k}.




The inclusions in (<ref>) follow from Lemma <ref>. The first two bounds in (<ref>) are due to (<ref>) in Theorem <ref>. 

Now, we note that the second inequality in (<ref>) implies

    (z_j-1-y_j^2+b_j-w_j-1^2)1-σ/2ξ_j≤ϕ_j(z_j-1,w_j-1)    for  j=1,2,….

The relation above, together with the definition of γ_j, yields

    z_j-1-y_j^2+b_j-w_j-1^2≤2/(1-σ)ξ_jγ_j∇ϕ_j^2    for  j=1,2,….

Multiplying the above inequality by 1Γ_kρ_jγ_j and adding from j=1 to k, we obtain

    1/Γ_k∑_j=1^kρ_jγ_j(y_j,b_j)-(z_j-1,w_j-1)^2≤    1/Γ_k∑_j=1^k2/(1-σ)ξ_jρ_jγ_j^2∇ϕ_j^2
    
    =     1/Γ_k∑_j=1^k2/(1-σ)ξ_j(2-ρ_j)ρ_j(2-ρ_j)γ_j^2∇ϕ_j^2
    ≤    φ_k∑_j=1^kρ_j(2-ρ_j)γ_j^2∇ϕ_j^2
    ≤    φ_kd_0^2,

where the second and the third inequalities are due to the definition of φ_k and the first bound in (<ref>), respectively. 
Substituting equation above into (<ref>) we obtain the last bound in (<ref>).


Theorems <ref> and <ref> provide general complexity results for Algorithm <ref>.
Observe that the derived bounds are expressed in terms of ξ_k and Γ_k. Next result, which is a direct consequence of these theorems, presents iteration-complexity
bounds for Algorithm <ref> to obtain (δ,ϵ)-approximate solutions of problem (<ref>).

 
 
 Assume the hypotheses of Theorem <ref>. Assume also condition (A.1) and
 define ξ:=min{λ,1λ}. Then, for all δ, ϵ>0, the following statements hold.
 
 
  (a) There exists an index 
 
    i = 𝒪(max{d_0^2/ξ^2δ^2,d_0^2/ξϵ})

such that the iterate (x_i,y_i) is a (δ,ϵ)-solution of problem (<ref>). 
 
  (b) There exists an index
 
    k_0 = 𝒪(max{d_0/ξδ,d_0^2/ξϵ})

 such that, for any k ≥ k_0, the ergodic iterate (x_k,y_k) is a (δ,ϵ)-solution of problem (<ref>). 
 
 


We first note that assumption (A.1) implies

    ξ_j≥ξ        for   j=1,2,….

Now, we combine the definition of Γ_k in (<ref>) with (<ref>) and (<ref>) to obtain
 
    Γ_k≥ k(1-ρ)ξ(1-σ)/4.

Furthermore, the inequality above, together with (<ref>) and the definition of φ_k, yields 
 
    φ_k≤8/(1-ρ)^2(1-σ)^2ξ^2.

We conclude the proof combining Theorems <ref> and <ref> with these three relations above. 


 


§ A SEQUENTIAL INEXACT CASE


In this section, we propose an inexact variant of a sequential case of the PSM and study its iteration-complexity. We observe that, unless α_k=0, subproblems (<ref>) and (<ref>) cannot
be solved in parallel. For example, if we specialize the PSM by setting α_k=1 for all k, we have to perform on each iteration the following steps

    λ_kb_k + x_k   = z_k-1 + λ_kw_k-1,       b_k∈ B(x_k),
    
    μ_ka_k + y_k   = x_k - μ_kw_k-1,       a_k∈ A(y_k).

Therefore, the first problem above must be solved after the second one; these steps cannot be performed simultaneously like the proximal subproblems of Algorithm <ref>. However,
this choice of α_k could be an advantage since the second subproblem uses more recent information, that is x_k instead of z_k-1. 

In this section, we are assuming that the resolvent mappings of operator B are easy to evaluate, but this is not the case for the proximal mappings associated with operator A. Such situations are typical in practice even in the case of convex optimization. Indeed, if A=∂ f and B=∂ g are the subdifferential operators of functions f and g, where f and g are proper, convex and lower semicontinuous, then the solutions of the MIP (<ref>) are minimizers of the sum f+g. In this case, 
in order to evaluate 
the resolvent mapping (I+λ A)^-1=(I+λ∂ f)^-1, it is necessary to solve a strongly convex minimization problem and, if f has a complicated algebraic expression, such problem could be hard to solve exactly. Therefore, it is desirable to admit inexact solutions of the proximal subproblems associated with this operator.

With these assumptions, we propose the following modification of the specific case of the PSM where α_k=1 for all iteration k. Specifically, in Algorithm <ref> below we allow the solution of the second proximal subproblem to be approximated, provided that the approximate solution satisfies the relative error condition of Definition <ref>.



We note that the maximum tolerance for the relative error in the resolution of (<ref>)-(<ref>) is 1/2, instead of 1 as in Algorithm <ref>.
We also note that the proximal parameter in step 1 of Algorithm <ref> is not allowed to change from one subproblem to another within an iteration.

For every integer k≥1 denote by ϕ_k the decomposable separator associated with the triplets (x_k,b_k,0) and (y_k,a_k,ϵ^y_k), calculated in step 1 of Algorithm <ref> (see Definition <ref>).
It is thus clear that if ϕ_k(z_k-1,w_k-1)>0 for all integer k≥1, then Algorithm <ref> is an instance of the general scheme presented in section <ref>.

The following lemma implies that Algorithm <ref> stops in step 2 when it has found a point in the extended solution set AB.



Let {(x_k,b_k)}, {(y_k,a_k,ϵ^y_k)}, {(z_k,w_k)}, {λ_k} and {ρ_k} be the sequences generated by Algorithm <ref>, 
and {ϕ_k} be the sequence of decomposable separators associated with Algorithm <ref>. Then, for all integer k≥1, we have

    ϕ_k(z_k-1,w_k-1)≥1-2σ/2τ_k(a_k+b_k^2+x_k-y_k^2)≥0,

where 

    τ_k:=min{λ_k,1/λ_k}.

If ∇ϕ_k>0, then it follows that ϕ_k(z_k-1,w_k-1)>0. Furthermore, ∇ϕ_k=0 if and only if (x_k,b_k)=(y_k,-a_k)∈AB.




Since 

    ϕ_k(z_k-1,w_k-1)=z_k-1-x_kb_k-w_k-1  + z_k-1-y_ka_k+w_k-1 - ϵ^y_k,

adding and subtracting x_ka_k+w_k-1 on the right-hand side of this equation and regrouping the terms, we obtain

    ϕ_k(z_k-1,w_k-1)=    z_k-1-x_kb_k+a_k  + x_k-y_ka_k+w_k-1 - ϵ^y_k
    
    =     λ_kb_k-w_k-1b_k+a_k + 1/2λ_k[x_k-y_k^2+λ_k(a_k+w_k-1)^2]
        - 1/2λ_k[r_k^2 + 2λ_kϵ^y_k],

where we have used in the last equality the identity in (<ref>) and r_k is given in (<ref>). We observe that 

    λ_kb_k-w_k-1b_k+a_k = λ_k/2[b_k-w_k-1^2+b_k+a_k^2-a_k+w_k-1^2].

Hence, combining equality above with (<ref>) and the error criterion (<ref>) we have

    ϕ_k(z_k-1,w_k-1)≥λ_k/2b_k-w_k-1^2 + λ_k/2a_k+b_k^2 + 1-σ/2λ_kx_k-y_k^2 - σλ_k/2a_k+w_k-1^2.

Since a_k+w_k-1^2≤2a_k+b_k^2+2b_k-w_k-1^2, we deduce that

    ϕ_k(z_k-1,w_k-1)≥λ_k(1-2σ)/2b_k-w_k-1^2 + λ_k(1-2σ)/2a_k+b_k^2 + 1-σ/2λ_kx_k-y_k^2.

The inequalities in (<ref>) now follow from the relation above, the definition of τ_k and noting that 1-σ≥1-2σ>0.

The claim that ∇ϕ_k>0 implies ϕ_k(z_k-1,w_k-1)>0 is obtained as a direct consequence of (<ref>). To prove the remaining assertion of the lemma we observe
that if ∇ϕ_k=0, then x_k=y_k, b_k=-a_k and it follows from (<ref>), the first equality in (<ref>) and the fact that ϵ^y_k∈_+, that ϵ^y_k=0.
Thus, we have (x_k,b_k)∈AB.


From now on we assume that Algorithm <ref> generates infinite sequences {x_k} and {y_k}, which is equivalent to ∇ϕ_k>0 for every integer k≥1. 

We are now ready to establish pointwise iteration-complexity bounds for Algorithm <ref>.
The theorem below will be proven in much the same way as Theorem <ref>, using Lemma <ref> instead of Lemma <ref>. 



Take (z_0,w_0)∈^n×^n and let  {(x_k,b_k)}, {(y_k,a_k,ϵ^y_k)}, {λ_k}, {γ_k} and {ρ_k} be the sequences generated by Algorithm <ref>. 
Let d_0 be the distance of (z_0,w_0) to AB and, for all integer k≥1, let τ_k be given by (<ref>). Then, for every integer k≥1, we have

    b_k∈ B(x_k),         a_k∈ A^ϵ^y_k(y_k),

and there exists an index 1≤ i≤ k such that 

    a_i+b_i^2 + x_i-y_i^2≤    4d_0^2/(1-2σ)^2(1-ρ)^2τ_i∑_j=1^kτ_j,
    
    ϵ^y_i≤    4σ d_0^2/(1-2σ)^2(1-ρ)^2∑_j=1^kτ_j.




The inclusions in (<ref>) are due to step 1 of Algorithm <ref>. It follows from the definition of γ_k and inequality (<ref>) that

    γ_k≥(1-2σ/2)τ_k      for  k=1,2,….

Squaring both sides of the above inequality and multiplying by ∇ϕ_k^2 we obtain

    γ_k^2∇ϕ_k^2≥(1-2σ/2)^2τ_k^2∇ϕ_k^2,      for  k=1,2,….

Now, we note that the error criterion (<ref>) implies

    ϵ^y_k≤σ/2λ_k[x_k-y_k^2+λ_k(a_k+b_k)^2].

Consequently, we have

    ϵ^y_k≤σ/2λ_kx_k-y_k^2+σλ_ka_k+w_k-1^2 +σλ_kb_k-w_k-1^2.

The above inequality, together with (<ref>), yields

    ϵ^y_k≤2σ/1-2σϕ_k(z_k-1,w_k-1).

Next, multiplying the above relation by γ_k and combining with (<ref>), after some manipulations, we obtain

    (1-2σ)^2/4στ_kϵ^y_k≤γ_k^2∇ϕ_k^2.

Finally, defining

    ψ_k:=max{(1-2σ)^2/4τ_k∇ϕ_k^2,(1-2σ)^2/4σϵ^y_k}

and using (<ref>) and (<ref>), we can conclude the proof proceeding analogously to the proof of Theorem <ref>.


The following theorem presents complexity estimates in the ergodic sense for Algorithm <ref>.



Let {(x_k,b_k)}, {(y_k,a_k,ϵ^y_k)}, {γ_k} and {ρ_k} be the sequences generated by Algorithm <ref>. Let 
{(x_k,b_k,ϵ^x_k)} and {(y_k,a_k,ϵ^y_k)} be the associated sequences of ergodic iterates, defined as in (<ref>)-(<ref>), and consider τ_k given by (<ref>). Then, for all integer k≥1, we have

    b_k∈ B^ϵ^x_k(x_k),        a_k∈ A^ϵ^y_k(y_k),

and

    a_k+b_k≤2d_0/Γ_k,    x_k-y_k≤2d_0/Γ_k,      ϵ^x_k + ϵ^y_k≤d_0^2(ϑ_k+4)/Γ_k,

where d_0 is the distance of (z_0,w_0) to AB and 

    ϑ_k:=max_j=1,…,k{8/τ_j(1-2σ)(2-ρ_j)Γ_k}.




Since Algorithm <ref> is an instance of Algorithm <ref>, Lemma <ref> and Theorem <ref> apply, therefore the inclusions in (<ref>) and the first two inequalities in (<ref>) follow.

We derive now an estimate for the sum on the right-hand side of (<ref>). We note that (<ref>) implies

    ϕ_j(z_j-1,w_j-1)≥λ_j(1-2σ/2)b_j-w_j-1^2

for all integer j≥1. We also note that 

    z_j-1-y_j=z_j-1-x_j+x_j-y_j=λ_j(b_j-w_j-1)+x_j-y_j,

where the last identity is due to the equality in (<ref>). This last expression and the triangle inequality for norms yield

    z_j-1-y_j≤λ_jb_j-w_j-1+x_j-y_j.

Moreover, squaring both sides of the inequality above and making some manipulations, we obtain

    1/2λ_jz_j-1-y_j^2   ≤λ_jb_j-w_j-1^2+1/λ_jx_j-y_j^2
       ≤2/1-2σϕ_j(z_j-1,w_j-1),

where the last inequality follows from (<ref>). Now, adding (<ref>) and (<ref>) we have

    1/2λ_jz_j-1-y_j^2+λ_jb_j-w_j-1^2≤4/1-2σϕ_j(z_j-1,w_j-1).

The above relation, together with the definitions of γ_j and τ_j, implies

    b_j-w_j-1^2 + z_j-1-y_j^2≤8/(1-2σ)τ_jγ_j∇ϕ_j^2.

Multiplying both sides of the above inequality by 1Γ_kρ_jγ_j and adding from j=1 to k, we obtain the desired estimate, i.e.

    1Γ_k∑_j=1^kρ_jγ_j[b_j-w_j-1^2 + z_j-1-y_j^2]    ≤1Γ_k∑_j=1^k8/(1-2σ)τ_jρ_jγ_j^2∇ϕ_j^2
       = 1Γ_k∑_j=1^k8/(1-2σ)τ_j(2-ρ_j)ρ_j(2-ρ_j)γ_j^2∇ϕ_j^2
       ≤ϑ_k∑_j=1^kρ_j(2-ρ_j)γ_j^2∇ϕ_j^2
       ≤ϑ_kd_0^2,

where the second and the third inequalities above follow from the definition of ϑ_k and (<ref>), respectively.
The proof of the last bound in (<ref>) now follows combining the above relation with (<ref>).


Next result provides complexity bounds for Algorithm <ref> to find a (δ,ϵ)-approximate solution of problem 
(<ref>).

It may be proven in much the same way as Theorem <ref> and for the sake of brevity we omit the proof here. 


Assume the hypotheses of Theorem <ref>. Suppose also that there exist λ and λ such that λ≥λ>0 and
λ_k∈[λ,λ], for all integer k≥1, and define τ:=min{λ,1λ}. Then, for every δ, ϵ>0, the following claims hold.


  (a) There exists an index 

    i = 𝒪(max{d_0^2/τ^2δ^2,d_0^2/τϵ})

such that the point (x_i,y_i) calculated by Algorithm <ref> is a (δ,ϵ)-approximate solution of problem (<ref>).

  (b) There exists an index

    k_0 = 𝒪(max{d_0/τδ,d_0^2/τϵ})

such that, for any k ≥ k_0, the ergodic iterate (x_k,y_k) is a (δ,ϵ)-approximate solution of problem (<ref>).





§ CONCLUSIONS

We introduced a general projective splitting scheme for solving monotone inclusion problems given by the sum of two maximal monotone operators, which generalizes the family of projective splitting methods (PSM) proposed by Eckstein and Svaiter. Using this general framework we analyzed the iteration-complexity of the family of PSM and, as a consequence, we obtained the iteration-complexity of the two-operator case of the Spingarn partial inverse method. We introduced two inexact variants of two special cases of the family of PSM, which allow the resolvent mappings to be solved inexactly. We also proved the iteration-complexity for the above-mentioned methods.





Acknowledgments    This work is part of the author's Ph.D. thesis, written under the supervision of Benar Fux Svaiter at IMPA, and supported by CAPES and FAPERJ.

spmpsci_unsrt


