MSC2020: 47J25, 47H05, 47J22, 49J53.
Introduction
Let H \mathcal{H} H be a real Hilbert space and let A : H ⇒ H A:\mathcal{H}\Rightarrow\mathcal{H} A : H ⇒ H . We study the relaxed preconditioned proximal point algorithm (PPPA)
x ˉ k ∈ ( P + A ) − 1 P x k , x k + 1 = x k + λ k ( x ˉ k − x k ) , (1) \bar{x}^{k}\in(P+A)^{-1}Px^{k},\qquad x^{k+1}=x^{k}+\lambda_k(\bar{x}^{k}-x^{k}), \tag*{(1)} x ˉ k ∈ ( P + A ) − 1 P x k , x k + 1 = x k + λ k ( x ˉ k − x k ) , (1)
for finding a zero of A A A , where P P P is bounded, self-adjoint, and positive semidefinite. We call { x ˉ k } \{\bar{x}^{k}\} { x ˉ k } the shadow sequence . For P = γ − 1 Id P=\gamma^{-1}\operatorname{Id} P = γ − 1 Id and λ k ≡ 1 \lambda_k\equiv1 λ k ≡ 1 , this is the classical proximal point method of Martinet [23 ] and Rockafellar [26 ] . Degenerate preconditioners arise naturally in operator splitting: Douglas–Rachford splitting, Chambolle–Pock at the critical stepsize, and graph-based splitting schemes [5 ] admit such representations. Further examples of such representations are given in [12 ] .
A systematic Hilbert-space theory of degenerate PPPA for monotone inclusions was developed by Bredies–Chenchene–Lorenz–Naldi [4 ] through a reduction to the range of P P P and a parallel composition. Their framework also accommodates monotonicity restricted to graph points whose operator values lie in ran P \operatorname{ran} P ran P , a condition further studied by Xue–Zhang [28 ] . Beyond monotonicity, nondegenerate proximal methods have been studied under cohypomonotonicity [7 ] , negative and star-negative comonotonicity [15 ] , and submonotonicity [20 ] . A local nonmonotone PPPA analysis with matrix-valued relaxation also yields extensions of Spingarn’s method and progressive decoupling [13 ] . For degenerate PPPA, Evens–Pas–Latafat–Patrinos [12 ] developed a finite-dimensional analysis under an oblique weak Minty condition, with applications to Douglas–Rachford and Chambolle–Pock [11 ] .
A common basis for comparing these assumptions is the framework of ( U , V ) (U,V) ( U , V ) -semimonotonicity [1 , 11 , 12 ] . Here, U U U and V V V are self-adjoint operators, which we refer to as the monotonicity modulus and comonotonicity modulus , respectively. The pairwise condition requires ⟨ x − y , a − b ⟩ ≥ ⟨ x − y , U ( x − y ) ⟩ + ⟨ a − b , V ( a − b ) ⟩ \langle x-y,a-b\rangle\ge\langle x-y,U(x-y)\rangle+\langle a-b,V(a-b)\rangle ⟨ x − y , a − b ⟩ ≥ ⟨ x − y , U ( x − y )⟩ + ⟨ a − b , V ( a − b )⟩ for every ( x , a ) , ( y , b ) ∈ gra A (x,a),(y,b) \in\operatorname{gra} A ( x , a ) , ( y , b ) ∈ gra A . In this work, we consider its solution-relative counterpart, which requires the inequality only when ( y , b ) = ( x ⋆ , 0 ) (y,b)=(x^\star,0) ( y , b ) = ( x ⋆ , 0 ) for prescribed x ⋆ x^\star x ⋆ in a nonempty set S ⋆ ⊆ zer A S^\star\subseteq\operatorname{zer} A S ⋆ ⊆ zer A . The solution-relative condition with U = 0 U=0 U = 0 recovers the V V V -oblique weak Minty condition studied in the finite-dimensional setting in [12 ] , which need not imply monotonicity even when V = 0 V=0 V = 0 . Allowing a negative monotonicity modulus U U U further enlarges this class. Table 1 summarizes the operator assumptions and convergence guarantees of representative PPA and PPPA analyses.
Table 1. Comparison of operator assumptions and convergence guarantees for PPA and PPPA.
Approach and main ideas
Building on the reduced-space formulation of [4 ] , we study degenerate PPPA for possibly nonmonotone inclusions by treating its reduced dynamics as a forward method. When P P P has closed range R : = ran P \mathcal{R}:=\operatorname{ran} P R := ran P , the factorization P = C C ∗ P=CC^* P = C C ∗ gives reduced variables z k : = C ∗ x k z^k:=C^*x^k z k := C ∗ x k and residuals q k : = C ∗ ( x k − x ˉ k ) q^k := C^*(x^k-\bar{x}^k) q k := C ∗ ( x k − x ˉ k ) satisfying
z k + 1 = z k − λ k q k , where q k ∈ F ( z k ) , z^{k+1}=z^k-\lambda_k q^k,\qquad\text{where}\quad q^k\in F(z^k), z k + 1 = z k − λ k q k , where q k ∈ F ( z k ) ,
and F F F is the complementary resolvent of a parallel composition of A A A by C ∗ C^* C ∗ . This representation holds as an identity of set-valued mappings, without requiring monotonicity or admissibility (see Proposition 4.2 ). Moreover, relative semimonotonicity of either A A A (or its range-restricted graph A R ( x ) : = A x ∩ R A_R(x):=Ax\cap R A R ( x ) := A x ∩ R ) transfers to F F F naturally (see Lemma 4.3 ). This motivates us to develop a general convergence theory for forward iterations of possibly set-valued, relatively semimonotone mappings. Extending classical estimates for single-valued quasi-cocoercive mappings (cf. Definition 2.1(ii)) in [9 , 24 ] , the theory yields Fejér estimates and residual rates under adaptive stepsize. It also establishes strong and linear convergence when the monotonicity modulus of the forward map is strongly monotone, and local linear rates under metric subregularity even when this modulus is bounded below by a negative multiple of the identity.
The reduced variables z k = C ∗ x k z^k=C^*x^k z k = C ∗ x k and z k − q k = C ∗ x ˉ k z^k-q^k=C^*\bar{x}^k z k − q k = C ∗ x ˉ k encode, respectively, the projected PPPA iterates Π R x k \Pi_Rx^k Π R x k and projected shadows Π R x ˉ k \Pi_R\bar{x}^k Π R x ˉ k . The forward theory yields Fejér monotonicity and, under suitable parameter conditions, q k → 0 q^k\to0 q k → 0 . Consequently, both projected sequences are bounded, and their difference converges strongly to zero. However, these conclusions do not ensure that their weak cluster points are projections of zeros of A A A , even when A A A is continuous, as shown by Example 4.7 . This distinction motivates the study of demiclosedness of F F F at zero, which suffices for this projected solution identification and, under an appropriate solution-set condition, weak convergence of both projected sequences. We show that this condition on F F F follows from demiclosedness of A A A (or of the range-restricted operator A R A_R A R ) at zero and the bounded-recovery condition (see Definition 2.5 (i)). These conditions also ensure boundedness of { x ˉ k } \{\bar{x}^k\} { x ˉ k } and that their weak cluster points are zeros of A A A . Weak convergence of { x ˉ k } \{\bar{x}^k\} { x ˉ k } then follows when A A A has only one zero x x x with C ∗ x = z ∞ C^*x=z^\infty C ∗ x = z ∞ , where z ∞ z^\infty z ∞ is the weak limit of { z k } \{z^k\} { z k } , as is the case under admissibility (see Definition 2.4 ). The conclusions extend to the original PPPA iterates under an additional relaxation condition.
The monotonicity modulus U U U provides further properties. Under suitable conditions, the lower bound U ⪰ τ P U\succeq\tau P U ⪰ τ P with τ > 0 \tau>0 τ > 0 translates into a strongly monotone modulus for F F F , so that the general forward theory gives strong and linear convergence; a negative bound U ⪰ − σ P U\succeq-\sigma P U ⪰ − σ P with 0 ≤ σ < 1 / 2 0\leq\sigma<1/2 0 ≤ σ < 1/2 similarly yields local linear rates under metric subregularity. Another role of U U U is that its strong monotonicity on ker P \ker P ker P yields a Lipschitz recovery estimate (see Definition 2.5 (ii)), which can be used to transfer strong convergence and linear rates to the full PPPA shadows and, under suitable relaxation, the iterates. For Chambolle–Pock and Douglas–Rachford splitting, the primal–dual structure provides another route to Lipschitz recovery, even when U = 0 U=0 U = 0 .
Contributions
The forward viewpoint clarifies the distinct requirements for convergence of the reduced dynamics, identification of projected limits, and convergence of the full-space shadows. The main contributions are summarized as follows.
Forward theory under relative semimonotonicity. We extend classical estimates for single-valued quasi-cocoercive mappings to possibly set-valued, solution-relative semimonotone forward maps. Apart from Fejér estimates and residual rates, we obtain strong convergence under a strongly monotone monotonicity modulus (Proposition 3.1), and local linear rates under metric subregularity when the monotonicity modulus has a negative lower bound (Proposition 3.4 ).
(ii) Projected convergence and solution identification. A two-dimensional counterexample with continuous A A A shows that the projected PPPA iterates and shadows can converge to a point outside Π R ( zer A ) \Pi_{\mathcal{R}}(\operatorname{zer} A) Π R ( zer A ) Example 4.7 , demonstrating that the projected identification and convergence assertions in [12 Theorem 2.4(iii),(v)] require an additional assumption. We establish projected solution identification and weak convergence under demiclosedness of F F F at zero Proposition 4.5 , with sufficient conditions involving demiclosedness of A R A_{\mathcal{R}} A R and bounded recovery Lemma 4.8 .
(iii) Full-space recovery and convergence. Under bounded recovery, when A A A has exactly one zero x x x with C ∗ x = z ∞ C^*x=z^\infty C ∗ x = z ∞ , where z ∞ z^\infty z ∞ is the weak limit of { z k } \{z^k\} { z k } , we establish weak convergence of the full PPPA shadows and, under suitable relaxation, the iterates, without requiring admissibility Theorem 4.10 . Strong monotonicity of U U U on ker P \ker P ker P , together with additional conditions, yields Lipschitz recovery Theorem 4.11 , transferring strong convergence and linear rates to the full shadows when U ⪰ τ P U \succeq\tau P U ⪰ τ P with τ > 0 \tau>0 τ > 0 Theorem 4.12 . Local linear rates also extend to the full shadows when U ⪰ − σ P U \succeq-\sigma P U ⪰ − σ P with σ ∈ [ 0 , 1 / 2 ) \sigma\in[0,1/2) σ ∈ [ 0 , 1/2 ) , under metric subregularity and suitable recovery conditions Corollary 4.13.
(iv) Primal–dual splitting and recovery. For Chambolle–Pock and Douglas–Rachford splitting, full-graph relative semimonotonicity with a block-diagonal V V V yields Lipschitz recovery even when U = 0 U=0 U = 0 Theorem 5.1 . This shows that the projected identification and full-shadow convergence results of [11 , 12 ] hold, the latter without continuity of the component resolvents § 5 .
Preliminaries
Throughout, H \mathcal{H} H and K \mathcal{K} K are real Hilbert spaces, and N : = { 0 , 1 , 2 , … } \mathbb{N}:=\{0,1,2,\ldots\} N := { 0 , 1 , 2 , … } . We denote by B ( H , K ) \mathcal{B}(\mathcal{H},\mathcal{K}) B ( H , K ) the space of bounded linear operators from H \mathcal{H} H to K \mathcal{K} K , and B ( H ) : = B ( H , H ) \mathcal{B}(\mathcal{H}):=\mathcal{B}(\mathcal{H},\mathcal{H}) B ( H ) := B ( H , H ) . We write Id H \operatorname{Id}_{\mathcal{H}} Id H for the identity operator on H \mathcal{H} H , and simply Id \operatorname{Id} Id when the space is clear. A self-adjoint operator U ∈ B ( H ) U\in\mathcal{B}(\mathcal{H}) U ∈ B ( H ) is said to be strongly monotone on a closed subspace S ⊆ H S\subseteq\mathcal{H} S ⊆ H if there exists μ > 0 \mu>0 μ > 0 such that ⟨ h , U h ⟩ ≥ μ ∥ h ∥ 2 \langle h,Uh\rangle\geq\mu\|h\|^2 ⟨ h , U h ⟩ ≥ μ ∥ h ∥ 2 for every h ∈ S h\in S h ∈ S . For a closed subspace S S S of a Hilbert space, Π S \Pi_S Π S denotes the orthogonal projector onto S S S . For a subset S S S of a Hilbert space, cl S \operatorname{cl} S cl S denotes its closure and dist ( x , S ) : = inf s ∈ S ∥ x − s ∥ \operatorname{dist}(x,S):=\inf_{s\in S}\|x-s\| dist ( x , S ) := inf s ∈ S ∥ x − s ∥ . For r > 0 r>0 r > 0 and x ˉ ∈ H \bar{x}\in\mathcal{H} x ˉ ∈ H , we write B r ( x ˉ ) : = { x ∈ H : ∥ x − x ˉ ∥ < r } B_r(\bar{x}):=\{x\in\mathcal{H}:\|x-\bar{x}\|<r\} B r ( x ˉ ) := { x ∈ H : ∥ x − x ˉ ∥ < r } . A sequence { z k } k ∈ N \{z^k\}_{k\in\mathbb{N}} { z k } k ∈ N is said to be Fejér monotone with respect to a nonempty set S S S if ∥ z k + 1 − z ⋆ ∥ ≤ ∥ z k − z ⋆ ∥ \|z^{k+1}-z^\star\|\leq\|z^k-z^\star\| ∥ z k + 1 − z ⋆ ∥ ≤ ∥ z k − z ⋆ ∥ for all z ⋆ ∈ S z^\star\in S z ⋆ ∈ S , k ∈ N k\in\mathbb{N} k ∈ N . Weak and strong convergence are denoted by ⇀ \rightharpoonup ⇀ and → \to → , respectively. For a set-valued operator A A A , we write dom A : = { x : A x ≠ ∅ } \operatorname{dom} A:=\{x:Ax\ne\varnothing\} dom A := { x : A x = ∅ } , ran A : = ⋃ x ∈ H A x \operatorname{ran} A:=\bigcup_{x\in\mathcal{H}}Ax ran A := ⋃ x ∈ H A x , gra A : = { ( x , a ) : a ∈ A x } \operatorname{gra} A:=\{(x,a):a\in Ax\} gra A := {( x , a ) : a ∈ A x } , zer A : = { x : 0 ∈ A x } \operatorname{zer} A:=\{x:0\in Ax\} zer A := { x : 0 ∈ A x } , and A − 1 ( a ) : = { x : a ∈ A x } A^{-1}(a):=\{x:a\in Ax\} A − 1 ( a ) := { x : a ∈ A x } . For a single-valued operator T T T , we write Fix T : = { x : T x = x } \operatorname{Fix} T:=\{x:Tx=x\} Fix T := { x : T x = x } .
Semimonotonicity and closedness
We define the class of semimonotone maps considered in recent works [1 , 11 , 12 ] , together with its solution-relative counterpart.
Definition 2.1 ((U , V U,V U , V )-semimonotonicity). Let A : H ⇉ H A:\mathcal{H}\rightrightarrows\mathcal{H} A : H ⇉ H , and let U , V ∈ B ( H ) U,V\in\mathcal{B}(\mathcal{H}) U , V ∈ B ( H ) be self-adjoint.
(i) We say that A A A is ( U , V ) (U,V) ( U , V ) -semimonotone if
⟨ x − y , a − b ⟩ ≥ ⟨ x − y , U ( x − y ) ⟩ + ⟨ a − b , V ( a − b ) ⟩ \langle x-y,a-b\rangle\geq\langle x-y,U(x-y)\rangle+\langle a-b,V(a-b)\rangle ⟨ x − y , a − b ⟩ ≥ ⟨ x − y , U ( x − y )⟩ + ⟨ a − b , V ( a − b )⟩ for all ( x , a ) , ( y , b ) ∈ gra A (x,a),(y,b)\in\operatorname{gra} A ( x , a ) , ( y , b ) ∈ gra A .
In particular, for β > 0 \beta>0 β > 0 , we say that A A A is β \beta β -cocoercive if it is ( 0 , β Id ) (0,\beta\operatorname{Id}) ( 0 , β Id ) -semimonotone.
(ii) Let ∅ ≠ S ⋆ ⊆ zer A \varnothing\ne S^\star\subseteq\operatorname{zer} A ∅ = S ⋆ ⊆ zer A . We say that A A A is relatively ( U , V ) (U,V) ( U , V ) -semimonotone with respect to S ⋆ S^\star S ⋆ if
⟨ x − x ⋆ , a ⟩ ≥ ⟨ x − x ⋆ , U ( x − x ⋆ ) ⟩ + ⟨ a , V a ⟩ ∀ ( x , a ) ∈ gra A , x ⋆ ∈ S ⋆ . \langle x-x^\star,a\rangle\ge\langle x-x^\star,U(x-x^\star)\rangle+\langle a,Va\rangle\qquad\forall(x,a)\in\operatorname{gra} A,\quad x^\star\in S^\star. ⟨ x − x ⋆ , a ⟩ ≥ ⟨ x − x ⋆ , U ( x − x ⋆ )⟩ + ⟨ a , V a ⟩ ∀ ( x , a ) ∈ gra A , x ⋆ ∈ S ⋆ .
When U = 0 U=0 U = 0 , we also say that A A A is weakly V V V -comonotone relative to S ⋆ S^\star S ⋆ , which is also known as the V V V -oblique weak Minty condition [12 ] . In particular, for β > 0 \beta>0 β > 0 , we say that A A A is β \beta β -quasi-cocoercive relative to S ⋆ S^\star S ⋆ if it is relatively ( 0 , β Id ) (0,\beta\operatorname{Id}) ( 0 , β Id ) -semimonotone with respect to S ⋆ S^\star S ⋆ .
We refer to U U U and V V V as the monotonicity modulus and comonotonicity modulus , respectively, of the semimonotonicity inequality. Global ( U , V ) (U,V) ( U , V ) -semimonotonicity implies relative ( U , V ) (U,V) ( U , V ) -semimonotonicity with respect to every nonempty subset of zer A \operatorname{zer} A zer A . We allow S ⋆ ⊊ zer A S^\star\subsetneq\operatorname{zer} A S ⋆ ⊊ zer A because the solution-relative inequality may hold only at selected zeros.
Remark 2.2. Quasi-cocoercivity admits several useful interpretations and consequences.
(i) Suppose that A : H → H A:\mathcal{H}\to\mathcal{H} A : H → H is single-valued. If S = { x ⋆ } S=\{x^\star\} S = { x ⋆ } , then Definition 2.1(ii) is precisely 1 / β 1/\beta 1/ β -star-cocoercivity around x ⋆ x^\star x ⋆ in the convention of [14 Definition 2.1] . An equivalent condition appeared earlier as co-coercivity around a reference point in [19 Definition 3.1] . If instead S = zer A S=\operatorname{zer} A S = zer A and T : = Id − A T:=\operatorname{Id}-A T := Id − A , then Definition 2.1(ii) is precisely condition (A) of [24 ] . It is also equivalent to conical 1 / ( 2 β ) 1/(2\beta) 1/ ( 2 β ) -quasiaveragedness of T T T in the sense of [9 Definition 2.1] .
(ii) Unlike cocoercivity, quasi-cocoercivity does not force A A A to be single-valued, since it compares graph points only with the prescribed zeros. For example, A : H ⇉ H A:\mathcal{H}\rightrightarrows\mathcal{H} A : H ⇉ H defined by A x : = { x , 2 x } Ax:=\{x,2x\} A x := { x , 2 x } is 1 / 2 1/2 1/2 -quasi-cocoercive relative to zer A = { 0 } \operatorname{zer} A=\{0\} zer A = { 0 } , although it is set-valued at every x ≠ 0 x\ne0 x = 0 . By contrast, cocoercivity forces single-valuedness on the domain. Nevertheless, quasi-cocoercivity constrains the values at x ⋆ ∈ S x^\star\in S x ⋆ ∈ S , since a ∈ A x ⋆ a\in Ax^\star a ∈ A x ⋆ implies that a = 0 a=0 a = 0 , i.e., A x ⋆ = { 0 } Ax^\star=\{0\} A x ⋆ = { 0 } .
We recall the notions of graph closedness and demiclosedness at zero for set-valued operators; see, e.g., [16 Definition 2] for the latter.
Definition 2.3 (Graph closedness and demiclosedness at zero). Let A : H ⇉ H A:\mathcal{H}\rightrightarrows\mathcal{H} A : H ⇉ H . We say that A A A is demiclosed at zero if x j ⇀ x x^j\rightharpoonup x x j ⇀ x , a j → 0 a^j\to0 a j → 0 , and a j ∈ A x j a^j\in Ax^j a j ∈ A x j imply 0 ∈ A x 0\in Ax 0 ∈ A x .
Degenerate metrics, admissibility, and recovery
Throughout this paper, P ∈ B ( H ) ∖ { 0 } P\in\mathcal{B}(\mathcal{H})\setminus\{0\} P ∈ B ( H ) ∖ { 0 } is a self-adjoint and positive semidefinite operator with closed range R : = ran P \mathcal{R}:=\operatorname{ran}P R := ran P . Then H = R ⊕ ker P \mathcal{H}=\mathcal{R}\oplus\ker P H = R ⊕ ker P , and the restriction P ∣ R : R → R P|_{\mathcal{R}}:\mathcal{R}\to\mathcal{R} P ∣ R : R → R is bounded, self-adjoint, and strongly positive. We equip R \mathcal{R} R with the Hilbert structure inherited from H \mathcal{H} H and use the canonical factorization
C : = ι R ( P ∣ R ) 1 / 2 : R → H , C ⋆ = ( P ∣ R ) 1 / 2 Π R : H → R , C C ⋆ = P , (2) C:=\iota_{\mathcal{R}}(P|_{\mathcal{R}})^{1/2}:\mathcal{R}\to\mathcal{H},\qquad C^\star=(P|_{\mathcal{R}})^{1/2}\Pi_{\mathcal{R}}:\mathcal{H}\to\mathcal{R},\qquad CC^\star=P, \tag*{(2)} C := ι R ( P ∣ R ) 1/2 : R → H , C ⋆ = ( P ∣ R ) 1/2 Π R : H → R , C C ⋆ = P , (2)
where ι R : R → H \iota_{\mathcal{R}}:\mathcal{R}\to\mathcal{H} ι R : R → H is the canonical inclusion. Thus, C C C is injective, ran C = R \operatorname{ran}C=\mathcal{R} ran C = R , and C ⋆ C^\star C ⋆ is onto. Moreover, C ⋆ ∣ R = ( P ∣ R ) 1 / 2 C^\star|_{\mathcal{R}}=(P|_{\mathcal{R}})^{1/2} C ⋆ ∣ R = ( P ∣ R ) 1/2 is a bounded isomorphism on R \mathcal{R} R , and hence
Π R x = ( P ∣ R ) − 1 / 2 C ⋆ x , x ∈ H . (3) \Pi_{\mathcal{R}}x=(P|_{\mathcal{R}})^{-1/2}C^\star x,\qquad x\in\mathcal{H}. \tag*{(3)} Π R x = ( P ∣ R ) − 1/2 C ⋆ x , x ∈ H . (3)
We denote the seminorm ∥ x ∥ P 2 : = ⟨ x , P x ⟩ = ∥ C ⋆ x ∥ 2 \|x\|_P^2:=\langle x,Px\rangle=\|C^\star x\|^2 ∥ x ∥ P 2 := ⟨ x , P x ⟩ = ∥ C ⋆ x ∥ 2 .
Following [4 Definition 2.1] , we use the following terminology.
Definition 2.4 (Admissible preconditioner). Let A : H ⇉ H A:\mathcal{H}\rightrightarrows\mathcal{H} A : H ⇉ H . A bounded self-adjoint positive semidefinite operator P P P is an admissible preconditioner for A A A if ( P + A ) − 1 P : H → H (P+A)^{-1}P:\mathcal{H}\to\mathcal{H} ( P + A ) − 1 P : H → H is single-valued and has full domain.
Since P = C C ∗ P = CC^* P = C C ∗ , the preconditioned resolvent factors through R \mathcal{R} R as
( P + A ) − 1 P = Φ C ∗ , where Φ : = ( P + A ) − 1 C : R ⇒ H . (4) (P + A)^{-1}P = \Phi C^*, \qquad\text{where } \Phi:= (P + A)^{-1}C : \mathcal{R} \Rightarrow\mathcal{H}. \tag*{(4)} ( P + A ) − 1 P = Φ C ∗ , where Φ := ( P + A ) − 1 C : R ⇒ H . (4)
We call Φ \Phi Φ the shadow-recovery map , since the shadows in (1) satisfy x ˉ k ∈ Φ ( C ∗ x k ) \bar{x}^{k} \in\Phi(C^*x^k) x ˉ k ∈ Φ ( C ∗ x k ) . As C ∗ C^* C ∗ is onto, P P P is admissible for A A A if and only if Φ \Phi Φ is single-valued and has full domain. We also use two recovery properties that do not require single-valuedness.
Definition 2.5 (Bounded and Lipschitz recovery). Let Φ \Phi Φ be given by (4) .
(i) The bounded-recovery condition holds if Φ \Phi Φ maps bounded sets of R \mathcal{R} R to bounded sets of H \mathcal{H} H .
(ii) Let ∅ ≠ S ⋆ ⊆ zer A \varnothing\ne S^\star\subseteq\operatorname{zer} A ∅ = S ⋆ ⊆ zer A . A Lipschitz recovery estimate holds relative to S ⋆ S^\star S ⋆ if there exists K > 0 K > 0 K > 0 such that
∥ x ˉ − x ⋆ ∥ ≤ K ∥ z − C ∗ x ⋆ ∥ ∀ x ⋆ ∈ S ⋆ , z ∈ R , x ˉ ∈ Φ ( z ) . (5) \lVert\bar{x} - x^\star\rVert\le K \lVert z - C^*x^\star\rVert\qquad\forall x^\star\in S^\star,\quad z \in\mathcal{R},\quad\bar{x} \in\Phi(z). \tag*{(5)} ∥ x ˉ − x ⋆ ∥ ≤ K ∥ z − C ∗ x ⋆ ∥ ∀ x ⋆ ∈ S ⋆ , z ∈ R , x ˉ ∈ Φ ( z ) . (5) For x ⋆ ∈ zer A x^\star\in\operatorname{zer} A x ⋆ ∈ zer A , a local Lipschitz recovery estimate at x ⋆ x^\star x ⋆ means that the same inequality in (5) holds for every z ∈ B r ( C ∗ x ⋆ ) z \in B_r(C^*x^\star) z ∈ B r ( C ∗ x ⋆ ) and x ˉ ∈ Φ ( z ) \bar{x} \in\Phi(z) x ˉ ∈ Φ ( z ) , for some K , r > 0 K,r > 0 K , r > 0 .
The local Lipschitz recovery estimate is precisely outer Lipschitz continuity of Φ \Phi Φ at C ∗ x ⋆ C^*x^\star C ∗ x ⋆ , relative to dom Φ \operatorname{dom}\Phi dom Φ , in the sense of [10 Chapter 3D] . It does not require Φ \Phi Φ to be single-valued near C ∗ x ⋆ C^*x^\star C ∗ x ⋆ or Lipschitz continuous between arbitrary reduced points.
Lemma 2.6 (Consequences of Lipschitz recovery). If (5) holds relative to ∅ ≠ S ⋆ ⊆ zer A \varnothing\ne S^\star\subseteq\operatorname{zer} A ∅ = S ⋆ ⊆ zer A , then the bounded-recovery condition holds and Φ ( C ∗ x ⋆ ) = { x ⋆ } \Phi(C^*x^\star) = \{x^\star\} Φ ( C ∗ x ⋆ ) = { x ⋆ } for every x ⋆ ∈ S ⋆ x^\star\in S^\star x ⋆ ∈ S ⋆ . In particular, x ⋆ x^\star x ⋆ is the unique zero of A A A satisfying C ∗ x = C ∗ x ⋆ C^*x = C^*x^\star C ∗ x = C ∗ x ⋆ . The identity Φ ( C ∗ x ⋆ ) = { x ⋆ } \Phi(C^*x^\star) = \{x^\star\} Φ ( C ∗ x ⋆ ) = { x ⋆ } and uniqueness conclusion also hold under a local Lipschitz recovery estimate at x ⋆ x^\star x ⋆ .
Proof. Fix x ⋆ ∈ S ⋆ x^\star\in S^\star x ⋆ ∈ S ⋆ and let K K K be as in (5) . For any bounded B ⊆ R B \subseteq\mathcal{R} B ⊆ R and x ˉ ∈ Φ ( z ) \bar{x} \in\Phi(z) x ˉ ∈ Φ ( z ) with z ∈ B z \in B z ∈ B ,
∥ x ˉ ∥ ≤ ∥ x ⋆ ∥ + K ( ∥ z ∥ + ∥ C ∗ x ⋆ ∥ ) . \lVert\bar{x}\rVert\le\lVert x^\star\rVert+ K(\lVert z\rVert+ \lVert C^*x^\star\rVert). ∥ x ˉ ∥ ≤ ∥ x ⋆ ∥ + K (∥ z ∥ + ∥ C ∗ x ⋆ ∥) .
It immediately follows that Φ ( B ) \Phi(B) Φ ( B ) is bounded. Since 0 ∈ A x ⋆ 0 \in Ax^\star 0 ∈ A x ⋆ , P x ⋆ = C ( C ∗ x ⋆ ) ∈ ( P + A ) x ⋆ Px^\star= C(C^*x^\star) \in(P + A)x^\star P x ⋆ = C ( C ∗ x ⋆ ) ∈ ( P + A ) x ⋆ , so x ⋆ ∈ Φ ( C ∗ x ⋆ ) x^\star\in\Phi(C^*x^\star) x ⋆ ∈ Φ ( C ∗ x ⋆ ) . Applying (5) at z = C ∗ x ⋆ z = C^*x^\star z = C ∗ x ⋆ gives Φ ( C ∗ x ⋆ ) = { x ⋆ } \Phi(C^*x^\star) = \{x^\star\} Φ ( C ∗ x ⋆ ) = { x ⋆ } . Every x ∈ zer A x \in\operatorname{zer} A x ∈ zer A with C ∗ x = C ∗ x ⋆ C^*x = C^*x^\star C ∗ x = C ∗ x ⋆ belongs to this set and therefore equals x ⋆ x^\star x ⋆ . Both conclusions use the recovery estimate only at z = C ∗ x ⋆ z = C^*x^\star z = C ∗ x ⋆ , so they remain valid under local Lipschitz recovery.
Forward iterations under relative semimonotonicity
Let K \mathcal{K} K be a real Hilbert space. Given a set-valued mapping F : K ⇒ K F : \mathcal{K} \Rightarrow\mathcal{K} F : K ⇒ K , we study forward iterations
z k + 1 = z k − λ k q k , q k ∈ F ( z k ) , (6) z^{k+1} = z^k - \lambda_k q^k, \qquad q^k \in F(z^k), \tag*{(6)} z k + 1 = z k − λ k q k , q k ∈ F ( z k ) , (6)
under the assumption that F F F is relatively ( U , V ) (U,V) ( U , V ) -semimonotone with respect to a nonempty subset of its zeros, where V V V is strongly monotone. We first consider in § 3.1 the case U ⪰ 0 U \succeq0 U ⪰ 0 , which effectively reduces to quasi-cocoercive forward iterations (cf. Definition 2.1 (ii)), with some additional convergence results when U U U is strongly monotone. The case where U U U is bounded below by a negative multiple of the identity is treated in § 3.2 under an additional error bound assumption.
Convergence
The following proposition establishes the convergence of (6) under relative semimonotonicity.
Proposition 3.1 (Relative semimonotone forward iteration). Let F : K ⇉ K F:\mathcal{K}\rightrightarrows\mathcal{K} F : K ⇉ K be relatively ( U , V ) (U,V) ( U , V ) -semimonotone with respect to ∅ ≠ S ⊆ zer F \varnothing\ne S\subseteq\operatorname{zer}F ∅ = S ⊆ zer F , where U ⪰ 0 U\succeq0 U ⪰ 0 and V ⪰ η Id V\succeq\eta\operatorname{Id} V ⪰ η Id with η > 0 \eta>0 η > 0 . Let z 0 ∈ K z^0\in\mathcal{K} z 0 ∈ K , and let { z k } \{z^k\} { z k } be generated by (6) with λ k ∈ ( 0 , 2 β k ] \lambda_k\in(0,2\beta_k] λ k ∈ ( 0 , 2 β k ] , where β k > 0 \beta_k>0 β k > 0 satisfying ⟨ q k , V q k ⟩ ≥ β k ∥ q k ∥ 2 \langle q^k,Vq^k\rangle\ge\beta_k\|q^k\|^2 ⟨ q k , V q k ⟩ ≥ β k ∥ q k ∥ 2 . Set δ k : = λ k ( 2 β k − λ k ) \delta_k:=\lambda_k(2\beta_k-\lambda_k) δ k := λ k ( 2 β k − λ k ) . Then the following hold.
(i) { z k } k ∈ N \{z^k\}_{k\in\mathbb{N}} { z k } k ∈ N is Fejér monotone with respect to S S S .
(ii) If lim inf k → ∞ δ k > 0 \liminf_{k\to\infty}\delta_k>0 lim inf k → ∞ δ k > 0 , then ∑ k = 0 ∞ ∥ q k ∥ 2 < + ∞ \sum_{k=0}^{\infty}\|q^k\|^2<+\infty ∑ k = 0 ∞ ∥ q k ∥ 2 < + ∞ and q k → 0 q^k\to0 q k → 0 . If, in addition, F F F is demiclosed at zero, then every weak cluster point of { z k } \{z^k\} { z k } belongs to zer F \operatorname{zer}F zer F . If moreover S = zer F S=\operatorname{zer}F S = zer F , then z k ⇀ z ⋆ z^k\rightharpoonup z^\star z k ⇀ z ⋆ for some z ⋆ ∈ zer F z^\star\in\operatorname{zer}F z ⋆ ∈ zer F .
(iii) For every z ⋆ ∈ S z^\star\in S z ⋆ ∈ S and N ∈ N N\in\mathbb{N} N ∈ N ,
∥ ∑ k = 0 N λ k q k ∑ k = 0 N λ k ∥ ≤ 2 ∥ z 0 − z ⋆ ∥ ∑ k = 0 N λ k . \left\|\frac{\sum_{k=0}^{N}\lambda_kq^k}{\sum_{k=0}^{N}\lambda_k}\right\|\le\frac{2\|z^0-z^\star\|}{\sum_{k=0}^{N}\lambda_k}. ∑ k = 0 N λ k ∑ k = 0 N λ k q k ≤ ∑ k = 0 N λ k 2∥ z 0 − z ⋆ ∥ . In particular, if lim inf k → ∞ λ k > 0 \liminf_{k\to\infty}\lambda_k>0 lim inf k → ∞ λ k > 0 , the right-hand side is O ( N − 1 ) O(N^{-1}) O ( N − 1 ) . Moreover, if δ : = inf k δ k > 0 \delta:=\inf_k\delta_k>0 δ := inf k δ k > 0 , then
∥ 1 N + 1 ∑ k = 0 N q k ∥ ≤ ∥ z 0 − z ⋆ ∥ δ ( N + 1 ) = O ( N − 1 / 2 ) . \left\|\frac{1}{N+1}\sum_{k=0}^{N}q^k\right\|\le\frac{\|z^0-z^\star\|}{\sqrt{\delta(N+1)}}=O(N^{-1/2}). N + 1 1 k = 0 ∑ N q k ≤ δ ( N + 1 ) ∥ z 0 − z ⋆ ∥ = O ( N − 1/2 ) . (iv) For every N N N such that ∑ k = 0 N δ k > 0 \sum_{k=0}^{N}\delta_k>0 ∑ k = 0 N δ k > 0 and every z ⋆ ∈ S z^\star\in S z ⋆ ∈ S ,
min 0 ≤ k ≤ N ∥ q k ∥ 2 ≤ ∥ z 0 − z ⋆ ∥ 2 ∑ k = 0 N δ k . \min_{0\le k\le N}\|q^k\|^2\le\frac{\|z^0-z^\star\|^2}{\sum_{k=0}^{N}\delta_k}. 0 ≤ k ≤ N min ∥ q k ∥ 2 ≤ ∑ k = 0 N δ k ∥ z 0 − z ⋆ ∥ 2 . In particular, if δ k ≥ κ > 0 \delta_k\ge\kappa>0 δ k ≥ κ > 0 for all k k k , then the right-hand side is at most ∥ z 0 − z ⋆ ∥ 2 κ ( N + 1 ) \frac{\|z^0-z^\star\|^2}{\kappa(N+1)} κ ( N + 1 ) ∥ z 0 − z ⋆ ∥ 2 .
(v) For every z ⋆ ∈ S z^\star\in S z ⋆ ∈ S , ∑ k = 0 ∞ λ k ∥ U 1 / 2 ( z k − z ⋆ ) ∥ 2 < + ∞ \sum_{k=0}^{\infty}\lambda_k\|U^{1/2}(z^k-z^\star)\|^2<+\infty ∑ k = 0 ∞ λ k ∥ U 1/2 ( z k − z ⋆ ) ∥ 2 < + ∞ . If lim inf k → ∞ λ k > 0 \liminf_{k\to\infty}\lambda_k>0 lim inf k → ∞ λ k > 0 , then U 1 / 2 ( z k − z ⋆ ) → 0 U^{1/2}(z^k-z^\star)\to0 U 1/2 ( z k − z ⋆ ) → 0 . If U ⪰ μ Id U\succeq\mu\operatorname{Id} U ⪰ μ Id for some μ > 0 \mu>0 μ > 0 , then the weaker condition ∑ k = 0 ∞ λ k = + ∞ \sum_{k=0}^{\infty}\lambda_k=+\infty ∑ k = 0 ∞ λ k = + ∞ already ensures z k → z ⋆ z^k\to z^\star z k → z ⋆ strongly. Moreover, if lim inf k → ∞ λ k > 0 \liminf_{k\to\infty}\lambda_k>0 lim inf k → ∞ λ k > 0 , then the convergence is Q Q Q -linear.
Proof. First, we note from the relative semimonotonicity assumption that
⟨ q k , z k − z ⋆ ⟩ ≥ ⟨ z k − z ⋆ , U ( z k − z ⋆ ) ⟩ + β k ∥ q k ∥ 2 ∀ z ⋆ ∈ S . (7) \langle q^k,z^k-z^\star\rangle\ge\langle z^k-z^\star,U(z^k-z^\star)\rangle+\beta_k\|q^k\|^2\qquad\forall z^\star\in S. \tag*{(7)} ⟨ q k , z k − z ⋆ ⟩ ≥ ⟨ z k − z ⋆ , U ( z k − z ⋆ )⟩ + β k ∥ q k ∥ 2 ∀ z ⋆ ∈ S . (7)
From (6) and (7), we have for every $z^\star\in S
∥ z k + 1 − z ⋆ ∥ 2 ≤ ∥ z k − z ⋆ ∥ 2 − 2 λ k ∥ U 1 / 2 ( z k − z ⋆ ) ∥ 2 − λ k ⟨ q k , ( 2 V − λ k Id ) q k ⟩ ≤ ∥ z k − z ⋆ ∥ 2 − 2 λ k ∥ U 1 / 2 ( z k − z ⋆ ) ∥ 2 − δ k ∥ q k ∥ 2 . (8) \begin{aligned}
\|z^{k+1}-z^\star\|^2
&\le\|z^k-z^\star\|^2-2\lambda_k\|U^{1/2}(z^k-z^\star)\|^2-\lambda_k\langle q^k,(2V-\lambda_k\operatorname{Id})q^k\rangle\\
&\le\|z^k-z^\star\|^2-2\lambda_k\|U^{1/2}(z^k-z^\star)\|^2-\delta_k\|q^k\|^2. \tag*{(8)}
\end{aligned} ∥ z k + 1 − z ⋆ ∥ 2 ≤ ∥ z k − z ⋆ ∥ 2 − 2 λ k ∥ U 1/2 ( z k − z ⋆ ) ∥ 2 − λ k ⟨ q k , ( 2 V − λ k Id ) q k ⟩ ≤ ∥ z k − z ⋆ ∥ 2 − 2 λ k ∥ U 1/2 ( z k − z ⋆ ) ∥ 2 − δ k ∥ q k ∥ 2 . (8)
This proves (i). Summing (8) from k = 0 k=0 k = 0 to N N N yields
2 ∑ k = 0 N λ k ∥ U 1 / 2 ( z k − z ⋆ ) ∥ 2 + ∑ k = 0 N δ k ∥ q k ∥ 2 ≤ ∥ z 0 − z ⋆ ∥ 2 , (9) 2\sum_{k=0}^{N}\lambda_k\|U^{1/2}(z^k-z^\star)\|^2+\sum_{k=0}^{N}\delta_k\|q^k\|^2\le\|z^0-z^\star\|^2, \tag*{(9)} 2 k = 0 ∑ N λ k ∥ U 1/2 ( z k − z ⋆ ) ∥ 2 + k = 0 ∑ N δ k ∥ q k ∥ 2 ≤ ∥ z 0 − z ⋆ ∥ 2 , (9)
which implies the first assertion in (ii). Since { z k } \{z^k\} { z k } is bounded by (i) and q k → 0 q^k\to0 q k → 0 , demiclosedness of F F F at zero implies that every weak cluster point belongs to zer F \operatorname{zer}F zer F . If also S = zer F S=\operatorname{zer}F S = zer F , the distances ∥ z k − z ⋆ ∥ \|z^k-z^\star\| ∥ z k − z ⋆ ∥ converge for every z ⋆ ∈ zer F z^\star\in\operatorname{zer}F z ⋆ ∈ zer F , and Opial’s argument gives the weak convergence of { z k } \{z^k\} { z k } to some point in zer F \operatorname{zer}F zer F . This completes the proof of (ii).
For (iii), summing (6) gives ∑ k = 0 N λ k q k = z 0 − z N + 1 \sum_{k=0}^{N}\lambda_kq^k=z^0-z^{N+1} ∑ k = 0 N λ k q k = z 0 − z N + 1 . By Fejér monotonicity,
∥ z 0 − z N + 1 ∥ ≤ ∥ z 0 − z ⋆ ∥ + ∥ z N + 1 − z ⋆ ∥ ≤ 2 ∥ z 0 − z ⋆ ∥ , \|z^0-z^{N+1}\|\le\|z^0-z^\star\|+\|z^{N+1}-z^\star\|\le2\|z^0-z^\star\|, ∥ z 0 − z N + 1 ∥ ≤ ∥ z 0 − z ⋆ ∥ + ∥ z N + 1 − z ⋆ ∥ ≤ 2∥ z 0 − z ⋆ ∥ ,
@page 7/26 starts_mid=0 ends_mid=1
Proposition 3.1 (Relative semimonotone forward iteration). Let F : K ⇉ K F:\mathcal{K}\rightrightarrows\mathcal{K} F : K ⇉ K be relatively ( U , V ) (U,V) ( U , V ) -semimonotone with respect to ∅ ≠ S ⊆ zer F \varnothing\ne S\subseteq\operatorname{zer}F ∅ = S ⊆ zer F , where U ⪰ 0 U\succeq0 U ⪰ 0 and V ⪰ η Id V\succeq\eta\operatorname{Id} V ⪰ η Id with η > 0 \eta>0 η > 0 . Let z 0 ∈ K z^0\in\mathcal{K} z 0 ∈ K , and let { z k } \{z^k\} { z k } be generated by (6) with λ k ∈ ( 0 , 2 β k ] \lambda_k\in(0,2\beta_k] λ k ∈ ( 0 , 2 β k ] , where β k > 0 \beta_k>0 β k > 0 satisfying ⟨ q k , V q k ⟩ ≥ β k ∥ q k ∥ 2 \langle q^k,Vq^k\rangle\ge\beta_k\|q^k\|^2 ⟨ q k , V q k ⟩ ≥ β k ∥ q k ∥ 2 . Set δ k : = λ k ( 2 β k − λ k ) \delta_k:=\lambda_k(2\beta_k-\lambda_k) δ k := λ k ( 2 β k − λ k ) . Then the following hold.
(i) { z k } k ∈ N \{z^k\}_{k\in\mathbb{N}} { z k } k ∈ N is Fejér monotone with respect to S S S .
(ii) If lim inf k → ∞ δ k > 0 \liminf_{k\to\infty}\delta_k>0 lim inf k → ∞ δ k > 0 , then ∑ k = 0 ∞ ∥ q k ∥ 2 < + ∞ \sum_{k=0}^{\infty}\|q^k\|^2<+\infty ∑ k = 0 ∞ ∥ q k ∥ 2 < + ∞ and q k → 0 q^k\to0 q k → 0 . If, in addition, F F F is demiclosed at zero, then every weak cluster point of { z k } \{z^k\} { z k } belongs to zer F \operatorname{zer}F zer F . If moreover S = zer F S=\operatorname{zer}F S = zer F , then z k ⇀ z ⋆ z^k\rightharpoonup z^\star z k ⇀ z ⋆ for some z ⋆ ∈ zer F z^\star\in\operatorname{zer}F z ⋆ ∈ zer F .
(iii) For every z ⋆ ∈ S z^\star\in S z ⋆ ∈ S and N ∈ N N\in\mathbb{N} N ∈ N ,
∥ ∑ k = 0 N λ k q k ∑ k = 0 N λ k ∥ ≤ 2 ∥ z 0 − z ⋆ ∥ ∑ k = 0 N λ k . \left\|\frac{\sum_{k=0}^{N}\lambda_kq^k}{\sum_{k=0}^{N}\lambda_k}\right\|\le\frac{2\|z^0-z^\star\|}{\sum_{k=0}^{N}\lambda_k}. ∑ k = 0 N λ k ∑ k = 0 N λ k q k ≤ ∑ k = 0 N λ k 2∥ z 0 − z ⋆ ∥ . In particular, if lim inf k → ∞ λ k > 0 \liminf_{k\to\infty}\lambda_k>0 lim inf k → ∞ λ k > 0 , the right-hand side is O ( N − 1 ) O(N^{-1}) O ( N − 1 ) . Moreover, if δ : = inf k δ k > 0 \delta:=\inf_k\delta_k>0 δ := inf k δ k > 0 , then
∥ 1 N + 1 ∑ k = 0 N q k ∥ ≤ ∥ z 0 − z ⋆ ∥ δ ( N + 1 ) = O ( N − 1 / 2 ) . \left\|\frac{1}{N+1}\sum_{k=0}^{N}q^k\right\|\le\frac{\|z^0-z^\star\|}{\sqrt{\delta(N+1)}}=O(N^{-1/2}). N + 1 1 k = 0 ∑ N q k ≤ δ ( N + 1 ) ∥ z 0 − z ⋆ ∥ = O ( N − 1/2 ) . (iv) For every N N N such that ∑ k = 0 N δ k > 0 \sum_{k=0}^{N}\delta_k>0 ∑ k = 0 N δ k > 0 and every z ⋆ ∈ S z^\star\in S z ⋆ ∈ S ,
min 0 ≤ k ≤ N ∥ q k ∥ 2 ≤ ∥ z 0 − z ⋆ ∥ 2 ∑ k = 0 N δ k . \min_{0\le k\le N}\|q^k\|^2\le\frac{\|z^0-z^\star\|^2}{\sum_{k=0}^{N}\delta_k}. 0 ≤ k ≤ N min ∥ q k ∥ 2 ≤ ∑ k = 0 N δ k ∥ z 0 − z ⋆ ∥ 2 . In particular, if δ k ≥ κ > 0 \delta_k\ge\kappa>0 δ k ≥ κ > 0 for all k k k , then the right-hand side is at most ∥ z 0 − z ⋆ ∥ 2 κ ( N + 1 ) \frac{\|z^0-z^\star\|^2}{\kappa(N+1)} κ ( N + 1 ) ∥ z 0 − z ⋆ ∥ 2 .
(v) For every z ⋆ ∈ S z^\star\in S z ⋆ ∈ S , ∑ k = 0 ∞ λ k ∥ U 1 / 2 ( z k − z ⋆ ) ∥ 2 < + ∞ \sum_{k=0}^{\infty}\lambda_k\|U^{1/2}(z^k-z^\star)\|^2<+\infty ∑ k = 0 ∞ λ k ∥ U 1/2 ( z k − z ⋆ ) ∥ 2 < + ∞ . If lim inf k → ∞ λ k > 0 \liminf_{k\to\infty}\lambda_k>0 lim inf k → ∞ λ k > 0 , then U 1 / 2 ( z k − z ⋆ ) → 0 U^{1/2}(z^k-z^\star)\to0 U 1/2 ( z k − z ⋆ ) → 0 . If U ⪰ μ Id U\succeq\mu\operatorname{Id} U ⪰ μ Id for some μ > 0 \mu>0 μ > 0 , then the weaker condition ∑ k = 0 ∞ λ k = + ∞ \sum_{k=0}^{\infty}\lambda_k=+\infty ∑ k = 0 ∞ λ k = + ∞ already ensures z k → z ⋆ z^k\to z^\star z k → z ⋆ strongly. Moreover, if lim inf k → ∞ λ k > 0 \liminf_{k\to\infty}\lambda_k>0 lim inf k → ∞ λ k > 0 , then the convergence is Q Q Q -linear.
Proof. First, we note from the relative semimonotonicity assumption that
⟨ q k , z k − z ⋆ ⟩ ≥ ⟨ z k − z ⋆ , U ( z k − z ⋆ ) ⟩ + β k ∥ q k ∥ 2 ∀ z ⋆ ∈ S . (10) \langle q^k,z^k-z^\star\rangle\ge\langle z^k-z^\star,U(z^k-z^\star)\rangle+\beta_k\|q^k\|^2\qquad\forall z^\star\in S. \tag*{(10)} ⟨ q k , z k − z ⋆ ⟩ ≥ ⟨ z k − z ⋆ , U ( z k − z ⋆ )⟩ + β k ∥ q k ∥ 2 ∀ z ⋆ ∈ S . (10)
From (6) and (7), we have for every $z^\star\in S
∥ z k + 1 − z ⋆ ∥ 2 ≤ ∥ z k − z ⋆ ∥ 2 − 2 λ k ∥ U 1 / 2 ( z k − z ⋆ ) ∥ 2 − λ k ⟨ q k , ( 2 V − λ k Id ) q k ⟩ ≤ ∥ z k − z ⋆ ∥ 2 − 2 λ k ∥ U 1 / 2 ( z k − z ⋆ ) ∥ 2 − δ k ∥ q k ∥ 2 . (11) \begin{aligned}
\|z^{k+1}-z^\star\|^2
&\le\|z^k-z^\star\|^2-2\lambda_k\|U^{1/2}(z^k-z^\star)\|^2-\lambda_k\langle q^k,(2V-\lambda_k\operatorname{Id})q^k\rangle\\
&\le\|z^k-z^\star\|^2-2\lambda_k\|U^{1/2}(z^k-z^\star)\|^2-\delta_k\|q^k\|^2. \tag*{(11)}
\end{aligned} ∥ z k + 1 − z ⋆ ∥ 2 ≤ ∥ z k − z ⋆ ∥ 2 − 2 λ k ∥ U 1/2 ( z k − z ⋆ ) ∥ 2 − λ k ⟨ q k , ( 2 V − λ k Id ) q k ⟩ ≤ ∥ z k − z ⋆ ∥ 2 − 2 λ k ∥ U 1/2 ( z k − z ⋆ ) ∥ 2 − δ k ∥ q k ∥ 2 . (11)
This proves (i). Summing (8) from k = 0 k=0 k = 0 to N N N yields
2 ∑ k = 0 N λ k ∥ U 1 / 2 ( z k − z ⋆ ) ∥ 2 + ∑ k = 0 N δ k ∥ q k ∥ 2 ≤ ∥ z 0 − z ⋆ ∥ 2 , (12) 2\sum_{k=0}^{N}\lambda_k\|U^{1/2}(z^k-z^\star)\|^2+\sum_{k=0}^{N}\delta_k\|q^k\|^2\le\|z^0-z^\star\|^2, \tag*{(12)} 2 k = 0 ∑ N λ k ∥ U 1/2 ( z k − z ⋆ ) ∥ 2 + k = 0 ∑ N δ k ∥ q k ∥ 2 ≤ ∥ z 0 − z ⋆ ∥ 2 , (12)
which implies the first assertion in (ii). Since { z k } \{z^k\} { z k } is bounded by (i) and q k → 0 q^k\to0 q k → 0 , demiclosedness of F F F at zero implies that every weak cluster point belongs to zer F \operatorname{zer}F zer F . If also S = zer F S=\operatorname{zer}F S = zer F , the distances ∥ z k − z ⋆ ∥ \|z^k-z^\star\| ∥ z k − z ⋆ ∥ converge for every z ⋆ ∈ zer F z^\star\in\operatorname{zer}F z ⋆ ∈ zer F , and Opial’s argument gives the weak convergence of { z k } \{z^k\} { z k } to some point in zer F \operatorname{zer}F zer F . This completes the proof of (ii).
For (iii), summing (6) gives ∑ k = 0 N λ k q k = z 0 − z N + 1 \sum_{k=0}^{N}\lambda_kq^k=z^0-z^{N+1} ∑ k = 0 N λ k q k = z 0 − z N + 1 . By Fejér monotonicity,
∥ z 0 − z N + 1 ∥ ≤ ∥ z 0 − z ⋆ ∥ + ∥ z N + 1 − z ⋆ ∥ ≤ 2 ∥ z 0 − z ⋆ ∥ , (13) \|z^0-z^{N+1}\|\le\|z^0-z^\star\|+\|z^{N+1}-z^\star\|\le2\|z^0-z^\star\|, \tag*{(13)} ∥ z 0 − z N + 1 ∥ ≤ ∥ z 0 − z ⋆ ∥ + ∥ z N + 1 − z ⋆ ∥ ≤ 2∥ z 0 − z ⋆ ∥ , (13)
which proves the first estimate. If δ : = inf k δ k > 0 \delta:= \inf_k \delta_k > 0 δ := inf k δ k > 0 , Jensen’s inequality and (9) give
∥ 1 N + 1 ∑ k = 0 N q k ∥ 2 ≤ 1 N + 1 ∑ k = 0 N ∥ q k ∥ 2 ≤ ∥ z 0 − z ⋆ ∥ 2 δ ( N + 1 ) . \left\| \frac{1}{N+1}\sum_{k=0}^{N}q^k \right\|^2 \leq\frac{1}{N+1}\sum_{k=0}^{N}\left\|q^k\right\|^2 \leq\frac{\left\|z^0-z^\star\right\|^2}{\delta(N+1)}. N + 1 1 k = 0 ∑ N q k 2 ≤ N + 1 1 k = 0 ∑ N q k 2 ≤ δ ( N + 1 ) z 0 − z ⋆ 2 .
This proves (iii). On the other hand, (iv) follows immediately since
( min 0 ≤ k ≤ N ∥ q k ∥ 2 ) ∑ k = 0 N δ k ≤ ∑ k = 0 N δ k ∥ q k ∥ 2 . \left(\min_{0\leq k\leq N}\left\|q^k\right\|^2\right)\sum_{k=0}^{N}\delta_k \leq\sum_{k=0}^{N}\delta_k\left\|q^k\right\|^2. ( 0 ≤ k ≤ N min q k 2 ) k = 0 ∑ N δ k ≤ k = 0 ∑ N δ k q k 2 .
The summability assertion in (v) follows from (9). If lim inf k λ k > 0 \liminf_k\lambda_k>0 lim inf k λ k > 0 , the convergence U 1 / 2 ( z k − z ⋆ ) → 0 U^{1/2}(z^k-z^\star)\to0 U 1/2 ( z k − z ⋆ ) → 0 follows. If U ⪰ μ Id U\succeq\mu\operatorname{Id} U ⪰ μ Id for some μ > 0 \mu>0 μ > 0 , then ∑ k λ k ∥ z k − z ⋆ ∥ 2 < + ∞ \sum_k\lambda_k\left\|z^k-z^\star\right\|^2<+\infty ∑ k λ k z k − z ⋆ 2 < + ∞ . By (i), the sequence a k : = ∥ z k − z ⋆ ∥ 2 a_k:=\left\|z^k-z^\star\right\|^2 a k := z k − z ⋆ 2 is nonincreasing, so a k → a a_k\to a a k → a for some a ≥ 0 a\geq0 a ≥ 0 . If a > 0 a>0 a > 0 , then ∑ k λ k a k ≥ a ∑ k λ k = + ∞ \sum_k\lambda_k a_k\geq a\sum_k\lambda_k=+\infty ∑ k λ k a k ≥ a ∑ k λ k = + ∞ , a contradiction. Hence a = 0 a=0 a = 0 , proving z k → z ⋆ z^k\to z^\star z k → z ⋆ strongly. Furthermore, if lim inf k λ k > 0 \liminf_k\lambda_k>0 lim inf k λ k > 0 , then (8) and U ⪰ μ Id U\succeq\mu\operatorname{Id} U ⪰ μ Id give ∥ z k + 1 − z ⋆ ∥ 2 ≤ ( 1 − 2 μ λ k ) ∥ z k − z ⋆ ∥ 2 \left\|z^{k+1}-z^\star\right\|^2\leq(1-2\mu\lambda_k)\left\|z^k-z^\star\right\|^2 z k + 1 − z ⋆ 2 ≤ ( 1 − 2 μ λ k ) z k − z ⋆ 2 . Since λ k \lambda_k λ k is eventually bounded away from zero, this yields Q Q Q -linear convergence. This completes the proof of (v). □
For q k ≠ 0 q^k\ne0 q k = 0 , the largest admissible coefficient in Proposition 3.1 is β k = ⟨ q k , V q k ⟩ / ∥ q k ∥ 2 ≥ η \beta_k=\langle q^k,Vq^k\rangle/\left\|q^k\right\|^2\geq\eta β k = ⟨ q k , V q k ⟩ / q k 2 ≥ η . Thus, the relaxation adapts to the residual direction and may exceed 2 η 2\eta 2 η . We may also take β k ≡ η \beta_k\equiv\eta β k ≡ η , which gives the fixed stepsize condition 0 < λ k < 2 η 0<\lambda_k<2\eta 0 < λ k < 2 η .
Remark 3.2 (Relation with classical fixed-point iterations). Suppose that F : K → K F:\mathcal{K}\to\mathcal{K} F : K → K is single-valued and β \beta β -quasi-cocoercive relative to S = zer F S=\operatorname{zer}F S = zer F , corresponding to U = 0 U=0 U = 0 and V = β Id V=\beta\operatorname{Id} V = β Id . Taking β k ≡ β \beta_k\equiv\beta β k ≡ β , T : = Id − F T:=\operatorname{Id}-F T := Id − F , and ρ : = 1 / ( 2 β ) \rho:=1/(2\beta) ρ := 1/ ( 2 β ) , we have δ k = ρ − 1 λ k ( 1 − ρ λ k ) \delta_k=\rho^{-1}\lambda_k(1-\rho\lambda_k) δ k = ρ − 1 λ k ( 1 − ρ λ k ) and the iteration in Proposition 3.1 becomes z k + 1 = ( 1 − λ k ) z k + λ k T z k z^{k+1}=(1-\lambda_k)z^k+\lambda_kTz^k z k + 1 = ( 1 − λ k ) z k + λ k T z k . By Remark 2.2(i), T T T is conically ρ \rho ρ -quasiaveraged. In this setting, Proposition 3.1(i),(ii) recover the Fejér monotonicity and residual convergence in [9 Proposition 2.2(i),(ii)] . The ergodic estimate in [9 Proposition 2.2(iii)] also follows from the residual summability in Proposition 3.1(ii) and Jensen’s inequality. Moreover, under demiclosedness of F F F at zero, the weak convergence conclusion in Proposition 3.1(ii) is consistent with the classical result of [24 Theorem 1] .
Unlike these single-valued formulations, Proposition 3.1 permits arbitrary selections from a set-valued F F F , operator-valued moduli U , V U,V U , V , and iteration-dependent coefficients β k \beta_k β k . The nonnegative U U U -term additionally yields further conclusions in Proposition 3.1(v).
Linear convergence under metric subregularity
Metric subregularity is a standard local error-bound property for set-valued mappings; see, e.g., [10 Section 3H] . Together with suitable descent properties, metric subregularity has been used to establish local linear convergence of proximal and fixed-point iterations, both in Hilbert-space monotone settings [18 ] and in finite-dimensional nonmonotone settings [12 , 21 ] .
Definition 3.3 (Metric subregularity). Let F : K ⇉ K F:\mathcal{K}\rightrightarrows\mathcal{K} F : K ⇉ K and let ( z ˉ , q ˉ ) ∈ gra F (\bar z,\bar q)\in\operatorname{gra}F ( z ˉ , q ˉ ) ∈ gra F . We say that F F F is metrically subregular at z ˉ \bar z z ˉ for q ˉ \bar q q ˉ if there exist χ , R > 0 \chi,R>0 χ , R > 0 such that
dist ( z , F − 1 ( q ˉ ) ) ≤ χ dist ( q ˉ , F ( z ) ) ∀ z ∈ B R ( z ˉ ) . \operatorname{dist}(z,F^{-1}(\bar q))\leq\chi\operatorname{dist}(\bar q,F(z))\qquad\forall z\in B_R(\bar z). dist ( z , F − 1 ( q ˉ )) ≤ χ dist ( q ˉ , F ( z )) ∀ z ∈ B R ( z ˉ ) .
For q ˉ = 0 \bar q=0 q ˉ = 0 , this is the local error bound dist ( z , zer F ) ≤ χ dist ( 0 , F ( z ) ) \operatorname{dist}(z,\operatorname{zer}F)\leq\chi\operatorname{dist}(0,F(z)) dist ( z , zer F ) ≤ χ dist ( 0 , F ( z )) . Equivalently, metric subregularity of F F F corresponds to calmness of F − 1 F^{-1} F − 1 ; see [10 ] . We establish local linear convergence under metric subregularity of F F F or G : = ( F − 1 − Id ) − 1 G:=(F^{-1}-\operatorname{Id})^{-1} G := ( F − 1 − Id ) − 1 . Note that q ∈ F ( z ) q\in F(z) q ∈ F ( z ) if and only if q ∈ G ( z − q ) q\in G(z-q) q ∈ G ( z − q ) , and zer G = zer F \operatorname{zer}G=\operatorname{zer}F zer G = zer F .
Proposition 3.4 (Local linear convergence under metric subregularity). Let F : K ⇉ K F:\mathcal{K}\rightrightarrows\mathcal{K} F : K ⇉ K be relatively ( U , V ) (U,V) ( U , V ) -semimonotone with respect to zer F ≠ ∅ \operatorname{zer}F\ne\varnothing zer F = ∅ , where U ⪰ − ε Id U\succeq-\varepsilon\operatorname{Id} U ⪰ − ε Id for some ε ≥ 0 \varepsilon\geq0 ε ≥ 0 and V ⪰ η Id V\succeq\eta\operatorname{Id} V ⪰ η Id for
some η > 0 \eta> 0 η > 0 . Fix z ⋆ ∈ zer F z^\star\in\operatorname{zer} F z ⋆ ∈ zer F and suppose that, for some R > 0 R > 0 R > 0 , F F F has nonempty values on B R ( z ⋆ ) B_R(z^\star) B R ( z ⋆ ) and one of the following holds:
(a) F F F is metrically subregular at z ⋆ z^\star z ⋆ for zero with modulus χ > 0 \chi> 0 χ > 0 , with the error bound holding on B R ( z ⋆ ) B_R(z^\star) B R ( z ⋆ ) ;
(b) G G G is metrically subregular at z ⋆ z^\star z ⋆ for zero with modulus χ ^ > 0 \widehat{\chi} > 0 χ > 0 , with the error bound holding on B R ( z ⋆ ) B_R(z^\star) B R ( z ⋆ ) .
Let { z k } \{z^k\} { z k } be generated by (6) with 0 < λ k ≤ 2 β k 0 < \lambda_k \le2\beta_k 0 < λ k ≤ 2 β k , where β k ≥ η \beta_k \ge\eta β k ≥ η satisfies ⟨ q k , V q k ⟩ ≥ β k ∥ q k ∥ 2 \langle q^k,Vq^k\rangle\ge\beta_k\lVert q^k\rVert^2 ⟨ q k , V q k ⟩ ≥ β k ∥ q k ∥ 2 . Under (a) or (b), respectively, set
Δ k : = { λ k ( 2 β k − λ k − 2 ε χ 2 ) , under (a) , λ k [ 2 β k − λ k − 2 ε ( χ ^ + ∣ 1 − λ k ∣ ) 2 ] , under (b) . (14) \Delta_k :=
\begin{cases}
\lambda_k(2\beta_k-\lambda_k-2\varepsilon\chi^2), & \text{under (a)},\\
\lambda_k[2\beta_k-\lambda_k-2\varepsilon(\widehat{\chi}+|1-\lambda_k|)^2], & \text{under (b)}.
\end{cases} \tag*{(14)} Δ k := { λ k ( 2 β k − λ k − 2 ε χ 2 ) , λ k [ 2 β k − λ k − 2 ε ( χ + ∣1 − λ k ∣ ) 2 ] , under (a) , under (b) . (14)
and suppose that Δ k ≥ κ \Delta_k \ge\kappa Δ k ≥ κ for all k k k , where κ > 0 \kappa> 0 κ > 0 . Define m ε ( t ) : = ( 1 + 1 + 4 t ε ) / ( 2 t ) m_\varepsilon(t) := (1+\sqrt{1+4t\varepsilon})/(2t) m ε ( t ) := ( 1 + 1 + 4 tε ) / ( 2 t ) . Then there exist r ∈ ( 0 , R ) r \in(0,R) r ∈ ( 0 , R ) , ρ ∈ [ 0 , 1 ) \rho\in[0,1) ρ ∈ [ 0 , 1 ) , and Γ > 0 \Gamma> 0 Γ > 0 (depending only on R R R , κ \kappa κ , ε \varepsilon ε , η \eta η , ∥ V ∥ \lVert V\rVert ∥ V ∥ , and χ \chi χ or χ ^ \widehat{\chi} χ ) such that, whenever z 0 ∈ B r ( z ⋆ ) z^0 \in B_r(z^\star) z 0 ∈ B r ( z ⋆ ) , the following hold.
(i) The iterates satisfy z k ∈ B R ( z ⋆ ) z^k \in B_R(z^\star) z k ∈ B R ( z ⋆ ) for all k k k , and, under (b), also z k − q k ∈ B R ( z ⋆ ) z^k-q^k \in B_R(z^\star) z k − q k ∈ B R ( z ⋆ ) .
(ii) If d k : = dist ( z k , zer F ) d_k := \operatorname{dist}(z^k,\operatorname{zer} F) d k := dist ( z k , zer F ) , then d k + 1 ≤ ρ d k d_{k+1} \le\rho d_k d k + 1 ≤ ρ d k , and hence d k ≤ d 0 ρ k d_k \le d_0\rho^k d k ≤ d 0 ρ k . Moreover, ∥ q k ∥ ≤ m ε ( η ) d 0 ρ k \lVert q^k\rVert\le m_\varepsilon(\eta)d_0\rho^k ∥ q k ∥ ≤ m ε ( η ) d 0 ρ k , and ∥ z k + 1 − z k ∥ ≤ ( 1 − ρ ) Γ d k \lVert z^{k+1}-z^k\rVert\le(1-\rho)\Gamma d_k ∥ z k + 1 − z k ∥ ≤ ( 1 − ρ ) Γ d k .
(iii) The sequence { z k } \{z^k\} { z k } converges strongly to some z ∞ ∈ zer F z^\infty\in\operatorname{zer} F z ∞ ∈ zer F , and, for every m ≥ k m \ge k m ≥ k , ∥ z m − z k ∥ ≤ Γ d k \lVert z^m-z^k\rVert\le\Gamma d_k ∥ z m − z k ∥ ≤ Γ d k and ∥ z k − z ∞ ∥ ≤ Γ d k \lVert z^k-z^\infty\rVert\le\Gamma d_k ∥ z k − z ∞ ∥ ≤ Γ d k .
(iv) The auxiliary sequence z ^ k : = z k − q k \widehat{z}^k := z^k-q^k z k := z k − q k converges strongly to z ∞ z^\infty z ∞ , with ∥ z ^ k − z ∞ ∥ ≤ ( Γ + m ε ( β k ) ) d k \lVert\widehat{z}^k-z^\infty\rVert\le(\Gamma+m_\varepsilon(\beta_k))d_k ∥ z k − z ∞ ∥ ≤ ( Γ + m ε ( β k )) d k .
If ε = 0 \varepsilon= 0 ε = 0 , the bounds in (iii)–(iv) hold with Γ \Gamma Γ replaced by min { 2 , Γ } \min\{2,\Gamma\} min { 2 , Γ } , and m 0 ( β k ) = 1 / β k m_0(\beta_k)=1/\beta_k m 0 ( β k ) = 1/ β k .
Proof. For every z ∈ zer F z \in\operatorname{zer} F z ∈ zer F , relative semimonotonicity and V ⪰ η Id V \succeq\eta\operatorname{Id} V ⪰ η Id imply F ( z ) = { 0 } F(z)=\{0\} F ( z ) = { 0 } . Thus, if q k = 0 q^k=0 q k = 0 for some k k k , the iteration is stationary thereafter. We may therefore assume that q k ≠ 0 q^k\ne0 q k = 0 for all k k k . For q k ≠ 0 q^k\ne0 q k = 0 , note that η ≤ β k ≤ β ‾ \eta\le\beta_k \le\overline{\beta} η ≤ β k ≤ β where β ‾ : = ∥ V ∥ \overline{\beta}:=\lVert V\rVert β := ∥ V ∥ . Relative semimonotonicity gives, for every w ∈ zer F w \in\operatorname{zer} F w ∈ zer F ,
⟨ q k , z k − w ⟩ ≥ β k ∥ q k ∥ 2 − ε ∥ z k − w ∥ 2 . (15) \langle q^k,z^k-w\rangle\ge\beta_k\lVert q^k\rVert^2-\varepsilon\lVert z^k-w\rVert^2. \tag*{(15)} ⟨ q k , z k − w ⟩ ≥ β k ∥ q k ∥ 2 − ε ∥ z k − w ∥ 2 . (15)
By Cauchy–Schwarz and solving the quadratic inequality for ∥ q k ∥ \lVert q^k\rVert ∥ q k ∥ 6 , (15) gives ∥ q k ∥ ≤ m ε ( β k ) ∥ z k − w ∥ \lVert q^k\rVert\le m_\varepsilon(\beta_k)\lVert z^k-w\rVert ∥ q k ∥ ≤ m ε ( β k ) ∥ z k − w ∥ , and taking the infimum over w ∈ zer F w \in\operatorname{zer} F w ∈ zer F yields ∥ q k ∥ ≤ m ε ( β k ) d k \lVert q^k\rVert\le m_\varepsilon(\beta_k)d_k ∥ q k ∥ ≤ m ε ( β k ) d k . Since m ε m_\varepsilon m ε is nonincreasing and η ≤ β k ≤ β ‾ \eta\le\beta_k \le\overline{\beta} η ≤ β k ≤ β , we have ∥ q k ∥ ≤ M d k \lVert q^k\rVert\le M d_k ∥ q k ∥ ≤ M d k where M : = m ε ( η ) M:=m_\varepsilon(\eta) M := m ε ( η ) . Moreover,
∥ z k + 1 − z k ∥ = λ k ∥ q k ∥ ≤ 2 β k m ε ( β k ) d k = ( 1 + 1 + 4 ε β k ) d k ≤ Θ d k , (16) \lVert z^{k+1}-z^k\rVert=\lambda_k\lVert q^k\rVert\le2\beta_km_\varepsilon(\beta_k)d_k=(1+\sqrt{1+4\varepsilon\beta_k})d_k\le\Theta d_k, \tag*{(16)} ∥ z k + 1 − z k ∥ = λ k ∥ q k ∥ ≤ 2 β k m ε ( β k ) d k = ( 1 + 1 + 4 ε β k ) d k ≤ Θ d k , (16)
where Θ : = 1 + 1 + 4 ε β ‾ \Theta:=1+\sqrt{1+4\varepsilon\overline{\beta}} Θ := 1 + 1 + 4 ε β .
Set δ k : = λ k ( 2 β k − λ k ) \delta_k:=\lambda_k(2\beta_k-\lambda_k) δ k := λ k ( 2 β k − λ k ) . From (6) and (15) , for every w ∈ zer F w \in\operatorname{zer} F w ∈ zer F ,
∥ z k + 1 − w ∥ 2 ≤ ( 1 + 2 λ k ε ) ∥ z k − w ∥ 2 − δ k ∥ q k ∥ 2 . (17) \lVert z^{k+1}-w\rVert^2\le(1+2\lambda_k\varepsilon)\lVert z^k-w\rVert^2-\delta_k\lVert q^k\rVert^2. \tag*{(17)} ∥ z k + 1 − w ∥ 2 ≤ ( 1 + 2 λ k ε ) ∥ z k − w ∥ 2 − δ k ∥ q k ∥ 2 . (17)
Taking the infimum over w ∈ zer F w \in\operatorname{zer} F w ∈ zer F gives
d k + 1 2 ≤ ( 1 + 2 λ k ε ) d k 2 − δ k ∥ q k ∥ 2 . (18) d_{k+1}^{2} \le\left(1+2\lambda_k\varepsilon\right)d_k^{2}-\delta_k\left\|q^k\right\|^{2}. \tag*{(18)} d k + 1 2 ≤ ( 1 + 2 λ k ε ) d k 2 − δ k q k 2 . (18)
Under (a), if z k ∈ B R ( z ⋆ ) z^k \in B_R(z^\star) z k ∈ B R ( z ⋆ ) , the error bound gives d k ≤ χ ∥ q k ∥ d_k \le\chi\left\|q^k\right\| d k ≤ χ q k , and hence d k + 1 2 ≤ ( 1 − Δ k / χ 2 ) d k 2 d_{k+1}^{2} \le\left(1-\Delta_k/\chi^2\right)d_k^{2} d k + 1 2 ≤ ( 1 − Δ k / χ 2 ) d k 2 . Under (b), if z k − q k ∈ B R ( z ⋆ ) z^k-q^k \in B_R(z^\star) z k − q k ∈ B R ( z ⋆ ) , then q k ∈ G ( z k − q k ) q^k \in G(z^k-q^k) q k ∈ G ( z k − q k ) yields dist ( z k − q k , zer F ) ≤ χ ~ ∥ q k ∥ \operatorname{dist}(z^k-q^k,\operatorname{zer} F) \le\widetilde{\chi}\left\|q^k\right\| dist ( z k − q k , zer F ) ≤ χ q k . Set b k : = χ ~ + ∣ 1 − λ k ∣ b_k:=\widetilde{\chi}+\lvert1-\lambda_k\rvert b k := χ + ∣ 1 − λ k ∣ . The triangle inequality and (6) gives d k + 1 ≤ b k ∥ q k ∥ d_{k+1}\le b_k\left\|q^k\right\| d k + 1 ≤ b k q k , so (18) yields ( b k 2 + δ k ) d k + 1 2 ≤ ( 1 + 2 λ k ε ) b k 2 d k 2 (b_k^2+\delta_k)d_{k+1}^2\le(1+2\lambda_k\varepsilon)b_k^2d_k^2 ( b k 2 + δ k ) d k + 1 2 ≤ ( 1 + 2 λ k ε ) b k 2 d k 2 , and therefore d k + 1 2 ≤ ( 1 − Δ k / ( b k 2 + δ k ) ) d k 2 d_{k+1}^2\le\left(1-\Delta_k/(b_k^2+\delta_k)\right)d_k^2 d k + 1 2 ≤ ( 1 − Δ k / ( b k 2 + δ k ) ) d k 2 . As δ k ≤ β ‾ 2 \delta_k\le\overline{\beta}^2 δ k ≤ β 2 , b k ≤ χ ~ + 1 + 2 β ‾ b_k\le\widetilde{\chi}+1+2\overline{\beta} b k ≤ χ + 1 + 2 β , and Δ k ≥ κ \Delta_k\ge\kappa Δ k ≥ κ , we have d k + 1 2 ≤ ( 1 − κ / D ) d k 2 d_{k+1}^2\le(1-\kappa/D)d_k^2 d k + 1 2 ≤ ( 1 − κ / D ) d k 2 where D : = β ‾ 2 + ( χ ~ + 1 + 2 β ‾ ) 2 D:=\overline{\beta}^2+(\widetilde{\chi}+1+2\overline{\beta})^2 D := β 2 + ( χ + 1 + 2 β ) 2 . Thus, with
ρ 2 : = { max { 0 , 1 − κ / χ 2 } , under (a) max { 0 , 1 − κ / D } , under (b) , \rho^2:=\begin{cases}
\max\{0,1-\kappa/\chi^2\}, & \text{under (a)}\\
\max\{0,1-\kappa/D\}, & \text{under (b)},
\end{cases} ρ 2 := { max { 0 , 1 − κ / χ 2 } , max { 0 , 1 − κ / D } , under (a) under (b) ,
where ρ ∈ [ 0 , 1 ) \rho\in[0,1) ρ ∈ [ 0 , 1 ) , we have shown that
d k + 1 ≤ ρ d k whenever { z k ∈ B R ( z ⋆ ) , under (a) , or z k − q k ∈ B R ( z ⋆ ) under (b) . (19) d_{k+1}\le\rho d_k\quad\text{whenever}\quad
\begin{cases}
z^k\in B_R(z^\star), & \text{under (a)},\ \text{or}\\
z^k-q^k\in B_R(z^\star) & \text{under (b)}.
\end{cases} \tag*{(19)} d k + 1 ≤ ρ d k whenever { z k ∈ B R ( z ⋆ ) , z k − q k ∈ B R ( z ⋆ ) under (a) , or under (b) . (19)
Set Γ : = Θ / ( 1 − ρ ) \Gamma:=\Theta/(1-\rho) Γ := Θ/ ( 1 − ρ ) . Choose r ∈ ( 0 , R ) r\in(0,R) r ∈ ( 0 , R ) so that ( 1 + Γ ) r < R (1+\Gamma)r<R ( 1 + Γ ) r < R under (a), or ( 1 + Γ + M ) r < R (1+\Gamma+M)r<R ( 1 + Γ + M ) r < R under (b). Let z 0 ∈ B r ( z ⋆ ) z^0\in B_r(z^\star) z 0 ∈ B r ( z ⋆ ) . Under (a), we prove by induction that z k ∈ B R ( z ⋆ ) z^k\in B_R(z^\star) z k ∈ B R ( z ⋆ ) and d k + 1 ≤ ρ d k d_{k+1}\le\rho d_k d k + 1 ≤ ρ d k . Indeed, suppose that z j ∈ B R ( z ⋆ ) z^j\in B_R(z^\star) z j ∈ B R ( z ⋆ ) for all j < k j<k j < k . By (19) , d j ≤ ρ j d 0 d_j\le\rho^j d_0 d j ≤ ρ j d 0 for j ≤ k j\le k j ≤ k . Using (16) ,
∥ z k − z ⋆ ∥ ≤ ∥ z 0 − z ⋆ ∥ + Θ ∑ j = 1 k d j − 1 ≤ ∥ z 0 − z ⋆ ∥ + Γ d 0 ≤ ( 1 + Γ ) ∥ z 0 − z ⋆ ∥ < R . (20) \left\|z^k-z^\star\right\|\le\left\|z^0-z^\star\right\|+\Theta\sum_{j=1}^{k}d_{j-1}
\le\left\|z^0-z^\star\right\|+\Gamma d_0\le(1+\Gamma)\left\|z^0-z^\star\right\|<R. \tag*{(20)} z k − z ⋆ ≤ z 0 − z ⋆ + Θ j = 1 ∑ k d j − 1 ≤ z 0 − z ⋆ + Γ d 0 ≤ ( 1 + Γ ) z 0 − z ⋆ < R . (20)
Thus, z k ∈ B R ( z ⋆ ) z^k\in B_R(z^\star) z k ∈ B R ( z ⋆ ) , and hence d k + 1 ≤ ρ d k d_{k+1}\le\rho d_k d k + 1 ≤ ρ d k by (19) . This completes the induction under (a).
Under (b), since ∥ q 0 ∥ ≤ M d 0 \left\|q^0\right\|\le Md_0 q 0 ≤ M d 0 , we have ∥ z 0 − q 0 − z ⋆ ∥ ≤ ( 1 + M ) ∥ z 0 − z ⋆ ∥ < R \left\|z^0-q^0-z^\star\right\|\le(1+M)\left\|z^0-z^\star\right\|<R z 0 − q 0 − z ⋆ ≤ ( 1 + M ) z 0 − z ⋆ < R . Thus, the base case z 0 − q 0 ∈ B R ( z ⋆ ) z^0-q^0\in B_R(z^\star) z 0 − q 0 ∈ B R ( z ⋆ ) holds. Suppose that z j − q j ∈ B R ( z ⋆ ) z^j-q^j\in B_R(z^\star) z j − q j ∈ B R ( z ⋆ ) for all j < k j<k j < k . By (19) , d j ≤ ρ j d 0 d_j\le\rho^j d_0 d j ≤ ρ j d 0 for j ≤ k j\le k j ≤ k . Arguing as in (a), we obtain ∥ z k − z ⋆ ∥ ≤ ( 1 + Γ ) ∥ z 0 − z ⋆ ∥ < R \left\|z^k-z^\star\right\|\le(1+\Gamma)\left\|z^0-z^\star\right\|<R z k − z ⋆ ≤ ( 1 + Γ ) z 0 − z ⋆ < R . Moreover, since ∥ q k ∥ ≤ M d k ≤ M d 0 \left\|q^k\right\|\le Md_k\le Md_0 q k ≤ M d k ≤ M d 0 ,
∥ z k − q k − z ⋆ ∥ ≤ ∥ z k − z ⋆ ∥ + ∥ q k ∥ ≤ ( 1 + Γ + M ) ∥ z 0 − z ⋆ ∥ < R . \left\|z^k-q^k-z^\star\right\|\le\left\|z^k-z^\star\right\|+\left\|q^k\right\|
\le(1+\Gamma+M)\left\|z^0-z^\star\right\|<R. z k − q k − z ⋆ ≤ z k − z ⋆ + q k ≤ ( 1 + Γ + M ) z 0 − z ⋆ < R .
Thus, z k , z k − q k ∈ B R ( z ⋆ ) z^k,z^k-q^k\in B_R(z^\star) z k , z k − q k ∈ B R ( z ⋆ ) , and hence d k + 1 ≤ ρ d k d_{k+1}\le\rho d_k d k + 1 ≤ ρ d k by (19) . This completes the induction under (b). Hence, we have proved (i) and (ii).
For every m ≥ k m\ge k m ≥ k , (16) and triangle inequality gives ∥ z m − z k ∥ ≤ Θ ∑ j = k m − 1 d j ≤ Γ d k \left\|z^m-z^k\right\|\le\Theta\sum_{j=k}^{m-1}d_j\le\Gamma d_k z m − z k ≤ Θ ∑ j = k m − 1 d j ≤ Γ d k . Since d k → 0 d_k\to0 d k → 0 , the sequence { z k } \{z^k\} { z k } is Cauchy and converges strongly to some z ∞ ∈ K z^\infty\in K z ∞ ∈ K . Letting k → ∞ k\to\infty k → ∞ in (20) , we have ∥ z ∞ − z ⋆ ∥ ≤ ( 1 + Γ ) ∥ z 0 − z ⋆ ∥ < R \left\|z^\infty-z^\star\right\|\le(1+\Gamma)\left\|z^0-z^\star\right\|<R ∥ z ∞ − z ⋆ ∥ ≤ ( 1 + Γ ) z 0 − z ⋆ < R . Moreover, dist ( z ∞ , zer F ) ≤ ∥ z ∞ − z k ∥ + d k → 0 \operatorname{dist}(z^\infty,\operatorname{zer} F)\le\left\|z^\infty-z^k\right\|+d_k\to0 dist ( z ∞ , zer F ) ≤ z ∞ − z k + d k → 0 , so z ∞ ∈ cl ( zer F ) z^\infty\in\operatorname{cl}(\operatorname{zer} F) z ∞ ∈ cl ( zer F ) . Choose q ∈ F ( z ∞ ) q\in F(z^\infty) q ∈ F ( z ∞ ) , which is possible since z ∞ ∈ B R ( z ⋆ ) z^\infty\in B_R(z^\star) z ∞ ∈ B R ( z ⋆ ) , and let w j ∈ zer F w_j\in\operatorname{zer} F w j ∈ zer F converge to z ∞ z^\infty z ∞ . Relative semimonotonicity yields η ∥ q ∥ 2 ≤ ⟨ q , z ∞ − w j ⟩ + ε ∥ z ∞ − w j ∥ 2 \eta\left\|q\right\|^2\le\langle q,z^\infty-w_j\rangle+\varepsilon\left\|z^\infty-w_j\right\|^2 η ∥ q ∥ 2 ≤ ⟨ q , z ∞ − w j ⟩ + ε ∥ z ∞ − w j ∥ 2 . Letting j → ∞ j\to\infty j → ∞ gives q = 0 q=0 q = 0 , and hence z ∞ ∈ zer F z^\infty\in\operatorname{zer} F z ∞ ∈ zer F . Letting m → ∞ m\to\infty m → ∞ in ∥ z m − z k ∥ ≤ Γ d k \left\|z^m-z^k\right\|\le\Gamma d_k z m − z k ≤ Γ d k proves ∥ z k − z ∞ ∥ ≤ Γ d k \left\|z^k-z^\infty\right\|\le\Gamma d_k z k − z ∞ ≤ Γ d k . This proves (iii).
By (i), q k → 0 q^k\to0 q k → 0 , and hence z ^ k = z k − q k → z ∞ \widehat{z}^k=z^k-q^k\to z^\infty z k = z k − q k → z ∞ . The triangle inequality gives ∥ z ^ k − z ∞ ∥ ≤ [ Γ + m ε ( β k ) ] d k \left\|\widehat{z}^k-z^\infty\right\|\le[\Gamma+m_\varepsilon(\beta_k)]d_k z k − z ∞ ≤ [ Γ + m ε ( β k )] d k , proving (iv). Finally, when ε = 0 \varepsilon=0 ε = 0 , (17) shows that the sequence is Fejér monotone with respect to zer F \operatorname{zer} F zer F . Thus, for every m ≥ k m\ge k m ≥ k and w ∈ zer F w\in\operatorname{zer} F w ∈ zer F , $\left|z^m-z^k\right|\le\left|z^m-w\right|+\left|z^k-w\right| \le 2 ∥ z k − w ∥ 2\lVert z^k-w\rVert 2 ∥ z k − w ∥ . Taking the infimum over w ∈ zer F w \in\operatorname{zer} F w ∈ zer F gives ∥ z m − z k ∥ ≤ 2 d k \lVert z^m-z^k\rVert\le2d_k ∥ z m − z k ∥ ≤ 2 d k . Letting m → ∞ m \to\infty m → ∞ yields the improved bounds in (iii). The corresponding bound in (iv) follows by the triangle inequality and m 0 ( β k ) = 1 / β k m_0(\beta_k)=1/\beta_k m 0 ( β k ) = 1/ β k .
Under (a), if η > ε χ ^ 2 \eta>\varepsilon\widehat{\chi}^{2} η > ε χ 2 , choosing λ k ≡ η − ε χ ^ 2 \lambda_k\equiv\eta-\varepsilon\widehat{\chi}^{2} λ k ≡ η − ε χ 2 and β k ≡ η \beta_k\equiv\eta β k ≡ η gives Δ k = ( η − ε χ ^ 2 ) 2 > 0 \Delta_k=(\eta-\varepsilon\widehat{\chi}^{2})^2>0 Δ k = ( η − ε χ 2 ) 2 > 0 . Under (b), λ k ≡ 1 \lambda_k\equiv1 λ k ≡ 1 and β k ≡ η \beta_k\equiv\eta β k ≡ η are admissible whenever 2 η − 1 > 2 ε χ ^ 2 2\eta-1>2\varepsilon\widehat{\chi}^{2} 2 η − 1 > 2 ε χ 2 , since then Δ k = 2 η − 1 − 2 ε χ ^ 2 > 0 \Delta_k=2\eta-1-2\varepsilon\widehat{\chi}^{2}>0 Δ k = 2 η − 1 − 2 ε χ 2 > 0 .
Under the hypotheses of Proposition 3.4 , metric subregularity of G G G at z ⋆ z^\star z ⋆ for zero implies that of F F F with modulus 1 + χ ^ 1+\widehat{\chi} 1 + χ . Indeed, for z z z near z ⋆ z^\star z ⋆ and q ∈ F ( z ) q\in F(z) q ∈ F ( z ) , the residual bound gives ∥ q ∥ ≤ m ε ( η ) ∥ z − z ⋆ ∥ \lVert q\rVert\le m_\varepsilon(\eta)\lVert z-z^\star\rVert ∥ q ∥ ≤ m ε ( η ) ∥ z − z ⋆ ∥ , so z − q z-q z − q also lies in the corresponding neighborhood. Hence, dist ( z , zer F ) ≤ ( 1 + χ ^ ) ∥ q ∥ \operatorname{dist}(z,\operatorname{zer} F)\le(1+\widehat{\chi})\lVert q\rVert dist ( z , zer F ) ≤ ( 1 + χ ) ∥ q ∥ . Thus, (b) implies (a) locally, although (b) can yield a smaller contraction factor, as illustrated in Remark 3.5.
If U ⪰ μ Id U\succeq\mu\operatorname{Id} U ⪰ μ Id for some μ > 0 \mu>0 μ > 0 , then zer F = { z ⋆ } \operatorname{zer} F=\{z^\star\} zer F = { z ⋆ } , and relative semimonotonicity and Cauchy–Schwarz give μ ∥ z − z ⋆ ∥ ≤ ∥ q ∥ \mu\lVert z-z^\star\rVert\le\lVert q\rVert μ ∥ z − z ⋆ ∥ ≤ ∥ q ∥ for every ( z , q ) ∈ gra F (z,q)\in\operatorname{gra} F ( z , q ) ∈ gra F . Thus, F F F is globally metrically subregular with modulus 1 / μ 1/\mu 1/ μ . The corresponding direct convergence result is given by Proposition 3.1(v).
Remark 3.5 (Relation to almost averagedness and ordinary PPA). For constant λ k ≡ λ \lambda_k\equiv\lambda λ k ≡ λ and β k ≡ β \beta_k\equiv\beta β k ≡ β , (13) has the algebraic form of the pointwise almost-averaged inequality, with violation 2 λ ε 2\lambda\varepsilon 2 λ ε and averaging constant λ / ( 2 β ) \lambda/(2\beta) λ / ( 2 β ) ; see [21 Proposition 2.1(iii)] .
Let t > 0 t>0 t > 0 and consider the proximal point iteration z k + 1 ∈ J t A z k z^{k+1}\in J_{tA}z^k z k + 1 ∈ J t A z k , where J t A : = ( Id + t A ) − 1 J_{tA}:=(\operatorname{Id}+tA)^{-1} J t A := ( Id + t A ) − 1 . This is (6) with λ k ≡ 1 \lambda_k\equiv1 λ k ≡ 1 and F : = Id − J t A F:=\operatorname{Id}-J_{tA} F := Id − J t A , since q k : = z k − z k + 1 ∈ F ( z k ) q^k:=z^k-z^{k+1}\in F(z^k) q k := z k − z k + 1 ∈ F ( z k ) . Moreover, G = ( F − 1 − Id ) − 1 = t A G=(F^{-1}-\operatorname{Id})^{-1}=tA G = ( F − 1 − Id ) − 1 = t A and zer F = zer A \operatorname{zer} F=\operatorname{zer} A zer F = zer A . Local submonotonicity of t A tA t A with violation ν ≥ 0 \nu\ge0 ν ≥ 0 in the sense of [20 Definition 2] gives ⟨ q , z − w ⟩ ≥ ∥ q ∥ 2 − ν ∥ z − w ∥ 2 \langle q,z-w\rangle\ge\lVert q\rVert^2-\nu\lVert z-w\rVert^2 ⟨ q , z − w ⟩ ≥ ∥ q ∥ 2 − ν ∥ z − w ∥ 2 for nearby zeros w w w and q ∈ F ( z ) q\in F(z) q ∈ F ( z ) satisfying the local graph restrictions. Thus, F F F satisfies a local form of (11) with β k ≡ 1 \beta_k\equiv1 β k ≡ 1 and ε = ν \varepsilon=\nu ε = ν . In the notation of Definition 2.1 , their condition is local ( − ϑ / t Id , − t ϑ Id ) (-\vartheta/t\operatorname{Id},-t\vartheta\operatorname{Id}) ( − ϑ / t Id , − tϑ Id ) -semimonotonicity of A A A , where ϑ : = ν / ( 1 + 2 ν ) \vartheta:=\nu/(1+2\nu) ϑ := ν / ( 1 + 2 ν ) ; cf. Lemma 4.3 with P = t − 1 Id P=t^{-1}\operatorname{Id} P = t − 1 Id and τ = − ϑ \tau=-\vartheta τ = − ϑ .
Suppose that A A A is metrically subregular at the reference zero for zero with modulus χ A > 0 \chi_A>0 χ A > 0 , and set a : = χ A / t a:=\chi_A/t a := χ A / t . Then G = t A G=tA G = t A is metrically subregular with modulus a a a . For λ k = β k = 1 \lambda_k=\beta_k=1 λ k = β k = 1 , the one-step estimate d k + 1 2 ≤ ( 1 − Δ k / ( b k + δ k ) ) d k 2 d_{k+1}^2\le(1-\Delta_k/(b_k+\delta_k))d_k^2 d k + 1 2 ≤ ( 1 − Δ k / ( b k + δ k )) d k 2 in the proof of Proposition 3.4 (b) has δ k = 1 \delta_k=1 δ k = 1 , b k = a b_k=a b k = a , and Δ k = 1 − 2 ν a 2 \Delta_k=1-2\nu a^2 Δ k = 1 − 2 ν a 2 . Hence, the squared contraction factor is ρ 2 = ( 1 + 2 ν ) a 2 / ( 1 + a 2 ) \rho^2=(1+2\nu)a^2/(1+a^2) ρ 2 = ( 1 + 2 ν ) a 2 / ( 1 + a 2 ) , provided 2 ν a 2 < 1 2\nu a^2<1 2 ν a 2 < 1 . This is strictly smaller than the limiting squared factor 1 + 2 ν − ( 1 + a ) − 2 1+2\nu-(1+a)^{-2} 1 + 2 ν − ( 1 + a ) − 2 in [20 Theorem 2] , whose contractivity condition 2 ν ( 1 + a ) 2 < 1 2\nu(1+a)^2<1 2 ν ( 1 + a ) 2 < 1 implies ours. When ν = 0 \nu=0 ν = 0 , taking square roots gives the classical rate χ A / χ A 2 + t 2 \chi_A/\sqrt{\chi_A^2+t^2} χ A / χ A 2 + t 2 of [18 Theorem 3.1] .
This comparison concerns contraction factors rather than convergence theorems. While Proposition 3.4 requires a solution-relative inequality for all values of F F F , [20 ] assumes pairwise submonotonicity on a restricted graph region, with additional conditions ensuring the existence of proximal steps within that region. Thus, neither theorem directly subsumes the other.
Degenerate PPPA as a forward method
We now specialize the forward theory of § 3 to the PPPA
x ˉ k ∈ ( P + A ) − 1 P x k , x k + 1 = x k + λ k ( x ˉ k − x k ) . (21) \bar{x}^k\in(P+A)^{-1}Px^k,\qquad x^{k+1}=x^k+\lambda_k(\bar{x}^k-x^k). \tag*{(21)} x ˉ k ∈ ( P + A ) − 1 P x k , x k + 1 = x k + λ k ( x ˉ k − x k ) . (21)
Throughout this section, along with the standing assumptions in § 2.2 , we assume that dom ( ( P + A ) − 1 P ) = H \operatorname{dom}((P+A)^{-1}P)=\mathcal{H} dom (( P + A ) − 1 P ) = H , so that the shadow sequence { x ˉ k } \{\bar{x}^k\} { x ˉ k } is well defined.
Reduced forward representation
We consider a reduced representation of (21) on R \mathcal{R} R by setting z k : = C ∗ x k ∈ R z^k := C^*x^k \in\mathcal{R} z k := C ∗ x k ∈ R , which we call the reduced PPPA sequence . Observe that P x k = C z k Px^k = Cz^k P x k = C z k , and so (21) gives
x ˉ k ∈ ( P + A ) − 1 C z k , z k + 1 = z k − λ k ( z k − C ∗ x ˉ k ) . (22) \bar{x}^k \in(P+A)^{-1}Cz^k, \qquad z^{k+1}=z^k-\lambda_k(z^k-C^*\bar{x}^k). \tag*{(22)} x ˉ k ∈ ( P + A ) − 1 C z k , z k + 1 = z k − λ k ( z k − C ∗ x ˉ k ) . (22)
This motivates the definition of the reduced forward map F : R ⇉ R F:\mathcal{R}\rightrightarrows\mathcal{R} F : R ⇉ R by
F ( z ) : = { z − C ∗ x ˉ : x ˉ ∈ ( P + A ) − 1 C z } . (23) F(z):=\{z-C^*\bar{x}:\bar{x}\in(P+A)^{-1}Cz\}. \tag*{(23)} F ( z ) := { z − C ∗ x ˉ : x ˉ ∈ ( P + A ) − 1 C z } . (23)
Equivalently, q ∈ F ( z ) q\in F(z) q ∈ F ( z ) if and only if there exists x ˉ ∈ H \bar{x}\in\mathcal{H} x ˉ ∈ H such that C ∗ x ˉ = z − q C^*\bar{x}=z-q C ∗ x ˉ = z − q and C q ∈ A x ˉ Cq\in A\bar{x} C q ∈ A x ˉ . If P P P is admissible for A A A , then F F F is single-valued.
Proposition 4.1 (Reduced forward representation). Let ( x k , x ˉ k ) (x^k,\bar{x}^k) ( x k , x ˉ k ) be generated by (21) , and set
z k : = C ∗ x k and q k : = C ∗ ( x k − x ˉ k ) = z k − C ∗ x ˉ k . (24) z^k:=C^*x^k \qquad\text{and}\qquad q^k:=C^*(x^k-\bar{x}^k)=z^k-C^*\bar{x}^k. \tag*{(24)} z k := C ∗ x k and q k := C ∗ ( x k − x ˉ k ) = z k − C ∗ x ˉ k . (24) Then
C q k = P ( x k − x ˉ k ) ∈ A x ˉ k , (25) Cq^k=P(x^k-\bar{x}^k)\in A\bar{x}^k, \tag*{(25)} C q k = P ( x k − x ˉ k ) ∈ A x ˉ k , (25) z k + 1 = z k − λ k q k , where q k ∈ F ( z k ) , and (26) z^{k+1}=z^k-\lambda_kq^k,\qquad\text{where }q^k\in F(z^k),\qquad\text{and} \tag*{(26)} z k + 1 = z k − λ k q k , where q k ∈ F ( z k ) , and (26) ∥ q k ∥ = ∥ x k − x ˉ k ∥ P . (27) \lVert q^k\rVert=\lVert x^k-\bar{x}^k\rVert_P. \tag*{(27)} ∥ q k ∥ = ∥ x k − x ˉ k ∥ P . (27)
Proof. Since x ˉ k ∈ ( P + A ) − 1 P x k \bar{x}^k\in(P+A)^{-1}Px^k x ˉ k ∈ ( P + A ) − 1 P x k , we have P ( x k − x ˉ k ) ∈ A x ˉ k P(x^k-\bar{x}^k)\in A\bar{x}^k P ( x k − x ˉ k ) ∈ A x ˉ k . Then C q k = C C ∗ ( x k − x ˉ k ) = P ( x k − x ˉ k ) ∈ A x ˉ k Cq^k=CC^*(x^k-\bar{x}^k)=P(x^k-\bar{x}^k)\in A\bar{x}^k C q k = C C ∗ ( x k − x ˉ k ) = P ( x k − x ˉ k ) ∈ A x ˉ k . This proves (25) . It also follows from the definition of F F F that q k = z k − C ∗ x ˉ k ∈ F ( z k ) q^k=z^k-C^*\bar{x}^k\in F(z^k) q k = z k − C ∗ x ˉ k ∈ F ( z k ) , which together with (22) gives (26) . Finally, (27) directly follows from (24) .
The reduced forward map F F F can also be expressed in terms of the parallel composition of A A A by C ∗ C^* C ∗ [3 Definition 25.39] . For an operator B B B , we write J B : = ( Id + B ) − 1 J_B:=(\operatorname{Id}+B)^{-1} J B := ( Id + B ) − 1 for its resolvent , which need not be single-valued, and denote by
A C : = C ∗ ▹ A : = ( C ∗ A − 1 C ) − 1 : R ⇉ R A_C:=C^*\triangleright A:=(C^*A^{-1}C)^{-1}:\mathcal{R}\rightrightarrows\mathcal{R} A C := C ∗ ▹ A := ( C ∗ A − 1 C ) − 1 : R ⇉ R
the parallel composition. Under appropriate monotonicity and admissibility assumptions, the reduced-resolvent identity J A C = C ∗ ( P + A ) − 1 C J_{A_C}=C^*(P+A)^{-1}C J A C = C ∗ ( P + A ) − 1 C was established in [4 Theorem 2.13] . The following proposition establishes these identities without requiring monotonicity or admissibility.
Proposition 4.2 (Parallel-composition representation). As identities of set-valued mappings on R \mathcal{R} R ,
C ∗ ( P + A ) − 1 C = J A C , (28) C^*(P+A)^{-1}C=J_{A_C}, \tag*{(28)} C ∗ ( P + A ) − 1 C = J A C , (28) F = J A C − 1 = Id R − J A C , (29) F=J_{A_C^{-1}}=\operatorname{Id}_{\mathcal{R}}-J_{A_C}, \tag*{(29)} F = J A C − 1 = Id R − J A C , (29) zer F = zer A C = C ∗ ( zer A ) . (30) \operatorname{zer}F=\operatorname{zer}A_C=C^*(\operatorname{zer}A). \tag*{(30)} zer F = zer A C = C ∗ ( zer A ) . (30)
Proof. Let z , p ∈ R z,p\in\mathcal{R} z , p ∈ R and x ˉ ∈ H \bar{x}\in\mathcal{H} x ˉ ∈ H with p = C ∗ x ˉ p=C^*\bar{x} p = C ∗ x ˉ . Since P x ˉ = C p P\bar{x}=Cp P x ˉ = C p , we have x ˉ ∈ ( P + A ) − 1 C z \bar{x}\in(P+A)^{-1}Cz x ˉ ∈ ( P + A ) − 1 C z if and only if C ( z − p ) ∈ A x ˉ C(z-p)\in A\bar{x} C ( z − p ) ∈ A x ˉ . Hence p ∈ C ∗ ( P + A ) − 1 C z p\in C^*(P+A)^{-1}Cz p ∈ C ∗ ( P + A ) − 1 C z if and only if p ∈ C ∗ A − 1 C ( z − p ) p\in C^*A^{-1}C(z-p) p ∈ C ∗ A − 1 C ( z − p ) , that is, z − p ∈ A C p z-p\in A_Cp z − p ∈ A C p , or equivalently p ∈ J A C ( z ) p\in J_{A_C}(z) p ∈ J A C ( z ) . This proves (28) . On the other hand, by the definition of F F F , q ∈ F ( z ) q\in F(z) q ∈ F ( z ) if and only if z − q ∈ C ∗ ( P + A ) − 1 C z = J A C ( z ) z-q\in C^*(P+A)^{-1}Cz=J_{A_C}(z) z − q ∈ C ∗ ( P + A ) − 1 C z = J A C ( z ) . Moreover, z − q ∈ J A C ( z ) z-q\in J_{A_C}(z) z − q ∈ J A C ( z ) if and only if q ∈ A C ( z − q ) q\in A_C(z-q) q ∈ A C ( z − q ) , that is, z − q ∈ A C − 1 q z-q\in A_C^{-1}q z − q ∈ A C − 1 q , or equivalently q ∈ J A C − 1 ( z ) q\in J_{A_C^{-1}}(z) q ∈ J A C − 1 ( z ) . This proves (29) . Finally, 0 ∈ F ( z ) 0\in F(z) 0 ∈ F ( z ) if and only if z ∈ J A C ( z ) z\in J_{A_C}(z) z ∈ J A C ( z ) , that is, 0 ∈ A C z 0\in A_Cz 0 ∈ A C z , or equivalently z ∈ C ∗ A − 1 ( 0 ) = C ∗ ( zer A ) z\in C^*A^{-1}(0)=C^*(\operatorname{zer}A) z ∈ C ∗ A − 1 ( 0 ) = C ∗ ( zer A ) . □
Let p k : = C ∗ x ˉ k = z k − q k p^k:=C^*\bar{x}^k=z^k-q^k p k := C ∗ x ˉ k = z k − q k . By Proposition 4.2, p k ∈ J A C ( z k ) p^k\in J_{A_C}(z^k) p k ∈ J A C ( z k ) , and hence (26) can also be written as z k + 1 = ( 1 − λ k ) z k + λ k p k z^{k+1}=(1-\lambda_k)z^k+\lambda_kp^k z k + 1 = ( 1 − λ k ) z k + λ k p k . Thus, the reduced PPPA (26) can be viewed either as a relaxed proximal iteration for A C A_C A C , as in [4 ] , or as a forward iteration for the complementary resolvent F = J A C − 1 F = J_{A_C^{-1}} F = J A C − 1 . The latter viewpoint allows us to directly apply the convergence results of § 3 , since relative semimonotonicity of A A A yields that of F F F ; see Lemma 4.3 .
Range-restricted operator. As observed by [4 Eq. (2.4) and Proposition 2.5] and further explored by [28 Lemma 2.2 and Definition 2.1] , only graph points of A A A whose operator values belong to R \mathcal{R} R are relevant to the preconditioned resolvent. To make this explicit, define
A R ( x ) : = A x ∩ R , x ∈ H . (31) A_{\mathcal{R}}(x) := Ax \cap\mathcal{R}, \qquad x \in\mathcal{H}. \tag*{(31)} A R ( x ) := A x ∩ R , x ∈ H . (31)
Since C z − P x ˉ ∈ R Cz-P\bar{x} \in\mathcal{R} C z − P x ˉ ∈ R for all z ∈ R z \in\mathcal{R} z ∈ R and x ˉ ∈ H \bar{x} \in\mathcal{H} x ˉ ∈ H , we have ( P + A R ) − 1 C = ( P + A ) − 1 C (P+A_{\mathcal{R}})^{-1}C = (P+A)^{-1}C ( P + A R ) − 1 C = ( P + A ) − 1 C . Moreover, 0 ∈ R 0 \in\mathcal{R} 0 ∈ R and ran C = R \operatorname{ran} C = \mathcal{R} ran C = R imply that zer A R = zer A \operatorname{zer} A_{\mathcal{R}} = \operatorname{zer} A zer A R = zer A and ( A R ) C = A C (A_{\mathcal{R}})_C = A_C ( A R ) C = A C . In particular, the reduced forward map admits the equivalent representation F = J ( ( A R ) C ) − 1 F = J_{((A_{\mathcal{R}})_C)^{-1}} F = J (( A R ) C ) − 1 . Thus, replacing A A A with A R A_{\mathcal{R}} A R changes neither the PPPA nor its reduced forward representation. As will be seen below, the semimonotonicity and demiclosedness assumptions can be imposed on A R A_{\mathcal{R}} A R instead of on A A A . Similarly, sufficient error bounds involving the original operator can be formulated using A R A_{\mathcal{R}} A R .
Basic convergence and projected solution identification
The following lemma transfers relative semimonotonicity of A R A_{\mathcal{R}} A R given by (31) to F F F .
Lemma 4.3 (Transfer of relative semimonotonicity). Let ∅ ≠ S ⋆ ⊆ zer A \varnothing\ne S^\star\subseteq\operatorname{zer} A ∅ = S ⋆ ⊆ zer A , and suppose that A R A_{\mathcal{R}} A R is relatively ( U , V ) (U,V) ( U , V ) -semimonotone with respect to S ⋆ S^\star S ⋆ , that is,
⟨ x − x ⋆ , a ⟩ ≥ ⟨ x − x ⋆ , U ( x − x ⋆ ) ⟩ + ⟨ a , V a ⟩ ∀ x ⋆ ∈ S ⋆ , x ∈ H , a ∈ A x ∩ R , \langle x-x^\star,a\rangle\ge\langle x-x^\star,U(x-x^\star)\rangle+ \langle a,Va\rangle\quad\forall x^\star\in S^\star,\ x \in\mathcal{H},\ a \in Ax \cap\mathcal{R}, ⟨ x − x ⋆ , a ⟩ ≥ ⟨ x − x ⋆ , U ( x − x ⋆ )⟩ + ⟨ a , V a ⟩ ∀ x ⋆ ∈ S ⋆ , x ∈ H , a ∈ A x ∩ R , and let F F F be given by (23) . Suppose that U ⪰ τ P U \succeq\tau P U ⪰ τ P for some τ ∈ R \tau\in\mathbb{R} τ ∈ R . Let q ∈ F ( z ) q \in F(z) q ∈ F ( z ) and x ˉ ∈ ( P + A ) − 1 C z \bar{x} \in(P+A)^{-1}Cz x ˉ ∈ ( P + A ) − 1 C z satisfy q = z − C ∗ x ˉ q = z-C^\ast\bar{x} q = z − C ∗ x ˉ . Then, for every x ⋆ ∈ S ⋆ x^\star\in S^\star x ⋆ ∈ S ⋆ , with d : = z − C ∗ x ⋆ d := z-C^\ast x^\star d := z − C ∗ x ⋆ ,
( 1 + 2 τ ) ⟨ q , d ⟩ ≥ τ ∥ d ∥ 2 + ⟨ q , ( H + τ Id R ) q ⟩ + ∥ ( U − τ P ) 1 / 2 ( x ˉ − x ⋆ ) ∥ 2 (32) (1+2\tau)\langle q,d\rangle\ge\tau\lVert d\rVert^2+\langle q,(H+\tau\operatorname{Id}_{\mathcal{R}})q\rangle+\left\lVert(U-\tau P)^{1/2}(\bar{x}-x^\star)\right\rVert^2 \tag*{(32)} ( 1 + 2 τ ) ⟨ q , d ⟩ ≥ τ ∥ d ∥ 2 + ⟨ q , ( H + τ Id R ) q ⟩ + ( U − τ P ) 1/2 ( x ˉ − x ⋆ ) 2 (32) where H : = Id R + C ∗ V C H := \operatorname{Id}_{\mathcal{R}}+C^\ast V C H := Id R + C ∗ V C . Consequently, if τ > − 1 / 2 \tau>-1/2 τ > − 1/2 , F F F is relatively ( τ 1 + 2 τ Id R , H + τ Id R 1 + 2 τ ) \left(\frac{\tau}{1+2\tau}\operatorname{Id}_{\mathcal{R}},\frac{H+\tau\operatorname{Id}_{\mathcal{R}}}{1+2\tau}\right) ( 1 + 2 τ τ Id R , 1 + 2 τ H + τ Id R ) -semimonotone with respect to C ∗ S ⋆ C^\ast S^\star C ∗ S ⋆ , where C ∗ S ⋆ ⊆ zer F C^\ast S^\star\subseteq\operatorname{zer} F C ∗ S ⋆ ⊆ zer F .
Proof. Since C q ∈ A x ˉ ∩ R Cq \in A\bar{x}\cap\mathcal{R} C q ∈ A x ˉ ∩ R and C ∗ ( x ˉ − x ⋆ ) = d − q C^\ast(\bar{x}-x^\star)=d-q C ∗ ( x ˉ − x ⋆ ) = d − q , relative semimonotonicity gives
⟨ q , d ⟩ = ∥ q ∥ 2 + ⟨ q , C ∗ ( x ˉ − x ⋆ ) ⟩ ≥ ⟨ q , H q ⟩ + ⟨ x ˉ − x ⋆ , U ( x ˉ − x ⋆ ) ⟩ . \langle q,d\rangle=\lVert q\rVert^2+\langle q,C^\ast(\bar{x}-x^\star)\rangle\ge\langle q,Hq\rangle+\langle\bar{x}-x^\star,U(\bar{x}-x^\star)\rangle. ⟨ q , d ⟩ = ∥ q ∥ 2 + ⟨ q , C ∗ ( x ˉ − x ⋆ )⟩ ≥ ⟨ q , H q ⟩ + ⟨ x ˉ − x ⋆ , U ( x ˉ − x ⋆ )⟩ . Writing U = τ P + ( U − τ P ) U=\tau P+(U-\tau P) U = τ P + ( U − τ P ) and using ⟨ x ˉ − x ⋆ , P ( x ˉ − x ⋆ ) ⟩ = ∥ d − q ∥ 2 \langle\bar{x}-x^\star,P(\bar{x}-x^\star)\rangle=\lVert d-q\rVert^2 ⟨ x ˉ − x ⋆ , P ( x ˉ − x ⋆ )⟩ = ∥ d − q ∥ 2 , we obtain
⟨ q , d ⟩ ≥ ⟨ q , H q ⟩ + τ ∥ d − q ∥ 2 + ∥ ( U − τ P ) 1 / 2 ( x ˉ − x ⋆ ) ∥ 2 , \langle q,d\rangle\ge\langle q,Hq\rangle+\tau\lVert d-q\rVert^2+\left\lVert(U-\tau P)^{1/2}(\bar{x}-x^\star)\right\rVert^2, ⟨ q , d ⟩ ≥ ⟨ q , H q ⟩ + τ ∥ d − q ∥ 2 + ( U − τ P ) 1/2 ( x ˉ − x ⋆ ) 2 , from which we get (32) . Since U − τ P ⪰ 0 U-\tau P\succeq0 U − τ P ⪰ 0 and 1 + 2 τ > 0 1+2\tau>0 1 + 2 τ > 0 , dropping the last term and dividing by 1 + 2 τ 1+2\tau 1 + 2 τ proves the semimonotonicity claim on F F F . Finally, C ∗ S ⋆ ⊆ zer F C^\ast S^\star\subseteq\operatorname{zer} F C ∗ S ⋆ ⊆ zer F follows from (30) . □ \square □
In the simple case U ⪰ 0 U\succeq0 U ⪰ 0 , taking τ = 0 \tau=0 τ = 0 in Lemma 4.3 shows that F F F is relatively ( 0 , H ) (0,H) ( 0 , H ) -semimonotone with respect to C ∗ S ⋆ C^\ast S^\star C ∗ S ⋆ . We can then apply Proposition 3.1 directly to (26) .
Corollary 4.4 (Convergence of the reduced PPPA). Let ∅ ≠ S ⋆ ⊆ zer A \varnothing\ne S^\star\subseteq\operatorname{zer} A ∅ = S ⋆ ⊆ zer A , and suppose that A R A_{\mathcal{R}} A R is relatively ( U , V ) (U,V) ( U , V ) -semimonotone with respect to S ⋆ S^\star S ⋆ , where U ⪰ 0 U\succeq0 U ⪰ 0 and H H H is strongly monotone. Let { ( x k , x ˉ k ) } \{(x^k,\bar{x}^k)\} {( x k , x ˉ k )} be generated by (21) , and let ( z k , q k ) (z^k,q^k) ( z k , q k ) be given by (24) . Suppose that
λ k ∈ ( 0 , 2 β k ] where β k > 0 satisfies ⟨ q k , H q k ⟩ ≥ β k ∥ q k ∥ 2 . (33) \lambda_k\in(0,2\beta_k] \quad\text{where }\beta_k>0\text{ satisfies }\langle q^k,Hq^k\rangle\ge\beta_k\lVert q^k\rVert^2. \tag*{(33)} λ k ∈ ( 0 , 2 β k ] where β k > 0 satisfies ⟨ q k , H q k ⟩ ≥ β k ∥ q k ∥ 2 . (33) Set δ k : = λ k ( 2 β k − λ k ) \delta_k:=\lambda_k(2\beta_k-\lambda_k) δ k := λ k ( 2 β k − λ k ) . Then the following hold.
(i) { z k } \{z^k\} { z k } is Fejér monotone with respect to C ∗ S ∗ C^*S^* C ∗ S ∗ ; that is, { x k } \{x^k\} { x k } is Fejér monotone with respect to S ∗ S^* S ∗ in the P P P -seminorm. Moreover, { q k } \{q^k\} { q k } , { Π R x k } \{\Pi_Rx^k\} { Π R x k } , and { Π R x ˉ k } \{\Pi_R\bar{x}^k\} { Π R x ˉ k } are bounded.
(ii) If lim inf k → ∞ δ k > 0 \liminf_{k\to\infty}\delta_k>0 lim inf k → ∞ δ k > 0 , then ∑ k = 0 ∞ ∥ q k ∥ 2 < + ∞ \sum_{k=0}^{\infty}\lVert q^k\rVert^2<+\infty ∑ k = 0 ∞ ∥ q k ∥ 2 < + ∞ , q k → 0 q^k\to0 q k → 0 , and P ( x k − x ˉ k ) → 0 P(x^k-\bar{x}^k)\to0 P ( x k − x ˉ k ) → 0 .
(iii) For every x ⋆ ∈ S ⋆ x^\star\in S^\star x ⋆ ∈ S ⋆ and N ∈ N N\in\mathbb{N} N ∈ N ,
∥ ∑ k = 0 N λ k q k ∑ k = 0 N λ k ∥ ≤ 2 ∥ x 0 − x ⋆ ∥ P / ∑ k = 0 N λ k , \left\lVert\frac{\sum_{k=0}^{N}\lambda_kq^k}{\sum_{k=0}^{N}\lambda_k}\right\rVert\leq2\lVert x^0-x^\star\rVert_P\bigg/\sum_{k=0}^{N}\lambda_k, ∑ k = 0 N λ k ∑ k = 0 N λ k q k ≤ 2 ∥ x 0 − x ⋆ ∥ P / k = 0 ∑ N λ k ,
which is O ( N − 1 ) O(N^{-1}) O ( N − 1 ) if lim inf k λ k > 0 \liminf_k\lambda_k>0 lim inf k λ k > 0 . If δ : = inf k δ k > 0 \delta:=\inf_k\delta_k>0 δ := inf k δ k > 0 , then also
∥ ( N + 1 ) − 1 ∑ k = 0 N q k ∥ ≤ ∥ x 0 − x ⋆ ∥ P / δ ( N + 1 ) . \left\lVert(N+1)^{-1}\sum_{k=0}^{N}q^k\right\rVert\leq\lVert x^0-x^\star\rVert_P/\sqrt{\delta(N+1)}. ( N + 1 ) − 1 k = 0 ∑ N q k ≤ ∥ x 0 − x ⋆ ∥ P / δ ( N + 1 ) .
(iv) For every x ⋆ ∈ S ⋆ x^\star\in S^\star x ⋆ ∈ S ⋆ and N N N such that ∑ k = 0 N δ k > 0 \sum_{k=0}^{N}\delta_k>0 ∑ k = 0 N δ k > 0 ,
min 0 ≤ k ≤ N ∥ q k ∥ 2 = min 0 ≤ k ≤ N ∥ x k − x ˉ k ∥ P 2 ≤ ∥ x 0 − x ⋆ ∥ P 2 ∑ k = 0 N δ k . \min_{0\leq k\leq N}\lVert q^k\rVert^2=\min_{0\leq k\leq N}\lVert x^k-\bar{x}^k\rVert_P^2\leq\frac{\lVert x^0-x^\star\rVert_P^2}{\sum_{k=0}^{N}\delta_k}. 0 ≤ k ≤ N min ∥ q k ∥ 2 = 0 ≤ k ≤ N min ∥ x k − x ˉ k ∥ P 2 ≤ ∑ k = 0 N δ k ∥ x 0 − x ⋆ ∥ P 2 .
If δ k ≥ κ > 0 \delta_k\geq\kappa>0 δ k ≥ κ > 0 for all k k k , the right-hand side is at most ∥ x 0 − x ⋆ ∥ P 2 / [ κ ( N + 1 ) ] \lVert x^0-x^\star\rVert_P^2/[\kappa(N+1)] ∥ x 0 − x ⋆ ∥ P 2 / [ κ ( N + 1 )] .
Proof. By Lemma 4.3 and Eq. (26) , we can directly invoke Proposition 3.1. From Proposition 3.1(i), we obtain the claim on { z k } \{z^k\} { z k } . Using the definition of z k z^k z k , we get that
∥ C ∗ x k + 1 − C ∗ x ⋆ ∥ 2 ≤ ∥ C ∗ x k − C ∗ x ⋆ ∥ 2 \lVert C^*x^{k+1}-C^*x^\star\rVert^2\leq\lVert C^*x^k-C^*x^\star\rVert^2 ∥ C ∗ x k + 1 − C ∗ x ⋆ ∥ 2 ≤ ∥ C ∗ x k − C ∗ x ⋆ ∥ 2
for all k ∈ N k\in\mathbb{N} k ∈ N , which proves the Fejér monotonicity on { x k } \{x^k\} { x k } in the P P P -seminorm. Moreover, we have from (32) with τ = 0 \tau=0 τ = 0 that
⟨ q k , z k − C ∗ x ⋆ ⟩ ≥ ⟨ q k , H q k ⟩ ≥ η H ∥ q k ∥ 2 , \langle q^k,z^k-C^*x^\star\rangle\geq\langle q^k,Hq^k\rangle\geq\eta_H\lVert q^k\rVert^2, ⟨ q k , z k − C ∗ x ⋆ ⟩ ≥ ⟨ q k , H q k ⟩ ≥ η H ∥ q k ∥ 2 ,
where
η H : = inf ∥ q ∥ = 1 ⟨ q , H q ⟩ = ∥ H − 1 ∥ − 1 , (34) \eta_H:=\inf_{\lVert q\rVert=1}\langle q,Hq\rangle=\lVert H^{-1}\rVert^{-1}, \tag*{(34)} η H := ∥ q ∥ = 1 inf ⟨ q , H q ⟩ = ∥ H − 1 ∥ − 1 , (34)
which is positive since H H H is strongly monotone. Thus, η H ∥ q k ∥ ≤ ∥ z k − C ∗ x ⋆ ∥ \eta_H\lVert q^k\rVert\leq\lVert z^k-C^*x^\star\rVert η H ∥ q k ∥ ≤ ∥ z k − C ∗ x ⋆ ∥ and we get the boundedness of { q k } \{q^k\} { q k } . With the boundedness of { z k } \{z^k\} { z k } and { q k } \{q^k\} { q k } , while noting (25) and (3) , we have
Π R x k = ( P ∣ R ) − 1 / 2 z k and Π R x ˉ k = ( P ∣ R ) − 1 / 2 ( z k − q k ) , (35) \Pi_Rx^k=(P|_R)^{-1/2}z^k\quad\text{and}\quad\Pi_R\bar{x}^k=(P|_R)^{-1/2}(z^k-q^k), \tag*{(35)} Π R x k = ( P ∣ R ) − 1/2 z k and Π R x ˉ k = ( P ∣ R ) − 1/2 ( z k − q k ) , (35)
we get the rest of the claim of (i). Finally, parts (ii)--(iv) directly follow from Proposition 3.1(ii)--(iv) by noting Eqs. (25) and (27) and ∥ z 0 − C ∗ x ⋆ ∥ = ∥ x 0 − x ⋆ ∥ P \lVert z^0-C^*x^\star\rVert=\lVert x^0-x^\star\rVert_P ∥ z 0 − C ∗ x ⋆ ∥ = ∥ x 0 − x ⋆ ∥ P .
Projected identification and convergence. The estimates above do not by themselves identify the weak cluster points of { z k } \{z^k\} { z k } as zeros of F F F . This requires a demiclosedness property of F F F .
Proposition 4.5 (Projected identification and convergence). Suppose the assumptions of Corollary 4.4 hold, lim inf k δ k > 0 \liminf_k\delta_k>0 lim inf k δ k > 0 , and F F F is demiclosed at zero. Then the following hold.
(i) Every weak cluster point of { z k } \{z^k\} { z k } belongs to C ∗ ( zer A ) C^*(\operatorname{zer} A) C ∗ ( zer A ) . Consequently, every weak cluster point of { Π R x k } \{\Pi_Rx^k\} { Π R x k } or { Π R x ˉ k } \{\Pi_R\bar{x}^k\} { Π R x ˉ k } belongs to Π R ( zer A ) \Pi_R(\operatorname{zer} A) Π R ( zer A ) .
(ii) If, in addition,
C ∗ S ∗ = C ∗ ( zer A ) , (36) C^*S^*=C^*(\operatorname{zer} A), \tag*{(36)} C ∗ S ∗ = C ∗ ( zer A ) , (36) then z k ⇀ z ∞ ∈ C ∗ ( zer A ) z^k\rightharpoonup z^\infty\in C^*(\operatorname{zer} A) z k ⇀ z ∞ ∈ C ∗ ( zer A ) , and both { Π R x k } \{\Pi_Rx^k\} { Π R x k } or { Π R x ˉ k } \{\Pi_R\bar{x}^k\} { Π R x ˉ k } converge weakly to ( P ∣ R ) − 1 / 2 z ∞ ∈ Π R ( zer A ) (P|_R)^{-1/2}z^\infty\in\Pi_R(\operatorname{zer} A) ( P ∣ R ) − 1/2 z ∞ ∈ Π R ( zer A ) .
Proof. By Proposition 3.1(ii), q k → 0 q^k\to0 q k → 0 and every weak cluster point of { z k } \{z^k\} { z k } belongs to zer F = C ∗ ( zer A ) = ( P ∣ R ) 1 / 2 Π R ( zer A ) \operatorname{zer}F=C^*(\operatorname{zer} A)=(P|_R)^{1/2}\Pi_R(\operatorname{zer} A) zer F = C ∗ ( zer A ) = ( P ∣ R ) 1/2 Π R ( zer A ) , where the last equality holds by (2) . Consequently, by Eq. (35) , weak cluster points of Π R x k \Pi_Rx^k Π R x k and Π R x ˉ k \Pi_R\bar{x}^k Π R x ˉ k belong to the set ( P ∣ R ) − 1 / 2 zer F = Π R ( zer A ) (P|_R)^{-1/2}\operatorname{zer}F=\Pi_R(\operatorname{zer} A) ( P ∣ R ) − 1/2 zer F = Π R ( zer A ) , proving (i). Under (36) , the weak convergence follows again from Proposition 3.1(ii), (35) and (2) .
Global ( U , V ) (U,V) ( U , V ) -semimonotonicity provides a sufficient condition for the demiclosedness assumption in Proposition 4.5 , together with a last-iterate residual rate.
Proposition 4.6 (Convergence under global ( U , V ) (U,V) ( U , V ) -semimonotonicity). Suppose that zer A ≠ ∅ \operatorname{zer} A \ne\varnothing zer A = ∅ , that A R A_{\mathcal R} A R is globally ( U , V ) (U,V) ( U , V ) -semimonotone with U ⪰ 0 U \succeq0 U ⪰ 0 , and that H H H is strongly monotone. Let η H \eta_H η H be given by (34) . Then F F F is η H \eta_H η H -cocoercive, and hence single-valued, η H − 1 \eta_H^{-1} η H − 1 -Lipschitz continuous, and demiclosed at zero.
If 0 ≤ λ k ≤ 2 η H 0 \leq\lambda_k \leq2\eta_H 0 ≤ λ k ≤ 2 η H and ∑ k = 0 ∞ λ k ( 2 η H − λ k ) = + ∞ \sum_{k=0}^{\infty}\lambda_k(2\eta_H-\lambda_k)=+\infty ∑ k = 0 ∞ λ k ( 2 η H − λ k ) = + ∞ , then { z k } \{z^k\} { z k } is Fejér monotone with respect to C ∗ ( zer A ) C^*(\operatorname{zer} A) C ∗ ( zer A ) , q k → 0 q^k \to0 q k → 0 , and z k ⇀ z ∞ ∈ C ∗ ( zer A ) z^k \rightharpoonup z^\infty\in C^*(\operatorname{zer} A) z k ⇀ z ∞ ∈ C ∗ ( zer A ) . Moreover, Π R x k , Π R x ˉ k ⇀ ( P ∣ R ) − 1 / 2 z ∞ ∈ Π R ( zer A ) \Pi_{\mathcal R}x^k,\Pi_{\mathcal R}\bar{x}^k \rightharpoonup(P|_{\mathcal R})^{-1/2}z^\infty\in\Pi_{\mathcal R}(\operatorname{zer} A) Π R x k , Π R x ˉ k ⇀ ( P ∣ R ) − 1/2 z ∞ ∈ Π R ( zer A ) . If, in addition, inf k λ k ( 2 η H − λ k ) > 0 \inf_k\lambda_k(2\eta_H-\lambda_k)>0 inf k λ k ( 2 η H − λ k ) > 0 , then ∥ x k − x ˉ k ∥ P 2 = o ( k − 1 ) \|x^k-\bar{x}^k\|_P^2=o(k^{-1}) ∥ x k − x ˉ k ∥ P 2 = o ( k − 1 ) .
Proof. Let ( z , q ) , ( z ′ , q ′ ) ∈ gra F (z,q),(z',q') \in\operatorname{gra} F ( z , q ) , ( z ′ , q ′ ) ∈ gra F , and choose x ˉ , y ˉ ∈ H \bar{x},\bar{y}\in\mathcal H x ˉ , y ˉ ∈ H such that C q ∈ A R x ˉ , C q ′ ∈ A R y ˉ , C ∗ x ˉ = z − q Cq\in A_{\mathcal R}\bar{x}, Cq'\in A_{\mathcal R}\bar{y}, C^*\bar{x}=z-q C q ∈ A R x ˉ , C q ′ ∈ A R y ˉ , C ∗ x ˉ = z − q , and C ∗ y ˉ = z ′ − q ′ C^*\bar{y}=z'-q' C ∗ y ˉ = z ′ − q ′ . By global semimonotonicity, ⟨ q − q ′ , z − z ′ ⟩ ≥ ⟨ q − q ′ , H ( q − q ′ ) ⟩ ≥ η H ∥ q − q ′ ∥ 2 \langle q-q',z-z'\rangle\geq\langle q-q',H(q-q')\rangle\geq\eta_H\|q-q'\|^2 ⟨ q − q ′ , z − z ′ ⟩ ≥ ⟨ q − q ′ , H ( q − q ′ )⟩ ≥ η H ∥ q − q ′ ∥ 2 . Hence, F F F is η H \eta_H η H -cocoercive and, by the standing full-domain assumption, single-valued and η H − 1 \eta_H^{-1} η H − 1 -Lipschitz continuous. By [3 Proposition 4.39] , N : = Id R − 2 η H F N:=\operatorname{Id}_{\mathcal R}-2\eta_HF N := Id R − 2 η H F is nonexpansive. Hence, the demiclosedness principle [3 Corollary 4.28] implies that F F F is demiclosed at zero. The remaining claims follow from [2 Proposition 2.9] by expressing (26) as a Krasnosel’skii–Mann iteration of N N N , noting that Fix N = zer F = C ∗ ( zer A ) \operatorname{Fix}N=\operatorname{zer}F=C^*(\operatorname{zer} A) Fix N = zer F = C ∗ ( zer A ) , and using (35) and (27) . □
Failure of projected identification. In contrast to the above result, relative semimonotonicity alone does not ensure demiclosedness of F F F , even when A A A is continuous in finite dimensions.
Example 4.7 (Projected limit outside the projected zero set). Let H = R 2 \mathcal H=\mathbb R^2 H = R 2 , P = ( 1 0 0 0 ) P=\begin{pmatrix}1&0\\0&0\end{pmatrix} P = ( 1 0 0 0 ) and A ( u , v ) = ( u 1 + v 2 , 0 ) A(u,v)=\left(\frac{u}{1+v^2},0\right) A ( u , v ) = ( 1 + v 2 u , 0 ) . Then A A A is continuous, zer A = { 0 } × R \operatorname{zer} A=\{0\}\times\mathbb R zer A = { 0 } × R , and ⟨ ( u , v ) − ( 0 , t ) , A ( u , v ) ⟩ = u 2 / ( 1 + v 2 ) ≥ 0 \langle(u,v)-(0,t),A(u,v)\rangle=u^2/(1+v^2)\geq0 ⟨( u , v ) − ( 0 , t ) , A ( u , v )⟩ = u 2 / ( 1 + v 2 ) ≥ 0 for every t ∈ R t\in\mathbb R t ∈ R . Thus A A A is relatively ( 0 , 0 ) (0,0) ( 0 , 0 ) -semimonotone with respect to zer A \operatorname{zer} A zer A . For x = ( s , t ) x=(s,t) x = ( s , t ) , every x ˉ = ( u , v ) ∈ ( P + A ) − 1 P x \bar{x}=(u,v)\in(P+A)^{-1}Px x ˉ = ( u , v ) ∈ ( P + A ) − 1 P x satisfies u = s ( 1 + v 2 ) / ( 2 + v 2 ) u=s(1+v^2)/(2+v^2) u = s ( 1 + v 2 ) / ( 2 + v 2 ) , where v ∈ R v\in\mathbb R v ∈ R is arbitrary. Hence, ( P + A ) − 1 P (P+A)^{-1}P ( P + A ) − 1 P has full domain and F ( s , 0 ) = { ( s 2 + v 2 , 0 ) : v ∈ R } F(s,0)=\left\{\left(\frac{s}{2+v^2},0\right):v\in\mathbb R\right\} F ( s , 0 ) = { ( 2 + v 2 s , 0 ) : v ∈ R } for all ( s , 0 ) ∈ R (s,0)\in\mathbb R ( s , 0 ) ∈ R .
Since H = Id R H=\operatorname{Id}_{\mathbb R} H = Id R , we may take β k ≡ 1 \beta_k\equiv1 β k ≡ 1 and λ k ≡ 1 \lambda_k\equiv1 λ k ≡ 1 , so that δ k ≡ 1 \delta_k\equiv1 δ k ≡ 1 and (21) reduces to x k + 1 ∈ ( P + A ) − 1 P x k x^{k+1}\in(P+A)^{-1}Px^k x k + 1 ∈ ( P + A ) − 1 P x k and x k + 1 = x ˉ k x^{k+1}=\bar{x}^k x k + 1 = x ˉ k . Starting from x 0 = ( s 0 , 0 ) x^0=(s_0,0) x 0 = ( s 0 , 0 ) with s 0 > 0 s_0>0 s 0 > 0 , the sequence x k = ( s k , k ) x^k=(s_k,k) x k = ( s k , k ) can be generated from (21) where
s k + 1 = s k 1 + ( k + 1 ) 2 2 + ( k + 1 ) 2 = s k ( 1 − 1 2 + ( k + 1 ) 2 ) = s 0 ∏ j = 0 k ( 1 − a j ) , s_{k+1}=s_k\frac{1+(k+1)^2}{2+(k+1)^2}=s_k\left(1-\frac{1}{2+(k+1)^2}\right)=s_0\prod_{j=0}^{k}(1-a_j), s k + 1 = s k 2 + ( k + 1 ) 2 1 + ( k + 1 ) 2 = s k ( 1 − 2 + ( k + 1 ) 2 1 ) = s 0 j = 0 ∏ k ( 1 − a j ) , with a j = ( 2 + ( j + 1 ) 2 ) − 1 a_j=(2+(j+1)^2)^{-1} a j = ( 2 + ( j + 1 ) 2 ) − 1 . Since ∑ j = 0 ∞ a j < + ∞ \sum_{j=0}^{\infty}a_j<+\infty ∑ j = 0 ∞ a j < + ∞ , s k → s ∞ > 0 s_k\to s_\infty>0 s k → s ∞ > 0 . Consequently, Π R x k , Π R x ˉ k → ( s ∞ , 0 ) \Pi_{\mathcal R}x^k,\Pi_{\mathcal R}\bar{x}^k\to(s_\infty,0) Π R x k , Π R x ˉ k → ( s ∞ , 0 ) , although Π R ( zer A ) = { ( 0 , 0 ) } \Pi_{\mathcal R}(\operatorname{zer} A)=\{(0,0)\} Π R ( zer A ) = {( 0 , 0 )} . Meanwhile, q k = ( 1 2 + ( k + 1 ) 2 , 0 ) → 0 q^k=\left(\frac{1}{2+(k+1)^2},0\right)\to0 q k = ( 2 + ( k + 1 ) 2 1 , 0 ) → 0 , while 0 ∉ F ( s ∞ , 0 ) 0\notin F(s_\infty,0) 0 ∈ / F ( s ∞ , 0 ) . Thus F F F is not demiclosed at zero, so that the hypothesis of Proposition 4.5 does not hold. □
Thus, the projected identification and convergence assertions of [12, Theorem 2.4(iii),(v)] require an additional assumption. By Proposition 4.5 , demiclosedness of F F F at zero suffices, together with (36) for convergence.
Sufficient conditions for demiclosedness of F F F . We next characterize demiclosedness of F F F at zero and provide a sufficient condition for it.
Lemma 4.8 (Demiclosedness and bounded recovery). The following are equivalent.
F F F is demiclosed at zero.
A C A_C A C is demiclosed at zero.
If q j → 0 q^j \to0 q j → 0 , C q j ∈ A R x j Cq^j \in A_Rx^j C q j ∈ A R x j , and C ∗ x j ⇀ p C^*x^j \rightharpoonup p C ∗ x j ⇀ p , then p ∈ C ∗ ( zer A ) p \in C^*(\operatorname{zer} A) p ∈ C ∗ ( zer A ) .
Moreover, these conditions hold if A R A_R A R is demiclosed at zero and the bounded-recovery condition (see Definition 2.5(i)) holds.
Proof. By Proposition 4.2 , q ∈ F ( z ) q \in F(z) q ∈ F ( z ) if and only if q ∈ A C ( z − q ) q \in A_C(z-q) q ∈ A C ( z − q ) , and zer F = zer A C \operatorname{zer} F=\operatorname{zer} A_C zer F = zer A C by (30) . If q j → 0 q^j \to0 q j → 0 , then z j ⇀ z z^j \rightharpoonup z z j ⇀ z if and only if z j − q j ⇀ z z^j-q^j \rightharpoonup z z j − q j ⇀ z . Hence (i) and (ii) are equivalent. Since A C − 1 = C ∗ A − 1 C A_C^{-1}=C^*A^{-1}C A C − 1 = C ∗ A − 1 C , we have q j ∈ A C p j q^j \in A_Cp^j q j ∈ A C p j if and only if p j = C ∗ x j p^j=C^*x^j p j = C ∗ x j for some x j ∈ H x^j \in\mathcal{H} x j ∈ H with C q j ∈ A x j Cq^j \in Ax^j C q j ∈ A x j , equivalently C q j ∈ A R x j Cq^j \in A_Rx^j C q j ∈ A R x j , because C q j ∈ R Cq^j \in R C q j ∈ R . As zer A C = C ∗ ( zer A ) \operatorname{zer} A_C=C^*(\operatorname{zer} A) zer A C = C ∗ ( zer A ) , (ii) and (iii) are equivalent.
Finally, suppose that A R A_R A R is demiclosed at zero and the bounded-recovery condition holds. Let the sequences in the premise of (iii) be given, and set z j : = C ∗ x j + q j z^j:=C^*x^j+q^j z j := C ∗ x j + q j . Then x j ∈ ( P + A ) − 1 C z j x^j\in(P+A)^{-1}Cz^j x j ∈ ( P + A ) − 1 C z j and { z j } \{z^j\} { z j } is bounded because z j ⇀ p z^j\rightharpoonup p z j ⇀ p . By the bounded-recovery condition, { x j } \{x^j\} { x j } is bounded, so x j ⇀ x x^j\rightharpoonup x x j ⇀ x along a subsequence. Since C q j ∈ A R x j Cq^j\in A_Rx^j C q j ∈ A R x j and C q j → 0 Cq^j\to0 C q j → 0 , demiclosedness of A R A_R A R gives x ∈ zer A x\in\operatorname{zer} A x ∈ zer A . Moreover, C ∗ x = p C^*x=p C ∗ x = p , so (iii) holds.
Global Lipschitz continuity of ( P + A ) − 1 (P+A)^{-1} ( P + A ) − 1 implies the bounded-recovery condition and was assumed in [4 Theorem 2.9] for full-space convergence under monotonicity. Assuming that P P P is admissible for A A A , Xue–Zhang [28 Assumption 7 and Proposition 5.1] weakened this requirement to Lipschitz continuity of ( P + A ) − 1 ∣ R (P+A)^{-1}|_R ( P + A ) − 1 ∣ R . Both assumptions imply the bounded-recovery condition, which requires neither Lipschitz continuity nor single-valuedness.
Convergence of the PPPA sequences
We now turn to the full PPPA sequences { x k } \{x^k\} { x k } and { x ˉ k } \{\bar{x}^k\} { x ˉ k } . The following lemma identifies the weak cluster points of the shadows and gives sufficient conditions for weak convergence of both sequences.
Lemma 4.9 (Weak convergence of the PPPA sequences). Let { ( x k , x ˉ k ) } \{(x^k,\bar{x}^k)\} {( x k , x ˉ k )} be generated by (21) , with z k , q k z^k,q^k z k , q k defined by (24) . Suppose that q k → 0 q^k\to0 q k → 0 and A R A_R A R is demiclosed at zero. Then every weak cluster point of { x ˉ k } \{\bar{x}^k\} { x ˉ k } belongs to zer A \operatorname{zer} A zer A . If, in addition, z k ⇀ z ∞ z^k\rightharpoonup z^\infty z k ⇀ z ∞ , let
X : = { x ∈ zer A : C ∗ x = z ∞ } . (37) X:=\{x\in\operatorname{zer} A:C^*x=z^\infty\}. \tag*{(37)} X := { x ∈ zer A : C ∗ x = z ∞ } . (37) Then the following hold.
(i) Every weak cluster point of { x ˉ k } \{\bar{x}^k\} { x ˉ k } belongs to X X X .
(ii) If { x ˉ k } \{\bar{x}^k\} { x ˉ k } is bounded, then X ≠ ∅ X\ne\varnothing X = ∅ . If, moreover, X = { x ∞ } X=\{x^\infty\} X = { x ∞ } , then x ˉ k ⇀ x ∞ \bar{x}^k\rightharpoonup x^\infty x ˉ k ⇀ x ∞ . In particular, X X X is a singleton whenever P P P is admissible for A A A .
(iii) If x ˉ k ⇀ x ∞ \bar{x}^k\rightharpoonup x^\infty x ˉ k ⇀ x ∞ and
0 < λ ‾ ≤ λ k ≤ λ ‾ < 2 ( k ∈ N ) , (38) 0<\underline{\lambda}\leq\lambda_k\leq\overline{\lambda}<2\qquad(k\in\mathbb{N}), \tag*{(38)} 0 < λ ≤ λ k ≤ λ < 2 ( k ∈ N ) , (38) then x k ⇀ x ∞ x^k\rightharpoonup x^\infty x k ⇀ x ∞ .
Proof. Let x ˉ k j ⇀ x ˉ \bar{x}^{k_j}\rightharpoonup\bar{x} x ˉ k j ⇀ x ˉ . By (25) , C q k j ∈ A R x ˉ k j Cq^{k_j}\in A_R\bar{x}^{k_j} C q k j ∈ A R x ˉ k j and C q k j → 0 Cq^{k_j}\to0 C q k j → 0 . Demiclosedness of A R A_R A R gives x ˉ ∈ zer A R = zer A \bar{x}\in\operatorname{zer} A_R=\operatorname{zer} A x ˉ ∈ zer A R = zer A . If z k ⇀ z ∞ z^k\rightharpoonup z^\infty z k ⇀ z ∞ , then C ∗ x ˉ k j = z k j − q k j ⇀ z ∞ C^*\bar{x}^{k_j}=z^{k_j}-q^{k_j}\rightharpoonup z^\infty C ∗ x ˉ k j = z k j − q k j ⇀ z ∞ , whence C ∗ x ˉ = z ∞ C^*\bar{x}=z^\infty C ∗ x ˉ = z ∞ . This proves (i).
For (ii), boundedness of { x ˉ k } \{\bar{x}^k\} { x ˉ k } ensures the existence of weak cluster points, so (i) gives X ≠ ∅ X\ne\varnothing X = ∅ . If X = { x ∞ } X=\{x^\infty\} X = { x ∞ } , every weakly convergent subsequence of { x ˉ k } \{\bar{x}^k\} { x ˉ k } has limit x ∞ x^\infty x ∞ . By boundedness, it follows that x ˉ k ⇀ x ∞ \bar{x}^{k} \rightharpoonup x^{\infty} x ˉ k ⇀ x ∞ . Now, suppose that P P P is admissible for A A A . For every x ∈ X x \in X x ∈ X , we have x ∈ zer A x \in\operatorname{zer} A x ∈ zer A and C ∗ x = z ∞ C^{*}x = z^{\infty} C ∗ x = z ∞ . Hence, C z ∞ = P x ∈ ( P + A ) x Cz^{\infty} = Px \in(P + A)x C z ∞ = P x ∈ ( P + A ) x , so x ∈ ( P + A ) − 1 C z ∞ x \in(P + A)^{-1}Cz^{\infty} x ∈ ( P + A ) − 1 C z ∞ . Admissibility implies that X X X has at most one element. Since X ≠ ∅ X \ne\varnothing X = ∅ under the boundedness assumption, the conclusion follows.
Finally, suppose that x k ⇀ x ∞ x^{k} \rightharpoonup x^{\infty} x k ⇀ x ∞ and (38) holds. Fix h ∈ H h \in\mathcal{H} h ∈ H and set a k : = ⟨ x k − x ∞ , h ⟩ a_k := \langle x^{k} - x^{\infty}, h\rangle a k := ⟨ x k − x ∞ , h ⟩ and b k : = ⟨ x ˉ k − x ∞ , h ⟩ b_k := \langle\bar{x}^{k} - x^{\infty}, h\rangle b k := ⟨ x ˉ k − x ∞ , h ⟩ . Since b k → 0 b_k \to0 b k → 0 and θ : = max { ∣ 1 − λ ∣ , ∣ 1 − λ ˉ ∣ } < 1 \theta:= \max\{|1-\lambda|, |1-\bar{\lambda}|\} < 1 θ := max { ∣1 − λ ∣ , ∣1 − λ ˉ ∣ } < 1 , the recursion a k + 1 = ( 1 − λ k ) a k + λ k b k a_{k+1} = (1-\lambda_k)a_k+\lambda_k b_k a k + 1 = ( 1 − λ k ) a k + λ k b k derived from (21) gives ∣ a k + 1 ∣ ≤ θ ∣ a k ∣ + λ ˉ ∣ b k ∣ |a_{k+1}| \le\theta|a_k|+\bar{\lambda}|b_k| ∣ a k + 1 ∣ ≤ θ ∣ a k ∣ + λ ˉ ∣ b k ∣ . By [25 § 2.2.1, Lemma 3] , a k → 0 a_k \to0 a k → 0 . Since h ∈ H h \in\mathcal{H} h ∈ H was arbitrary, x k ⇀ x ∞ x^{k} \rightharpoonup x^{\infty} x k ⇀ x ∞ , proving (iii).
We now combine the reduced convergence results with Lemma 4.9 to establish projected convergence and, under additional conditions, weak convergence of the full PPPA sequences.
Theorem 4.10 (Weak convergence of the PPPA sequences). Suppose the assumptions of Corollary 4.4 hold, lim inf k δ k > 0 \liminf_k \delta_k > 0 lim inf k δ k > 0 , and (36) holds. Assume further that A R A_{\mathcal{R}} A R is demiclosed at zero and the bounded-recovery condition holds. Then there exists z ∞ ∈ C ∗ ( zer A ) z^{\infty} \in C^{*}(\operatorname{zer} A) z ∞ ∈ C ∗ ( zer A ) such that
z k ⇀ z ∞ , Π R x k , Π R x ˉ k ⇀ ( P ∣ R ) − 1 / 2 z ∞ ∈ Π R ( zer A ) . (39) z^{k} \rightharpoonup z^{\infty}, \qquad\Pi_{\mathcal{R}}x^{k},\ \Pi_{\mathcal{R}}\bar{x}^{k} \rightharpoonup(P|_{\mathcal{R}})^{-1/2}z^{\infty} \in\Pi_{\mathcal{R}}(\operatorname{zer} A). \tag*{(39)} z k ⇀ z ∞ , Π R x k , Π R x ˉ k ⇀ ( P ∣ R ) − 1/2 z ∞ ∈ Π R ( zer A ) . (39) Moreover, { x ˉ k } \{\bar{x}^{k}\} { x ˉ k } is bounded, and the set X ⊆ zer A X \subseteq\operatorname{zer} A X ⊆ zer A defined by (37) is nonempty and contains every weak cluster point of { x ˉ k } \{\bar{x}^{k}\} { x ˉ k } . If X = { x ∞ } X = \{x^{\infty}\} X = { x ∞ } , then x ˉ k ⇀ x ∞ \bar{x}^{k} \rightharpoonup x^{\infty} x ˉ k ⇀ x ∞ . This uniqueness condition holds, in particular, when P P P is admissible for A A A . If also (38) holds, then x k ⇀ x ∞ x^{k} \rightharpoonup x^{\infty} x k ⇀ x ∞ .
Proof. By Corollary 4.4 , { z k } \{z^{k}\} { z k } is bounded and q k → 0 q^{k} \to0 q k → 0 . Demiclosedness of A R A_{\mathcal{R}} A R at zero and the bounded-recovery condition imply demiclosedness of F F F at zero by Lemma 4.8 . Thus, Proposition 4.5 (ii) yields (39) . Since { z k } \{z^{k}\} { z k } is bounded, the bounded-recovery condition also implies boundedness of { x ˉ k } \{\bar{x}^{k}\} { x ˉ k } . The remaining conclusions follow from Lemma 4.9 .
Further consequences of the monotonicity modulus
We now exploit the monotonicity modulus U U U of A R A_{\mathcal{R}} A R . First, the nonnegative term in (32) yields a Lipschitz recovery estimate (Definition 2.5 (ii)).
Theorem 4.11 (Lipschitz recovery from the monotonicity modulus). Let ∅ ≠ S ⋆ ⊆ zer A \varnothing\ne S^{\star} \subseteq\operatorname{zer} A ∅ = S ⋆ ⊆ zer A , and suppose that A R A_{\mathcal{R}} A R is relatively ( U , V ) (U,V) ( U , V ) -semimonotone with respect to S ⋆ S^{\star} S ⋆ . Suppose that U ⪰ τ P U \succeq\tau P U ⪰ τ P for some τ ∈ R \tau\in\mathbb{R} τ ∈ R , H + τ Id R \mathcal{H}+\tau\operatorname{Id}_{\mathcal{R}} H + τ Id R is strongly monotone, and U U U is strongly monotone on ker P \ker P ker P , that is, ⟨ h , U h ⟩ ≥ γ ∥ h ∥ 2 \langle h,Uh\rangle\ge\gamma\|h\|^{2} ⟨ h , U h ⟩ ≥ γ ∥ h ∥ 2 for all h ∈ ker P h \in\ker P h ∈ ker P and some γ > 0 \gamma> 0 γ > 0 . Then the Lipschitz recovery estimate (5) holds relative to S ⋆ S^{\star} S ⋆ . Consequently, the bounded-recovery condition holds and Φ ( C ∗ x ⋆ ) = { x ⋆ } \Phi(C^{*}x^{\star}) = \{x^{\star}\} Φ ( C ∗ x ⋆ ) = { x ⋆ } for every x ⋆ ∈ S ⋆ x^{\star} \in S^{\star} x ⋆ ∈ S ⋆ .
Proof. Fix x ⋆ ∈ S ⋆ x^{\star} \in S^{\star} x ⋆ ∈ S ⋆ , z ∈ R z \in\mathcal{R} z ∈ R , and x ˉ ∈ ( P + A ) − 1 C z \bar{x} \in(P + A)^{-1}Cz x ˉ ∈ ( P + A ) − 1 C z . Set d : = z − C ∗ x ⋆ d := z - C^{*}x^{\star} d := z − C ∗ x ⋆ , q : = z − C ∗ x ˉ q := z - C^{*}\bar{x} q := z − C ∗ x ˉ , and W : = U − τ P ⪰ 0 W := U - \tau P \succeq0 W := U − τ P ⪰ 0 . Let η > 0 \eta> 0 η > 0 be such that H + τ Id R ⪰ η Id R \mathcal{H}+\tau\operatorname{Id}_{\mathcal{R}} \succeq\eta\operatorname{Id}_{\mathcal{R}} H + τ Id R ⪰ η Id R . By (32) and Cauchy–Schwarz,
∥ W 1 / 2 ( x ˉ − x ⋆ ) ∥ 2 + η ∥ q ∥ 2 ≤ ( 1 + 2 τ ) ⟨ q , d ⟩ − τ ∥ d ∥ 2 ≤ ∣ 1 + 2 τ ∣ ∥ q ∥ ∥ d ∥ + max { − τ , 0 } ∥ d ∥ 2 . \left\|W^{1/2}(\bar{x}-x^{\star})\right\|^{2}+\eta\|q\|^{2}\le(1+2\tau)\langle q,d\rangle-\tau\|d\|^{2}\le|1+2\tau|\|q\|\|d\|+\max\{-\tau,0\}\|d\|^{2}. W 1/2 ( x ˉ − x ⋆ ) 2 + η ∥ q ∥ 2 ≤ ( 1 + 2 τ ) ⟨ q , d ⟩ − τ ∥ d ∥ 2 ≤ ∣1 + 2 τ ∣∥ q ∥∥ d ∥ + max { − τ , 0 } ∥ d ∥ 2 .
Applying Young’s inequality to the last expression yields ∥ W 1 / 2 ( x ˉ − x ⋆ ) ∥ 2 + η 2 ∥ q ∥ 2 ≤ L ∥ d ∥ 2 \left\|W^{1/2}(\bar{x}-x^{\star})\right\|^{2}+\frac{\eta}{2}\|q\|^{2}\le L\|d\|^{2} W 1/2 ( x ˉ − x ⋆ ) 2 + 2 η ∥ q ∥ 2 ≤ L ∥ d ∥ 2 , where L : = max { − τ , 0 } + ( 1 + 2 τ ) 2 / ( 2 η ) L := \max\{-\tau,0\}+(1+2\tau)^{2}/(2\eta) L := max { − τ , 0 } + ( 1 + 2 τ ) 2 / ( 2 η ) . Hence, ∥ q ∥ ≤ c ∥ d ∥ \|q\|\le c\|d\| ∥ q ∥ ≤ c ∥ d ∥ and ∥ W 1 / 2 ( x ˉ − x ⋆ ) ∥ ≤ L ∥ d ∥ \left\|W^{1/2}(\bar{x}-x^{\star})\right\|\le\sqrt{L}\|d\| W 1/2 ( x ˉ − x ⋆ ) ≤ L ∥ d ∥ , where c : = 2 L / η c := \sqrt{2L/\eta} c := 2 L / η .
Write x ˉ − x ⋆ = r + h \bar{x}-x^{\star}=r+h x ˉ − x ⋆ = r + h with r ∈ R r \in\mathcal{R} r ∈ R and h ∈ ker P h \in\ker P h ∈ ker P . Then C ∗ r = C ∗ ( x ˉ − x ⋆ ) = d − q C^{*}r=C^{*}(\bar{x}-x^{\star})=d-q C ∗ r = C ∗ ( x ˉ − x ⋆ ) = d − q and by (2) , ( P ∣ R ) 1 / 2 r = d − q (P|_{\mathcal{R}})^{1/2}r=d-q ( P ∣ R ) 1/2 r = d − q . Thus, ∥ r ∥ ≤ M ( ∥ d ∥ + ∥ q ∥ ) ≤ M ( 1 + c ) ∥ d ∥ \|r\|\le M(\|d\|+\|q\|)\le M(1+c)\|d\| ∥ r ∥ ≤ M ( ∥ d ∥ + ∥ q ∥ ) ≤ M ( 1 + c ) ∥ d ∥ , where M : = ∥ ( P ∣ R ) − 1 / 2 ∥ M := \left\|(P|_{\mathcal{R}})^{-1/2}\right\| M := ( P ∣ R ) − 1/2 . On the other hand, ⟨ h , W h ⟩ = ⟨ h , U h ⟩ ≥ γ ∥ h ∥ 2 \langle h,Wh\rangle=\langle h,Uh\rangle\ge\gamma\|h\|^{2} ⟨ h , W h ⟩ = ⟨ h , U h ⟩ ≥ γ ∥ h ∥ 2 , and so γ ∥ h ∥ ≤ ∥ W 1 / 2 h ∥ ≤ L ∥ d ∥ + ∥ W ∥ ∥ r ∥ \sqrt{\gamma}\|h\|\le\|W^{1/2}h\|\le\sqrt{L}\|d\|+\sqrt{\|W\|}\|r\| γ ∥ h ∥ ≤ ∥ W 1/2 h ∥ ≤ L ∥ d ∥ + ∥ W ∥ ∥ r ∥ . Combining these estimates proves (5) with K : = M ( 1 + c ) ( 1 + ∥ W ∥ / γ ) + L / γ K:=M(1+c)(1+\sqrt{\|W\|/\gamma})+\sqrt{L/\gamma} K := M ( 1 + c ) ( 1 + ∥ W ∥/ γ ) + L / γ . The rest of the claims follows from Lemma 2.6.
If A R A_R A R is demiclosed at zero, then Theorem 4.11 and Lemma 4.8 imply that F F F is demiclosed at zero. Moreover, under the assumptions of Theorem 4.10 other than bounded-recovery condition, strong monotonicity of U U U on ker P \ker P ker P suffices to obtain x ˉ k ⇀ x ∞ ∈ S ⋆ \bar{x}^{k}\rightharpoonup x^{\infty}\in S^{\star} x ˉ k ⇀ x ∞ ∈ S ⋆ , without requiring admissibility.
We next apply Proposition 3.1(v) to directly obtain strong and linear convergence.
Theorem 4.12 (Strong and linear convergence of the PPPA). Let ∅ ≠ S ⋆ ⊆ zer A \varnothing\ne S^{\star}\subseteq\operatorname{zer} A ∅ = S ⋆ ⊆ zer A , and suppose that A R A_R A R is relatively ( U , V ) (U,V) ( U , V ) -semimonotone with respect to S ⋆ S^{\star} S ⋆ , where U ⪰ τ P U\succeq\tau P U ⪰ τ P for some τ > 0 \tau>0 τ > 0 and H + τ Id R H+\tau\operatorname{Id}_{R} H + τ Id R is strongly monotone. Suppose that λ k ∈ ( 0 , 2 β k T ] \lambda_k\in(0,2\beta_k^T] λ k ∈ ( 0 , 2 β k T ] , where β k T > 0 \beta_k^T>0 β k T > 0 satisfies ⟨ q k , ( H + τ Id R ) q k ⟩ ≥ ( 1 + 2 τ ) β k T ∥ q k ∥ 2 \langle q^k,(H+\tau\operatorname{Id}_{R})q^k\rangle\ge(1+2\tau)\beta_k^T\|q^k\|^{2} ⟨ q k , ( H + τ Id R ) q k ⟩ ≥ ( 1 + 2 τ ) β k T ∥ q k ∥ 2 . Then C ⋆ ( zer A ) = { z ⋆ } C^{\star}(\operatorname{zer} A)=\{z^{\star}\} C ⋆ ( zer A ) = { z ⋆ } . Moreover,
(i) If ∑ k λ k = + ∞ \sum_k\lambda_k=+\infty ∑ k λ k = + ∞ , then z k → z ⋆ z^k\to z^{\star} z k → z ⋆ , q k → 0 q^k\to0 q k → 0 , and Π R x k , Π R x ˉ k → ( P ∣ R ) − 1 / 2 z ⋆ \Pi_Rx^k,\Pi_R\bar{x}^k\to(P|_R)^{-1/2}z^{\star} Π R x k , Π R x ˉ k → ( P ∣ R ) − 1/2 z ⋆ strongly.
(ii) If lim inf k λ k > 0 \liminf_k\lambda_k>0 lim inf k λ k > 0 , then { z k } \{z^k\} { z k } converges Q Q Q -linearly, while { q k } \{q^k\} { q k } , { Π R x k } \{\Pi_Rx^k\} { Π R x k } , and { Π R x ˉ k } \{\Pi_R\bar{x}^k\} { Π R x ˉ k } converge R R R -linearly to their respective limits in (i).
(iii) If, in addition, a local Lipschitz recovery estimate holds at some x ⋆ ∈ S ⋆ x^{\star}\in S^{\star} x ⋆ ∈ S ⋆ , then zer A = { x ⋆ } \operatorname{zer} A=\{x^{\star}\} zer A = { x ⋆ } and x ˉ k → x ⋆ \bar{x}^k\to x^{\star} x ˉ k → x ⋆ strongly whenever ∑ k λ k = + ∞ \sum_k\lambda_k=+\infty ∑ k λ k = + ∞ . If lim inf k λ k > 0 \liminf_k\lambda_k>0 lim inf k λ k > 0 , then { x ˉ k } \{\bar{x}^k\} { x ˉ k } converges R R R -linearly. If also (38) holds, then x k → x ⋆ x^k\to x^{\star} x k → x ⋆ R R R -linearly.
Proof. Fix x ⋆ ∈ S ⋆ x^{\star}\in S^{\star} x ⋆ ∈ S ⋆ and set z ⋆ : = C ⋆ x ⋆ z^{\star}:=C^{\star}x^{\star} z ⋆ := C ⋆ x ⋆ . By Lemma 4.3, F F F is relatively ( a τ Id R , V τ ) (a_{\tau}\operatorname{Id}_{R},V_{\tau}) ( a τ Id R , V τ ) -semimonotone with respect to C ⋆ S ⋆ C^{\star}S^{\star} C ⋆ S ⋆ , where a τ : = τ / ( 1 + 2 τ ) > 0 a_{\tau}:=\tau/(1+2\tau)>0 a τ := τ / ( 1 + 2 τ ) > 0 and V τ : = ( H + τ Id R ) / ( 1 + 2 τ ) ≻ 0 V_{\tau}:=(H+\tau\operatorname{Id}_{R})/(1+2\tau)\succ0 V τ := ( H + τ Id R ) / ( 1 + 2 τ ) ≻ 0 . Taking q = 0 q=0 q = 0 in (32) shows that zer F = { z ⋆ } \operatorname{zer} F=\{z^{\star}\} zer F = { z ⋆ } . Hence, C ⋆ ( zer A ) = { z ⋆ } C^{\star}(\operatorname{zer} A)=\{z^{\star}\} C ⋆ ( zer A ) = { z ⋆ } by (30) .
The strong and Q Q Q -linear convergence of { z k } \{z^k\} { z k } in (i) and (ii) follow directly from Proposition 3.1(v).
Choose η > 0 \eta>0 η > 0 such that V τ ⪰ η Id R V_{\tau}\succeq\eta\operatorname{Id}_{R} V τ ⪰ η Id R . Relative semimonotonicity gives η ∥ q k ∥ 2 ≤ ⟨ q k , z k − z ⋆ ⟩ \eta\|q^k\|^{2}\le\langle q^k,z^k-z^{\star}\rangle η ∥ q k ∥ 2 ≤ ⟨ q k , z k − z ⋆ ⟩ , whence ∥ q k ∥ ≤ η − 1 ∥ z k − z ⋆ ∥ \|q^k\|\le\eta^{-1}\|z^k-z^{\star}\| ∥ q k ∥ ≤ η − 1 ∥ z k − z ⋆ ∥ . Thus, the convergence and rates of { q k } \{q^k\} { q k } follow, and (35) gives the corresponding conclusions for both projected PPPA sequences.
For (iii), Lemma 2.6 shows that x ⋆ x^{\star} x ⋆ is the unique zero of A A A satisfying C ⋆ x = z ⋆ C^{\star}x=z^{\star} C ⋆ x = z ⋆ . Since C ⋆ ( zer A ) = { z ⋆ } C^{\star}(\operatorname{zer} A)=\{z^{\star}\} C ⋆ ( zer A ) = { z ⋆ } , we have zer A = { x ⋆ } \operatorname{zer} A=\{x^{\star}\} zer A = { x ⋆ } . By (i), whenever ∑ k λ k = + ∞ \sum_k\lambda_k=+\infty ∑ k λ k = + ∞ , we have z k → z ⋆ z^k\to z^{\star} z k → z ⋆ , so the local Lipschitz recovery estimate gives ∥ x ˉ k − x ⋆ ∥ ≤ K ∥ z k − z ⋆ ∥ \|\bar{x}^k-x^{\star}\|\le K\|z^k-z^{\star}\| ∥ x ˉ k − x ⋆ ∥ ≤ K ∥ z k − z ⋆ ∥ for all sufficiently large k k k . Hence, x ˉ k → x ⋆ \bar{x}^k\to x^{\star} x ˉ k → x ⋆ strongly. If lim inf k λ k > 0 \liminf_k\lambda_k>0 lim inf k λ k > 0 , then (ii) and the same bound yield R R R -linear convergence of { x ˉ k } \{\bar{x}^k\} { x ˉ k } . Finally, under (38) , the recursion x k + 1 = ( 1 − λ k ) x k + λ k x ˉ k x^{k+1}=(1-\lambda_k)x^k+\lambda_k\bar{x}^k x k + 1 = ( 1 − λ k ) x k + λ k x ˉ k implies R R R -linear convergence of { x k } \{x^k\} { x k } , by an argument analogous to Lemma 4.9(iii).
Linear convergence under metric subregularity
We apply Proposition 3.4 to the reduced PPPA when U ⪰ − σ P U\succeq-\sigma P U ⪰ − σ P for some 0 ≤ σ < 1 / 2 0\le\sigma<1/2 0 ≤ σ < 1/2 . For x ∈ H x\in\mathcal{H} x ∈ H , let dist P ( x , zer A ) : = inf x ⋆ ∈ zer A ∥ x − x ⋆ ∥ P \operatorname{dist}_{P}(x,\operatorname{zer} A):=\inf_{x^{\star}\in\operatorname{zer} A}\|x-x^{\star}\|_{P} dist P ( x , zer A ) := inf x ⋆ ∈ zer A ∥ x − x ⋆ ∥ P . By (30) , dist P ( x , zer A ) = dist ( C ⋆ x , zer F ) \operatorname{dist}_{P}(x,\operatorname{zer} A)=\operatorname{dist}(C^{\star}x,\operatorname{zer} F) dist P ( x , zer A ) = dist ( C ⋆ x , zer F ) .
Corollary 4.13 (Local linear convergence of the PPPA). Let ∅ ≠ S ⋆ ⊆ zer A \varnothing\ne S^{\star}\subseteq\operatorname{zer} A ∅ = S ⋆ ⊆ zer A satisfy (36) , and suppose that A R A_R A R is relatively ( U , V ) (U,V) ( U , V ) -semimonotone with respect to S ⋆ S^{\star} S ⋆ , where U ⪰ − σ P U\succeq-\sigma P U ⪰ − σ P for some 0 ≤ σ < 1 / 2 0\le\sigma<1/2 0 ≤ σ < 1/2 and H − σ Id R H-\sigma\operatorname{Id}_{R} H − σ Id R is strongly monotone. Fix x ⋆ ∈ S ⋆ x^{\star}\in S^{\star} x ⋆ ∈ S ⋆ and set z ⋆ : = C ⋆ x ⋆ z^{\star}:=C^{\star}x^{\star} z ⋆ := C ⋆ x ⋆ . Suppose that, for some R > 0 R>0 R > 0 , one of the following holds:
(a) F F F is metrically subregular at z ⋆ z^\star z ⋆ for zero with modulus χ > 0 \chi> 0 χ > 0 , with the error bound holding on B R ( z ⋆ ) B_R(z^\star) B R ( z ⋆ ) ;
(b) G = A C G = A_C G = A C is metrically subregular at z ⋆ z^\star z ⋆ for zero with modulus χ ^ > 0 \widehat{\chi} > 0 χ > 0 , with the error bound holding on B R ( z ⋆ ) B_R(z^\star) B R ( z ⋆ ) .
Let { ( x k , x ˉ k ) } \{(x^k,\bar{x}^k)\} {( x k , x ˉ k )} be generated by (21) , with z k , q k z^k,q^k z k , q k given by (24) . Set ε : = σ / ( 1 − 2 σ ) \varepsilon:= \sigma/(1-2\sigma) ε := σ / ( 1 − 2 σ ) and β σ : = ( η H − σ ) / ( 1 − 2 σ ) > 0 \beta_\sigma:= (\eta_H-\sigma)/(1-2\sigma)>0 β σ := ( η H − σ ) / ( 1 − 2 σ ) > 0 . Suppose that
0 < λ k ≤ 2 β k , β k ≥ β σ , ⟨ q k , ( H − σ Id R ) q k ⟩ ≥ ( 1 − 2 σ ) β k ∥ q k ∥ 2 . (40) 0 < \lambda_k \le2\beta_k,\qquad\beta_k \ge\beta_\sigma,\qquad\langle q^k,(H-\sigma\operatorname{Id}_{\mathcal{R}})q^k\rangle\ge(1-2\sigma)\beta_k\lVert q^k\rVert^2. \tag*{(40)} 0 < λ k ≤ 2 β k , β k ≥ β σ , ⟨ q k , ( H − σ Id R ) q k ⟩ ≥ ( 1 − 2 σ ) β k ∥ q k ∥ 2 . (40) Under (a) or (b), respectively, set
Δ k : = { λ k ( 2 β k − λ k − 2 ε χ 2 ) , under (a) , λ k [ 2 β k − λ k − 2 ε ( χ ^ + ∣ 1 − λ k ∣ ) 2 ] , under (b) . (41) \Delta_k := \begin{cases}
\lambda_k(2\beta_k-\lambda_k-2\varepsilon\chi^2), & \text{under (a)},\\
\lambda_k[2\beta_k-\lambda_k-2\varepsilon(\widehat{\chi}+|1-\lambda_k|)^2], & \text{under (b)}.
\end{cases} \tag*{(41)} Δ k := { λ k ( 2 β k − λ k − 2 ε χ 2 ) , λ k [ 2 β k − λ k − 2 ε ( χ + ∣1 − λ k ∣ ) 2 ] , under (a) , under (b) . (41) Suppose that Δ k ≥ κ \Delta_k \ge\kappa Δ k ≥ κ for all k k k , for some κ > 0 \kappa> 0 κ > 0 . Then there exist r ∈ ( 0 , R ) r \in(0,R) r ∈ ( 0 , R ) , ρ ∈ [ 0 , 1 ) \rho\in[0,1) ρ ∈ [ 0 , 1 ) , and Γ > 0 \Gamma> 0 Γ > 0 such that, whenever ∥ x 0 − x ⋆ ∥ P < r \lVert x^0-x^\star\rVert_P < r ∥ x 0 − x ⋆ ∥ P < r , the following hold.
(i) Let d k : = dist P ( x k , zer A ) d_k:=\operatorname{dist}_P(x^k,\operatorname{zer} A) d k := dist P ( x k , zer A ) . Then d k + 1 ≤ ρ d k d_{k+1}\le\rho d_k d k + 1 ≤ ρ d k , and hence d k ≤ d 0 ρ k d_k\le d_0\rho^k d k ≤ d 0 ρ k . Moreover, ∥ x k − x ˉ k ∥ P = ∥ q k ∥ ≤ m ε ( β k ) d k \lVert x^k-\bar{x}^k\rVert_P=\lVert q^k\rVert\le m_\varepsilon(\beta_k)d_k ∥ x k − x ˉ k ∥ P = ∥ q k ∥ ≤ m ε ( β k ) d k , and ∥ x k + 1 − x k ∥ P ≤ ( 1 − ρ ) Γ d k \lVert x^{k+1}-x^k\rVert_P\le(1-\rho)\Gamma d_k ∥ x k + 1 − x k ∥ P ≤ ( 1 − ρ ) Γ d k .
(ii) The reduced PPPA sequence { z k } \{z^k\} { z k } converges strongly to some z ∞ ∈ C ∗ ( zer A ) z^\infty\in C^*(\operatorname{zer} A) z ∞ ∈ C ∗ ( zer A ) and, for every m ≥ k m\ge k m ≥ k , ∥ x m − x k ∥ P ≤ Γ d k \lVert x^m-x^k\rVert_P\le\Gamma d_k ∥ x m − x k ∥ P ≤ Γ d k , ∥ z k − z ∞ ∥ ≤ Γ d k \lVert z^k-z^\infty\rVert\le\Gamma d_k ∥ z k − z ∞ ∥ ≤ Γ d k , and ∥ C ∗ x ˉ k − z ∞ ∥ ≤ [ Γ + m ε ( β k ) ] d k \lVert C^* \bar{x}^k-z^\infty\rVert\le[\Gamma+m_\varepsilon(\beta_k)]d_k ∥ C ∗ x ˉ k − z ∞ ∥ ≤ [ Γ + m ε ( β k )] d k . Consequently, both projected PPPA sequences converge R R R -linearly to ( P ∣ R ) − 1 / 2 z ∞ (P|_R)^{-1/2}z^\infty ( P ∣ R ) − 1/2 z ∞ .
(iii) Suppose, in addition, that (5) holds with a constant K > 0 K>0 K > 0 uniformly over S ⋆ S^\star S ⋆ . Then there exists x ∞ ∈ S ⋆ x^\infty\in S^\star x ∞ ∈ S ⋆ , the unique zero of A A A with C ∗ x ∞ = z ∞ C^*x^\infty=z^\infty C ∗ x ∞ = z ∞ , such that ∥ x ˉ k − x ∞ ∥ ≤ K Γ d k \lVert\bar{x}^k-x^\infty\rVert\le K\Gamma d_k ∥ x ˉ k − x ∞ ∥ ≤ K Γ d k . Thus, { x ˉ k } \{\bar{x}^k\} { x ˉ k } converges strongly and R R R -linearly to x ∞ x^\infty x ∞ and if (38) holds, then x k → x ∞ x^k\to x^\infty x k → x ∞ R R R -linearly.
When σ = 0 \sigma=0 σ = 0 , the bounds in (ii)–(iii) hold with Γ 0 : = min { 2 , Γ } \Gamma_0:=\min\{2,\Gamma\} Γ 0 := min { 2 , Γ } in place of Γ \Gamma Γ , and m 0 ( β k ) = 1 / β k m_0(\beta_k)=1/\beta_k m 0 ( β k ) = 1/ β k .
Proof. By Lemma 4.3 with τ = − σ \tau=-\sigma τ = − σ and (36) , F F F is relatively ( − ε Id R , V σ ) (-\varepsilon\operatorname{Id}_{\mathcal{R}},V_\sigma) ( − ε Id R , V σ ) -semimonotone with respect to zer F = C ∗ ( zer A ) \operatorname{zer} F=C^*(\operatorname{zer} A) zer F = C ∗ ( zer A ) , where V σ : = ( H − σ Id R ) / ( 1 − 2 σ ) ⪰ β σ Id R V_\sigma:=(H-\sigma\operatorname{Id}_{\mathcal{R}})/(1-2\sigma)\succeq\beta_\sigma\operatorname{Id}_{\mathcal{R}} V σ := ( H − σ Id R ) / ( 1 − 2 σ ) ⪰ β σ Id R . The standing full-domain assumption ensures that F F F has nonempty values everywhere. By (26) , the reduced PPPA is precisely the forward iteration (6) for F F F . Moreover, (40) gives the required coefficients β k \beta_k β k , while (41) agrees with (10). Thus, Proposition 3.4 applies when ∥ z 0 − z ⋆ ∥ = ∥ x 0 − x ⋆ ∥ P < r \lVert z^0-z^\star\rVert=\lVert x^0-x^\star\rVert_P<r ∥ z 0 − z ⋆ ∥ = ∥ x 0 − x ⋆ ∥ P < r with sufficiently small r > 0 r>0 r > 0 . Using Eqs. (27) and (35) with Proposition 3.4(ii)–(iii) gives the estimates in (i) and (ii).
For (iii), choose x ∞ ∈ S ⋆ x^\infty\in S^\star x ∞ ∈ S ⋆ with C ∗ x ∞ = z ∞ C^*x^\infty=z^\infty C ∗ x ∞ = z ∞ , which is possible by (36) . Eq. (5) gives ∥ x ˉ k − x ∞ ∥ ≤ K ∥ z k − z ∞ ∥ ≤ K Γ d k \lVert\bar{x}^k-x^\infty\rVert\le K\lVert z^k-z^\infty\rVert\le K\Gamma d_k ∥ x ˉ k − x ∞ ∥ ≤ K ∥ z k − z ∞ ∥ ≤ K Γ d k . As in the proof of Theorem 4.12(iii), applying the same estimate at z = z ∞ z=z^\infty z = z ∞ shows that x ∞ x^\infty x ∞ is the unique zero of A A A with C ∗ x ∞ = z ∞ C^*x^\infty=z^\infty C ∗ x ∞ = z ∞ . The R R R -linear convergence of { x k } \{x^k\} { x k } under (38) follows by the same argument as in Theorem 4.12(iii). Lastly, the improved bounds when σ = 0 \sigma=0 σ = 0 follow from Proposition 3.4. □
Sufficient conditions for metric subregularity of F F F and G G G . The Lipschitz recovery estimate (5) used in Corollary 4.13(iii) follows from Theorem 4.11 if U U U is strongly monotone on ker P \ker P ker P . The following transfers metric subregularity of A R A_R A R to F F F and G G G , using only a local version of this estimate.
Lemma 4.14 (Transfer of metric subregularity). Let x ⋆ ∈ zer A x^\star\in\operatorname{zer} A x ⋆ ∈ zer A and z ⋆ : = C ∗ x ⋆ ∈ zer F z^\star:= C^\ast x^\star\in\operatorname{zer} F z ⋆ := C ∗ x ⋆ ∈ zer F . Suppose that A R A_R A R is metrically subregular at x ⋆ x^\star x ⋆ for zero with modulus χ R > 0 \chi_R > 0 χ R > 0 . Suppose also that there exist K , R L > 0 K, R_L > 0 K , R L > 0 such that
∥ x ˉ − x ⋆ ∥ ≤ K ∥ z − z ⋆ ∥ ∀ z ∈ B R L ( z ⋆ ) , x ˉ ∈ ( P + A ) − 1 C z . (42) \|\bar{x}-x^\star\| \le K\|z-z^\star\| \qquad\forall z \in B_{R_L}(z^\star),\quad\bar{x} \in(P+A)^{-1}Cz. \tag*{(42)} ∥ x ˉ − x ⋆ ∥ ≤ K ∥ z − z ⋆ ∥ ∀ z ∈ B R L ( z ⋆ ) , x ˉ ∈ ( P + A ) − 1 C z . (42) Then F F F and G : = ( F − 1 − Id ) − 1 = A C G := (F^{-1}-\operatorname{Id})^{-1}=A_C G := ( F − 1 − Id ) − 1 = A C are metrically subregular at z ⋆ z^\star z ⋆ for zero, with moduli 1 + c 1+c 1 + c and c c c , respectively, where c : = χ R ∥ P ∥ c:=\chi_R\|P\| c := χ R ∥ P ∥ . If the error bound for A R A_R A R holds globally, then both reduced error bounds hold globally without assuming (42) .
Proof. By metric subregularity, there exists r A > 0 r_A>0 r A > 0 such that
dist ( x , zer A ) ≤ χ R dist ( 0 , A R x ) ∀ x ∈ B r A ( x ⋆ ) . (43) \operatorname{dist}(x,\operatorname{zer} A)\le\chi_R\operatorname{dist}(0,A_Rx)\qquad\forall x\in B_{r_A}(x^\star). \tag*{(43)} dist ( x , zer A ) ≤ χ R dist ( 0 , A R x ) ∀ x ∈ B r A ( x ⋆ ) . (43)
Choose R 0 ∈ ( 0 , R L ) R_0\in(0,R_L) R 0 ∈ ( 0 , R L ) with K R 0 < r A KR_0<r_A K R 0 < r A . Let z ∈ B R 0 ( z ⋆ ) z\in B_{R_0}(z^\star) z ∈ B R 0 ( z ⋆ ) and q ∈ F ( z ) q\in F(z) q ∈ F ( z ) , and choose x ˉ ∈ ( P + A ) − 1 C z \bar{x}\in(P+A)^{-1}Cz x ˉ ∈ ( P + A ) − 1 C z with C ∗ x ˉ = z − q C^\ast\bar{x}=z-q C ∗ x ˉ = z − q and C q ∈ A R x ˉ Cq\in A_R\bar{x} C q ∈ A R x ˉ . Then x ˉ ∈ B r A ( x ⋆ ) \bar{x}\in B_{r_A}(x^\star) x ˉ ∈ B r A ( x ⋆ ) by (42) , and so by (43) , we get
dist ( z − q , zer F ) ≤ ∥ C ∗ ∥ dist ( x ˉ , zer A ) ≤ χ R ∥ C ∗ ∥ ∥ C q ∥ ≤ c ∥ q ∥ . (44) \operatorname{dist}(z-q,\operatorname{zer} F)\le\|C^\ast\|\operatorname{dist}(\bar{x},\operatorname{zer} A)\le\chi_R\|C^\ast\|\|Cq\|\le c\|q\|. \tag*{(44)} dist ( z − q , zer F ) ≤ ∥ C ∗ ∥ dist ( x ˉ , zer A ) ≤ χ R ∥ C ∗ ∥∥ C q ∥ ≤ c ∥ q ∥. (44)
Hence, dist ( z , zer F ) ≤ ( 1 + c ) ∥ q ∥ \operatorname{dist}(z,\operatorname{zer} F)\le(1+c)\|q\| dist ( z , zer F ) ≤ ( 1 + c ) ∥ q ∥ . Taking the infimum over q ∈ F ( z ) q\in F(z) q ∈ F ( z ) proves metric subregularity of F F F .
To establish that of G G G , choose 0 < s < min { R 0 / 2 , c R 0 / 2 } 0<s<\min\{R_0/2,cR_0/2\} 0 < s < min { R 0 /2 , c R 0 /2 } . If p ∈ B s ( z ⋆ ) p\in B_s(z^\star) p ∈ B s ( z ⋆ ) and q ∈ G ( p ) q\in G(p) q ∈ G ( p ) , then q ∈ F ( p + q ) q\in F(p+q) q ∈ F ( p + q ) . To prove metric subregularity of G G G with constant c c c , it suffices to show that dist ( p , zer F ) ≤ c ∥ q ∥ \operatorname{dist}(p,\operatorname{zer} F)\le c\|q\| dist ( p , zer F ) ≤ c ∥ q ∥ . When ∥ q ∥ < R 0 / 2 \|q\|<R_0/2 ∥ q ∥ < R 0 /2 , we have z : = p + q ∈ B R 0 ( z ⋆ ) z:=p+q\in B_{R_0}(z^\star) z := p + q ∈ B R 0 ( z ⋆ ) . Thus, (44) gives dist ( p , zer F ) ≤ c ∥ q ∥ \operatorname{dist}(p,\operatorname{zer} F)\le c\|q\| dist ( p , zer F ) ≤ c ∥ q ∥ . On the other hand, if ∥ q ∥ ≥ R 0 / 2 \|q\|\ge R_0/2 ∥ q ∥ ≥ R 0 /2 , we have dist ( p , zer F ) ≤ ∥ p − z ⋆ ∥ < s ≤ c R 0 / 2 ≤ c ∥ q ∥ \operatorname{dist}(p,\operatorname{zer} F)\le\|p-z^\star\|<s\le cR_0/2\le c\|q\| dist ( p , zer F ) ≤ ∥ p − z ⋆ ∥ < s ≤ c R 0 /2 ≤ c ∥ q ∥ . Hence, the metric subregularity of G G G holds.
If (43) holds on all of H \mathcal{H} H , the estimate (44) holds for every ( z , q ) ∈ gra F (z,q)\in\operatorname{gra} F ( z , q ) ∈ gra F without using (42) . The corresponding bounds for F F F and G G G are therefore global.
Since A R x ⊆ A x A_Rx\subseteq Ax A R x ⊆ A x and zer A R = zer A \operatorname{zer} A_R=\operatorname{zer} A zer A R = zer A , metric subregularity of A A A also implies that of A R A_R A R . By Lemma 4.14, metric subregularity of A R A_R A R at x ⋆ x^\star x ⋆ supplies either alternative in Corollary 4.13 whenever Lipschitz recovery holds at x ⋆ x^\star x ⋆ .
Finite-dimensional specialization
Suppose that H = R n \mathcal{H}=\mathbb{R}^n H = R n . If ( P + A ) − 1 P (P+A)^{-1}P ( P + A ) − 1 P is locally bounded at every point of R \mathcal{R} R , then the bounded-recovery condition holds, since C z = P ( ( P ∣ R ) − 1 / 2 z ) Cz=P((P|_{\mathcal{R}})^{-1/2}z) C z = P (( P ∣ R ) − 1/2 z ) for z ∈ R z\in\mathcal{R} z ∈ R and bounded subsets of R \mathcal{R} R have compact closure. If, in addition, A R A_R A R is outer semicontinuous, it is demiclosed at zero, so F F F is demiclosed at zero by Lemma 4.8. Local boundedness holds, in particular, when ( P + A ) − 1 P (P+A)^{-1}P ( P + A ) − 1 P is single-valued and continuous on R \mathcal{R} R , and outer semicontinuity of A A A implies that of A R A_R A R .
Corollary 4.15 (Finite-dimensional PPPA convergence). Suppose that H = R n \mathcal{H}=\mathbb{R}^n H = R n and the assumptions of Corollary 4.4 hold with lim inf k δ k > 0 \liminf_k\delta_k>0 lim inf k δ k > 0 . Suppose further that A R A_R A R is outer semicontinuous and ( P + A ) − 1 P (P+A)^{-1}P ( P + A ) − 1 P is locally bounded at every point of R \mathcal{R} R . Then F F F is demiclosed at zero, { x ˉ k } \{\bar{x}^k\} { x ˉ k } is bounded, and every accumulation point of { x ˉ k } \{\bar{x}^k\} { x ˉ k } belongs to zer A \operatorname{zer} A zer A . Moreover, every accumulation point of { Π R x k } \{\Pi_{\mathcal{R}}x^k\} { Π R x k } or { Π R x ˉ k } \{\Pi_{\mathcal{R}}\bar{x}^k\} { Π R x ˉ k } belongs to Π R ( zer A ) \Pi_{\mathcal{R}}(\operatorname{zer} A) Π R ( zer A ) .
If Π R S ⋆ = Π R ( zer A ) \Pi_{\mathcal{R}}S^\star=\Pi_{\mathcal{R}}(\operatorname{zer} A) Π R S ⋆ = Π R ( zer A ) , then both projected PPPA sequences converge in norm to the same point in Π R ( zer A ) \Pi_{\mathcal{R}}(\operatorname{zer} A) Π R ( zer A ) . If, in addition, P P P is admissible for A A A , then x ˉ k → x ∞ ∈ zer A \bar{x}^k\to x^\infty\in\operatorname{zer} A x ˉ k → x ∞ ∈ zer A . Under (38) , we also have x k → x ∞ x^k\to x^\infty x k → x ∞ .
Proof. By the preceding observations, A R A_R A R is demiclosed at zero and the bounded-recovery condition holds. Since C ∗ ∣ R C^\ast|_{\mathcal{R}} C ∗ ∣ R is an isomorphism, Π R S ⋆ = Π R ( zer A ) \Pi_{\mathcal{R}}S^\star=\Pi_{\mathcal{R}}(\operatorname{zer} A) Π R S ⋆ = Π R ( zer A ) is equivalent to C ∗ S ⋆ = C ∗ ( zer A ) C^\ast S^\star=C^\ast(\operatorname{zer} A) C ∗ S ⋆ = C ∗ ( zer A ) . The conclusions follow from Lemma 4.8 , Proposition 4.5 , and Theorem 4.10 , since weak and strong convergence coincide in R n \mathbb{R}^{n} R n .
To compare with [12 ] , let E ∈ R n × m E \in\mathbb{R}^{n \times m} E ∈ R n × m have orthonormal columns spanning R \mathcal{R} R , and set X : = E T P E ≽ 0 X := E^{\mathsf{T}}PE \succcurlyeq0 X := E T P E ≽ 0 . Identifying R \mathcal{R} R with R m \mathbb{R}^{m} R m through E E E , we have C = E X 1 / 2 C = EX^{1/2} C = E X 1/2 and
η H = 1 + λ min ( X 1 / 2 E T V E X 1 / 2 ) = 1 + λ min ( E T V P E ) . \eta_{H} = 1 + \lambda_{\min}\left(X^{1/2}E^{\mathsf{T}}VE X^{1/2}\right) = 1 + \lambda_{\min}\left(E^{\mathsf{T}}VPE\right). η H = 1 + λ m i n ( X 1/2 E T V E X 1/2 ) = 1 + λ m i n ( E T V P E ) .
Here, E T V P E E^{\mathsf{T}}VPE E T V P E is similar to the symmetric matrix X 1 / 2 E T V E X 1 / 2 X^{1/2}E^{\mathsf{T}}VE X^{1/2} X 1/2 E T V E X 1/2 . Hence, strong monotonicity of H H H is equivalent to [12 Assumption I.A4] . For q k ≠ 0 q^{k} \ne0 q k = 0 , the largest admissible β k \beta_{k} β k in (33) is ⟨ q k , H q k ⟩ / ∥ q k ∥ 2 \langle q^{k},Hq^{k}\rangle/\lVert q^{k}\rVert^{2} ⟨ q k , H q k ⟩ / ∥ q k ∥ 2 , which agrees with the adaptive coefficient in [12 Theorem 2.4] .
When U = 0 U = 0 U = 0 , Corollary 4.4 recovers the residual and best-iterate estimates of [12 Theorem 2.4] . Under global ( U , V ) (U,V) ( U , V ) -semimonotonicity with U ≽ 0 U \succcurlyeq0 U ≽ 0 , Proposition 4.6 also provides a Hilbert-space counterpart of the last-iterate squared-residual rate in [12 Theorem 2.11] . For the projected assertions in items (iii) and (v) of [12 Theorem 2.4] , which also appear as items (iii) and (iv) of its restatement in [11 Theorem 2.1] , the argument passes from limit points of the projected shadows to limit points of the shadows themselves. This step can fail when the kernel components of the shadows are unbounded: Example 4.7 satisfies the stated assumptions, yet its projected shadows converge to a point outside Π R ( zer A ) \Pi_{\mathcal{R}}(\operatorname{zer} A) Π R ( zer A ) . Corollary 4.15 shows that local boundedness of ( P + A ) − 1 P (P+A)^{-1}P ( P + A ) − 1 P suffices. Local boundedness holds, in particular, under the continuity assumption that both theorems impose for convergence of the full shadows.7 For the Douglas–Rachford and Chambolle–Pock applications of [11 , 12 ] , the required recovery condition follows from their full-graph semimonotonicity assumptions, so the projected identification and convergence conclusions of these applications remain valid (§ 5.2 ).
The linear convergence result of [12 Theorem 2.13] assumes metric subregularity of A A A at every zero, convexity of zer A \operatorname{zer} A zer A , and continuity of ( P + A ) − 1 P (P+A)^{-1}P ( P + A ) − 1 P , and gives an eventual rate from arbitrary initial points. For σ = 0 \sigma= 0 σ = 0 , Corollary 4.13 instead gives local reduced and projected rates without convexity or resolvent continuity. When its subregularity hypothesis is obtained from that of A R A_{\mathcal{R}} A R through Lemma 4.14 , which uses a local Lipschitz recovery estimate, alternative (a) yields a squared contraction factor of the same form as in [12 Theorem 2.13] , while alternative (b) can yield a sharper one; see Proposition 3.4 .
Primal–dual splitting
We now turn to Chambolle–Pock and Douglas–Rachford splitting. Let X \mathcal{X} X and Y \mathcal{Y} Y be real Hilbert spaces, A : X ⇉ X A:\mathcal{X}\rightrightarrows\mathcal{X} A : X ⇉ X , B : Y ⇉ Y B:\mathcal{Y}\rightrightarrows\mathcal{Y} B : Y ⇉ Y , and 0 ≠ L ∈ B ( X , Y ) 0 \ne L \in\mathcal{B}(\mathcal{X},\mathcal{Y}) 0 = L ∈ B ( X , Y ) . On H : = X ⊕ Y \mathcal{H}:=\mathcal{X}\oplus\mathcal{Y} H := X ⊕ Y , define
T P D ( u , v ) : = [ A u + L ∗ v B − 1 v − L u ] and P γ , τ : = [ γ − 1 Id X − L ∗ − L τ − 1 Id Y ] . (45) T_{\mathrm{PD}}(u,v):=\begin{bmatrix} Au+L^{*}v \\ B^{-1}v-Lu \end{bmatrix}
\quad\text{and}\quad
P_{\gamma,\tau}:=\begin{bmatrix} \gamma^{-1}\operatorname{Id}_{\mathcal{X}} & -L^{*} \\ -L & \tau^{-1}\operatorname{Id}_{\mathcal{Y}} \end{bmatrix}. \tag*{(45)} T PD ( u , v ) := [ A u + L ∗ v B − 1 v − Lu ] and P γ , τ := [ γ − 1 Id X − L − L ∗ τ − 1 Id Y ] . (45)
with γ , τ > 0 \gamma,\tau>0 γ , τ > 0 . Thus, zer T P D \operatorname{zer}T_{\mathrm{PD}} zer T PD consists of pairs ( u , v ) (u,v) ( u , v ) satisfying − L ∗ v ∈ A u -L^{*}v\in Au − L ∗ v ∈ A u and L u ∈ B − 1 v Lu\in B^{-1}v Lu ∈ B − 1 v . In particular, u u u solves the composite inclusion 0 ∈ A u + L ∗ B ( L u ) 0\in Au+L^{*}B(Lu) 0 ∈ A u + L ∗ B ( Lu ) . Moreover, P γ , τ ≽ 0 P_{\gamma,\tau}\succcurlyeq0 P γ , τ ≽ 0 if and only if γ τ ∥ L ∥ 2 ≤ 1 \gamma\tau\lVert L\rVert^{2}\le1 γ τ ∥ L ∥ 2 ≤ 1 , and it is strongly monotone when the inequality is strict. At the critical stepsize γ τ ∥ L ∥ 2 = 1 \gamma\tau\lVert L\rVert^{2}=1 γ τ ∥ L ∥ 2 = 1 , the range of P γ , τ P_{\gamma,\tau} P γ , τ need not be closed in Hilbert spaces. Indeed,
P γ , τ = Q [ γ − 1 Id X 0 0 γ S ] Q ∗ , where Q : = [ Id 0 − γ L Id ] P_{\gamma,\tau}=Q\begin{bmatrix} \gamma^{-1}\operatorname{Id}_{\mathcal{X}} & 0 \\ 0 & \gamma S \end{bmatrix}Q^{*},\quad\text{where}\quad Q:=\begin{bmatrix} \operatorname{Id} & 0 \\ -\gamma L & \operatorname{Id} \end{bmatrix} P γ , τ = Q [ γ − 1 Id X 0 0 γ S ] Q ∗ , where Q := [ Id − γ L 0 Id ]
and S : = ∥ L ∥ 2 Id Y − L L ∗ S := \lVert L\rVert^{2}\operatorname{Id}_{Y}-LL^{*} S := ∥ L ∥ 2 Id Y − L L ∗ . Since Q Q Q is boundedly invertible, P γ , τ P_{\gamma,\tau} P γ , τ has closed range if and only if S S S has closed range.
Write x k = ( u k , v k ) x^{k}=(u^{k},v^{k}) x k = ( u k , v k ) and x ˉ k = ( u ˉ k , v ˉ k ) \bar{x}^{k}=(\bar{u}^{k},\bar{v}^{k}) x ˉ k = ( u ˉ k , v ˉ k ) for the PPPA iterates and shadows, respectively. Then x ˉ k ∈ ( P γ , τ + T P D ) − 1 P γ , τ x k \bar{x}^{k}\in(P_{\gamma,\tau}+T_{\mathrm{PD}})^{-1}P_{\gamma,\tau}x^{k} x ˉ k ∈ ( P γ , τ + T PD ) − 1 P γ , τ x k is equivalent to
u ˉ k ∈ J γ A ( u k − γ L ∗ v k ) and v ˉ k ∈ J τ B − 1 ( v k + τ L ( 2 u ˉ k − u k ) ) . (46) \bar{u}^{k}\in J_{\gamma A}(u^{k}-\gamma L^{*}v^{k})\quad\text{and}\quad\bar{v}^{k}\in J_{\tau B^{-1}}(v^{k}+\tau L(2\bar{u}^{k}-u^{k})). \tag*{(46)} u ˉ k ∈ J γ A ( u k − γ L ∗ v k ) and v ˉ k ∈ J τ B − 1 ( v k + τ L ( 2 u ˉ k − u k )) . (46)
Together with x k + 1 = x k + λ k ( x ˉ k − x k ) x^{k+1}=x^{k}+\lambda_{k}(\bar{x}^{k}-x^{k}) x k + 1 = x k + λ k ( x ˉ k − x k ) , this gives the relaxed Chambolle–Pock iteration [6 ] . Full-domain component resolvents ensure dom ( ( P γ , τ + T P D ) − 1 P γ , τ ) = H \operatorname{dom}((P_{\gamma,\tau}+T_{\mathrm{PD}})^{-1}P_{\gamma,\tau})=\mathcal{H} dom (( P γ , τ + T PD ) − 1 P γ , τ ) = H . Henceforth, we suppose P : = P γ , τ ⪰ 0 P:=P_{\gamma,\tau}\succeq0 P := P γ , τ ⪰ 0 has closed range, and let R : = ran P \mathcal{R}:=\operatorname{ran}P R := ran P and P = C C ∗ P=CC^{*} P = C C ∗ be as in (2) on H \mathcal{H} H . We write F P D F_{\mathrm{PD}} F PD for the corresponding reduced forward map.
Bounded recovery from the primal–dual structure
We now exploit the primal–dual structure to obtain a Lipschitz recovery estimate for T P D T_{\mathrm{PD}} T PD . Unlike Theorem 4.11 , this requires no strong monotonicity of U U U on ker P \ker P ker P , but it assumes relative semimonotonicity on the full graph of T P D T_{\mathrm{PD}} T PD , not only on ( T P D ) R (T_{\mathrm{PD}})\mathcal{R} ( T PD ) R .
Theorem 5.1 (Primal–dual bounded recovery). Let ∅ ≠ S ⋆ ⊆ zer T P D \varnothing\ne S^{\star}\subseteq\operatorname{zer}T_{\mathrm{PD}} ∅ = S ⋆ ⊆ zer T PD and suppose that T P D T_{\mathrm{PD}} T PD is relatively ( U , V ) (U,V) ( U , V ) -semimonotone with respect to S ⋆ S^{\star} S ⋆ (on its full graph), where U ⪰ − σ P U\succeq-\sigma P U ⪰ − σ P for some σ ≥ 0 \sigma\ge0 σ ≥ 0 , where P = P γ , τ P=P_{\gamma,\tau} P = P γ , τ is given by (45) , and V = V 1 ⊕ V 2 V=V_{1}\oplus V_{2} V = V 1 ⊕ V 2 where V 1 , V 2 V_{1},V_{2} V 1 , V 2 are self-adjoint blocks. Suppose that H : = Id R + C ∗ V C H:=\operatorname{Id}_{\mathcal{R}}+C^{*}VC H := Id R + C ∗ V C satisfies
H − σ Id R ⪰ κ Id R for some κ > 0. (47) H-\sigma\operatorname{Id}_{\mathcal{R}}\succeq\kappa\operatorname{Id}_{\mathcal{R}}\qquad\text{for some }\kappa>0. \tag*{(47)} H − σ Id R ⪰ κ Id R for some κ > 0. (47) Then the Lipschitz recovery estimate (5) holds relative to S ⋆ S^{\star} S ⋆ ; that is, there exists K P D > 0 K_{\mathrm{PD}}>0 K PD > 0 such that, for every x ⋆ ∈ S ⋆ x^{\star}\in S^{\star} x ⋆ ∈ S ⋆ , x ∈ H x\in\mathcal{H} x ∈ H , and x ˉ ∈ ( P + T P D ) − 1 P x \bar{x}\in(P+T_{\mathrm{PD}})^{-1}Px x ˉ ∈ ( P + T PD ) − 1 P x ,
∥ x ˉ − x ⋆ ∥ ≤ K P D ∥ C ∗ ( x − x ⋆ ) ∥ . (48) \lVert\bar{x}-x^{\star}\rVert\le K_{\mathrm{PD}}\lVert C^{*}(x-x^{\star})\rVert. \tag*{(48)} ∥ x ˉ − x ⋆ ∥ ≤ K PD ∥ C ∗ ( x − x ⋆ )∥ . (48) Consequently, the bounded-recovery condition holds and ( P + T P D ) − 1 C ( C ∗ x ⋆ ) = { x ⋆ } (P+T_{\mathrm{PD}})^{-1}C(C^{*}x^{\star})=\{x^{\star}\} ( P + T PD ) − 1 C ( C ∗ x ⋆ ) = { x ⋆ } for every x ⋆ ∈ S ⋆ x^{\star}\in S^{\star} x ⋆ ∈ S ⋆ .
Proof. Fix x ⋆ = ( u ⋆ , v ⋆ ) ∈ S ⋆ x^{\star}=(u^{\star},v^{\star})\in S^{\star} x ⋆ = ( u ⋆ , v ⋆ ) ∈ S ⋆ , x = ( u , v ) ∈ H x=(u,v)\in\mathcal{H} x = ( u , v ) ∈ H , and x ˉ = ( u ˉ , v ˉ ) ∈ ( P + T P D ) − 1 P x \bar{x}=(\bar{u},\bar{v})\in(P+T_{\mathrm{PD}})^{-1}Px x ˉ = ( u ˉ , v ˉ ) ∈ ( P + T PD ) − 1 P x . Since x ⋆ ∈ zer T P D x^{\star}\in\operatorname{zer}T_{\mathrm{PD}} x ⋆ ∈ zer T PD , − L ∗ v ⋆ ∈ A u ⋆ -L^{*}v^{\star}\in Au^{\star} − L ∗ v ⋆ ∈ A u ⋆ , and L u ⋆ ∈ B − 1 v ⋆ Lu^{\star}\in B^{-1}v^{\star} L u ⋆ ∈ B − 1 v ⋆ . By (46) , u ˉ ∈ J γ A ( s ) \bar{u}\in J_{\gamma A}(s) u ˉ ∈ J γ A ( s ) and v ˉ ∈ J τ B − 1 ( t ) \bar{v}\in J_{\tau B^{-1}}(t) v ˉ ∈ J τ B − 1 ( t ) , where s : = u − γ L ∗ v s:=u-\gamma L^{*}v s := u − γ L ∗ v , and t : = v + τ L ( 2 u ˉ − u ) t:=v+\tau L(2\bar{u}-u) t := v + τ L ( 2 u ˉ − u ) . Set s ⋆ : = u ⋆ − γ L ∗ v ⋆ s^{\star}:=u^{\star}-\gamma L^{*}v^{\star} s ⋆ := u ⋆ − γ L ∗ v ⋆ and t ⋆ : = v ⋆ + τ L u ⋆ t^{\star}:=v^{\star}+\tau Lu^{\star} t ⋆ := v ⋆ + τ L u ⋆ .
We first derive bounds for ∥ u ˉ − u ⋆ ∥ \lVert\bar{u}-u^{\star}\rVert ∥ u ˉ − u ⋆ ∥ and ∥ v ˉ − v ⋆ ∥ \lVert\bar{v}-v^{\star}\rVert ∥ v ˉ − v ⋆ ∥ in terms of ∥ s − s ⋆ ∥ \lVert s-s^{\star}\rVert ∥ s − s ⋆ ∥ and ∥ t − t ⋆ ∥ \lVert t-t^{\star}\rVert ∥ t − t ⋆ ∥ , respectively. Since P + P V P = C H C ∗ P+PVP=CHC^{*} P + P V P = C H C ∗ , (47) gives
P + P V P ⪰ ( σ + κ ) P . (49) P+PVP\succeq(\sigma+\kappa)P. \tag*{(49)} P + P V P ⪰ ( σ + κ ) P . (49)
By a direct calculation using the definition of P P P , diagonal blocks of P + P V P P+PVP P + P V P are γ − 1 Q 1 \gamma^{-1}Q_{1} γ − 1 Q 1 and τ − 1 Q 2 \tau^{-1}Q_{2} τ − 1 Q 2 , where Q 1 : = Id X + γ − 1 V 1 + γ L ∗ V 2 L Q_{1}:=\operatorname{Id}_{X}+\gamma^{-1}V_{1}+\gamma L^{*}V_{2}L Q 1 := Id X + γ − 1 V 1 + γ L ∗ V 2 L and Q 2 : = Id Y + τ − 1 V 2 + τ L V 1 L ∗ Q_{2}:=\operatorname{Id}_{Y}+\tau^{-1}V_{2}+\tau LV_{1}L^{*} Q 2 := Id Y + τ − 1 V 2 + τ L V 1 L ∗ . By (49) ,
⟨ h , ( Q 1 − σ Id X ) h ⟩ ≥ κ ∥ h ∥ 2 and ⟨ g , ( Q 2 − σ Id Y ) g ⟩ ≥ κ ∥ g ∥ 2 , (50) \langle h,(Q_{1}-\sigma\operatorname{Id}_{X})h\rangle\ge\kappa\lVert h\rVert^{2}\quad\text{and}\quad\langle g,(Q_{2}-\sigma\operatorname{Id}_{Y})g\rangle\ge\kappa\lVert g\rVert^{2}, \tag*{(50)} ⟨ h , ( Q 1 − σ Id X ) h ⟩ ≥ κ ∥ h ∥ 2 and ⟨ g , ( Q 2 − σ Id Y ) g ⟩ ≥ κ ∥ g ∥ 2 , (50)
for every h ∈ X h\in X h ∈ X and g ∈ Y g\in Y g ∈ Y . Meanwhile, since γ − 1 ( s − u ˉ ) ∈ A u ˉ \gamma^{-1}(s-\bar{u})\in A\bar{u} γ − 1 ( s − u ˉ ) ∈ A u ˉ and L u ⋆ ∈ B − 1 v ⋆ Lu^{\star}\in B^{-1}v^{\star} L u ⋆ ∈ B − 1 v ⋆ , we have
T P D ( u ˉ , v ⋆ ) = ( A u ˉ + L ∗ v ⋆ , B − 1 v ⋆ − L u ˉ ) T_{\mathrm{PD}}(\bar{u},v^{\star})=(A\bar{u}+L^{*}v^{\star},B^{-1}v^{\star}-L\bar{u}) T PD ( u ˉ , v ⋆ ) = ( A u ˉ + L ∗ v ⋆ , B − 1 v ⋆ − L u ˉ )
⊇ ( γ − 1 ( s − u ˉ ) + L ∗ v ⋆ , L u ⋆ − L u ˉ ) = ( γ − 1 ( s − s ⋆ − h ) , − L h ) , \begin{aligned}
\supseteq(\gamma^{-1}(s-\bar{u})+L^{*}v^{\star},Lu^{\star}-L\bar{u}) \\
&=(\gamma^{-1}(s-s^{\star}-h),-Lh),
\end{aligned} ⊇ ( γ − 1 ( s − u ˉ ) + L ∗ v ⋆ , L u ⋆ − L u ˉ ) = ( γ − 1 ( s − s ⋆ − h ) , − L h ) ,
where h : = u ˉ − u ⋆ h:=\bar{u}-u^{\star} h := u ˉ − u ⋆ . Applying relative semimonotonicity to this graph point and x ⋆ x^{\star} x ⋆ , and using U ⪰ − σ P U\succeq-\sigma P U ⪰ − σ P , the definition of P P P and V = V 1 ⊕ V 2 V=V_{1}\oplus V_{2} V = V 1 ⊕ V 2 , we obtain
γ − 1 ⟨ h , s − s ⋆ − h ⟩ ≥ − σ γ − 1 ∥ h ∥ 2 + γ − 2 ⟨ s − s ⋆ − h , V 1 ( s − s ⋆ − h ) ⟩ + ⟨ L h , V 2 L h ⟩ . \gamma^{-1}\langle h,s-s^{\star}-h\rangle\ge-\sigma\gamma^{-1}\lVert h\rVert^{2}+\gamma^{-2}\langle s-s^{\star}-h,V_{1}(s-s^{\star}-h)\rangle+\langle Lh,V_{2}Lh\rangle. γ − 1 ⟨ h , s − s ⋆ − h ⟩ ≥ − σ γ − 1 ∥ h ∥ 2 + γ − 2 ⟨ s − s ⋆ − h , V 1 ( s − s ⋆ − h )⟩ + ⟨ L h , V 2 L h ⟩ .
Multiplying by γ \gamma γ , expanding the inner products, and rearranging gives
⟨ h , ( Q 1 − σ Id X ) h ⟩ ≤ ⟨ h , s − s ⋆ ⟩ + 2 γ − 1 ⟨ h , V 1 ( s − s ⋆ ) ⟩ − γ − 1 ⟨ s − s ⋆ , V 1 ( s − s ⋆ ) ⟩ . \langle h,(\mathsf{Q}_1-\sigma\operatorname{Id}_{\mathcal{X}})h\rangle\le\langle h,s-s^\star\rangle+2\gamma^{-1}\langle h,V_1(s-s^\star)\rangle-\gamma^{-1}\langle s-s^\star,V_1(s-s^\star)\rangle. ⟨ h , ( Q 1 − σ Id X ) h ⟩ ≤ ⟨ h , s − s ⋆ ⟩ + 2 γ − 1 ⟨ h , V 1 ( s − s ⋆ )⟩ − γ − 1 ⟨ s − s ⋆ , V 1 ( s − s ⋆ )⟩ .
Together with (50) , this yields
κ ∥ h ∥ 2 ≤ ⟨ h , s − s ⋆ ⟩ + 2 γ − 1 ⟨ h , V 1 ( s − s ⋆ ) ⟩ − γ − 1 ⟨ s − s ⋆ , V 1 ( s − s ⋆ ) ⟩ . (51) \kappa\lVert h\rVert^2\le\langle h,s-s^\star\rangle+2\gamma^{-1}\langle h,V_1(s-s^\star)\rangle-\gamma^{-1}\langle s-s^\star,V_1(s-s^\star)\rangle. \tag*{(51)} κ ∥ h ∥ 2 ≤ ⟨ h , s − s ⋆ ⟩ + 2 γ − 1 ⟨ h , V 1 ( s − s ⋆ )⟩ − γ − 1 ⟨ s − s ⋆ , V 1 ( s − s ⋆ )⟩ . (51)
Similarly, since τ − 1 ( t − v ˉ ) ∈ B − 1 v ˉ \tau^{-1}(t-\bar v)\in B^{-1}\bar v τ − 1 ( t − v ˉ ) ∈ B − 1 v ˉ and − L ∗ v ⋆ ∈ A u ⋆ -L^\ast v^\star\in Au^\star − L ∗ v ⋆ ∈ A u ⋆ , we have T P D ( u ⋆ , v ˉ ) ∋ ( L ∗ g , τ − 1 ( t − t ⋆ − g ) ) T_{\mathrm{PD}}(u^\star,\bar v)\ni(L^\ast g,\tau^{-1}(t-t^\star-g)) T PD ( u ⋆ , v ˉ ) ∋ ( L ∗ g , τ − 1 ( t − t ⋆ − g )) , where g : = v ˉ − v ⋆ g:=\bar v-v^\star g := v ˉ − v ⋆ . The same argument gives
κ ∥ g ∥ 2 ≤ ⟨ g , t − t ⋆ ⟩ + 2 τ − 1 ⟨ g , V 2 ( t − t ⋆ ) ⟩ − τ − 1 ⟨ t − t ⋆ , V 2 ( t − t ⋆ ) ⟩ . (52) \kappa\lVert g\rVert^2\le\langle g,t-t^\star\rangle+2\tau^{-1}\langle g,V_2(t-t^\star)\rangle-\tau^{-1}\langle t-t^\star,V_2(t-t^\star)\rangle. \tag*{(52)} κ ∥ g ∥ 2 ≤ ⟨ g , t − t ⋆ ⟩ + 2 τ − 1 ⟨ g , V 2 ( t − t ⋆ )⟩ − τ − 1 ⟨ t − t ⋆ , V 2 ( t − t ⋆ )⟩ . (52)
Applying Cauchy–Schwarz to (51) and (52) , we get
κ ∥ h ∥ 2 ≤ ( 1 + 2 a 1 ) ∥ h ∥ ∥ s − s ⋆ ∥ + a 1 ∥ s − s ⋆ ∥ 2 , κ ∥ g ∥ 2 ≤ ( 1 + 2 a 2 ) ∥ g ∥ ∥ t − t ⋆ ∥ + a 2 ∥ t − t ⋆ ∥ 2 . \begin{aligned}
\kappa\lVert h\rVert^2&\le(1+2a_1)\lVert h\rVert\lVert s-s^\star\rVert+a_1\lVert s-s^\star\rVert^2,\\
\kappa\lVert g\rVert^2&\le(1+2a_2)\lVert g\rVert\lVert t-t^\star\rVert+a_2\lVert t-t^\star\rVert^2.
\end{aligned} κ ∥ h ∥ 2 κ ∥ g ∥ 2 ≤ ( 1 + 2 a 1 ) ∥ h ∥ ∥ s − s ⋆ ∥ + a 1 ∥ s − s ⋆ ∥ 2 , ≤ ( 1 + 2 a 2 ) ∥ g ∥ ∥ t − t ⋆ ∥ + a 2 ∥ t − t ⋆ ∥ 2 .
where a 1 : = γ − 1 ∥ V 1 ∥ a_1:=\gamma^{-1}\lVert V_1\rVert a 1 := γ − 1 ∥ V 1 ∥ and a 2 : = τ − 1 ∥ V 2 ∥ a_2:=\tau^{-1}\lVert V_2\rVert a 2 := τ − 1 ∥ V 2 ∥ . Solving these quadratic inequalities and plugging in h = u ˉ − u ⋆ h=\bar u-u^\star h = u ˉ − u ⋆ , g = v ˉ − v ⋆ g=\bar v-v^\star g = v ˉ − v ⋆ gives K 1 , K 2 > 0 K_1,K_2>0 K 1 , K 2 > 0 , depending only on γ \gamma γ , τ \tau τ , κ \kappa κ , ∥ V 1 ∥ \lVert V_1\rVert ∥ V 1 ∥ , and ∥ V 2 ∥ \lVert V_2\rVert ∥ V 2 ∥ , such that
∥ u ˉ − u ⋆ ∥ ≤ K 1 ∥ s − s ⋆ ∥ and ∥ v ˉ − v ⋆ ∥ ≤ K 2 ∥ t − t ⋆ ∥ . (53) \lVert\bar u-u^\star\rVert\le K_1\lVert s-s^\star\rVert\quad\text{and}\quad\lVert\bar v-v^\star\rVert\le K_2\lVert t-t^\star\rVert. \tag*{(53)} ∥ u ˉ − u ⋆ ∥ ≤ K 1 ∥ s − s ⋆ ∥ and ∥ v ˉ − v ⋆ ∥ ≤ K 2 ∥ t − t ⋆ ∥ . (53)
On the other hand, by the definitions of P P P , s s s , and t t t , P ( x − x ⋆ ) = ( γ − 1 ( s − s ⋆ ) , τ − 1 ( t − t ⋆ ) − 2 L ( u ˉ − u ⋆ ) ) P(x-x^\star)=(\gamma^{-1}(s-s^\star),\tau^{-1}(t-t^\star)-2L(\bar u-u^\star)) P ( x − x ⋆ ) = ( γ − 1 ( s − s ⋆ ) , τ − 1 ( t − t ⋆ ) − 2 L ( u ˉ − u ⋆ )) . Combining this identity with (53) , we obtain
∥ x ˉ − x ⋆ ∥ ≤ ∥ u ˉ − u ⋆ ∥ + ∥ v ˉ − v ⋆ ∥ ≤ K 1 ∥ s − s ⋆ ∥ + K 2 ∥ t − t ⋆ ∥ ≤ γ K 1 ∥ P ( x − x ⋆ ) ∥ + τ K 2 ( ∥ P ( x − x ⋆ ) ∥ + 2 ∥ L ∥ ∥ u ˉ − u ⋆ ∥ ) ≤ K ^ P D ∥ P ( x − x ⋆ ) ∥ , \begin{aligned}
\lVert\bar x-x^\star\rVert&\le\lVert\bar u-u^\star\rVert+\lVert\bar v-v^\star\rVert\\
&\le K_1\lVert s-s^\star\rVert+K_2\lVert t-t^\star\rVert\\
&\le\gamma K_1\lVert P(x-x^\star)\rVert+\tau K_2(\lVert P(x-x^\star)\rVert+2\lVert L\rVert\lVert\bar u-u^\star\rVert)\\
&\le\widehat K_{\mathrm{PD}}\lVert P(x-x^\star)\rVert,
\end{aligned} ∥ x ˉ − x ⋆ ∥ ≤ ∥ u ˉ − u ⋆ ∥ + ∥ v ˉ − v ⋆ ∥ ≤ K 1 ∥ s − s ⋆ ∥ + K 2 ∥ t − t ⋆ ∥ ≤ γ K 1 ∥ P ( x − x ⋆ )∥ + τ K 2 (∥ P ( x − x ⋆ )∥ + 2 ∥ L ∥ ∥ u ˉ − u ⋆ ∥) ≤ K PD ∥ P ( x − x ⋆ )∥ ,
where K ^ P D : = γ K 1 + τ K 2 ( 1 + 2 γ ∥ L ∥ K 1 ) \widehat K_{\mathrm{PD}}:=\gamma K_1+\tau K_2(1+2\gamma\lVert L\rVert K_1) K PD := γ K 1 + τ K 2 ( 1 + 2 γ ∥ L ∥ K 1 ) . Since P = C C ∗ ⪰ 0 P=CC^\ast\succeq0 P = C C ∗ ⪰ 0 and P 2 ⪯ ∥ P ∥ P P^2\preceq\lVert P\rVert P P 2 ⪯ ∥ P ∥ P , we have ∥ P ( x − x ⋆ ) ∥ ≤ ∥ P ∥ ∥ C ∗ ( x − x ⋆ ) ∥ \lVert P(x-x^\star)\rVert\le\sqrt{\lVert P\rVert}\lVert C^\ast(x-x^\star)\rVert ∥ P ( x − x ⋆ )∥ ≤ ∥ P ∥ ∥ C ∗ ( x − x ⋆ )∥ . Thus, (48) follows with K P D : = ∥ P ∥ K ^ P D K_{\mathrm{PD}}:=\sqrt{\lVert P\rVert}\widehat K_{\mathrm{PD}} K PD := ∥ P ∥ K PD . The rest of the claim follows from Lemma 2.6 .
Consequences for Chambolle–Pock and Douglas–Rachford
Although the projected assertions of the general result [11 Theorem 2.1] require an additional hypothesis, such as demiclosedness of the reduced map at zero (Example 4.7 and Proposition 4.5 ), the Chambolle–Pock conclusions of that work hold under its assumptions. In [11 Assumption II] , the primal–dual weak Minty condition is imposed on the full graph of T P D T_{\mathrm{PD}} T PD with a block-diagonal V V V . Their Stepsize Rule I ensures P ⪰ 0 P\succeq0 P ⪰ 0 and 1 + η ˉ > 0 1+\bar\eta>0 1 + η ˉ > 0 , where η ˉ \bar\eta η ˉ is defined in their equation (5). Since η H = 1 + η ˉ \eta_H=1+\bar\eta η H = 1 + η ˉ by § 4.6 , (47) holds with σ = 0 \sigma=0 σ = 0 . Thus, Theorem 5.1 gives Lipschitz recovery, including at the critical stepsize. In finite dimensions, outer semicontinuity of A A A and B B B implies demiclosedness of ( T P D ) R (T_{\mathrm{PD}})_R ( T PD ) R at zero, and hence of F P D F_{\mathrm{PD}} F PD by Lemmas 2.6 and 4.8 . Consequently, Corollary 4.4 and Proposition 4.5 establish the boundedness and projected identification in [11 Theorem 3.1(iii)] . Under their condition Π R S ⋆ = Π R ( zer T P D ) \Pi_{R}S^\star=\Pi_{R}(\operatorname{zer}T_{\mathrm{PD}}) Π R S ⋆ = Π R ( zer T PD ) , equivalently C ∗ S ⋆ = C ∗ ( zer T P D ) C^\ast S^\star=C^\ast(\operatorname{zer}T_{\mathrm{PD}}) C ∗ S ⋆ = C ∗ ( zer T PD ) , Theorems 4.10 and 5.1 also give convergence in norm of the projected sequences and full shadows, without the continuity of the component resolvents assumed in [11 Theorem 3.1(iv)] . The full PPPA iterates converge as well under (38) . Douglas–Rachford splitting is the special case L = Id L=\operatorname{Id} L = Id and τ = 1 / γ \tau=1/\gamma τ = 1/ γ , as observed in [11 ] . Thus, the conclusions of [12 Theorem 3.3] also hold, with item (v) requiring no continuity of the resolvents.
Future directions
The semimonotonicity calculus for Chambolle–Pock splitting in [11 ] combines the monotonicity and comonotonicity moduli of the component operators to obtain a comonotonicity modulus V V V for T P D T_{\mathrm{PD}} T PD , with U = 0 U = 0 U = 0 . Our framework allows a nonzero monotonicity modulus U U U . Developing a primal–dual semimonotonicity calculus that retains and exploits this modulus may yield stronger convergence guarantees. More broadly, the forward viewpoint developed in this paper suggests revisiting other splitting algorithms, such as extragradient [17 ] , forward–backward–forward [27 ] , forward–reflected–backward [22 ] , and more general distributed and primal–dual splitting frameworks [8 , 9 ] . Our semimonotone splitting framework [1 ] also admits a direct forward interpretation, but its analysis relies on classical cocoercivity estimates. An interesting question is whether these algorithms, possibly through suitable reformulations, admit forward operators satisfying the relative semimonotonicity conditions of § 3 , leading to more general convergence guarantees.
AI-assisted research and writing disclosure
The research was developed by the author, with AI assistance in the following aspects: ChatGPT suggested the concrete counterexample in Example 4.7 and assisted with the literature review; ChatGPT and Claude assisted in refining the manuscript’s exposition. The author assumes full responsibility for the manuscript.