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

Kaihuang Chen, Defeng Sun, Yancheng Yuan, Guojun Zhang, Xinyuan ZhaoarXiv 2025 · DOI · arXiv

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.

Introduction

In the domain of large-scale optimization, splitting methods are indispensable tools for decomposing complex problems into manageable sub-problems. Among the most prominent are the Douglas-Rachford (DR) and Peaceman-Rachford (PR) methods. While the PR method is often faster in practice, it has historically been viewed as "unstable" because it does not always converge to a single point for general convex optimization problems (COPs), often oscillating indefinitely.

This research addresses a long-standing theoretical gap: even if the point-wise steps of the PR method diverge, does their average—the ergodic sequence—eventually converge to the optimal solution? We provide the mathematical proof that it does, establishing a new foundation for using PR-based methods in robust optimization frameworks.

Methodology and Theoretical Framework

Our analysis reformulates the preconditioned Alternating Direction Method of Multipliers (pADMM) as a degenerate proximal point algorithm (dPPA). This framework allows for several key technical advancements:

  • Semi-proximal Terms: We incorporate "slack" terms into the sub-problems, enhancing numerical stability and making them easier to solve for high-dimensional datasets.
  • $\\epsilon$-enlargement Analysis: To prove convergence, we utilize the concept of $\\epsilon$-enlargements of maximal monotone operators. This approach demonstrates that the averaged sequence effectively "squeezes" toward the optimal solution over time.
  • Iteration Complexity: We establish a theoretical iteration complexity of $O(1/k)$, proving that the error decreases at a rate inversely proportional to the number of iterations.

The Restart Strategy

While ergodic sequences are theoretically guaranteed to converge, they can suffer from slow practical performance because the average retains the influence of poor initial guesses. To mitigate this, we implement a "restart" strategy. By periodically resetting the average once the algorithm reaches a certain proximity to the goal, we discard stale data and accelerate the path to the optimum. This creates the Restarted Ergodic Peaceman-Rachford (rEPR) variant.

Experimental Results

We evaluated the proposed method using 49 diverse instances from Mittelmann’s Linear Programming (LP) benchmark set, executed on NVIDIA A100 GPUs. The results highlight the significant advantages of the rEPR method:

  • Efficiency: The rEPR method was the fastest solver for 50% of the benchmark problems.
  • Speedup: It solved 60% of the instances in approximately half the time required by the restarted Douglas-Rachford (rEDR) version.
  • Robustness: Within a 3,600-second time limit, rEPR successfully solved 20% more problems than the standard point-wise DR method.
  • Convergence Stability: In cases where standard PR failed due to oscillation (e.g., the "ex10" instance), the ergodic version maintained smooth convergence.

Conclusion and Future Work

This study transforms the PR method from a high-risk, high-reward heuristic into a mathematically guaranteed tool for convex optimization. By proving ergodic convergence and demonstrating the power of the restart strategy, we provide a superior alternative to the standard DR method for large-scale linear programming.

Future research will focus on characterizing the theoretical mechanisms that allow the restart strategy to enhance the PR method more effectively than the DR method. Additionally, we aim to extend these experiments to non-linear convex problems and conic programming to further validate the method's versatility.

Summary updated

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.
BibTeX
@misc{chen2025peaceman,
  author = {Kaihuang Chen and Defeng Sun and Yancheng Yuan and Guojun Zhang and Xinyuan Zhao},
  title = {{Peaceman-Rachford Splitting Method Converges Ergodically for Solving Convex Optimization Problems}},
  year = {2025},
  eprint = {2501.07807},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.07807},
  howpublished = {arXiv},
}
Figure