Complexity of Linearized Perturbed Augmented Lagrangian Methods for Nonsmooth Nonconvex Optimization with Nonlinear Equality Constraints
Lahcen El Bourkhissi, Ion Necoara, Panagiotis Patrinos, Quoc Tran-Dinh · 2025
Read Complexity of Linearized Perturbed Augmented Lagrangian Methods for Nonsmooth Nonconvex Optimization with Nonlinear Equality Constraints by Lahcen El Bourkhissi, Ion Necoara, Panagiotis Patrinos, Quoc Tran-Dinh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-01056.txt.
Introduction
Four authors wrote an optimization paper in two thousand twenty-five on hard problems with rough parts and strict equality constraints. Such problems mix smooth pieces with nonsmooth ones and shapes that curve the wrong way, which defeats many solvers. The authors propose a method in the augmented Lagrangian family, with two twists.
The dual variable in the penalty term is scaled down slightly, a perturbation that steadies the method. The smooth parts of the goal and the constraints are linearized at each step, leaving a convex subproblem that is usually easy to solve. A measured ascent step then updates the dual variables. The paper analyzes how fast the method converges.
Catalog record
| CREATOR | Lahcen El Bourkhissi, Ion Necoara, Panagiotis Patrinos, Quoc Tran-Dinh |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 130 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-01056
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Complexity of Linearized Perturbed Augmented Lagrangian Methods for Nonsmooth Nonconvex Optimization with Nonlinear Equality Constraints Lahcen El Bourkhissi, Ion Necoara, Panagiotis Patrinos, Quoc Tran-Dinh Abstract This paper addresses a class of general nonsmooth and nonconvex composite optimization problems subject to nonlinear equality constraints. We assume that a part of the objective function and the functional constraints exhibit local smoothness. To tackle this challenging class of problems, we propose a novel linearized perturbed augmented Lagrangian method. This method incorporates a perturbation in the augmented Lagrangian function by scaling the dual variable with a sub-unitary parameter. Furthermore, we linearize the smooth components of the objective and the constraints within the perturbed Lagrangian function at the current iterate, while preserving the nonsmooth components. This approach, inspired by prox-linear (or Gauss-Newton) methods, results in a convex subproblem that is typically easy to solve. The solution of this subproblem then serves as the next primal iterate, followed by a perturbed ascent step to update the dual variables. Under a newly introduced constraint qualification condition, we establish the boundedness of the dual iterates. We derive convergence guarantees for the primal iterates, proving convergence to an ϵ \epsilon -first-order optimal solution within 𝒪 ( ϵ − 3 ) \mathcal{O}(\epsilon^{-3}) evaluations of the problem’s functions and their first derivatives. Moreover, when the problem exhibits for example a semialgebraic property, we derive improved local convergence results. Finally, we validate the theoretical findings and assess the practical performance of our proposed algorithm through numerical comparisons with existing state-of-the-art methods. \NatBibNumeric \MSCCLASS 90C25, 90C06, 65K05. keywords Nonconvex optimization, nonsmooth objective, nonlinear equality constraints, linearized perturbed augmented Lagrangian, convergence analysis. † † authors: Automatic Control and Systems Engineering Department, Politehnica Bucharest, 060042 Bucharest, Romania, [email protected] Automatic Control and Systems Engineering Department, Politehnica Bucharest, 060042 Bucharest, Romania and Gheorghe Mihoc-Caius Iacob Institute of Mathematical Statistics and Applied Mathematics of the Romanian Academy, 050711 Bucharest, Romania, [email protected] Department of Electrical Engineering, K.U. Leuven, B-3001 Leuven, Belgium, [email protected] Department of Statistics and Operations Research, University of North Carolina at Chapel Hill, NC 27599 Chapel Hill, USA [email protected] † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † history: 2024 1 Introduction. Numerous applications across diverse fields, including statistics, control and signal processing, and machine learning, can be formulated as nonsmooth nonconvex optimization problems subject to nonlinear equality constraints (see, e.g., [ 17 , 22 , 25 ] ). This paper addresses this class of challenging problems by employing a perturbed augmented Lagrangian approach. Originally introduced in [ 16 , 30 ] to minimize functions subject to linear equality constraints, the augmented Lagrangian method, also known as the method of multipliers, has proven to be a powerful tool to develop scalable optimization algorithms. Even in the context of nonconvex problems, it offers several theoretical advantages, such as a zero duality gap and an exact penalty representation (see [ 31 ] ). Furthermore, the augmented Lagrangian framework serves as the foundation for the Alternating Direction Method of Multipliers (ADMM), a highly efficient method for solving large-scale (and distributed) optimization problems, as demonstrated in, e.g., [ 5 , 7 , 9 , 12 ] . Related work. While the augmented Lagrangian method has been extensively applied to convex problems, see [ 2 , 5 , 12 , 25 , 28 ] and non-convex problems with linear equality constraints, see [ 14 , 17 , 18 , 36 ] , its application to non-convex optimization problems with nonlinear equality constraints has been relatively limited (see, e.g., [ 7 , 9 , 15 , 21 , 32 , 33 ] as a few examples). For instance, Hajinezhad and Hong [ 14 ] and Lu [ 21 ] proposed perturbed variants of the augmented Lagrangian method. This approach introduces a geometric perturbation of the dual variables, controlled by a coefficient 1-\tau\in(0,1) . Notably, these perturbed methods can be viewed as an interpolation between the standard augmented Lagrangian method (when 1-\tau\to 1 ) and the quadratic penalty method (when 1-\tau\to 0 ). More specifically, Hajinezhad and Hong in [ 14 ] introduced a perturbed augmented Lagrangian method for solving linearly constrained optimization problems. These problems involve a composite objective function consisting of a smooth (potentially nonconvex) component and a convex (nonsmooth but Lipschitz) component, along with simple constraints. Their method employed a primal metric proximal gradient step followed by a perturbed dual gradient ascent step. Under appropriate conditions, including a penalty parameter of order \mathcal{O}(\epsilon^{-1}) , the authors demonstrated that this method achieves an \epsilon -first-order optimal solution with a complexity of \mathcal{O}(\epsilon^{-4}) for a free perturbation parameter 1-\tau . Furthermore, for problems involving nonconvex inequality constraints, a smooth objective function, and simple set constraints, Lu in [ 21 ] proposed a perturbed augmented Lagrangian method. This method linearizes the nonlinear constraints within the perturbed augmented Lagrangian function during the primal update, followed by a perturbed dual update. The author established a convergence rate of \mathcal{O}(\epsilon^{-3}) for finding an \epsilon -first-order solution when the penalty parameter is set to \mathcal{O}(\epsilon^{-1}) and the perturbation parameter 1-\tau is below a small threshold. This parameter choice makes the method resemble more closely a quadratic penalty approach than a traditional augmented Lagrangian approach. However, the definition of an \epsilon -first-order solution presented by the author is questionable; while feasibility is ensured at the proposed point, the satisfaction of the optimality condition remains unclear. This ambiguity arises particularly from the vagueness and lack of clear justification for inequality (263) in [ 21 ] . In [ 15 ] , an adaptive augmented Lagrangian method was employed to tackle a class of nonconvex optimization problems characterized by nonsmoothness and a nonlinear functional composite structure in the objective function. To address this structure, a slack variable was introduced, transforming the original problem into one with a nonsmooth objective and nonlinear equality constraints. This reformulation involves two sets of variables: the original variables and the newly introduced slack variables. Notably, when considering these two variable sets collectively, their problem can be viewed as a specific instance of the problem addressed in this paper. The authors in [ 15 ] then applied an ADMM scheme to solve the reformulated problem. This approach involves linearizing the smooth component of the augmented Lagrangian function at each iteration, resulting in proximal updates for each step of the algorithm. Under the assumption of bounded dual multipliers – specifically, assuming that there exists a constant M>0 such that \|y^{k}\|\leq M for all iterations k – their method achieves an \epsilon -first-order optimal solution with a complexity of \mathcal{O}(\epsilon^{-2}) . However, to ensure that the iterates remain \epsilon -feasible after a certain number of iterations, it is crucial that the penalty parameter \rho_{k} satisfies the condition \rho_{k}\geq\frac{2M}{\epsilon} . Consequently, based on the proof of Theorem 2 in [ 15 ] , the overall complexity of their method is ultimately \mathcal{O}(\epsilon^{-4}) . Furthermore, Sahin et al. [ 32 ] addressed the inexact solution of the augmented Lagrangian subproblem and incorporated a decreasing stepsize for updating the dual multipliers to ensure the boundedness of these multipliers. Their analysis established a total complexity of \mathcal{O}(\epsilon^{-4}) for their inexact augmented Lagrangian method (iALM) to