# Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints arXiv: https://arxiv.org/abs/2311.09065 ยท HTML: https://mlsanity.com/paper/2311.09065/ ## Key facts - Cited by 2 papers in the map (data through 14 Oct 2026). - Builds on 38 of its 66 references that are in the map. - First posted on arXiv 15 Nov 2023. ## Builds on (most cited first, 30 of 38) - [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013) - [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018) - [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016) - [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013) - [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016) - [Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functions](https://mlsanity.com/paper/1802.02988/) (2018) - [Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems](https://mlsanity.com/paper/1707.03505/) (2017) - [Recent Theoretical Advances in Non-Convex Optimization](https://mlsanity.com/paper/2012.06188/) (2020) - [An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints](https://mlsanity.com/paper/1906.11357/) (2019) - [Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming](https://mlsanity.com/paper/1711.05812/) (2017) - [Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization](https://mlsanity.com/paper/2007.01284/) (2020) - [On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1806.04781/) (2018) - [Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs](https://mlsanity.com/paper/1802.03504/) (2018) - [A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization](https://mlsanity.com/paper/1812.10229/) (2018) - [Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis](https://mlsanity.com/paper/1605.02408/) (2016) - [A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization](https://mlsanity.com/paper/2006.16440/) (2020) - [Primal-dual stochastic gradient method for convex programs with many functional constraints](https://mlsanity.com/paper/1802.02724/) (2018) - [Mirror Descent and Convex Optimization Problems With Non-Smooth Inequality Constraints](https://mlsanity.com/paper/1710.06612/) (2017) - [Moreau Envelope Augmented Lagrangian Method for Nonconvex Optimization with Linear Constraints](https://mlsanity.com/paper/2101.08519/) (2021) - [First-order methods for constrained convex programming based on linearized augmented Lagrangian function](https://mlsanity.com/paper/1711.08020/) (2017) - [Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter](https://mlsanity.com/paper/1702.00763/) (2017) - [Complexity of first order inexact Lagrangian and penalty methods for conic convex programming](https://mlsanity.com/paper/1506.05320/) (2015) - [On the non-ergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming](https://mlsanity.com/paper/1603.05738/) (2016) - [Iteration complexity of first-order augmented Lagrangian methods for convex conic programming](https://mlsanity.com/paper/1803.09941/) (2018) - [A Simple Parallel Algorithm with an O(1/t) Convergence Rate for General Convex Programs](https://mlsanity.com/paper/1512.08370/) (2015) - [Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications](https://mlsanity.com/paper/1604.00543/) (2016) - [Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems](https://mlsanity.com/paper/2006.08048/) (2020) - [Iteration-complexity of a proximal augmented Lagrangian method for solving nonconvex composite optimization problems with nonlinear convex constraints](https://mlsanity.com/paper/2008.07080/) (2020) - [Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization](https://mlsanity.com/paper/1505.03175/) (2015) - [Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs](https://mlsanity.com/paper/1705.07229/) (2017) ## Built on by (most cited first, 2 of 2) - [Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions](https://mlsanity.com/paper/2502.19764/) (2025) - [Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity](https://mlsanity.com/paper/2607.08954/) (2026) ## 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.