mlsanityData to 7 Oct 2026

Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints

arXiv 2311.09065 ↗First posted 15 Nov 2023math.OC cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

We give a damped proximal augmented Lagrangian method (DPALM) for solving problems with a weakly-convex objective and convex linear/nonlinear constraints. Instead of taking a full stepsize, DPALM adopts a damped dual stepsize to ensure the boundedness of dual iterates. We show that DPALM can produce a (near) vareps-KKT point within O(vareps-2) outer iterations if each DPALM subproblem is solved to a proper accuracy. In addition, we establish overall iteration complexity of DPALM when the objective is either a regularized smooth function or in a regularized compositional form. For the former case, DPALM achieves the complexity of widetildeOleft(varepsilon-2.5 right) to produce an varepsilon-KKT point by applying an accelerated proximal gradient (APG) method to each DPALM subproblem. For the latter case, the complexity of DPALM is widetildeOleft(varepsilon-3 right) to produce a near varepsilon-KKT point by using an APG to solve a Moreau-envelope smoothed version of each subproblem. Our outer iteration complexity and the overall complexity either generalize existing best ones from unconstrained or linear-constrained problems to convex-constrained ones, or improve over the best-known results on solving the same-structured problems. Furthermore, numerical experiments on linearly/quadratically constrained non-convex quadratic programs and linear-constrained robust nonlinear least squares are conducted to demonstrate the empirical efficiency of the proposed DPALM over several state-of-the art methods.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 38 of its 66 references that are in the map. First posted on arXiv 15 Nov 2023.

Builds on

38 of 66 references.

References · 38

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  2. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  3. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  4. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 74
  5. 2016Efficiency of minimizing compositions of convex functions and smooth mapscited by 59
  6. 2018Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functionscited by 31
  7. 2017Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problemscited by 30
  8. 2020Recent Theoretical Advances in Non-Convex Optimizationcited by 30
  9. 2019An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraintscited by 29
  10. 2017Iteration complexity of inexact augmented Lagrangian methods for constrained convex programmingcited by 21
  11. 2020Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimizationcited by 21
  12. 2018On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimizationcited by 18
26 more
  1. 2018Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programscited by 15
  2. 2018A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimizationcited by 14
  3. 2016Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysiscited by 13
  4. 2020A global dual error bound and its application to the analysis of linearly constrained nonconvex optimizationcited by 13
  5. 2018Primal-dual stochastic gradient method for convex programs with many functional constraintscited by 12
  6. 2017Mirror Descent and Convex Optimization Problems With Non-Smooth Inequality Constraintscited by 10
  7. 2021Moreau Envelope Augmented Lagrangian Method for Nonconvex Optimization with Linear Constraintscited by 10
  8. 2017First-order methods for constrained convex programming based on linearized augmented Lagrangian functioncited by 9
  9. 2017Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parametercited by 8
  10. 2015Complexity of first order inexact Lagrangian and penalty methods for conic convex programmingcited by 7
  11. 2016On the non-ergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programmingcited by 7
  12. 2018Iteration complexity of first-order augmented Lagrangian methods for convex conic programmingcited by 7
  13. 2015A Simple Parallel Algorithm with an O(1/t) Convergence Rate for General Convex Programscited by 6
  14. 2016Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applicationscited by 6
  15. 2020Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problemscited by 6
  16. 2020Iteration-complexity of a proximal augmented Lagrangian method for solving nonconvex composite optimization problems with nonlinear convex constraintscited by 6
  17. 2015Adaptive inexact fast augmented Lagrangian methods for constrained convex optimizationcited by 5
  18. 2017Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programscited by 5
  19. 2020First-order methods for problems with O(1) functional constraints can have almost the same convergence rate as for unconstrained problemscited by 4
  20. 2017Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problemscited by 3
  21. 2021An Accelerated Inexact Dampened Augmented Lagrangian Method for Linearly-Constrained Nonconvex Composite Optimization Problemscited by 3
  22. 2013An Inexact Proximal Path-Following Algorithm for Constrained Convex Minimizationcited by 2
  23. 2018Primal-Dual Frank-Wolfe for Constrained Stochastic Programs with Convex and Non-convex Objectivescited by 2
  24. 2018Solving Non-smooth Constrained Programs with Lower Complexity than O(1/varepsilon): A Primal-Dual Homotopy Smoothing Approachcited by 2
  25. 2014A Primal-Dual Algorithmic Framework for Constrained Convex Minimizationcited by 1
  26. 2018Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimizationcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functionscited by 1
  2. 2026Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularitycited by 1