Pith. sign in

REVIEW 3 major objections 5 minor 55 references

A Triple-Bregman Balanced Primal-Dual Algorithm for Saddle Point Problems

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A new primal-dual algorithm for convex-concave saddle point problems splits the dual update into two Bregman subproblems, allowing larger step sizes than PDHG while retaining an O(1/N) ergodic convergence rate.

desk verdict A genuinely useful algorithmic template with a clean ergodic rate, but the global convergence proof relies on an unproven inequality and contains a real gap that needs repair. read the letter →

arxiv 2506.07117 v1 pith:E3XVL4EO submitted 2025-06-08 math.OC

Jintao Yu , Hongjin He This is my paper
classification math.OC MSC 65K0565K1090C25
keywords primal-dualalgorithmsaddlepointproblemBregmandistanceproximityoperatorconvex-concaveoptimizationPDHGlargerstepsizesergodicconvergencerate
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 proposes an algorithm for convex-concave saddle point problems with a bilinear coupling term, aimed at situations where the dual subproblem is much cheaper than the primal one. Instead of the standard PDHG pattern of one primal update followed by one dual update, TBDA performs a preliminary dual step, then a primal step, then a second dual step, with a separate Bregman proximal term in each subproblem. The authors claim that this rebalancing preserves global convergence and the standard $O(1/N)$ ergodic convergence rate while allowing strictly larger step sizes: under Euclidean kernels with $\tau = \theta\gamma$ and $\theta\ge 1$, convergence is guaranteed when $\mu\gamma > \frac{2}{3}\|A^\top A\|$, weaker than PDHG's $\mu\gamma > \|A^\top A\|$. Two strengthened versions are shown to give a better $O(1/N)$ rate when $f$ is relatively strongly convex, and an $O(1/\omega^N)$ linear rate when both $f$ and $g$ are relatively strongly convex. Numerical experiments on quadratic programs and robust PCA support the claim that the extra dual pass pays off in practice.

What carries the argument

The central object is Algorithm 1 (TBDA), whose updates are $\tilde y^{k+1}=\arg\min_y\{g(y)-\langle Ax^k,y\rangle+\gamma B_\phi(y,y^k)\}$, $x^{k+1}=\arg\min_x\{f(x)+\langle Ax,\tilde y^{k+1}\rangle+\mu B_\psi(x,x^k)\}$, followed by the extrapolation $\bar x^{k+1}=x^{k+1}+\sigma(x^{k+1}-x^k)$ and a second dual update $y^{k+1}=\arg\min_y\{g(y)-\langle A\bar x^{k+1},y\rangle+\tau B_\varphi(y,y^k)\}$. Each update uses its own Bregman distance $B_h(x,y)=h(x)-h(y)-\langle\nabla h(y),x-y\rangle$, which generalizes the Euclidean proximal term and lets the user move computational effort between the primal and dual sides. The load-bearing part of the proof is the descent inequality of Lemma 3.1, which expresses the decrease of the weighted sum of Bregman distances to a saddle point in terms of three successive Bregman terms and the cross term $\langle A(x^{k+1}-x^k), y^{k+1}-\tilde y^{k+1}\rangle$. Theorem 3.2 turns this into global convergence whenever the sufficient condition (3.29) holds with positive constants $c_1,c_2,c_3$, and Theorem 3.4 sums the same inequality and applies Jensen's inequality to obtain the ergodic $O(1/N)$ rate. The larger-step conclusion is obtained in Remark 3.3 by verifying (3.29) for Euclidean kernels through Cauchy-Schwarz and Young's inequalities, which yields the explicit conditions in (3.42).

What would settle it

Take a non-Euclidean Bregman kernel, for example the Kullback-Leibler Bregman distance on the probability simplex, and choose positive step sizes that satisfy the paper's stated convergence conditions but lie outside the Euclidean-verified region; if inequality (3.29) cannot be certified for that kernel, then the global-convergence theorem has no content for that setting. A concrete check is to run TBDA with step sizes in the claimed enlarged range $\frac{2}{3}\|A^\top A\| < \mu\gamma < \|A^\top A\|$ on a small saddle point problem and see whether the iterates actually converge; convergence would support the step-size claim, divergence or oscillation would refute it.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is that a primal-dual algorithm can be rebalanced by computing the dual variable twice, once as a predictor for the primal update and once after an extrapolation step, with independent Bregman kernels for the two dual subproblems and the primal subproblem. This triple-Bregman balanced primal-dual algorithm is globally convergent for convex-concave saddle point problems of the form $\min_x \max_y \{f(x)+\langle Ax,y\rangle - g(y)\}$, and its iterates satisfy the ergodic bound $G(\bar x^N,\bar y^N)=O(1/N)$. In the Euclidean specialization the paper proves a strictly weaker step-size condition, $\mu\gamma > \frac{2}{3}\|A^\top A\|$ when $\tau=\theta\gamma$ and $\theta\ge 1$, compared with the classical PDHG condition $\mu\gamma > \|A^\top A\|$, and it exhibits variants with improved rates under relative strong convexity: an $O(1/N)$ bound with better constants and a linear $O(1/\omega^N)$ bound. The convergence argument rests on a descent inequality, Lemma 3.1, combined with the sufficient condition (3.29) that three positive constants control the Bregman terms and the coupling cross term; Theorem 3.2 turns that inequality into global convergence and Theorem 3.4 into the ergodic rate. The framework is also shown to specialize to several existing methods, including ALM, linearized and balanced ALM, SPIDA, and multi-block splitting schemes.

Load-bearing premise

The load-bearing premise is that one can actually find positive constants $c_1,c_2,c_3$ making inequality (3.29) hold for the chosen Bregman kernels and step sizes; the paper verifies this directly only for Euclidean kernels (Remark 3.3), so for a general Bregman kernel the global-convergence theorem is conditional on an unverified inequality.

Editorial extensions

If this is right

  • For problems whose dual subproblem is much cheaper than the primal one, the extra dual solve is nearly free, so TBDA can be faster in wall-clock time than PDHG while keeping the same $O(1/N)$ worst-case guarantee.
  • Under Euclidean kernels with $\tau=\theta\gamma$ and $\theta\ge 1$, TBDA converges under the weaker step-size condition $\mu\gamma > \frac{2}{3}\|A^\top A\|$, so users may take larger steps than PDHG's $\mu\gamma > \|A^\top A\|$.
  • The three independent Bregman kernels give users freedom to match each subproblem to the geometry of $X$ and $Y$; the framework reproduces ALM, linearized ALM, balanced ALM, SPIDA, and multi-block splitting methods as special cases.
  • When $f$ is strongly convex relative to $\psi$, Algorithm 2 keeps $O(1/N)$ with a tighter bound, and when both $f$ and $g$ are relatively strongly convex, Algorithm 3 achieves a linear $O(1/\omega^N)$ rate.

Reading between the lines

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

  • Inference: the two-dual-pass construction suggests a general 'rebalance the cheap side' template: any primal-dual method whose dual update is a cheap projection can spend an extra dual solve as a predictor, so the same idea could be transplanted to stochastic or online variants of PDHG.
  • Inference: the coefficient $2/3$ in the Euclidean step-size bound is suggestive: the extremal case $\theta\ge 2$ in (3.41) is exactly where the constant becomes $2/3$, so it would be natural to test whether a golden-ratio choice of the extrapolation parameter $\sigma$ produces the same or a sharper bound.
  • Inference: because inequality (3.29) is verified only for Euclidean kernels, a direct extension of the paper would be to certify it for entropy-type Bregman kernels; if it holds, TBDA would apply cleanly to problems such as optimal transport where the subproblems then have closed-form updates.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper proposes TBDA, a primal-dual algorithm for convex-concave saddle point problems with a bilinear coupling term. The method performs two dual Bregman proximal updates and one primal Bregman proximal update, with an extrapolation step, in order to balance primal and dual subproblem costs. The authors derive a basic descent inequality (Lemma 3.1), claim global convergence (Theorem 3.2) and an ergodic O(1/N) rate (Theorem 3.4), give a Euclidean-kernel step-size verification (Remark 3.3), and propose two accelerated variants under relative strong convexity (Algorithms 2 and 3). Numerical experiments on quadratic optimization and RPCA compare the method with PDHG and SPIDA.

Significance. If the theoretical claims were fully established, the paper would be a useful contribution. The algorithmic framework is flexible and several existing schemes, including ALM, linearized ALM, balanced ALM, and SPIDA, are recovered as special cases. The ergodic-rate argument in Theorem 3.4 is clean and does not depend on the additional descent inequality (3.29); that part of the paper is a genuine strength. The Euclidean verification in Remark 3.3 is also a useful concrete check. However, the global-convergence proof in Theorem 3.2 currently contains an invalid limit argument, and the step-size comparison with PDHG is overstated as written. These issues are repairable but currently block the advertised central claim.

major comments (3)
  1. [Theorem 3.2, proof paragraph after (3.32)] The inference "Using the boundedness and monotonically decreasing property of the sequence {a_k} implies lim_{k→∞} a_k = lim_{j→∞} a_{k_j}=0" is invalid. Monotonicity and boundedness only give convergence of a_k to some nonnegative limit; the fact that a cluster point is a saddle point does not force the Bregman distance to the initially fixed reference saddle point (x̂, ŷ) to tend to zero. A concrete witness is A=0, f=g=0, X=Y=[0,1], Euclidean kernels, and x0≠x̂: every point is a saddle point, inequality (3.29) holds with zero left- and right-hand sides, the algorithm is constant, and a_k = μBψ(x̂,x0)>0. Therefore the proof does not establish whole-sequence convergence. A repair would need to re-apply the descent inequality at a cluster point and invoke additional coercivity and continuity properties of the Bregman kernels, which are not stated.
  2. [Assumption (3.29), Theorems 3.2, 4.1, 4.3] The global-convergence result is conditional on the existence of positive constants c1,c2,c3 satisfying (3.29), but this inequality is not derived from primitive conditions for general Bregman kernels. Remark 3.3 verifies (3.29) only in the Euclidean case. The same type of unproven sufficient condition is assumed in Theorem 4.1 and Theorem 4.3. The phrase "under some mild conditions" therefore overstates the support for the general Bregman setting. The paper should state (3.29) as a standing hypothesis with guidance on how to check it, or provide verifiable sufficient conditions on the kernels and step sizes from which (3.29) follows.
  3. [Remark 3.3, Eq. (3.42)] The claimed comparison with PDHG is not correct as stated. For the Euclidean case with τ=θγ and σ≥0, the condition for 1≤θ<2 is μγ > 2(1+σ)^2/((θ+1)(1+2σ)) ‖A^T A‖. At θ=1 and σ=1 this is μγ > 4/3 ‖A^T A‖, which is stricter than the PDHG condition μγ>‖A^T A‖ in (1.5), not larger. The displayed bound "> 2/3 ‖A^T A‖" only gives a lower bound and does not imply a comparison with the coefficient 1 appearing in PDHG. The statement that TBDA allows larger step sizes than PDHG when θ≥1 must be restricted to parameter regimes where the coefficient is actually below 1, and the comparison should account for the extrapolation parameter used in each method.
minor comments (5)
  1. [Introduction, page 3] The phrase "globally convergence" should be "globally convergent".
  2. [Proof of Theorem 3.4] "Jesen inequality" should be "Jensen inequality".
  3. [Remark 3.3, final sentence] "easily seen form (3.42)" should be "easily seen from (3.42)".
  4. [Remark 4.2] The displayed identity "t_N = Σ_{k=1}^N 1/β_{k+1}" is inconsistent with the definition t_N = Σ_{k=1}^N 1/β_{k-1} in Theorem 4.1; the index should be corrected.
  5. [Algorithm 1 and convergence analysis] Algorithm 1 labels the output "approximate saddle point (x̂, ŷ)", which collides with the fixed saddle point (x̂, ŷ) used throughout the convergence analysis; a different notation for the output would avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the proof-gap in Theorem 3.2 is a correctness issue, not a circular reduction.

full rationale

The paper's central claims are not circular. Theorem 3.4's ergodic O(1/N) bound is obtained by summing the Bregman three-point inequality (Lemma 3.1) and applying Jensen's inequality; it depends only on initial Bregman distances and the primal-dual gap, with no fitted parameters or assumed inequality. Theorem 3.2 is explicitly conditional on the descent condition (3.29), which the paper states as an assumption and verifies for Euclidean kernels in Remark 3.3; this is a conditional theorem rather than a definitional equivalence. The proof of Theorem 3.2 does contain a genuine gap: from monotone boundedness of a_k and the fact that a cluster point is a saddle point, the paper asserts lim a_k = 0, which does not follow when the cluster point differs from the reference saddle point (x̂,ŷ). This is a correctness flaw, not a circularity, because the conclusion is not an input to the proof by construction. Self-citations to [32] and [33] are used for algorithmic inspiration and for recovering existing ALM/SPIDA schemes, but they are not load-bearing in the new convergence analysis, and no fitted quantity is later renamed as a prediction. No pattern of self-definition, fitted input called prediction, imported uniqueness, or renamed known result appears.

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

The ledger is light on fitted numbers. The main load-bearing assumption is (3.29), an abstract sufficient condition that is assumed rather than derived for general kernels. The algorithm parameters are hand-chosen but not fitted to the theoretical claims. No new physical or conceptual entities are introduced.

free parameters (5)
  • proximal parameters γ, µ, τ = e.g., (γ,µ)=(∥A∥,∥A∥) for PDHG; TBDA settings in Table 1 follow (3.42)
    Chosen by hand; convergence conditions and numerical performance depend on them.
  • extrapolation parameter σ = σ=1 in most experiments; σ∈{1,2,3} in real-data tests
    User-chosen; part of step-size condition (3.42).
  • ratio θ = τ/γ = θ ∈ {2/3, 1, 2} in quadratic experiments
    Introduced to parameterize and analyze step-size enlargement in Remark 3.3.
  • parameter p in Algorithm 2 = p=1.5
    Controls the β_k update in Eq. (4.2).
  • ω in Algorithm 3 = ω>1, no concrete value given
    Defines the O(1/ω^N) rate in Theorem 4.3.
assumptions (5)
  • domain assumption Existence of a saddle point (x̂, ŷ) for problem (1.1)
    Used throughout Section 3; the paper assumes the saddle point set is nonempty.
  • ad hoc to paper Inequality (3.29): existence of c1,c2,c3 such that the descent bracket dominates the Bregman terms
    Assumed for Theorem 3.2; only verified for Euclidean kernels in Remark 3.3.
  • domain assumption f and g proper closed convex, X and Y nonempty closed convex, A bounded linear
    Problem setting (1.1).
  • standard math Bregman kernels strictly convex and differentiable on relevant domains
    Required for the Bregman distance definitions and three-point identities in Section 2.
  • domain assumption Strong convexity relative to Bregman kernels for Algorithms 2 and 3
    Assumed in Section 4 to obtain accelerated rates.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Triple-Bregman Balanced Primal-Dual Algorithm for Saddle Point Problems." pith.science (2026). https://pith.science/paper/E3XVL4EO

@misc{pith2026250607117,
  author       = {Pith},
  title        = {Pith review of: A Triple-Bregman Balanced Primal-Dual Algorithm for Saddle Point Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E3XVL4EO}},
  note         = {Machine review of arXiv:2506.07117}
}
read the original abstract

The primal-dual hybrid gradient (PDHG) method is one of the most popular algorithms for solving saddle point problems. However, when applying the PDHG method and its many variants to some real-world models commonly encountered in signal processing, imaging sciences, and statistical learning, there often exists an imbalance between the two subproblems, with the dual subproblem typically being easier to solve than the primal one. In this paper, we propose a flexible triple-Bregman balanced primal-dual algorithm (TBDA) to solve a class of (not necessarily smooth) convex-concave saddle point problems with a bilinear coupling term. Specifically, our TBDA mainly consists of two dual subproblems and one primal subproblem. Moreover, three Bregman proximal terms, each one with an individual Bregman kernel function, are embedded into the respective subproblems. In this way, it effectively enables us to strike a practical balance between the primal and dual subproblems. More interestingly, it provides us a flexible algorithmic framework to understand some existing iterative schemes and to produce customized structure-exploiting algorithms for applications. Theoretically, we first establish the global convergence and ergodic convergence rate of the TBDA under some mild conditions. In particular, our TBDA allows larger step sizes than the PDHG method under appropriate parameter settings. Then, when the requirements on objective functions are further strengthened, we accordingly introduce two improved versions with better convergence rates than the original TBDA. Some numerical experiments on synthetic and real datasets demonstrate that our TBDA performs better than the PDHG method and some other efficient variants in practice.

Figures

Figures reproduced from arXiv: 2506.07117 by the authors.

Figure 1
Figure 1. Illustration of the convergence behaviors of PDHG, SPIDA and TBDA with different proximal parameters for solving (3.5). 3.2. Understanding some first-order methods by TBDA. In this subsection, by choosing the Bregman kernel functions and the extrapolation parameter, we demonstrate the versatility of TBDA to produce many variants. Particularly, we focus on applying TBDA to the linearly constrained convex optimization… view at source ↗
Figure 2
Figure 2. Numerical comparison between the PDHG and our al￾gorithm for (5.1), where the bars represent the average results of 10 random trials and the line segments represent the standard de￾viation showing the stability of the algorithms. We can see from [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗
Figure 3
Figure 3. Results of the PDHG and TBDA for (5.2) with applica￾tion to real videos. From top to bottom: hall, highway, hall airport and lobby. The first column corresponds to one of the frames of each video. The second and third columns are the results obtained by the PDHG. The last two columns are the results obtained by our TBDA. developed two improved versions of TBDA. Computational results showed that TBDA outperforms the … view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

55 extracted references · 55 canonical work pages

  1. [1]

    Arrow, L

    K.J. Arrow, L. Hurwicz, and H. Uzawa, With contributions by H.B. Chenery, S.M. Johnson, S. Karlin, T. Marschak, and R.M. Solow. studies in linear and non-linear programming, Stan- ford Mathematical Studies in the Social Science, vol. II, Stanford Unversity Press, Stanford, California, 1958

    work page 1958

  2. [2]

    J. Bai, Y. Chen, X. Yu, and H.C. Zhang, Generalized asymmetric forward-backward-adjoint algorithms for convex-concave saddle-point problem , J. Sci. Comput. 102 (2025), Article No. 80 (33 pages)

    work page 2025

  3. [3]

    Bauschke, P

    H. Bauschke, P. Combettes, and D. Noll, Joint minimization with alternating Bregman prox- imity operators, Pac. J. Optim. 2 (2006), 401–424

    work page 2006

  4. [4]

    Bauschke, J

    H.H. Bauschke, J. Bolte, and M. Teboulle, A descent lemma beyond Lipschitz gradient con- tinuity: first-order methods revisited and applications , Math. Oper. Res. 42 (2017), no. 2, 330–348

    work page 2017

  5. [5]

    Bauschke, J.M

    H.H. Bauschke, J.M. Borwein, and P. Combettes, Bregman monotone optimization algo- rithms, SIAM J. Optim. 42 (2003), 596–636

    work page 2003

  6. [6]

    Beck, First-order methods in optimization , SIAM, Philadelphia, 2017

    A. Beck, First-order methods in optimization , SIAM, Philadelphia, 2017

    work page 2017

  7. [7]

    Bolte, S

    J. Bolte, S. Sabach, M. Teboulle, and Y. Vaisbourd, First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems , SIAM J. Optim. 28 (2018), no. 3, 2131–2151

    work page 2018

  8. [8]

    Bonettini and V

    S. Bonettini and V. Ruggiero, An alternating extragradientmethod for total variation based image restoration from Poisson data , Inverse Probl. 27 (2011), 095001. 28 JINTAO YU AND HONGJIN HE

    work page 2011

Show all 55 references
  1. [9]

    , On the convergence of primal-dual hybrid gradient algorithms for total variation image restoration, J. Math. Imaging Vis. 44 (2012), 236–253

    2012

  2. [10]

    Bonettini and V

    S. Bonettini and V. Ruggiero, An alternating extragradient method with non Euclidean pro- jections for saddle point problems , Comput. Optim. Appl. 59 (2014), 511–540

    2014

  3. [11]

    Br` egman,Relaxation method for finding a common point of convex sets and its ap- plication to optimization problems , Doklady Akademii Nauk, vol

    L.M. Br` egman,Relaxation method for finding a common point of convex sets and its ap- plication to optimization problems , Doklady Akademii Nauk, vol. 171, Russian Academy of Sciences, 1966, pp. 1019–1022

    1966

  4. [12]

    Cai, D.R

    X.J. Cai, D.R. Han, and L.L. Xu, An improved first-order primal-dual algorithm with a new correction step, J. Global Optim. 57 (2013), 1419–1428

    2013

  5. [13]

    Chambolle and J.P

    A. Chambolle and J.P. Contreras, Accelerated bregman primal-dual methods applied to opti- mal transport and wasserstein barycenter problems, SIAM J. Math. Data Sci. 4 (2022), no. 4, 1369–1395

    2022

  6. [14]

    Chambolle and T

    A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging , J. Math. Imaging Vis. 40 (2011), 120–145

    2011

  7. [15]

    25 (2016), 161–319

    , An introduction to continuous optimization for imaging , Acta Numer. 25 (2016), 161–319

    2016

  8. [16]

    Pro- gram

    , On the ergodic convergence rates of a first-order primal-dual algorithm , Math. Pro- gram. Ser. A 159 (2016), 253–287

    2016

  9. [17]

    Chang and J.F

    X.K. Chang and J.F. Yang, A golden ratio primal-dual algorithm for structured convex op- timization, J. Sci. Comput. 87 (2021), no. 2, 47

    2021

  10. [18]

    Chang, J.F

    X.K. Chang, J.F. Yang, and H.C. Zhang, Golden ratio primal-dual algorithm with linesearch , SIAM J. Optim. 32 (2022), 1584–1613

    2022

  11. [19]

    Chen, J.G

    P.J. Chen, J.G. Huang, and X.Q. Zhang, A primal-dual fixed point algorithm for multi-block convex minimization, J. Comput. Math. 34 (2016), 723–738

    2016

  12. [20]

    Condat, D

    L. Condat, D. Kitahara, A. Contreras, and A. Hirabayashi, Proximal splitting algorithms for convex optimization: A tour of recent advances, with new twists , SIAM Rev. 65 (2023), no. 2, 375–435

    2023

  13. [21]

    Esser, X

    E. Esser, X. Zhang, and T. Chan, A general framework for a class of first-order primal- dual algorithms for convex optimization in imaging sciences , SIAM J. Imaging Sci. 3 (2010), 1015–1046

    2010

  14. [22]

    Han, H.J

    D.R. Han, H.J. He, and L.L. Xu, A proximal parallel splitting method for minimizing sum of convex functions, J. Comput. Appl. Math. 256 (2014), 36–51

    2014

  15. [23]

    Han, H.J

    D.R. Han, H.J. He, H. Yang, and X.M. Yuan, A customized Douglas-Rachford splitting algo- rithm for separable convex minimization with linear constraints , Numer. Math. 127 (2014), 167–200

    2014

  16. [24]

    Han, X.M

    D.R. Han, X.M. Yuan, and W.X. Zhang, An augmented-Lagrangian-based parallel splitting method for separable convex minimization with applications to image processing, Math. Com- put. 83 (2014), 2263–2291

    2014

  17. [25]

    B.S. He, L.S. Hou, and X.M. Yuan, On full Jacobian decomposition of the augmented la- grangian method for separable convex programming, SIAM J. Optim. 25 (2015), no. 4, 2274– 2312

    2015

  18. [26]

    B.S. He, F. Ma, S. Xu, and X.M. Yuan, A generalized primal-dual algorithm with improved convergence condition for saddle point problems, SIAM J. Imaging Sci. 15 (2022), 1157–1183

    2022

  19. [27]

    B.S. He, F. Ma, and X.M. Yuan, An algorithmic framework of generalized primal-dual hybrid gradient methods for saddle point problems. , J Math. Imaging Vis. 58 (2017), no. 2, 279–293

    2017

  20. [28]

    B.S. He, H.K. Xu, and X.M. Yuan, On the proximal Jacobian decomposition of ALM for multiple-block separable convex minimization problems and its relationship to ADMM , J. Sci. Comput. 66 (2016), 1204–1217

    2016

  21. [29]

    B.S. He, S.J. Xu, and X.M. Yuan, On convergence of the Arrow-Hurwicz method for saddle point problems, J. Math. Imaging Vis. 64 (2022), 662–671

    2022

  22. [30]

    B.S. He, Y.F. You, and X.M. Yuan, On the convergence of primal dual hybrid gradient algorithm, SIAM J. Imaging Sci. 7 (2015), 2526–2537

    2015

  23. [31]

    He and X.M

    B.S. He and X.M. Yuan, Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective, SIAM J. Imaging Sci. 5 (2012), 119–149

    2012

  24. [32]

    , Balanced augmented lagrangian method for convex programming, arXiv:2108.08554, 2021

    2021 arXiv

  25. [33]

    H. He, K. Wang, and J. Yu, A symmetric primal-dual algorithmic framework for saddle point problems, (2025), arXiv: 2212.07587v2, to appear in J. Comput. Math. A TRIPLE-BREGMAN BALANCED PRIMAL-DUAL ALGORITHM 29

    2025 arXiv

  26. [34]

    Izmailov and M.V

    A.F. Izmailov and M.V. Solodov, Critical Lagrange multipliers: what we currently know about them, how they spoil our lives, and what we can do about it , TOP 23 (2015), 1–26

    2015

  27. [35]

    Jiang, X.J

    F. Jiang, X.J. Cai, Z.M. Wu, and D.R. Han, Approximate first-order primal-dual algorithms for saddle point problems , Math. Comput. 90 (2021), 1227–1262

    2021

  28. [36]

    Jiang, Z.M

    F. Jiang, Z.M. Wu, X.J. Cai, and H.C. Zhang, A first-order inexact primal-dual algorithm for a class of convex-concave saddle point problems , Numer. Algor. 88 (2021), 1109–1136

    2021

  29. [37]

    Jiang, Z.Y

    F. Jiang, Z.Y. Zhang, and H.J. He, Solving saddle point problems: a landscape of primal-dual algorithm with larger stepsizes , J. Global Optim. 85 (2023), 821–846

    2023

  30. [38]

    Komodakis and J

    N. Komodakis and J. C. Pesquet, Playing with duality an overview of recent primal dual ap- proaches for solving large scale optimization problems , IEEE Signal Process Mag. 32 (2015), no. 6, 31–54

    2015

  31. [39]

    Li and M

    Y. Li and M. Yan, On the improved conditions for some primal-dual algorithms , J. Sci. Comput. 99 (2024), Article No. 74 (17 pages)

    2024

  32. [40]

    Li and M

    Z. Li and M. Yan, New convergence analysis of a primal-dual algorithm with large stepsizes , Adv. Comput. Math. 47 (2021), no. 1, 1–20

    2021

  33. [41]

    H.H. Lu, R.M. Freund, and Y. Nesterov, Relatively smooth convex optimization by first-order methods, and applications , SIAM J. Optim. 28 (2018), no. 1, 333–354

    2018

  34. [42]

    Y. Ma, X.J. Cai, B. Jiang, and D. Han, Understanding the convergence of the preconditioned PDHG method: a view of indefinite proximal ADMM , J. Sci. Comput. 94 (2023), Article No. 60 (39 pages)

    2023

  35. [43]

    Malitsky and T

    Y. Malitsky and T. Pock, A first-order primal-dual algorithm with linesearch, SIAM J. Optim. 28 (2018), no. 1, 411–432

    2018

  36. [44]

    M¨ ollenhoff, E

    T. M¨ ollenhoff, E. Strekalovskiy, M. Moeller, and D. Cremers,The primal dual hybrid gradient method for semiconvex splittings , SIAM J. Imaging Sci. 8 (2015), 827–857

    2015

  37. [45]

    Moreau, Fonctions convexe dudual et points proximaux dans un espace hilbertien , C

    J.J. Moreau, Fonctions convexe dudual et points proximaux dans un espace hilbertien , C. R. Acad. Sci. Paris Ser. A Math 255 (1962), 2897–2899

    1962

  38. [46]

    Nedi´ c and A

    A. Nedi´ c and A. Ozdaglar,Subgradient methods for saddle point problems , J. Optim. Theory Appl. 142 (2009), 205–228

    2009

  39. [47]

    Parikh and S

    N. Parikh and S. Boyd, Proximal algorithms, Found. Trends Optim. 1 (2013), 123–231

    2013

  40. [48]

    Rasch and A

    J. Rasch and A. Chambolle, Inexact first-order primal–dual algorithms , Comput. Optim. Appl. 76 (2020), no. 2, 381–430

    2020

  41. [49]

    Razaviyayn, T

    M. Razaviyayn, T. Huang, S. Lu, M. Nouiehed, M. Sanjabi, and M. Hong, Nonconvex min- max optimization: Applications, challenges, and recent theoretical advances , IEEE Signal Process Mag. 37 (2020), no. 5, 55–66

    2020

  42. [50]

    Changho Suh, Convex optimization for machine learning , Now Publishers, Hanover, 2022

    2022

  43. [51]

    T. Valkonen, First-order primal–dual methods for nonsmooth non-convex optimisation , Handbook of Mathematical Models and Algorithms in Computer Vision and Imaging: Math- ematical Imaging and Vision (Cham) (K. Chen, C.-B. Sch¨ onlieb, X.-C. Tai, and L. Younces, eds.), Springer,...

    2021

  44. [52]

    K. Wang, J. Desai, and H.J. He, A note on augmented Lagrangian-based parallel splitting method, Optim. Lett. 9 (2015), 1199–1212

    2015

  45. [53]

    Wang and H.J

    K. Wang and H.J. He, A double extrapolation primal-dual algorithm for saddle point prob- lems, J. Sci. Comput. 85 (2020), no. 3, 1–30

    2020

  46. [54]

    Wang, J.T

    K. Wang, J.T. Yu, and H.J. He, A partially inexact generalized primal-dual hybrid gradient method for saddle point problems with bilinear couplings , J. Appl. Math. Comput. 69 (2023), 3693–3719

    2023

  47. [55]

    Zhu and T

    M.Q. Zhu and T. Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration, CAM Reports 08-34, UCLA, 2008. Department of Mathematics and Statistics, Ningbo University, Ningbo, 315211, China. Email address : yujintao0045@163.com Department of...

    2008

Pith tools

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