An accelerated semi-proximal ADMM with applications to multi-block sparse optimization problems

Liang Chen; Minru Bai; Peng Liu

REVIEW 2 major objections 4 minor 55 references

An accelerated semi-proximal ADMM with applications to multi-block sparse optimization problems

T0 review · 2 major / 4 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 The paper proves that a semi-proximal ADMM with extrapolation and increasing penalties converges at a non-ergodic O(1/K) rate while keeping subproblems solvable.

desk verdict Sound non-ergodic O(1/K) rate for semi-proximal ADMM, but the mixed-sparse application solves the wrong model because of a false constraint reformulation. read the letter →

arxiv 2505.20991 v1 pith:QQ5TBK54 submitted 2025-05-27 math.OC

Peng Liu , Liang Chen , Minru Bai This is my paper

classification math.OC MSC 90C2568Q2565K05

keywords ADMMsemi-proximalaccelerationnon-ergodicconvergencerateO(1/K)symmetricGauss-Seideldecompositionrobustlow-ranktensorcompletionmixedsparseoptimization

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 establishes that a semi-proximal alternating direction method of multipliers (sPADMM) can be accelerated to a non-ergodic O(1/K) convergence rate: both the objective-value gap and the constraint violation of the k-th iterate shrink like a constant over 1+k(1−τ), rather than only an averaged iterate doing so. The proposed AsPADMM algorithm combines Nesterov-style extrapolation with a penalty parameter that increases at each step, while retaining positive semidefinite proximal terms so that every subproblem is solvable. The same machinery, paired with a symmetric Gauss-Seidel decomposition, yields an accelerated method for multi-block convex problems with the same rate. The authors use this solver inside difference-of-convex algorithms for robust low-rank tensor completion and mixed sparse optimization, and report faster convergence than the unaccelerated semi-proximal ADMM on those examples.

What carries the argument

The load-bearing object is the extrapolation schedule θ_k = 1/(1 + k(1 − τ)) in Algorithm 4, which defines the corrected point v_k = y_k + θ_k(1 − θ_{k−1})/θ_{k−1}(y_k − y_{k−1}) and scales the augmented Lagrangian penalty by λ/θ_k, so the penalty increases at every iteration. The semi-proximal terms S_k and T_k are added to keep the x- and y-subproblems well defined, and the convergence proof telescopes an energy inequality only when Σf ≽ S_{k+1} − S_k and Σg ≽ T_{k+1} − T_k. For multi-block problems, the symmetric Gauss-Seidel decomposition converts the block steps into an equivalent semi-proximal step whose proximal operator is sGS(M_{λ/θ_k}); Proposition 1 bounds the successive difference of these operators by the explicitly computable operators Ξ_f and Ξ_g, and Theorem 3 requires Σf ≽ Ξ_f and Σg ≽ Ξ_g.

What would settle it

Take a strongly convex instance of (1) with a known optimum, fix positive semidefinite S and T satisfying the dominance conditions, and compute the left-hand sides of (6a)–(6b) for K = 1, ..., 1000; a single violation of either bound would disprove Theorem 2. Equivalently, a zero-curvature example such as min 0 + 0 subject to x + y = 0 with S_k = kI and T_k = 0 violates the dominance condition, and observing the sequence fail to satisfy the claimed rate would show that the condition is doing the work.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2: if (x*, y*, z*) is a KKT solution and {(xk, yk, zk)} is generated by Algorithm 4 with proximal terms S_k and T_k satisfying Σf ≽ S_{k+1} − S_k and Σg ≽ T_{k+1} − T_k, then for every K, the feasibility violation satisfies 0 ≤ ‖c − Ax_{K+1} − By_{K+1}‖ ≤ 2C3/(1 + K(1 − τ)) and the objective gap is bounded by constants divided by 1 + K(1 − τ). Thus the sequence converges globally to an optimal solution, and each individual iterate rather than an ergodic average achieves O(1/K) in both primal objective gap and feasibility. This improves on the optimal O(1/√K) non-ergodic rate of sPADMM while preserving the flexibility of positive semidefinite proximal terms, and the multi-block extension sGS-AsPADMM inherits the same rate.

Load-bearing premise

The proof relies on the proximal terms growing no faster than the curvature of f and g at every iteration; if the increase in S_k or T_k outruns Σ_f or Σ_g, the telescoping inequality and the O(1/K) guarantee are not established.

Editorial extensions

If this is right

Each iterate, not an average, is guaranteed to approach optimality at O(1/K), so sparse and low-rank structure is preserved in the iterates instead of being smeared out by averaging.
The proximal terms may be positive semidefinite, making the accelerated method applicable where classical accelerated ADMM subproblems can be unsolvable; taking S_k = T_k = 0 recovers the classical case.
Multi-block convex problems of the form (19) inherit the same O(1/K) non-ergodic rate through sGS-AsPADMM, giving a fast inner solver for difference-of-convex algorithms on tensor completion and mixed-sparse models.
The reported numerical results on robust low-rank tensor completion, mixed sparse optimization, and Lasso show the accelerated method reaching the same tolerances in fewer iterations and less time than the corresponding sPADMM variants.
The O(1/√K) non-ergodic rate of sPADMM identified in Theorem 1 is optimal for that class, so the acceleration genuinely closes the gap rather than only improving constants.

Reading between the lines

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

Our inference: the dominance conditions Σf ≽ S_{k+1} − S_k and Σg ≽ T_{k+1} − T_k can be read as a design rule for adaptive proximal terms, suggesting automatic schedules that raise S_k and T_k as fast as the curvature allows while preserving the O(1/K) guarantee.
Our inference: the same telescoping energy argument may extend to inexact or stochastic subproblem solves, provided the error terms can be absorbed into the same inequality; that would be a testable generalization beyond the paper.
Our inference: in the DC applications, accelerating the inner multi-block solve should reduce wall-clock time at fixed outer iteration counts, but the paper does not analyze the outer-loop complexity of the DC algorithm, which would need separate study.

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.

Desk Editor's Note

read the letter

The core result is real. Theorem 2 gives a non-ergodic O(1/K) rate for an accelerated semi-proximal ADMM with variable proximal terms and an increasing penalty, and the proof is a clean telescoping potential argument. The sGS-based multi-block extension is new and useful, since ergodic averaging destroys sparsity/low-rank structure. The RTC application in §6.1 looks sound and the numerical gains are believable.

The soft spot is exactly where the reader and stress-test put it: Proposition 2 is false. The constraint in (32) should be (B,B)z=y, not (B,-B)z=y. Splitting x into positive and negative parts gives (B,-B)(x1;x2)=Bx, and that equals B|x| only when every group of x is sign-consistent. The counterexample x=(1,-1), B=[1,1] gives B|x|=2 but (B,-B)(x+;x-)=0. So the DC surrogate, the penalty reformulation, Algorithm 7, and the numerical results in Figure 2 are solving a different model. The natural fix is to replace (B,-B) with (B,B), and then rerun the experiments. This does not touch the main convergence theorem, but it invalidates the paper's second application as written.

Minor points. The assumption Sigma_f >= S_{k+1}-S_k (and similarly for g) is real and can conflict with the growing penalty when f and g are flat; the paper states it, but the practical range of tau is narrower than it looks. The O(1/K) rate itself is not new, so the novelty claims versus [26] and [31] should be tempered; what is new is the variable-proximal formulation with solvable subproblems and the sGS extension. The Lasso example in §6.3 is a useful sanity check, but it does not add much.

Who should read this: anyone working on acceleration of ADMM, especially for sparse/low-rank problems where non-ergodic rates matter. It deserves a serious referee, but only with the understanding that the mixed-sparse section needs the fix and the experiments rerun. I would send it to review and ask for a revision, not desk-reject it.

Referee Report

2 major / 4 minor

Summary. The paper studies a semi-proximal ADMM (sPADMM) for two-block convex problems and proves an O(1/√K) non-ergodic convergence rate. It then introduces an accelerated variant (AsPADMM) that combines Nesterov-type extrapolation with monotonically increasing penalty parameters, and proves an O(1/K) non-ergodic rate for the last iterate (Theorem 2 and Corollary 1) under the condition that the growth of the variable proximal terms is dominated by the curvatures Σf and Σg. The algorithm is extended to multi-block convex composite problems via the symmetric Gauss-Seidel decomposition (sGS-AsPADMM, Theorem 3), and numerical experiments are reported for robust low-rank tensor completion, mixed sparse optimization, and Lasso. The main convergence proof is a telescoping potential argument with explicit constants, but the mixed-sparse application relies on an incorrect equivalence between problems (31) and (32).

Significance. If correct, the O(1/K) non-ergodic last-iterate rate for sPADMM with variable positive semidefinite proximal terms is a meaningful improvement over the standard O(1/√K) non-ergodic rate and is of practical interest for sparse and low-rank problems where ergodic averaging destroys structure. The proof is self-contained, the constants C3–C6 are explicit, and the sGS extension is technically nontrivial. The numerical results in §6.1 and §6.3 are consistent with the theoretical claims. However, the §6.2 application is currently invalid, so the paper's overall contribution can be accepted only after that section is repaired.

major comments (2)

[§6.2, Proposition 2 (Eqs. (31)–(32))] The asserted equivalence between (31) and (32) is false. The constraint (B,-B)z = y with z = (z1;z2) gives y = Bz1 - Bz2 = B(z1 - z2), not y = B|z1 - z2|. For example, with x = (1,-1) and B = [1,1], the split z = (x_+; x_-) satisfies (B,-B)z = 0 while B|x| = 2. Hence a feasible point of (32) is generally not feasible for (31), and the proof's claim that (B,-B)z = B|x| = y is incorrect. Because equations (33), (34), (35), and Algorithm 7 are all built on this equivalence, the numerical results in Figure 2 and the associated tables do not provide evidence about the mixed sparse model (30). The natural repair is to replace (B,-B) by (B,B), after which the positive-negative split satisfies (B,B)(x_+;x_-) = B|x| and ||(x_+;x_-)||_0 = ||x||_0; the section's derivations, Algorithm 7, and the experiments would then need to be redone accordingly.
[§6.2, proof of Proposition 2] Independently of the sign, the proof does not establish equivalence: the first direction starts with a solution (z*,y*) of (32) and asserts that (z1*-z2*, y*) is feasible for (31), but no argument rules out z1* and z2* having overlapping supports, in which case B|z1*-z2*| is not equal to B(z1*-z2*) = y*. The counterexample above shows the claim fails. The section must be reworked before any numerical claim is made.

minor comments (4)

[§6.2, Proposition 2 proof] The proof contains typos that obscure the argument: 'Dividing z* into' should be 'Splitting z* into', and the expression '||A(z1*-z2*)b||' is missing a minus sign before b.
[§5, first paragraph] The text refers to 'sGS-sPAMM' where it should read 'sGS-sPADMM'.
[Table 3] The first row reports 'dim of A 64 × 1028'; this appears to be a typo for 64 × 1024, which would match the surrounding sizes.
[Theorem 2 and Theorem 3] The assumptions Σ_f ≽ S_{k+1} - S_k and Σ_g ≽ T_{k+1} - T_k (and their multi-block counterparts Σ_f ≽ Ξ_f, Σ_g ≽ Ξ_g) mean that the proximal terms cannot grow faster than the curvature of f and g; since the effective penalty λ/θ_k is increasing, this is a nontrivial restriction. The statement would be clearer if the paper explicitly discussed how each application in §6.1–§6.3 enforces this condition.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the O(1/K) convergence proof is a self-contained potential-function argument with external, non-self-cited lemmas.

full rationale

The central claim, Theorem 2, is derived by constructing a potential function and telescoping the inequalities in Eqs. (15)-(16); the constants C3 and C4 are explicit functions of the initial iterate and the KKT solution, not fitted parameters, and the proof does not assume the desired O(1/K) rate. The only imported lemma, Lemma 1, is quoted from Li and Lin [26], which is not a self-citation by the present authors, so it serves as independent external support. The multi-block extension relies on the sGS decomposition theorem from Li, Sun and Toh [13], also external, while Proposition 1 supplies the needed bound rather than assuming it. Self-citations to prior work by the same group appear in background references and in the application modeling, but the load-bearing convergence argument does not reduce to any of them. The serious correctness defect flagged in Proposition 2 and Section 6.2, where the constraint (B,-B)z=y does not correctly encode B|x|=y, is a mathematical error in the application rather than a circularity: it does not make any derived quantity equal to its own input. No derivation in the paper is equivalent by construction to its assumptions, so the circularity score is 0.

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

The central theorem has no fitted constants; all constants in the rate bounds are explicit functions of initial distances. The user-chosen algorithm parameters (tau, beta, eta) affect the constants and the feasibility of the proximal-term increase assumption, but not the O(1/K) order. The mixed sparse application additionally assumes an equivalence that is false, so that portion of the ledger is broken.

free parameters (4)

tau (extrapolation and penalty growth parameter) = chosen in (0,1); e.g., 0.95 in RTC, 0.99 in mixed sparse
Controls the trade-off between extrapolation strength and the allowed growth of proximal terms; the proofs in Section 6 impose tau intervals to satisfy Sigma_f >= Xi_f.
beta (augmented Lagrangian penalty) = 0.1 in RTC, 0.05 in mixed sparse
Standard ADMM penalty chosen by hand; affects practical convergence speed.
eta (proximal parameter in DC subproblems) = not specified numerically
Added to make subproblems strongly convex; must be large enough relative to tau to satisfy the convergence condition.
lambda1, lambda2, rho1, rho2 (regularization and penalty weights in mixed sparse model) = e.g., lambda1=1e-4, lambda2=1e-6, rho1=3.3e-5, rho2=3e-6
Problem parameters chosen for the numerical tests, not part of the theoretical rate.

assumptions (5)

domain assumption The KKT system (4) admits a solution for problem (1).
Assumed in Theorems 1-3 to guarantee existence of optimal primal-dual solutions.
standard math Sigma_f and Sigma_g satisfying inequalities (2)-(3) exist for the convex functions f and g.
For closed proper convex functions, Sigma_f=0 and Sigma_g=0 always satisfy these inequalities, so this is not restrictive.
standard math The symmetric Gauss-Seidel decomposition theorem of Li, Sun, and Toh (cited as [13, Theorem 1]) holds for the quadratic operators M_lambda and N_lambda.
Used to rewrite Algorithm 5's sweeps as a proximal ADMM with sGS proximal terms (Eq. 25).
standard math Lemma 1 from [26] (a bound on sums of residuals) is valid.
Quoted as Lemma 1 and used to convert the residual bound (18) into the per-iteration bound (6b).
ad hoc to paper The equivalence between (31) and (32) asserted in Proposition 2.
This statement is false; the constraint (B,-B)z=y does not enforce y=B|x|. The proof incorrectly identifies B(z1-z2) with B|z1-z2|. This makes the mixed sparse optimization application invalid.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An accelerated semi-proximal ADMM with applications to multi-block sparse optimization problems." pith.science (2026). https://pith.science/paper/QQ5TBK54

@misc{pith2026250520991,
  author       = {Pith},
  title        = {Pith review of: An accelerated semi-proximal ADMM with applications to multi-block sparse optimization problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QQ5TBK54}},
  note         = {Machine review of arXiv:2505.20991}
}

abstract

As an extension of the alternating direction method of multipliers (ADMM), the semi-proximal ADMM (sPADMM) has been widely used in various fields due to its flexibility and robustness. In this paper, we first show that the two-block sPADMM algorithm can achieve an $O(1/\sqrt{K})$ non-ergodic convergence rate. Then we propose an accelerated sPADMM (AsPADMM) algorithm by introducing extrapolation techniques and incrementing penalty parameters. The proposed AsPADMM algorithm is proven to converge globally to an optimal solution with a non-ergodic convergence rate of $O(1/K)$. Furthermore, the AsPADMM can be extended and combined with the symmetric Gauss-Seidel decomposition to achieve an accelerated ADMM for multi-block problems. Finally, we apply the proposed AsPADMM to solving the multi-block subproblems in difference-of-convex algorithms for robust low-rank tensor completion problems and mixed sparse optimization problems. The numerical results suggest that the acceleration techniques bring about a notable improvement in the convergence speed.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

55 extracted references · 54 canonical work pages

[26]

Li, H., Lin, Z.C.: Accelerated alternating direction me thod of multipliers: An optimal O(1/K) non-ergodic analysis. J. Sci. Comput. 79(2), 671–699 (2019)

work page 2019
[31]

Sun, D.F., Yuan, Y.C., Zhang, G.J., Zhao, X.Y.: Accelera ting preconditioned ADMM via degenerate proximal point mappings. SIAM J. Optim. 35(2), 1165-1193 (2025)

work page 2025
[1]

and Marroco, A.: Sur l’approximation, par ´ el´ ements ﬁnis d’ordre un, et la r´ esolution, par p´ enalisation-dualit´ e d’une classe de probl` emes de Dirichlet non lin´ eaires

Glowinski, R. and Marroco, A.: Sur l’approximation, par ´ el´ ements ﬁnis d’ordre un, et la r´ esolution, par p´ enalisation-dualit´ e d’une classe de probl` emes de Dirichlet non lin´ eaires. Revue fran¸ caise d’atomatique, InformatiqueRecherche Op´ erationelle. Analyse Num´ erique9(2), 41–76 (1975)

work page 1975
[2]

Gabay, D., Mercier, B.: A dual algorithm for the solution o f nonlinear variational prob- lems via ﬁnite element approximation. Comput. Math. with Ap pl. 2(1), 17–40 (1976)

work page 1976
[3]

Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., e t al.: Distributed optimization and statistical learning via the alternating direction met hod of multipliers. Found. Trends Mach. Learn. 3(1), 1–122 (2011)

work page 2011
[4]

Chang, T.H., Hong, M.Y., W ang, X.F.: Multi-agent distrib uted optimization via inexact consensus ADMM. IEEE. Trans. Signal Process. 63(2), 482–497 (2014)

work page 2014
[5]

Hestenes, M.R.: Multiplier and gradient methods. J. Opti m. Theory. Appl. 4(5), 303– 320 (1969)

work page 1969
[6]

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

work page 1976

Show all 55 references

[7]

Chen, L., Sun, D.F., Toh, K.C.: A note on the convergence of ADMM for linearly constrained convex optimization problems. Comput. Optim. Appl. 66, 327–343 (2017)

2017
[8]

Eckstein, J.: Some saddle-function splitting methods fo r convex programming. Optim. Methods. Softw. 4(1), 75–83 (1994)

1994
[9]

He, B.S., Liao, L.Z., Han, D.R., Yang, H.: A new inexact alt ernating directions method for monotone variational inequalities. Math. Program. 92, 103–118 (2002)

2002
[10]

Advances in neural in formation processing systems

Lin, Z.C., Liu, R.S., Su, Z.X.: Linearized alternating d irection method with adaptive penalty for low-rank representation. Advances in neural in formation processing systems. (2011)

2011
[11]

Yang, J.F., Yuan, X.M.: Linearized augmented lagrangia n and alternating direction methods for nuclear norm minimization. Math. Comput. 82(281), 301–329 (2013)

2013
[12]

Fazel, M., Pong, T.K., Sun, D.F., Tseng, P.: Hankel matri x rank minimization with applications to system identiﬁcation and realization. SIA M J. Matrix Anal. Appl. 34(3), 946–977 (2013)

2013
[13]

Li, X.D., Sun, D.F., Toh, K.C.: A block symmetric Gauss-S eidel decomposition theorem for convex composite quadratic programming and its applica tions. Math. Program. 175, 395–418 (2019)

2019
[14]

Li, X.D., Sun, D.F., Toh, K.C.: A Schur complement based s emi-proximal ADMM for convex quadratic conic programming and extensions. Math. P rogram. 155(1-2), 333– 373 (2016)

2016
[15]

Chen, L., Sun, D.F., Toh, K.C.: An eﬃcient inexact symmet ric Gauss-Seidel based majorized ADMM for high-dimensional convex composite coni c programming. Math. Program. 161, 237–270 (2017)

2017
[16]

Chen, L., Sun, D.F., Toh, K.C., Zhang, N.: A uniﬁed algori thmic framework of sym- metric Gauss-Seidel decomposition based proximal ADMMs fo r convex composite pro- gramming. J. Comput. 37(6), 739–757 (2019)

2019
[17]

Chen, L., Li, X., Sun, D., Toh, K.C.: On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming. Math. Prog ram. 185, 111–161 (2021)

2021
[18]

Splitting methods in communication, imaging, science, and engineeri ng

Davis, D., Yin, W.: Convergence rate analysis of several splitting schemes. Splitting methods in communication, imaging, science, and engineeri ng. 115–163 (2016)

2016
[19]

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

2013
[20]

Cui, Y., Li, X.D., Sun, D.F., Toh, K.C.: On the convergenc e properties 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, 1013–1041 (2016)

2016
[21]

: Fast alternating direction op- timization methods

Goldstein, T., O’Donoghue, B., Setzer, S., Baraniuk, R. : Fast alternating direction op- timization methods. SIAM J. Imaging Sci. 7(3), 1588–1623 (2014) Accelerated Semi-Proximal ADMM 29

2014
[22]

Ouyang, Y.Y., Chen, Y.M., Lan, G.H., Pasiliao, E.: An acc elerated linearized alternating direction method of multipliers. SIAM J. Imaging Sci. 8(1), 644–681 (2015)

2015
[23]

Xu, Y.Y.: Accelerated ﬁrst-order primal-dual proximal methods for linearly constrained composite convex programming. SIAM J. Optim. 27(3), 1459–1484 (2017)

2017
[24]

arXiv preprint arXiv:2304.02459v2

Zhang, T., Xia, Y., Li, S.R.: Lagrangian-based methods i n convex optimization: prediction-correction frameworks with non-ergodic conve rgence rates. arXiv preprint arXiv:2304.02459v2. (2023)

2023 arXiv
[25]

Deng, W., Lai, M.J., Peng, Z.M., Yin, W.T.: Parallel mult i-block ADMM with o(1/K) convergence. J. Sci. Comput. 71, 712–736 (2017)

2017
[27]

Sabach, S., Teboulle, M.: Faster Lagrangian-based meth ods in convex optimization. SIAM J. Optim. 32(1), 204–227 (2022)

2022
[28]

Kim, D.: Accelerated proximal point method for maximall y monotone operators. Math. Program. 190, 57–87 (2021)

2021
[29]

arXiv preprint arXiv:2211.14881

Zhang, G.J., Yuan, Y.C., Sun, D.F.: An eﬃcient HPR algori thm for the W asser- stein barycenter problem with O(Dim(P )/ε) computational complexity. arXiv preprint arXiv:2211.14881. (2022)

2022 arXiv
[30]

Yang, B., Zhao, X.Y., Li, X.D., Sun, D.F.: An accelerated proximal alternating direction method of multipliers for optimal decentralized control of uncertain systems. J. Optim. Theory. Appl. 204(1), 9 (2025)

2025
[32]

A.: A family of variable metric proximal methods

Bonnans, J.F., Gilbert, J.C., Lemar´ echal, C., Sag´ astizabal, C. A.: A family of variable metric proximal methods. Math. Program. 68, 15–47 (1995)

1995
[33]

Li, X.D., Sun, D.F., Toh, K.-C.: An asymptotically super linearly convergent semismooth Newton augmented Lagrangian method for linear programming . SIAM J. Optim. 30 2410–2440 (2020)

2020
[34]

arXiv preprint arXiv:2408 .12179

Chen, K.H., Sun, D.F., Yuan, Y.C.: HPR-LP: An implementa tion of an HPR method for solving linear programming. arXiv preprint arXiv:2408 .12179. (2024)

2024
[35]

Princeton Universit y Press Princeton, 1970

Rockafellar, R.: Convex Analysis. Princeton Universit y Press Princeton, 1970

1970
[36]

Han, D.R., Sun, D.F., Zhang, L.W.: Linear rate convergen ce of the alternating direction method of multipliers for convex composite programming. Ma th. Oper. Res. 43(2), 622– 637 (2018)

2018
[37]

IEEE Access

Liu, Q.H., Shen, X.Y., Gu, Y.T.: Linearized ADMM for non- convex non-smooth opti- mization with convergence analysis. IEEE Access. 7, 76131–76144 (2019)

2019
[38]

W u, F.S., Li, C.Q., Li, Y.T., Tang, N.S.: Robust low-rank tensor completion via new regularized model with approximate SVD. Inf. Sci. 629, 646–666 (2023)

2023
[39]

W avelets and Sparsity XV

Deng, W., Yin, W.T., Zhang, Y.: Group sparse optimizatio n by alternating direction method. W avelets and Sparsity XV. 8858, 242–256 (2013)

2013
[40]

Chen, C.H., He, B.S., Ye, Y.Y., Yuan, X.M.: The direct ext ension of ADMM for multi- block convex minimization problems is not necessarily conv ergent. Math. Program. 155(1-2), 57–79 (2016)

2016
[41]

Zeng, J.S., Yin, W.T., Zhou, D.X.: Moreau envelope augme nted Lagrangian method for non-convex optimization with linear constraints. J. Sci. C omput. 91(2), 61 (2022)

2022
[42]

Zhang, J.W., Luo, Z.Q.: A proximal alternating directio n method of multiplier for lin- early constrained non-convex minimization. SIAM J. Optim. 30(3), 2272–2302 (2020)

2020
[43]

Zhang, J.W., Luo, Z.Q.: A global dual error bound and its a pplication to the analysis of linearly constrained non-convex optimization. SIAM J. Opt im. 32(3), 2319–2346 (2022)

2022
[44]

Pang, J.-S., Razaviyayn, M., Alvarado, A.: Computing B- stationary points of non- smooth DC programs. Math. Oper. Res. 42(1), 95-118 (2016)

2016
[45]

Zhao, X.Y., Bai, M.R., Sun, D.F., Zheng, L.B.: Robust ten sor completion: Equivalent surrogates, error bounds, and algorithms. SIAM J. Imaging S ci. 15(2), 625–669 (2022)

2022
[46]

IEEE Trans

Lu, C.Y., F, J.S., C, Y.D., L, W., L, Z.C., Y, S.C.: Tensor r obust principal component analysis with a new tensor nuclear norm. IEEE Trans. Pattern Anal. Mach. Intell. 42(4), 925–938 (2019)

2019
[47]

IE EE Transactions on image

Chan, R.H., Ho, C.W., Nikolova, M.: Salt-and-pepper noi se removal by median-type noise detectors and detail-preserving regularization. IE EE Transactions on image. 14(10), 1479–1485 (2005) 30 Peng Liu et al

2005
[48]

Liu, Y.L., Bi, S.J., Pan, S.H.: Equivalent Lipschitz sur rogates for zero-norm and rank optimization problems. J. Glob. Optim. 72(4), 679–704 (2018)

2018
[49]

: Distributed optimization and statistical learning via the alternating direction method of multipliers

Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J. : Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1–122 (2011) A Proof of Theorem 1. In this Appendix, we give a detailed proof of T...

2011
[50]

(41) From the iterative format of sPADMM, the following equation holds, Axk+1 + Byk+1 − Axk − Byk = 1 τ λ(2zk − zk+1 − zk−1)

and ( 38), we can derive the following inequalities, 0 ≤ ⟨ ˆ∇f (xk+1) − ˆ∇f (xk), xk+1 − xk⟩ = ⟨zk+1 − zk, A(xk+1 − xk)⟩ + λ(τ − 1)⟨Axk+1 + Byk+1 − Axk − Byk, A(xk+1 − xk)⟩ +λ⟨B(yk+1 − 2yk + yk−1), A(xk+1 − xk)⟩ − ⟨xk+1 − 2xk + xk−1, S(xk+1 − xk)⟩, (40) 0 ≤ ⟨ ˆ∇g(yk+1) − ˆ∇g(y...
[51]

For a detailed description of the last inequality above, we let ak := zk+1 − 2zk + zk−1 and bk := B(yk+1 − 2yk + yk−1)

and ( 41), there is 0 ≤ ⟨ ˆ∇f (xk+1) − ˆ∇f (xk), xk+1 − xk⟩ + ⟨ˆ∇g(yk+1) − ˆ∇g(yk), yk+1 − yk⟩ = ⟨zk+1 − zk, Axk+1 + Byk+1 − Axk − Byk⟩ + λ(τ − 1)‖Axk+1 + Byk+1 − Axk −Byk‖2 + λ⟨B(yk+1 − 2yk + yk−1), Axk+1 − Axk⟩ −⟨xk+1 − 2xk + xk−1, S(xk+1 − xk)⟩ − ⟨yk+1 − 2yk + yk−1, T (yk+1...
[52]

where the third inequality uses ( 41)

When τ = 1, combining ( 37) and ( 38), we can obtain 0 ≤ f (xk+1) + g(yk+1) − f (x∗) − g(y∗) + ⟨z∗, c − Axk+1 − Byk+1⟩ ≤ ⟨ ˆ∇f (xk+1), xk+1 − x∗⟩ + ⟨ˆ∇g(yk+1), yk+1 − y∗⟩ + ⟨z∗, c − Axk+1 − Byk+1⟩ = − 1 λ ⟨zk+1 − z∗, zk+1 − zk⟩ + ⟨B(yk+1 − yk), zk − zk+1⟩ +λ⟨B(yk+1 − yk), B(y∗...
[53]

from k = 1 to K and using( 39), one can get K( 1 λ ‖zK − zK+1‖2 + λ‖B(yK+1 − yK )‖2 + ‖xK+1 − xK ‖2 S + ‖yK+1 − yK ‖2 T ) ≤ ∑ K k=1( 1 λ ‖zk − zk+1‖2 + λ‖B(yk+1 − yk)‖2 + ‖xk+1 − xk‖2 S + ‖yk+1 − yk‖2 T ) ≤ C1 := 1 λ ‖z1 − z∗‖2 + λ‖B(y1 − y∗)‖2 + ‖x1 − x∗‖2 S + ‖y1 − y∗‖2 T + ...
[54]

Then, one can get 0 < m < 1, τ −2 2τ 2λ < t < 0, 0 < 1 4tτ 2 + λ 2 < λ 2 , t − τ −2 2τ 2λ < 1 2τ λ and ( t − τ −2 2τ λ )/( 1 2τ λ) = ( 1 4tτ 2 + λ 2 )/( λ 2 ) = m

When τ ∈ (0, 1), we let ˆak = zk+1 − zk, ˆbk = B(yk+1 − yk), t = τ −1− √ τ 2−τ +1 2τ 2λ and m = 2τ λt − τ −2 τ . Then, one can get 0 < m < 1, τ −2 2τ 2λ < t < 0, 0 < 1 4tτ 2 + λ 2 < λ 2 , t − τ −2 2τ 2λ < 1 2τ λ and ( t − τ −2 2τ λ )/( 1 2τ λ) = ( 1 4tτ 2 + λ 2 )/( λ 2 ) = m. ...
[55]

and ( 51), for K = 1, 2, · · · , one has τ λ‖AxK+1 + ByK+1 − c‖ = ‖zK+1 − zK ‖ ≤ √ τ λC K , ‖B(yK+1 − yK )‖ ≤ √ C λK , ‖yK+1− yK ‖T ≤ √ C K , and ‖xK+1 − xK ‖S ≤ √ C K . (52) On the other hand, using ( 44) and ( 49) we have 1 τ λ‖zk+1 − z∗‖2 + λ‖B(yk+1 − y∗)‖2 + ‖xk+1 − x∗‖2 S...

Pith tools

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

[1] [26]

Li, H., Lin, Z.C.: Accelerated alternating direction me thod of multipliers: An optimal O(1/K) non-ergodic analysis. J. Sci. Comput. 79(2), 671–699 (2019)

work page 2019

[2] [31]

Sun, D.F., Yuan, Y.C., Zhang, G.J., Zhao, X.Y.: Accelera ting preconditioned ADMM via degenerate proximal point mappings. SIAM J. Optim. 35(2), 1165-1193 (2025)

work page 2025

[3] [1]

and Marroco, A.: Sur l’approximation, par ´ el´ ements ﬁnis d’ordre un, et la r´ esolution, par p´ enalisation-dualit´ e d’une classe de probl` emes de Dirichlet non lin´ eaires

Glowinski, R. and Marroco, A.: Sur l’approximation, par ´ el´ ements ﬁnis d’ordre un, et la r´ esolution, par p´ enalisation-dualit´ e d’une classe de probl` emes de Dirichlet non lin´ eaires. Revue fran¸ caise d’atomatique, InformatiqueRecherche Op´ erationelle. Analyse Num´ erique9(2), 41–76 (1975)

work page 1975

[4] [2]

Gabay, D., Mercier, B.: A dual algorithm for the solution o f nonlinear variational prob- lems via ﬁnite element approximation. Comput. Math. with Ap pl. 2(1), 17–40 (1976)

work page 1976

[5] [3]

Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., e t al.: Distributed optimization and statistical learning via the alternating direction met hod of multipliers. Found. Trends Mach. Learn. 3(1), 1–122 (2011)

work page 2011

[6] [4]

Chang, T.H., Hong, M.Y., W ang, X.F.: Multi-agent distrib uted optimization via inexact consensus ADMM. IEEE. Trans. Signal Process. 63(2), 482–497 (2014)

work page 2014

[7] [5]

Hestenes, M.R.: Multiplier and gradient methods. J. Opti m. Theory. Appl. 4(5), 303– 320 (1969)

work page 1969

[8] [6]

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

work page 1976