betaFeedback

WorksMathematics

Degenerate Preconditioned Proximal Point Algorithms as Forward Methods for Nonmonotone Inclusions

Abstract

We study degenerate preconditioned proximal point algorithms (PPPA) for finding zeros of nonmonotone set-valued operators in Hilbert spaces under solution-relative (U,V)(U,V)-semimonotonicity, with possibly indefinite UU and VV. With a closed-range preconditioner PP, the reduced PPPA dynamics admit a forward representation through the complementary resolvent of a parallel composition, without requiring monotonicity or admissibility. Relative semimonotonicity of the range-restricted operator transfers to the reduced forward map, allowing our forward theory for possibly set-valued mappings to yield Fejér estimates and residual rates. Under suitable conditions, including demiclosedness of the reduced map at zero, the projected PPPA iterates and shadows converge weakly to a common projected zero. Without demiclosedness, a counterexample shows that the projected sequences may converge to a point outside the projected zero set, even when the original operator is continuous. Bounded recovery condition yields weak convergence of the full (non-projected) shadows. The monotonicity modulus UU yields additional results: under suitable conditions, U⪰τPU\succeqτP with τ>0τ>0 gives strong and linear convergence of the projected PPPA sequences, while U⪰−σPU\succeq-σP with 0≤σ<1/20\leσ<1/2 still permits local linear rates under metric subregularity. These strong convergence and linear rate guarantees extend to the full shadows when a Lipschitz recovery estimate holds, such as when UU is strongly monotone on ker⁡P\ker P. For Chambolle–Pock and Douglas–Rachford splitting, we establish Lipschitz recovery even when U=0U=0 by exploiting the primal–dual structure. Under suitable parameter conditions, full-shadow convergence guarantees, including RR-linear rates, extend to the original PPPA iterates.

MSC2020: 47J25, 47H05, 47J22, 49J53.

Introduction

Let H\mathcal{H} be a real Hilbert space and let A:H⇒HA:\mathcal{H}\Rightarrow\mathcal{H}. We study the relaxed preconditioned proximal point algorithm (PPPA)

xˉk∈(P+A)−1Pxk,xk+1=xk+λk(xˉk−xk),(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)}

for finding a zero of AA, where PP is bounded, self-adjoint, and positive semidefinite. We call {xˉk}\{\bar{x}^{k}\} the shadow sequence. For P=γ−1Id⁡P=\gamma^{-1}\operatorname{Id} and λk≡1\lambda_k\equiv1, 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 PP and a parallel composition. Their framework also accommodates monotonicity restricted to graph points whose operator values lie in ran⁡P\operatorname{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)-semimonotonicity [1, 11, 12]. Here, UU and VV 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 for every (x,a),(y,b)∈gra⁡A(x,a),(y,b) \in\operatorname{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) for prescribed x⋆x^\star in a nonempty set S⋆⊆zer⁡AS^\star\subseteq\operatorname{zer} A. The solution-relative condition with U=0U=0 recovers the VV-oblique weak Minty condition studied in the finite-dimensional setting in [12], which need not imply monotonicity even when V=0V=0. Allowing a negative monotonicity modulus UU further enlarges this class. Table 1 summarizes the operator assumptions and convergence guarantees of representative PPA and PPPA analyses.

ReferenceUUVVPairwise req.?Degen. PP?Proj. conv.Full conv.Linear conv.
Rockafellar [26]0000✓×✓✓✓
Bredies et al. [4]αP\alpha P, α≥0\alpha\ge000✓1✓✓✓✓2
Evens et al. [12]300general×✓✓4✓✓
Luke–Tam (2025)35−ϑ Id-\vartheta\,\mathrm{Id}−ϑ Id-\vartheta\,\mathrm{Id}✓×××✓
Xue–Zhang (2026)0000✓1✓✓✓×
Present workU⪰−σPU \succeq-\sigma Pgeneral×✓✓✓✓

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 PP has closed range R:=ran⁡P\mathcal{R}:=\operatorname{ran} P, the factorization P=CC∗P=CC^* gives reduced variables zk:=C∗xkz^k:=C^*x^k and residuals qk:=C∗(xk−xˉk)q^k := C^*(x^k-\bar{x}^k) satisfying

zk+1=zk−λkqk,whereqk∈F(zk),z^{k+1}=z^k-\lambda_k q^k,\qquad\text{where}\quad q^k\in F(z^k),

and FF is the complementary resolvent of a parallel composition of AA by 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 AA (or its range-restricted graph AR(x):=Ax∩RA_R(x):=Ax\cap R) transfers to FF 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 zk=C∗xkz^k=C^*x^k and zk−qk=C∗xˉkz^k-q^k=C^*\bar{x}^k encode, respectively, the projected PPPA iterates ΠRxk\Pi_Rx^k and projected shadows ΠRxˉk\Pi_R\bar{x}^k. The forward theory yields Fejér monotonicity and, under suitable parameter conditions, qk→0q^k\to0. 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 AA, even when AA is continuous, as shown by Example 4.7. This distinction motivates the study of demiclosedness of FF 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 FF follows from demiclosedness of AA (or of the range-restricted operator ARA_R) at zero and the bounded-recovery condition (see Definition 2.5(i)). These conditions also ensure boundedness of {xˉk}\{\bar{x}^k\} and that their weak cluster points are zeros of AA. Weak convergence of {xˉk}\{\bar{x}^k\} then follows when AA has only one zero xx with C∗x=z∞C^*x=z^\infty, where z∞z^\infty is the weak limit of {zk}\{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 UU provides further properties. Under suitable conditions, the lower bound U⪰τPU\succeq\tau P with τ>0\tau>0 translates into a strongly monotone modulus for FF, so that the general forward theory gives strong and linear convergence; a negative bound U⪰−σPU\succeq-\sigma P with 0≤σ<1/20\leq\sigma<1/2 similarly yields local linear rates under metric subregularity. Another role of UU is that its strong monotonicity on 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=0U=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.

  1. 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 AA shows that the projected PPPA iterates and shadows can converge to a point outside ΠR(zer⁡A)\Pi_{\mathcal{R}}(\operatorname{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 FF at zero Proposition 4.5, with sufficient conditions involving demiclosedness of ARA_{\mathcal{R}} and bounded recovery Lemma 4.8.

(iii) Full-space recovery and convergence. Under bounded recovery, when AA has exactly one zero xx with C∗x=z∞C^*x=z^\infty, where z∞z^\infty is the weak limit of {zk}\{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 UU on 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⪰τPU \succeq\tau P with τ>0\tau>0 Theorem 4.12. Local linear rates also extend to the full shadows when U⪰−σPU \succeq-\sigma P with σ∈[0,1/2)\sigma\in[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 VV yields Lipschitz recovery even when U=0U=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} and K\mathcal{K} are real Hilbert spaces, and N:={0,1,2,…}\mathbb{N}:=\{0,1,2,\ldots\}. We denote by B(H,K)\mathcal{B}(\mathcal{H},\mathcal{K}) the space of bounded linear operators from H\mathcal{H} to K\mathcal{K}, and B(H):=B(H,H)\mathcal{B}(\mathcal{H}):=\mathcal{B}(\mathcal{H},\mathcal{H}). We write Id⁡H\operatorname{Id}_{\mathcal{H}} for the identity operator on H\mathcal{H}, and simply Id⁡\operatorname{Id} when the space is clear. A self-adjoint operator U∈B(H)U\in\mathcal{B}(\mathcal{H}) is said to be strongly monotone on a closed subspace S⊆HS\subseteq\mathcal{H} if there exists μ>0\mu>0 such that ⟨h,Uh⟩≥μ∥h∥2\langle h,Uh\rangle\geq\mu\|h\|^2 for every h∈Sh\in S. For a closed subspace SS of a Hilbert space, ΠS\Pi_S denotes the orthogonal projector onto SS. For a subset SS of a Hilbert space, cl⁡S\operatorname{cl} S denotes its closure and dist⁡(x,S):=inf⁡s∈S∥x−s∥\operatorname{dist}(x,S):=\inf_{s\in S}\|x-s\|. For r>0r>0 and xˉ∈H\bar{x}\in\mathcal{H}, we write Br(xˉ):={x∈H:∥x−xˉ∥<r}B_r(\bar{x}):=\{x\in\mathcal{H}:\|x-\bar{x}\|<r\}. A sequence {zk}k∈N\{z^k\}_{k\in\mathbb{N}} is said to be Fejér monotone with respect to a nonempty set SS if ∥zk+1−z⋆∥≤∥zk−z⋆∥\|z^{k+1}-z^\star\|\leq\|z^k-z^\star\| for all z⋆∈Sz^\star\in S, k∈Nk\in\mathbb{N}. Weak and strong convergence are denoted by ⇀\rightharpoonup and →\to, respectively. For a set-valued operator AA, we write dom⁡A:={x:Ax≠∅}\operatorname{dom} A:=\{x:Ax\ne\varnothing\}, ran⁡A:=⋃x∈HAx\operatorname{ran} A:=\bigcup_{x\in\mathcal{H}}Ax, gra⁡A:={(x,a):a∈Ax}\operatorname{gra} A:=\{(x,a):a\in Ax\}, zer⁡A:={x:0∈Ax}\operatorname{zer} A:=\{x:0\in Ax\}, and A−1(a):={x:a∈Ax}A^{-1}(a):=\{x:a\in Ax\}. For a single-valued operator TT, we write Fix⁡T:={x:Tx=x}\operatorname{Fix} T:=\{x:Tx=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,VU,V)-semimonotonicity). Let A:H⇉HA:\mathcal{H}\rightrightarrows\mathcal{H}, and let U,V∈B(H)U,V\in\mathcal{B}(\mathcal{H}) be self-adjoint.

(i) We say that AA is (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

for all (x,a),(y,b)∈gra⁡A(x,a),(y,b)\in\operatorname{gra} A.

In particular, for β>0\beta>0, we say that AA is β\beta-cocoercive if it is (0,βId⁡)(0,\beta\operatorname{Id})-semimonotone.

References

  1. [1]J. H. Alcantara, M. N. Dao, and A. Takeda. A splitting framework for composite semimonotone inclusions, 2026. arXiv:2608.16609.arxiv.org/abs/2608.16609
  2. [2]S. Bartz, M. N. Dao, and H. M. Phan. Conical averagedness and convergence analysis of fixed point algorithms. J. Global Optim., 82:351–373, 2022. doi: 10.1007/s10898-021-01057-4.DOI
  3. [3]H. H. Bauschke and P. L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Cham, 2 edition, 2017.
  4. [4]K. Bredies, E. Chenchene, D. A. Lorenz, and E. Naldi. Degenerate preconditioned proximal point algorithms. SIAM J. Optim., 32(3):2376–2401, 2022. doi: 10.1137/21M1448112.DOI
  5. [5]K. Bredies, E. Chenchene, and E. Naldi. Graph and distributed extensions of the Douglas–Rachford method. SIAM J. Optim., 34(2):1569–1594, 2024. doi: 10.1137/22M1535097.DOI
  6. [6]A. Chambolle and T. Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision, 40:120–145, 2011. doi: 10.1007/s10851-010-0251-1.DOI
  7. [7]P. L. Combettes and T. Pennanen. Proximal methods for cohyponotone operators. SIAM Journal on Control and Optimization, 43(2):731–742, 2004. doi: 10.1137/S0363012903427336.DOI
  8. [8]M. N. Dao, H. M. Phan, M. K. Tam, and T. D. Truong. Primal-dual splitting for structured composite monotone inclusions with or without cocoercivity, 2025. arXiv:2512.10366.arxiv.org/abs/2512.10366
  9. [9]M. N. Dao, M. K. Tam, and T. D. Truong. A general approach to distributed operator splitting. J. Math. Anal. Appl., 562(2), 2026. doi: 10.1016/j.jmaa.2026.130692. Article 130692.DOI
  10. [10]A. L. Dontchev and R. T. Rockafellar. Implicit Functions and Solution Mappings: A View from Variational Analysis. Springer Series in Operations Research and Financial Engineering. Springer, New York, 2 edition, 2014. doi: 10.1007/978-1-4939-1037-3.DOI
  11. [11]B. Evens, P. Latafat, and P. Patrinos. Convergence of the Chambolle–Pock algorithm in the absence of monotonicity. J. Optim. Theory Appl., 206, 2025. doi: 10.1007/s10957-025-02680-x. Article 7.DOI
  12. [12]B. Evens, P. Pas, P. Latafat, and P. Patrinos. Convergence of the preconditioned proximal point method and Douglas–Rachford splitting in the absence of monotonicity. Math. Program., 214:247–301, 2025. doi: 10.1007/s10107-024-02182-0.DOI
  13. [13]B. Evens, P. Latafat, and P. Patrinos. Spingarn’s method and progressive decoupling beyond elicitable monotonicity. Computational Optimization and Applications, 95(2):777–817, 2026. doi: 10.1007/s10589-026-00812-1.DOI
  14. [14]E. Gorbunov, N. Loizou, and G. Gidel. Extragradient method: O(1/K) last-iterate convergence for monotone variational inequalities and connections with cocoercivity. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 366–402. PMLR, 2022.arxiv.org/abs/2110.04261
  15. [15]E. Gorbunov, A. Taylor, S. Horváth, and G. Gidel. Convergence of proximal point and extragradient-based methods beyond monotonicity: the case of negative comonotonicity. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 11614–11641, 2023.arxiv.org/abs/2210.13831
  16. [16]F. O. Isiogugu. Demiclosedness principle and approximation theorems for certain classes of multivalued mappings in Hilbert spaces. Fixed Point Theory and Applications, 2013, 2013. doi: 10.1186/1687-1812-2013-61. Article 61.DOI
  17. [17]G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody, 12(4):747–756, 1976. In Russian.
  18. [18]D. Leventhal. Metric subregularity and the proximal point method. J. Math. Anal. Appl., 360 (2):681–688, 2009. doi: 10.1016/j.jmaa.2009.07.012.DOI
  19. [19]N. Loizou, H. Berard, G. Gidel, I. Mitliagkas, and S. Lacoste-Julien. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. In Advances in Neural Information Processing Systems, volume 34, pages 19095–19108, 2021.arxiv.org/abs/2107.00052
  20. [20]D. R. Luke and M. K. Tam. Generalized monotonicity and the proximal point algorithm. Math. Oper. Res., 2025. doi: 10.1287/moor.2025.0863. Published online November 21, 2025.DOI
  21. [21]D. R. Luke, N. H. Thao, and M. K. Tam. Quantitative convergence analysis of iterated expansive, set-valued mappings. Math. Oper. Res., 43(4):1143–1176, 2018. doi: 10.1287/moor.2017.0898.DOI
  22. [22]Y. Malitsky and M. K. Tam. A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM Journal on Optimization, 30(2):1451–1472, 2020. doi: 10.1137/18M1207260.DOI
  23. [23]B. Martinet. Brève communication. régularisation d’inéquations variationnelles par approximations successives. Revue française d’informatique et de recherche opérationnelle. Série rouge, 4 (R3):154–158, 1970. doi: 10.1051/m2an/197004R301541.DOI
  24. [24]Ş. Măruşter. The solution by iteration of nonlinear equations in Hilbert spaces. Proceedings of the American Mathematical Society, 63(1):69–73, 1977. doi: 10.1090/S0002-9939-1977-0636944-2.DOI
  25. [25]B. T. Polyak. Introduction to Optimization. Translations Series in Mathematics and Engineering. Optimization Software, Inc., New York, 1987.
  26. [26]R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM J. Control Optim., 14(5):877–898, 1976. doi: 10.1137/0314056.DOI
  27. [27]P. Tseng. A modified forward-backward splitting method for maximal monotone map-pings. SIAM Journal on Control and Optimization, 38(2):431–446, 2000. doi: 10.1137/S0363012998338806.DOI
  28. [28]F. Xue and H. Zhang. On degenerate preconditioned proximal point methods under restricted monotonicity. J. Optim. Theory Appl., 208, 2026. doi: 10.1007/s10957-025-02915-x. Article 74.DOI

Paper details

vlnc:W_tsjxyp6m
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT, Claude

View statement
Looking for related papers…
Contents