pith. sign in

arxiv: 2407.09927 · v4 · submitted 2024-07-13 · 🧮 math.OC

An Adaptive Proximal ADMM for Nonconvex Linearly Constrained Composite Programs

Leandro Farias Maia , David H. Gutman , Renato D.C. Monteiro , Gilson N. Silva This is my paper

Pith reviewed 2026-05-23 23:01 UTC · model grok-4.3

classification 🧮 math.OC
keywords adaptive proximal ADMMnonconvex optimizationlinearly constrained composite programsweakly convex functionsiteration complexityfirst-order stationary pointsinexact subproblem solves
0
0 comments X

The pith

An adaptive proximal ADMM reaches approximate first-order stationary points for nonconvex constrained composite problems in a number of iterations matching the best known bounds for proximal ADMM methods, without any rank assumptions on the

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

The paper develops an adaptive proximal alternating direction method of multipliers for linearly constrained composite optimization problems in which one part of the objective is smooth and weakly convex while the other is convex and block-separable. The method is fully adaptive to all problem constants, permits inexact solution of each block proximal subproblem, and uses simple tests after each block update to decide whether to refresh the Lagrange multiplier or the penalty parameter. It proves that an approximate first-order stationary point is reached in iteration counts that match the state-of-the-art complexity results previously known only under stronger assumptions on the constraint matrices. A reader would care because the setting covers many practical nonconvex problems that arise in signal processing, machine learning, and engineering design, and the lack of rank requirements removes a common barrier to applying splitting methods.

Core claim

The adaptive proximal ADMM proceeds by sequentially solving the block proximal subproblems and then applying adaptive tests that decide whether to perform a full Lagrange multiplier update and/or a penalty-parameter update; under the stated weak-convexity and block-separability assumptions, this procedure produces an approximate first-order stationary point of the original constrained problem in a number of iterations that matches the best known complexity for the class of proximal ADMM methods, and the result holds without any rank assumptions on the constraint matrices.

What carries the argument

The adaptive tests after each block proximal subproblem solve that decide whether to update the multiplier and/or the penalty parameter.

If this is right

  • The method applies directly to linearly constrained problems whose constraint matrices may be rank-deficient.
  • No a-priori knowledge of smoothness or weak-convexity constants is required for the iteration bound to hold.
  • Inexact solves of the block proximal subproblems are permitted without degrading the overall iteration complexity.
  • The three numerical experiments indicate that the adaptivity yields measurable reductions in total computational effort on representative test problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same adaptive-test mechanism could be transplanted into other operator-splitting schemes that currently rely on fixed penalty schedules.
  • Because the complexity result is free of rank assumptions, the method may scale more gracefully to very large or ill-conditioned constraint systems than earlier proximal ADMM variants.
  • The allowance for inexact subproblem solves opens the possibility of pairing the outer iteration with fast inner solvers whose accuracy is adjusted dynamically.

Load-bearing premise

The smooth component of the objective is weakly convex while the nonsmooth component is convex and block-separable.

What would settle it

An instance satisfying the weak-convexity and block-separability assumptions on which the adaptive proximal ADMM requires asymptotically more iterations than the claimed state-of-the-art bound to produce an approximate first-order stationary point.

read the original abstract

This paper develops an adaptive proximal alternating direction method of multipliers (ADMM) for solving linearly constrained, composite optimization problems under the assumption that the smooth component of the objective is weakly convex, while the non-smooth component is convex and block-separable. The proposed method is adaptive to all problem parameters, including smoothness and weak convexity constants, and allows each of its block proximal subproblems to be inexactly solved. Each iteration of our adaptive proximal ADMM consists of two steps: the sequential solution of each block proximal subproblem; and adaptive tests to decide whether to perform a full Lagrange multiplier and/or penalty parameter update(s). Without any rank assumptions on the constraint matrices, it is shown that the adaptive proximal ADMM obtains an approximate first-order stationary point of the constrained problem in a number of iterations that matches the state-of-the-art complexity for the class of proximal ADMM's. The three proof-of-concept numerical experiments that conclude the paper suggest our adaptive proximal ADMM enjoys significant computational benefits.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper develops an adaptive proximal ADMM for linearly constrained composite optimization problems where the smooth objective component is weakly convex and the nonsmooth component is convex and block-separable. The method is adaptive to all parameters (including smoothness and weak-convexity constants), permits inexact solves of the block proximal subproblems, and consists of sequential block proximal updates followed by adaptive tests that decide whether to update the Lagrange multiplier and/or penalty parameter. Without rank assumptions on the constraint matrices, the paper claims that the method finds an approximate first-order stationary point in a number of iterations matching the state-of-the-art complexity for the class of proximal ADMM methods; three numerical experiments are presented as supporting evidence.

Significance. If the complexity bound is established under the stated assumptions, the result would be significant for nonconvex constrained optimization: it removes the common rank condition on the constraint matrices while retaining adaptivity to all parameters and tolerance to inexact subproblem solves. The absence of free parameters or ad-hoc axioms in the analysis, together with the explicit matching to prior proximal-ADMM complexity, strengthens the contribution if the derivation is correct.

minor comments (3)
  1. [§1] The abstract and introduction refer to 'state-of-the-art complexity for the class of proximal ADMM's' but do not cite the specific prior works whose bounds are being matched; adding these references in §1 would clarify the comparison.
  2. [§3] The description of the adaptive tests (step 2 of each iteration) is summarized at a high level; a more explicit statement of the test conditions and their relation to the penalty-parameter update rule would improve readability.
  3. [§2] Notation for the block-separable nonsmooth term and the linear constraint matrix is introduced without an explicit table of symbols; a short notation table would aid readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for recommending minor revision. We appreciate the recognition that establishing the stated complexity bound without rank assumptions on the constraint matrices, while retaining full adaptivity and tolerance to inexact subproblem solves, would constitute a significant contribution to nonconvex constrained optimization.

Circularity Check

0 steps flagged

Minor self-citation to prior proximal ADMM complexity; central derivation independent

full rationale

The paper presents an adaptive proximal ADMM with iteration complexity analysis that matches but does not reduce to prior results by construction or self-definition. The bound is derived from the adaptive scheme under the stated weak-convexity and block-separability assumptions, without rank conditions. References to state-of-the-art proximal ADMM complexity serve as external benchmarks rather than load-bearing justifications. No fitted inputs are renamed as predictions, no ansatz is smuggled via citation, and the derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the domain assumption of weak convexity of the smooth objective component and block-separability plus convexity of the nonsmooth component; no free parameters are fitted inside the algorithm itself because it is adaptive to those constants, and no new entities are postulated.

axioms (2)
  • domain assumption The smooth component of the objective is weakly convex
    Invoked in the abstract as the setting for which the method and its complexity guarantee are developed.
  • domain assumption The nonsmooth component is convex and block-separable
    Stated in the abstract as part of the problem class.

pith-pipeline@v0.9.0 · 5714 in / 1373 out tokens · 20348 ms · 2026-05-23T23:01:21.932162+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

60 extracted references · 60 canonical work pages · 1 internal anchor

  1. [1]

    Aybat and G

    N. Aybat and G. Iyengar. A first-order smoothed penalty method for compressed sensing. SIAM J. Optim., 21(1):287–313, 2011

    work page 2011

  2. [2]

    Aybat and G

    N. Aybat and G. Iyengar. A first-order augmented Lagrangian method for compressed sensing. SIAM J. Optim., 22(2):429–459, 2012

    work page 2012

  3. [3]

    Beck and M

    A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences , 2(1):183–202, 2009

    work page 2009

  4. [4]

    Beck and M

    A. Beck and M. Teboulle. Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE transactions on image processing , 18(11):2419–2434, 2009

    work page 2009

  5. [5]

    D. P. Bertsekas. Nonlinear programming. Taylor & Francis, 3ed edition, 2016

    work page 2016

  6. [6]

    Birgin, G

    E. Birgin, G. Haeser, and J. M. Mart´ ınez. Safeguarded augmented Lagrangian algorithms with scaled stopping criterion for the subproblems. Computational Optimization and Applications, 91:491–509, 2025

    work page 2025

  7. [7]

    S. Boyd, N. Parikh, and E. Chu. Distributed optimization and statistical learning via the alternating direction method of multipliers . Now Publishers Inc, 2011

    work page 2011

  8. [8]

    M. T. Chao, Y. Zhang, and J. B. Jian. An inertial proximal alternating direction method of multipliers for nonconvex optimization. International Journal of Computer Mathematics , 98(6):1199–1217, 2021

    work page 2021

  9. [9]

    Eckstein and D

    J. Eckstein and D. P. Bertsekas. On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55(1):293–318, 1992

    work page 1992

  10. [10]

    Eckstein and M

    J. Eckstein and M. C. Ferris. Operator-splitting methods for monotone affine variational inequalities, with a parallel application to optimal control. INFORMS Journal on Computing , 10(2):218–235, 1998

    work page 1998

  11. [11]

    Eckstein and M

    J. Eckstein and M. Fukushima. Some reformulations and applications of the alternating direction method of multipliers. In Large scale optimization, pages 115–134. Springer, 1994

    work page 1994

  12. [12]

    Eckstein and B

    J. Eckstein and B. F. Svaiter. A family of projective splitting methods for the sum of two maximal monotone operators. Mathematical Programming, 111(1):173–199, 2008

    work page 2008

  13. [13]

    Eckstein and B

    J. Eckstein and B. F. Svaiter. General projective splitting methods for sums of maximal monotone operators. SIAM Journal on Control and Optimization , 48(2):787–811, 2009. 31

    work page 2009

  14. [14]

    M. I. Florea and S. A. Vorobyov. An accelerated composite gradient method for large-scale composite objective problems. IEEE Transactions on Signal Processing , 67(2):444–459, 2018

    work page 2018

  15. [15]

    D. Gabay. Applications of the method of multipliers to variational inequalities. InStudies in mathematics and its applications , volume 15, pages 299–331. Elsevier, 1983

    work page 1983

  16. [16]

    Gabay and B

    D. Gabay and B. Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers & mathematics with applications , 2(1):17–40, 1976

    work page 1976

  17. [17]

    Glowinski and A

    R. Glowinski and A. Marroco. Sur l’approximation, par ´ el´ ements finis d’ordre un, et la r´ esolution, par p´ enalisation-dualit´ e d’une classe de probl` emes de dirichlet non lin´ eaires.ESAIM: Mathematical Mod- elling and Numerical Analysis-Mod´ elisation Math´ ematique et Analyse Num´ erique, 9(R2):41–76, 1975

    work page 1975

  18. [18]

    M. L. N. Goncalves, J. G. Melo, and R. D. C. Monteiro. Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems. Pacific Journal of Optimization , 15:379–398, 2019

    work page 2019

  19. [19]

    Hajinezhad and M

    D. Hajinezhad and M. Hong. Perturbed proximal primal–dual algorithm for nonconvex nonsmooth optimization. Math. Program., 176:207–245, 2019

    work page 2019

  20. [20]

    He and R

    Y. He and R. Monteiro. An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems. SIAM J. Optim. , 26(1):29–56, 2016

    work page 2016

  21. [21]

    He and R

    Y. He and R. D. C. Monteiro. Accelerating block-decomposition first-order methods for solving com- posite saddle-point and two-player Nash equilibrium problems. SIAM J. Optim. , 25:2182–2211, 2015

    work page 2015

  22. [22]

    J. B. Hiriart-Urruty and C. Lemarechal. Convex Analysis and Minimization Algorithms II. Advanced Theory and Bundle Methods . Springer, Berlin, 1993

    work page 1993

  23. [23]

    Hong, Z.-Q

    M. Hong, Z.-Q. Luo, and M. Razaviyayn. Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM Journal on Optimization , 26(1):337–364, 2016

    work page 2016

  24. [24]

    Izmailov, M

    A. Izmailov, M. Solodov, and E. Uskov. Global convergence of augmented Lagrangian methods ap- plied to optimization problems with degenerate constraints, including problems with complementarity constraints. SIAM Journal on Optimization , 22:1579–1606, 2012

    work page 2012

  25. [25]

    Z. Jia, J. Huang, and Z. Wu. An incremental aggregated proximal ADMM for linearly constrained non- convex optimization with application to sparse logistic regression problems. Journal of Computational and Applied Mathematics , 390:113384, 2021

    work page 2021

  26. [26]

    Jiang, T

    B. Jiang, T. Lin, S. Ma, and S. Zhang. Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis. Computational Optimization and Applications , 72(1):115–157, 2019

    work page 2019

  27. [27]

    W. Kong. Complexity-optimal and parameter-free first-order methods for finding stationary points of composite optimization problems. SIAM Journal on Optimization , 34(3):3005–3032, 2024

    work page 2024

  28. [28]

    Kong and R

    W. Kong and R. D. C. Monteiro. An accelerated inexact dampened augmented Lagrangian method for linearly constrained nonconvex composite optimization problems. Comput. Optim. Appl. , 2023

    work page 2023

  29. [29]

    Kong and R

    W. Kong and R. D. C. Monteiro. Global complexity bound of a proximal ADMM for linearly constrained nonseparable nonconvex composite programming. SIAM Journal on Optimization , 34(1):201–224, 2024

    work page 2024

  30. [30]

    W. Kong, J. G. Melo, and R. D. Monteiro. An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems. Computational Optimization and Applications, 76:305–346, 2020

    work page 2020

  31. [31]

    W. Kong, J. G. Melo, and R. Monteiro. FISTA and Extensions - Review and New Insights. Optimization Online, 2021. 32

    work page 2021

  32. [32]

    W. Kong, J. G. Melo, and R. D. Monteiro. Iteration complexity of a proximal augmented Lagrangian method for solving nonconvex composite optimization problems with nonlinear convex constraints. Mathematics of Operations Research, 48(2):1066–1094, 2023

    work page 2023

  33. [33]

    W. Kong, J. G. Melo, and R. D. C. Monteiro. Iteration complexity of an inner accelerated inexact proximal augmented Lagrangian method based on the classical Lagrangian function. SIAM Journal on Optimization, 33(1):181–210, 2023

    work page 2023

  34. [34]

    Lan and R

    G. Lan and R. D. C. Monteiro. Iteration-complexity of first-order penalty methods for convex program- ming. Math. Program., 138(1):115–139, 2013

    work page 2013

  35. [35]

    Lan and R

    G. Lan and R. D. C. Monteiro. Iteration-complexity of first-order augmented Lagrangian methods for convex programming. Math. Program., 155(1):511–547, 2016

    work page 2016

  36. [36]

    Y. Liu, X. Liu, and S. Ma. On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming. Math. Oper. Res., 44(2):632–650, 2019

    work page 2019

  37. [37]

    P.-L. Loh. Statistical consistency and asymptotic normality for high-dimensional robust $M$-estimators. The Annals of Statistics , 45(2):866 – 896, 2017. doi: 10.1214/16-AOS1471. URL https://doi.org/ 10.1214/16-AOS1471

    work page doi:10.1214/16-aos1471 2017

  38. [38]

    Lu and Z

    Z. Lu and Z. Zhou. Iteration-complexity of first-order augmented Lagrangian methods for convex conic programming. SIAM journal on optimization , 33(2):1159–1190, 2023

    work page 2023

  39. [39]

    J. Melo, R. D. C. Monteiro, and H. Wang. Iteration-complexity of an inexact proximal accelerated aug- mented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems. Available on arXiv:2006.08048 , 2020

    work page arXiv 2006

  40. [40]

    J. G. Melo and R. D. C. Monteiro. Iteration-complexity of a linearized proximal multiblock ADMM class for linearly constrained nonconvex optimization problems. Optimization Online preprint , 2017

    work page 2017

  41. [41]

    J. G. Melo and R. D. C. Monteiro. Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs. Available on arXiv:1705.07229 , 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  42. [42]

    J. G. Melo, R. D. Monteiro, and H. Wang. A proximal augmented Lagrangian method for linearly con- strained nonconvex composite optimization problems. Journal of Optimization Theory and Applications, 202(1):388–420, 2024

    work page 2024

  43. [43]

    Monteiro, Ortiz, and B

    R. Monteiro, Ortiz, and B. F. Svaiter. An adaptive accelerated first-order method for convex optimiza- tion. Comput. Optim. Appl. , 64:31–73, 2016

    work page 2016

  44. [44]

    R. D. C. Monteiro and B. F. Svaiter. Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM Journal on Optimization , 23(1):475–507, 2013

    work page 2013

  45. [45]

    Necoara, A

    I. Necoara, A. Patrascu, and F. Glineur. Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming. Optimization Methods and Software , 34(2):305–335, 2019

    work page 2019

  46. [46]

    Nesterov

    Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical programming, 140 (1):125–161, 2013

    work page 2013

  47. [47]

    Y. E. Nesterov. A method of solving a convex programming problem with convergence rate O 1 k2 . Dokl. Akad. Nauk SSSR , 269(3):543–547, 1983

    work page 1983

  48. [48]

    Y. E. Nesterov. Introductory lectures on convex optimization : a basic course . Kluwer Academic Publ., 2004

    work page 2004

  49. [49]

    Paquette, H

    C. Paquette, H. Lin, D. Drusvyatskiy, J. Mairal, and Z. Harchaoui. Catalyst for gradient-based noncon- vex optimization. In International Conference on Artificial Intelligence and Statistics , pages 613–622. PMLR, 2018. 33

    work page 2018

  50. [50]

    Patrascu, I

    A. Patrascu, I. Necoara, and Q. Tran-Dinh. Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization. Optim. Lett., 11(3):609–626, 2017

    work page 2017

  51. [51]

    R. T. Rockafellar. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of operations research, 1(2):97–116, 1976

    work page 1976

  52. [52]

    Ruszczy´ nski

    A. Ruszczy´ nski. An augmented Lagrangian decomposition method for block diagonal linear program- ming problems. Operations Research Letters, 8(5):287–294, 1989

    work page 1989

  53. [53]

    Sujanani and R

    A. Sujanani and R. D. C. Monteiro. An adaptive superfast inexact proximal augmented Lagrangian method for smooth nonconvex composite optimization problems. Journal of Scientific Computing , 97 (2):34, 2023

    work page 2023

  54. [54]

    Sun and X

    K. Sun and X. A. Sun. Dual descent augmented Lagrangian method and alternating direction method of multipliers. SIAM Journal on Optimization , 34(2):1679–1707, 2024

    work page 2024

  55. [55]

    Themelis and P

    A. Themelis and P. Patrinos. Douglas–Rachford splitting and ADMM for nonconvex optimization: Tight convergence results. SIAM Journal on Optimization , 30(1):149–181, 2020

    work page 2020

  56. [56]

    Y. Wang, W. Yin, and J. Zeng. Global convergence of ADMM in nonconvex nonsmooth optimization. Journal of Scientific Computing , 78(1):29–63, 2019

    work page 2019

  57. [57]

    Y. Xu. Iteration complexity of inexact augmented Lagrangian methods for constrained convex program- ming. Mathematical Programming, 185:199–244, 2021

    work page 2021

  58. [58]

    J. Zeng, W. Yin, and D. Zhou. Moreau envelope augmented Lagrangian method for nonconvex opti- mization with linear constraints. J. Scientific Comp. , 91(61), 2022

    work page 2022

  59. [59]

    Zhang and Z.-Q

    J. Zhang and Z.-Q. Luo. A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization. SIAM Journal on Optimization , 30(3):2272–2302, 2020

    work page 2020

  60. [60]

    Zhang and Z.-Q

    J. Zhang and Z.-Q. Luo. A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization. SIAM Journal on Optimization , 32(3):2319–2346, 2022. 34

    work page 2022