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

DOI10.1007/S10589-023-00464-5MaRDI QIDQ6097764zbMATH OpenFDO

Authors Weiwei Kong, Renato D. C. Monteiro

Publication date 7 June 2023

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

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

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)

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.

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

Cites work

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

Cited in

(11)

• Constrained composite optimization and augmented Lagrangian methods
• 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
• Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints
• Iteration Complexity of a Proximal Augmented Lagrangian Method for Solving Nonconvex Composite Optimization Problems with Nonlinear Convex 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

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)