Pith. sign in

REVIEW 3 major objections 4 minor 28 references

Peaceman-Rachford Splitting Method Converges Ergodically for Solving Convex Optimization Problems

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The averaged Peaceman-Rachford splitting method provably converges for convex optimization.

desk verdict The central claim—ergodic PR convergence for convex programs—is plausible and important; the main risk is the unverified equivalence imported from companion preprint [23], which a referee should check. read the letter →

arxiv 2501.07807 v1 pith:IAD732Z6 submitted 2025-01-14 math.OC

Kaihuang Chen , Defeng Sun , Yancheng Yuan , Guojun Zhang , Xinyuan Zhao This is my paper · ORCID
classification math.OC MSC 90C0590C0690C25
keywords Peaceman-RachfordsplittingergodicconvergenceconvexoptimizationdegenerateproximalpointalgorithmpreconditionedADMMlinearprogrammingrestartstrategy
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that the Peaceman-Rachford (PR) splitting method—an alternating algorithm for two-block convex optimization—converges when one looks at the running average of its iterates, a property called ergodic convergence. This resolves an open question: PR splitting is known to be faster than its relative Douglas-Rachford whenever it converges pointwise, but pointwise convergence can fail, and whether even the averaged sequence converged was unknown. The proof works for the relaxation factor $\rho \in (0,2]$, which includes the classic PR method ($\rho=2$) and the Douglas-Rachford method ($\rho=1$), and it allows semi-proximal terms that make the subproblems easier to solve. The paper also reports numerical experiments on linear programming benchmarks showing that a restarted averaged PR method consistently outperforms both the pointwise and averaged Douglas-Rachford methods. If correct, the result makes the averaged PR method a provably reliable choice for large-scale convex optimization.

What carries the argument

The carrying mechanism is the equivalence between the pADMM and a degenerate proximal point algorithm (dPPA) acting on the KKT operator $T$ of the convex problem, with a special positive semidefinite preconditioner $M$. The operator $M$ is a block matrix built from the constraint operators $B_1, B_2$, the penalty parameter $\sigma$, and the semi-proximal terms $T_1, T_2$; the dPPA step is $\bar w = (M+T)^{-1} M w$, followed by relaxation $w^{k+1} = (1-\rho) w^k + \rho \bar w^k$. Because the resolvent map is firmly nonexpansive in the $M$-seminorm, a distance-decrease inequality bounds the distance to any solution, and the classical nonlinear ergodic theorem supplies convergence of the averaged 'shadow' sequence. The Lipschitz continuity of $(M+T)^{-1}$ is what upgrades convergence of the shadow into convergence of the actual averaged iterates.

What would settle it

Run Algorithm 1 with $\rho=2$ and nonzero semi-proximal terms $T_1, T_2$ on a small convex problem with known solution, compute the dPPA iterates in (6) with $M$ as in (15) from the same starting point, and compare; any mismatch of the sequences, or any example where $(M+T)^{-1}$ fails to be Lipschitz, would invalidate Proposition 2 and with it Corollary 1.

Watch

Extended reading notes

Core claim

The paper's central claim is that the ergodic sequence $\{\bar w_a^k\}$ generated by the preconditioned alternating direction method of multipliers (pADMM) with relaxation parameter $\rho \in (0,2]$ converges to a Karush–Kuhn–Tucker point of the convex problem, provided the KKT system has a solution and the semi-proximal terms keep the subproblems well posed. Since $\rho=2$ in the pADMM is exactly the Peaceman-Rachford splitting method with semi-proximal terms, this gives the first ergodic convergence proof for PR splitting on convex optimization without strong monotonicity. The authors reach this by reformulating the pADMM as a degenerate proximal point algorithm with a positive semidefinite preconditioner, proving an ergodic convergence theorem for that general inclusion problem, and then transferring the result back to the optimization setting. They also establish an $O(1/k)$ ergodic iteration complexity for the objective error, feasibility violation, and KKT residual, with a constant half that of Douglas-Rachford.

Load-bearing premise

The entire proof depends on the imported claim that the alternating-direction iterations coincide exactly with a degenerate proximal point iteration whose resolvent $(M+T)^{-1}$ is Lipschitz continuous; if that equivalence fails for some semi-proximal operators $T_1, T_2$, the ergodic convergence theorem for the PR method does not follow.

Editorial extensions

If this is right

  • The averaged PR splitting method ($\rho=2$) converges for any convex problem satisfying the two structural assumptions, with no strong monotonicity required.
  • The same proof covers all $\rho \in (0,2]$, so the averaged Douglas-Rachford method ($\rho=1$) converges as a special case.
  • The averaged PR iterates have worst-case $O(1/k)$ complexity for objective gap, feasibility violation, and KKT residual, with constants half those of the corresponding Douglas-Rachford bounds.
  • With a restart strategy, the averaged PR method solves LP benchmark instances faster than both pointwise and averaged DR methods, and solves more instances within a time limit.
  • The pointwise sequence of the PR method can stay unbounded even when the averaged sequence converges, so averaging is the right object to analyze.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: the same dPPA reformulation could yield ergodic convergence for other splitting methods (e.g., primal-dual hybrid gradient variants) whenever they admit a degenerate proximal point representation.
  • Inference: the restart strategy's success hints that the ergodic sequence has oscillatory errors that averaging cancels; a testable extension is to measure how restart frequency interacts with the $\rho=2$ factor to see whether the factor-two complexity gap explains the observed speed-up.
  • Inference: the numerical comparison is on linear programs only; applying the restarted averaged PR method to conic or network optimization would show whether the advantage is generic.
  • Inference: the paper's complexity bound suggests that the averaged PR method's constant improves by a factor of two over DR, so iteration counts before restart should roughly halve; recording those counts on benchmark instances would directly test the mechanism.
Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

  1. Claim #1: The paper's central claim is that the ergodic sequence $\{\bar w_a^k\}$ generated by the preconditioned alternating direction method of multipliers (pADMM) with relaxation parameter $\rho \in (0,2]$ converges to a Karush–Kuhn–Tucker point of the convex problem, provided the KKT system has a solution and the semi-proximal terms keep the subproblems well posed. Since $\rho=2$ in the pADMM is exactly

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proves ergodic convergence of the preconditioned ADMM (pADMM) with relaxation parameter ρ∈(0,2], which includes the Peaceman–Rachford splitting method with semi-proximal terms at ρ=2, for convex optimization problems (1). The proof route is: reformulate the pADMM as a degenerate proximal point algorithm (dPPA) with preconditioner M (Proposition 2, imported from the companion preprint [23]); prove an ergodic convergence theorem for the dPPA (Theorem 1) using an ε-enlargement argument (Proposition 1) and Baillon's theorem; then transfer the result to the pADMM (Corollary 1). The paper also states an O(1/k) ergodic iteration complexity bound (Theorem 2) and reports numerical experiments on Mittelmann's LP benchmark in which a restarted ergodic PR method outperforms DR variants.

Significance. If the main theorem is correct, it settles a problem stated as open in the introduction: the averaged PR splitting method converges for convex optimization without strong monotonicity, and the convergence is for the primal–dual ergodic sequence rather than only a shadow sequence. The O(1/k) complexity bound and the numerical study on 49 LP instances are useful additions, and the analytical example in Appendix A nicely illustrates the obstruction to pointwise convergence. The dPPA ergodic result and its ε-enlargement proof appear to be the original contribution of this manuscript. However, the central bridge from the pADMM to the dPPA is not proved in the manuscript and is taken from an overlapping-author preprint, and two local steps in the proof of Theorem 1 and Proposition 1 need correction. The result is believable but the manuscript is not yet self-contained.

major comments (3)
  1. [Section 3, Proposition 2; also Theorem 2 via [23, Lemma 3.6]] The central claim of the paper rests on results imported without proof from the companion preprint [23] by four of the five authors: the equivalence between the pADMM in Algorithm 1 and the dPPA (6) under the preconditioner M in (15), the Lipschitz continuity of (M+T)^{-1}, and the estimate from [23, Lemma 3.6] used in Theorem 2. Corollary 1 transfers Theorem 1 to the pADMM precisely through this equivalence, so a failure of any of these ingredients would invalidate the main result. The manuscript must either include proofs of these supporting statements or cite a peer-reviewed published version; relying on an unreviewed preprint is not sufficient for a load-bearing step.
  2. [Section 2, proof of Proposition 1(b), Eq. (10)] The displayed chain does not justify the final bound ‖w0−w∗‖_M^2/(2ρ(k+1)). The authors use the estimate ‖w0−w̄_a^k‖_M ≤ 2‖w0−w∗‖_M but then substitute only ‖w0−w∗‖_M into the term 2‖w^{k+1}−w0‖_M‖w0−w̄_a^k‖_M. With a = ‖w^{k+1}−w0‖_M ≤ 2‖w0−w∗‖_M and b = ‖w0−w̄_a^k‖_M ≤ 2‖w0−w∗‖_M, the expression −a^2+2ab is bounded by 4‖w0−w∗‖_M^2, not by ‖w0−w∗‖_M^2. The stated bound (and the constant in Eq. (20) of Theorem 2) should be corrected. A corrected bound with an O(1/k) rate is still sufficient for Theorem 1.
  3. [Section 2, proof of Theorem 1, final paragraph] The Opial-type argument is not valid for the degenerate seminorm ‖·‖_M. When M has a nontrivial kernel, the strict inequality liminf ‖x_i−w∗‖_M < liminf ‖x_i−w∗_a‖_M can fail even when w∗ ≠ w∗_a, so the subsequent contradiction is not justified. The uniqueness of cluster points can be proved directly: if a subsequence w̄_a^{k_i} converges in norm to w∗, then by continuity of the M-seminorm ‖w∗−w∗_a‖_M = 0; since both w∗ and w∗_a lie in T^{-1}(0), Mw∗ = Mw∗_a and the single-valuedness of (M+T)^{-1} give w∗ = w∗_a. The Opial step should be replaced by this (or an equivalent) argument.
minor comments (4)
  1. [Appendix B, Eq. (29)] The norm in the second displayed inequality should be ‖z^k − z∗‖^2_{T2}, not ‖z^k − z∗‖^2_{T1}.
  2. [Section 2, proof of Theorem 1] Baillon's theorem yields weak convergence of the Cesàro means; the authors should state explicitly that weak and strong convergence coincide in the finite-dimensional setting before writing ‖u_a^k − C^*w_a^*‖ → 0.
  3. [Page 3, running header] The running header reads 'Ergodical Peaceman-Rachford Splitting Method'; 'Ergodical' should be 'Ergodic'.
  4. [Appendix B, proof of Theorem 2] The phrase 'combing with' should be 'combining with'.

Circularity Check

2 steps flagged · score 4.0 of 10

Ergodic PR convergence is not a tautology, but Corollary 1 reduces to Proposition 2 imported wholesale from the authors' own companion preprint [23], and Theorem 1 also imports load-bearing operator facts from [23].

  1. self citation load bearing [Section 3, Proposition 2 and Corollary 1]
    "Sun et al. [23] demonstrated the following equivalence between the pADMM in Algorithm 1 and the dPPA in (6). ... Proposition 2 ([23]) Suppose that Assumption 2 holds. Consider the operators T defined in (14) and M defined in (15), respectively. Then the sequence {wk} generated by the pADMM in Algorithm 1 coincides with the sequence {wk} generated by the dPPA in (6) with the same initial point w0 ∈ W. Additionally, M is an admissible preconditioner such that (M + T )−1 is Lipschitz continuous."

    Corollary 1, the paper's headline claim for the PR splitting method, is obtained by combining Theorem 1 with Proposition 2. The paper states 'The equivalence in Proposition 2 allows us to use the ergodic convergence results of the dPPA in Theorem 1 to establish the ergodic convergence of the pADMM' and then simply cites [23] for the equivalence and the Lipschitz continuity. Neither assertion is proved or independently verified in this manuscript; both are load-bearing because if the pADMM-to-dPPA equality or the Lipschitz property fails for some positive semidefinite T1, T2 allowed by Assumptions 1-2, Corollary 1 is unsupported. The central convergence claim thus reduces to an overlapping-author preprint rather than to a self-contained derivation.

  2. self citation load bearing [Section 2, proofs of Proposition 1 and Theorem 1]
    "Note that ˆT is M-firmly non-expansive, as stated in [23, Proposition 2.3] ... A straightforward calculation shows that uk+1 = ~Fρ uk, ∀k ≥ 0, where ~Fρ := (1 − ρ)I + ρ(C∗(M + T )−1C) with ρ ∈ (0, 2] is a non-expansive operator, as shown in [23, Proposition 2.5]."

    Theorem 1 is presented as the paper's new ergodic convergence result for the dPPA, but its proof depends on three facts imported from the same authors' companion preprint [23]: the M-firm nonexpansiveness of ˆT, the nonexpansiveness of the shadow operator ~Fρ, and the fixed-point equivalence Fix(~Fρ) = C∗T^{-1}(0). These facts are used to obtain boundedness of { ¯wk }, to apply Baillon's theorem, and to identify the limit. The paper does not derive them. Thus the dPPA ergodic theorem, and therefore the transfer to pADMM/PR, inherits its validity from a self-citation chain rather than from first-principles arguments in this manuscript.

full rationale

The paper is not circular in the definitional or fitted-prediction sense: Theorem 1 proves a genuine ergodic convergence theorem for the dPPA, the example in Appendix A is a concrete calculation, and the numerical experiments are evaluated on an external LP benchmark. The central reduction, however, is Corollary 1 = Theorem 1 + Proposition 2, where Proposition 2 is imported verbatim from the authors' own companion preprint [23], and Theorem 1's proof itself imports M-firm nonexpansiveness and shadow-operator facts from [23]. This is disclosed self-citation, but it is load-bearing: no independent proof or external verification of Proposition 2 or of the [23] operator properties is offered here. That justifies a moderate score of 4 rather than 0. There is also a nontrivial proof gap in Theorem 1's Opial-type argument for the degenerate M-seminorm, but that is a correctness concern, not a circularity issue.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

Total ledger: two explicit problem assumptions, one imported equivalence from an overlapping-author preprint, and standard ergodic theorems. This is a modest axiom burden for a convergence proof; the main risk is the untested imported equivalence rather than fitted parameters or invented entities.

assumptions (5)
  • domain assumption Assumption 1: KKT system (13) has a nonempty solution set.
    Needed to relate COP (1) to the zero set of the maximal monotone operator T in (14); standard constraint qualifications would imply it, but it is not automatic.
  • domain assumption Assumption 2: Sigma_f1 + B1^*B1 + T1 and Sigma_f2 + B2^*B2 + T2 are positive definite.
    Ensures each pADMM subproblem is well-defined and the dPPA equivalence holds.
  • domain assumption pADMM equivalence with dPPA under M in (15), and M-firm nonexpansiveness of the resolvent, imported from [23, Proposition 2 and Propositions 2.3 and 2.5].
    This is the load-bearing link from the COP algorithm to the dPPA theorem; it is cited from a companion preprint with overlapping authorship and not proved in this paper.
  • standard math Baillon's nonlinear ergodic theorem for nonexpansive operators.
    Used in Theorem 1 to show that the shadow average u_k^a converges; standard background result.
  • domain assumption L-Lipschitz continuity of (M+T)^-1.
    Imported from [23] under Assumption 2; used to establish boundedness of {wbar_k}.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Peaceman-Rachford Splitting Method Converges Ergodically for Solving Convex Optimization Problems." pith.science (2026). https://pith.science/paper/IAD732Z6

@misc{pith2026250107807,
  author       = {Pith},
  title        = {Pith review of: Peaceman-Rachford Splitting Method Converges Ergodically for Solving Convex Optimization Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IAD732Z6}},
  note         = {Machine review of arXiv:2501.07807}
}
read the original abstract

In this paper, we prove that the ergodic sequence generated by the Peaceman-Rachford (PR) splitting method with semi-proximal terms converges for convex optimization problems (COPs). Numerical experiments on the linear programming benchmark dataset further demonstrate that, with a restart strategy, the ergodic sequence of the PR splitting method with semi-proximal terms consistently outperforms both the point-wise and ergodic sequences of the Douglas-Rachford (DR) splitting method. These findings indicate that the restarted ergodic PR splitting method is a more effective choice for tackling large-scale COPs compared to its DR counterparts.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 26 canonical work pages

  1. [23]

    arXiv preprint arXiv:24 03.18618 (2024)

    Sun, D., Yuan, Y., Zhang, G., Zhao, X.: Accelerating prec onditioned ADMM via de- generate proximal point mappings. arXiv preprint arXiv:24 03.18618 (2024)

    work page 2024

  2. [1]

    Adona, V.A., Gon¸ calves, M.L., Melo, J.G.: Iteration-complexity analysis of a generalized alternating direction method of multipliers. J. Global Opt im. 73, 331–348 (2019) Ergodical Peaceman-Rachford Splitting Method 13

    work page 2019

  3. [2]

    In: Ad- vances in Neural Information Processing System, vol

    Applegate, D., D ´ ıaz, M., Hinder, O., Lu, H., Lubin, M., O’ Donoghue, B., Schudy, W.: Practical large-scale linear programming using primal-du al hybrid gradient. In: Ad- vances in Neural Information Processing System, vol. 34, pp . 20243–20257 (2021)

    work page 2021

  4. [3]

    Baillon, J.B.: Un th´ eor` eme de type ergodique pour les co ntractions non lin´ eaires dans un espace de hilbert. CR Acad. Sci. Paris S´ er. AB 280, 1511–1514 (1975)

    work page 1975

  5. [4]

    Bredies, K., Chenchene, E., Lorenz, D.A., Naldi, E.: Dege nerate preconditioned proximal point algorithms. SIAM J. Optim. 32(3), 2376–2401 (2022)

    work page 2022

  6. [5]

    Set-Valued Ana l

    Burachik, R.S., Iusem, A.N., Svaiter, B.F.: Enlargement of monotone operators with applications to variational inequalities. Set-Valued Ana l. 5, 159–180 (1997)

    work page 1997

  7. [6]

    Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal–dual algorithm. Math. Program. 159(1), 253–287 (2016)

    work page 2016

  8. [7]

    arXiv preprint a rXiv:2408.12179 (2024)

    Chen, K., Sun, D., Yuan, Y., Zhang, G., Zhao, X.: HPR-LP: An implementation of an HPR method for solving linear programming. arXiv preprint a rXiv:2408.12179 (2024)

    arXiv 2024

Show all 28 references
  1. [8]

    Cui, Y., Li, X., Sun, D., Toh, K.C.: On the convergence prop erties of a majorized alternating direction method of multipliers for linearly c onstrained convex optimization problems with coupled objective functions. J. Optim. Theor y Appl. 169(3), 1013–1041 (2016)

    2016

  2. [9]

    In: Splitting Methods in Communication, Imaging, Science, and Engineeri ng, pp

    Davis, D., Yin, W.: Convergence rate analysis of several s plitting schemes. In: Splitting Methods in Communication, Imaging, Science, and Engineeri ng, pp. 115–163. Springer (2016)

    2016

  3. [10]

    Nonlinear Anal

    Dong, Y., Fischer, A.: A family of operator splitting met hods revisited. Nonlinear Anal. 72(11), 4307–4315 (2010)

    2010

  4. [11]

    Eckstein, J., Bertsekas, D.P.: On the Douglas—Rachford splitting method and the prox- imal point algorithm for maximal monotone operators. Math. Program. 55(1), 293–318 (1992)

    1992

  5. [12]

    Fazel, M., Pong, T.K., Sun, D., Tseng, P.: Hankel matrix r ank minimization with ap- plications to system identification and realization. SIAM J . Matrix Anal. Appl. 34(3), 946–977 (2013)

    2013

  6. [13]

    Gabay, D.: Applications of the method of multipliers to v ariational inequalities. In: M. Fortin, R. Glowinski (eds.) Augmented Lagrangian Method s: Applications to the Numerical Solution of Boundary-Value Problems, Studies in Mathematics and Its Ap- plications, vol. 15, pp. 2...

  7. [14]

    IEEE Trans

    Giselsson, P., Boyd, S.: Linear convergence and metric s election for Douglas-Rachford splitting and ADMM. IEEE Trans. Automat. Control 62(2), 532–544 (2016)

    2016

  8. [15]

    Lions, P.L., Mercier, B.: Splitting algorithms for the s um of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1979)

    1979

  9. [16]

    Monteiro, R.D., Sim, C.K.: Complexity of the relaxed Pea ceman–Rachford splitting method for the sum of two maximal strongly monotone operator s. Comput. Optim. Appl. 70, 763–790 (2018)

    2018

  10. [17]

    Monteiro, R.D., Svaiter, B.F.: Iteration-complexity o f block-decomposition algorithms and the alternating direction method of multipliers. SIAM J . Optim. 23(1), 475–507 (2013)

    2013

  11. [18]

    Opial, Z.: W eak convergence of the sequence of successiv e approximations for nonex- pansive mappings (1967)

    1967

  12. [19]

    Rockafellar, R.T.: Convex Analysis, vol. 18. Princeton University Press (1970)

    1970

  13. [20]

    Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5), 877–898 (1976)

    1976

  14. [21]

    arXiv preprint arXiv:1 611.03167 (2016)

    Shen, L., Pan, S.: W eighted iteration complexity of the s PADMM on the KKT residuals for convex composite optimization. arXiv preprint arXiv:1 611.03167 (2016)

    2016

  15. [22]

    Sim, C.K.: Convergence rates for the relaxed Peaceman-R achford splitting method on a monotone inclusion problem. J. Optim. Theory Appl. 196(1), 298–323 (2023)

    2023

  16. [24]

    Xiao, Y., Chen, L., Li, D.: A generalized alternating dir ection method of multipliers with semi-proximal terms for convex composite conic progra mming. Math. Program. Comput. 10, 533–555 (2018) 14 Kaihuang Chen et al. A An analytical example of the ergodic convergence of the ...

    2018

  17. [25]

    ADMM T1 = 0, T2 = 0 1 1 O(1/k ) - Oε (1/k )1

  18. [26]

    GADMM T1 = 0, T2 = 0 (0 , 2] 1 O(1/k ) O(1/k ) -

  19. [27]

    (Majorized) sPADMM T1 ≽ 0, T2 ≽ 0 1 (0 , 1+ √ 5 2 ) O(1/k ) O(1/k ) -

  20. [28]

    sPADMM T1 ≽ 0, T2 ≽ 0 1 (0 , 1+ √ 5 2 ) O(1/k ) - Oε (1/k ) Ours pADMM T1 ≽ 0, T2 ≽ 0 (0 , 2] 1 O(1/k ) O(1/k ) Oε (1/k ) Ergodical Peaceman-Rachford Splitting Method 19 When T1 = 0 and T2 = 0, pADMM with ρ = 2 reduces to the PR splitting method, which corresponds to the GADMM...

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.