An accelerated inexact dampened augmented Lagrangian method for linearly-constrained nonconvex composite optimization problems

DOI10.1007/S10589-023-00464-5zbMATH Open1519.90186arXiv2110.11151MaRDI QIDQ6097764FDOQ6097764

Authors: Weiwei Kong, Renato D. C. Monteiro 

Publication date: 7 June 2023

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Abstract: This paper proposes and analyzes an accelerated inexact dampened augmented Lagrangian (AIDAL) method for solving linearly-constrained nonconvex composite optimization problems. Each iteration of the AIDAL method consists of: (i) inexactly solving a dampened proximal augmented Lagrangian (AL) subproblem by calling an accelerated composite gradient (ACG) subroutine; (ii) applying a dampened and under-relaxed Lagrange multiplier update; and (iii) using a novel test to check whether the penalty parameter of the AL function should be increased. Under several mild assumptions involving the dampening factor and the under-relaxation constant, it is shown that the AIDAL method generates an approximate stationary point of the constrained problem in $calO(varepsilo{n}^{-5/2}logvarepsilo{n}^{-1})$ iterations of the ACG subroutine, for a given tolerance $varepsilon>0$. Numerical experiments are also given to show the computational efficiency of the proposed method.

Full work available at URL: https://arxiv.org/abs/2110.11151

Recommendations

• An adaptive superfast inexact proximal augmented Lagrangian method for smooth nonconvex composite optimization problems
• Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs
• On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
• An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems
• Constrained composite optimization and augmented Lagrangian methods

zbMATH Keywords

iteration complexityinexact proximal augmented Lagrangian methodinner accelerated first-order methodslinearly constrained smooth nonconvex composite programs

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Nonconvex programming, global optimization (90C26)

Cites Work

• Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs
• Convex Analysis
• A first-order smoothed penalty method for compressed sensing
• Iteration-complexity of first-order penalty methods for convex programming
• An adaptive accelerated first-order method for convex optimization
• A first-order augmented Lagrangian method for compressed sensing
• A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization
• Iteration-complexity of first-order augmented Lagrangian methods for convex programming
• Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming
• Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization
• Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems
• Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
• Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization
• Stochastic first-order methods for convex and nonconvex functional constrained optimization
• On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
• An Accelerated Inexact Proximal Point Method for Solving Nonconvex-Concave Min-Max Problems
• An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems
• Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
• Iteration Complexity of an Inner Accelerated Inexact Proximal Augmented Lagrangian Method Based on the Classical Lagrangian Function

Cited In (11)

• Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs
• Global Complexity Bound of a Proximal ADMM for Linearly Constrained Nonseparable Nonconvex Composite Programming
• On the complexity of an augmented Lagrangian method for nonconvex optimization
• On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
• An adaptive superfast inexact proximal augmented Lagrangian method for smooth nonconvex composite optimization problems
• Iteration Complexity of a Proximal Augmented Lagrangian Method for Solving Nonconvex Composite Optimization Problems with Nonlinear Convex Constraints
• Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints
• Optimal inexactness schedules for tunable oracle-based methods
• An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimization
• An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems
• Constrained composite optimization and augmented Lagrangian methods

This page was built for publication: An accelerated inexact dampened augmented Lagrangian method for linearly-constrained nonconvex composite optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6097764)