On the ergodic convergence properties of the Peaceman-Rachford method and their applications in solving linear programming

Authors: Guojun Zhang, Kaihuang Chen, Yancheng Yuan, Xinyuan Zhao, Defeng Sun
Primary area: optimization
Keywords: Peaceman-Rachford method, ergodic convergence properties, linear programming, compleixty, parallel computing

Abstract:
In this paper, we study the ergodic convergence properties of the Peaceman-Rachford (PR) method with semi-proximal terms for solving convex optimization problems (COPs). By reformulating the PR method as a degenerate proximal point method, for the first time we establish the global convergence of the ergodic sequence generated by the PR method with broadly chosen semi-proximal terms under the assumption that there exists a  Karush–Kuhn–Tucker (KKT) solution to the COPs. This result represents a significant departure from previous studies on the non-ergodic convergence of the PR method, which typically requires strong convexity (or strong monotonicity in the reformulated operator) conditions that are hardly satisfied for COPs. Moreover, we establish an ergodic iteration complexity of $O(1/k)$ of the PR method with semi-proximal terms, measured by the objective error, the feasibility violation, and the KKT  residual using the $\varepsilon$-subdifferential. Based on these convergence properties, we introduce the solver EPR-LP, using the ergodic sequence of the PR method with semi-proximal terms for solving linear programming (LP) problems. EPR-LP incorporates an adaptive restart strategy and dynamic penalty parameter updates for efficiency and robustness. Extensive numerical experiments on LP benchmark datasets, executed on a high-performance GPU, show that our Julia-based solver outperforms the award-winning solver PDLP at a tolerance level of $10^{-8}$.

Decision: reject
Reviewer scores: 5, 3, 6, 5

Reviews and discussion:
<thread>
creation date:
1730576039891

thread_type:
official_review

<thread_object>
creator: reviewer_vxig

<content>
summary:
In this paper, the authors proved the ergodic convergence of the PR method with semi-proximal terms for solving convex optimization problems. We established the ergodic iteration complexity of $\mathcal{O}(1/k)$. Building on these results, the authors developed the solver EPR-LP for solving large-scale LP problems, which incorporates adaptive restart and penalty parameter updates. The authors also conduct numerical experiments and showed empirical results that are consistent with the theoretical analysis.

strengths:
In this submission, the authors established the ergodic convergence of the dPPM and proved the ergodic convergence of the pADMM through reformulating the pADMM as adPPM. They also proposed the solver EPR-LP, an implementation of the PR method that utilizes the ergodic sequence to solve LPs, incorporating an adaptive restart strategy and dynamic penalty parameter updates. The authors provided all the detailed mathematical proof and analysis as well as extensive numerical experiments on LP benchmark datasets. The structure of this submission is clear with high quality presentations.

weaknesses:
The only weakness of this paper is that the authors should present and proof the convergence analysis for the proposed algorithm 3: EPR-LP: A Peaceman-Rachford method using ergodic sequence. Although the authors presented the details for the restart strategy and the update rule for the $\sigma$, the authors should present the convergence results of the proposed method similar to Theorem 2.1 and Theorem 2.2. If the authors could supplement the theoretical analysis for the proposed algorithm, this submission deserves the acceptance of the publishment.

questions:
Could the authors provide some convergence theorems or results for the proposed algorithm 3?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730649709174

thread_type:
official_review

<thread_object>
creator: reviewer_7tp9

<content>
summary:
This paper studies the convergence and iteration complexity of the ergodic sequence generated by a fairly general preconditioned semi-proximal ADMM method. As a result, the authors establish the convergence rate of the ergodic sequence generated by the PR method. Motivated by recent developments in first-order algorithms for solving large-scale LPs, they instantiate the algorithm to solve the LP problem and conduct experiments to compare the proposed method with a state-of-the-art method, PDLP.

strengths:
When the quality of intermediate solutions suffices and the dimensionality of the data is large, parallelizable first-order methods are preferred over conventional IPMs and the simplex method. Recently, there has been a surge of investigation into designing highly efficient first-order methods for solving LPs. This work fits well within this line of research and establishes convergence behavior and rates for settings that were previously unknown.

weaknesses:
Overall, I believe the contribution is publishable, and the motivation is plausible. My comments are as follows.

* The proposed EPR-LP uses restart and dynamic penalty tuning. Are these heuristics covered in the convergence analysis?

* In Line 1 of Algorithm 1, compared with Algorithm 2, the variable $z^0$ may not be in the effective domain of the augmented Lagrangian. Could this cause issues for the algorithm, especially when rho is close to one?

* In the paragraph starting on Line 066, the authors mention that without the preconditioner and with $\rho=2$, Algorithm 1 is equivalent to GADMM induced by the PR method. Is this GADMM related to the GADMM of Davis-Yin in Table 2? If so, and if I understand correctly, as shown by the fourth line in Table 2, the ergodic convergence rate for the rho=2 case has already been established in Davis-Yin. I suggest the authors elaborate on the subtle differences between the algorithms referenced in Table 2, as it could be confusing to readers which cases are not covered in the literature and are introduced for the first time in this paper.

* Compared with other non-ergodic results in Table 2, why is the non-ergodic analysis in Appendix B only of Big-O type rather than small-o?

* For the figures in Section 4, what is the definition of the horizontal axis? I think it would be helpful to provide more details on the rationale for this choice.

* Regarding the third bullet on Line 454, I don’t think this observation is very meaningful. First, the bounds given in (13) and (14) represent worst-case behavior, which could be far from the actual data distribution in real-world datasets. Second, it appears that methods EPR-LP and EDR-LP use heuristic techniques, such as restart and penalty tuning, to improve numerical performance, which may not be reflected in (13) and (14).


Minor:
* The meaning of the abbreviation EPR-LP should be explained early before frequently used. Indeed, the first appearance of EPR-LP is at the abstract but only formally defined on Line 330 in page 7.

* The notation $A$ is defined as a matrix in Line 043, but could be used as a linear operator in, e.g., Line 075. This is not actually a problem, but making the terminology consistent would be preferable.

* Algorithm 2 appears two pages before its formal definition.

* Line 379: "Since" should be "since"

questions:
See above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730686762123

thread_type:
official_review

<thread_object>
creator: reviewer_2qxn

<content>
summary:
In this paper, the authors consider the ergodic convergence of a preconditioned ADMM (pADMM) for solving linearly constrained convex optimization problems, which includes the Peaceman-Rachford (PR) method as a special case (where the relaxation factor $\rho =2$). Their key approach is to reformulate pADMM as an equivalent degenerate proximal point method (dPPM) and analyze its convergence using the tool of enlargements of monotone operators. Following this approach, they establish an ergodic convergence rate of $O(1/k)$ for pADMM in terms of objective error, feasibility violation, and the KKT residual. They also implemented the PR method with an ergodic sequence, incorporating an adaptive restart strategy and dynamic penalty parameter updates, for solving large-scale linear programming problems. Experimental results demonstrate improved performance over the award-winning cuPDLP solver.

strengths:
- The authors analyze the ergodic convergence rate of the pADMM method with semi-proximal terms over a range of  $\rho \in (0,2]$ for the relaxation parameter. In comparison, prior studies either limit their analysis to the specific case $\rho = 1$ or primarily focus on last-iterate or asymptotic convergence. 
- The authors perform extensive numerical experiments on Mittelmann's LP benchmark set and LP instances derived from MIP relaxations. The results suggest a substantial improvement over cuPDLP.

weaknesses:
- My primary concern is the high similarity between this submission and the work by Chen et al. (2024), which the authors also cited in the introduction. Both papers examine pADMM-type methods with semi-proximal terms and reformulate them as a degenerate PPM method to analyze convergence. The main difference appears to be that the current submission omits the additional Halpern iteration used in Chen et al. (2024), which intuitively would simplify the analysis rather than add novel insights. Furthermore, I recommend including HPR-LP in the numerical experiments as a baseline for comparison. As it stands, the unique contribution of this paper remains unclear. 
- The paper also lacks a discussion of relevant studies on the convergence of the PR method. For example, Monteiro and Sim (2018) established similar ergodic convergence rates of $O(1/k)$ for the PR method using $\epsilon$-enlargements of monotone operators. A detailed discussion of how the current result differs from prior work, such as that of Monteiro and Sim, is necessary.


----

Kaihuang Chen, Defeng Sun, Yancheng Yuan, Guojun Zhang, and Xinyuan Zhao. "HPR- LP: An implementation of an HPR method for solving linear programming." arXiv preprint arXiv:2408.12179, 2024.

Renato DC Monteiro and Chee-Khian Sim. "Complexity of the relaxed Peaceman–Rachford splitting method for the sum of two maximal strongly monotone operators." Computational Optimization and Applications 70 (2018): 763-790.

questions:
- In the introduction, the authors mention that "the modified PDHG is a special case of Algorithm 1 with $\rho=1$." However, in Remark 3.1, they state that setting $\rho=1$ results in the DR method with semi-proximal terms. Could the authors clarify the difference between the DR method and the modified PDHG method in this context?
- In Assumption 2.2, it seems that the coefficient $\sigma$ is missing before $B_1^*B_1$ and $B_2^*B_2$. 
- In Proposition 2.1, the authors state that $\mathcal{M}$ is an admissible preconditioner such that $(\mathcal{M}+\mathcal{T})^{-1}$ is Lipschitz continuous. However, later in Line 260, these properties are presented as an assumption. Could the authors clarify this discrepancy?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730690809767

thread_type:
official_review

<thread_object>
creator: reviewer_cbuu

<content>
summary:
This paper studies ergodic version of PR method for solving LP based on the algorithm and its non-ergodic version of analysis in Chen et al., 2024 and Sun et al. 2024. Numerical results show the good performance over LP benchmarks.

strengths:
The results appear to be sound and the paper is clearly written.

weaknesses:
The overall results are somewhat expected, given the classical distinction between ergodic and non-ergodic convergence. The algorithm design and key techniques, such as the restart strategy and dynamic penalty parameter updates, were previously developed in Chen et al. (2024) and Sun et al. (2024). Additionally, the proof for the ergodic version builds on the degenerate PPM framework from Bredies et al. (2022). From a technical standpoint, achieving non-ergodic convergence is generally more challenging than ergodic convergence. The paper would be more compelling if it explored additional structural properties of LPs when using the ergodic average. Nevertheless, the numerical experiments already show some advantages when applying this approach in a straightforward manner.

questions:
Although Figure 1 includes comparisons, should the non-ergodic version of the algorithm also be incorporated into Figures 2 and 3? In general comparison between ergodic and non-ergodic convergence, taking averages can compromise some desirable properties. For this specific LP task, it would be valuable to see how the computational performance for the ergodic sequence compares, providing a clearer picture of its practical implications and insights.
</content>
</thread_object>

</thread>


Metareview: