Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints

DOI10.1007/S10915-022-01815-WzbMATH Open1494.90091arXiv2101.08519OpenAlexW3125897846MaRDI QIDQ2148118FDOQ2148118

Authors: Jinshan Zeng, Wotao Yin, Ding-Xuan Zhou 

Publication date: 21 June 2022

Published in: Journal of Scientific Computing (Search for Journal in Brave)

Abstract: The augmented Lagrangian method (ALM) is one of the most useful methods for constrained optimization. Its convergence has been well established under convexity assumptions or smoothness assumptions, or under both assumptions. ALM may experience oscillations and divergence when the underlying problem is simultaneously nonconvex and nonsmooth. In this paper, we consider the linearly constrained problem with a nonconvex (in particular, weakly convex) and nonsmooth objective. We modify ALM to use a Moreau envelope of the augmented Lagrangian and establish its convergence under conditions that are weaker than those in the literature. We call it the Moreau envelope augmented Lagrangian (MEAL) method. We also show that the iteration complexity of MEAL is $o(varepsilo{n}^{-2})$ to yield an $varepsilon$-accurate first-order stationary point. We establish its whole sequence convergence (regardless of the initial guess) and a rate when a Kurdyka-Lojasiewicz property is assumed. Moreover, when the subproblem of MEAL has no closed-form solution and is difficult to solve, we propose two practical variants of MEAL, an inexact version called iMEAL with an approximate proximal update, and a linearized version called LiMEAL for the constrained problem with a composite objective. Their convergence is also established.

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

Recommendations

• An alternating augmented Lagrangian method for constrained nonconvex optimization
• An accelerated inexact dampened augmented Lagrangian method for linearly-constrained nonconvex composite optimization problems
• On the complexity of an augmented Lagrangian method for nonconvex optimization
• On the convergence of inexact augmented Lagrangian methods for problems with convex constraints
• Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming

zbMATH Keywords

augmented Lagrangian methodMoreau envelopenonconvex nonsmooth optimizationproximal augmented Lagrangian methodKurdyka-Łojasiewicz inequality

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Cites Work

• Practical augmented Lagrangian methods for constrained optimization
• Nearly unbiased variable selection under minimax concave penalty
• Numerical Optimization
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Title not available (Why is that?)
• Variational Analysis
• Title not available (Why is that?)
• Multiplier and gradient methods
• Title not available (Why is that?)
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Global minimization using an augmented Lagrangian method with variable lower-level constraints
• Second-order negative-curvature methods for box-constrained and general constrained optimization
• Augmented Lagrangian methods under the constant positive linear dependence constraint qualification
• Numerical comparison of augmented Lagrangian algorithms for nonconvex problems
• The multiplier method of Hestenes and Powell applied to convex programming
• A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
• The boundedness of penalty parameters in an augmented Lagrangian method with constrained subproblems
• A Globally Convergent Augmented Lagrangian Algorithm for Optimization with General Constraints and Simple Bounds
• Clarke Subgradients of Stratifiable Functions
• On Augmented Lagrangian Methods with General Lower-Level Constraints
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Title not available (Why is that?)
• Trust Region Methods
• Convergence Properties of an Augmented Lagrangian Algorithm for Optimization with a Combination of General Equality and Linear Constraints
• Proximité et dualité dans un espace hilbertien
• On semi- and subanalytic geometry
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Title not available (Why is that?)
• Title not available (Why is that?)
• On gradients of functions definable in o-minimal structures
• Geometry of subanalytic and semialgebraic sets
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
• Parallel multi-block ADMM with \(o(1/k)\) convergence
• Local convergence of exact and inexact augmented Lagrangian methods under the second-order sufficient optimality condition
• A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization
• On Penalty and Multiplier Methods for Constrained Minimization
• An adaptive augmented Lagrangian method for large-scale constrained optimization
• A globally and quadratically convergent primal–dual augmented Lagrangian algorithm for equality constrained optimization
• Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
• Global convergence of ADMM in nonconvex nonsmooth optimization
• Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
• Convergence properties of a second order augmented Lagrangian method for mathematical programs with complementarity constraints
• Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points
• Universality of deep convolutional neural networks
• Complexity and performance of an augmented Lagrangian algorithm
• The method of penalty estimates for conditional extremum problems
• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• On Nonconvex Decentralized Gradient Descent
• A sequential optimality condition related to the quasi-normality constraint qualification and its algorithmic consequences
• Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization
• Stochastic model-based minimization of weakly convex functions
• Efficiency of minimizing compositions of convex functions and smooth maps
• Kurdyka-Łojasiewicz exponent via inf-projection
• Title not available (Why is that?)

Cited In (6)

• An adaptive superfast inexact proximal augmented Lagrangian method for smooth nonconvex composite optimization problems
• Study on \(L_1\) over \(L_2\) Minimization for nonnegative signal recovery
• Block coordinate type methods for optimization and learning
• High probability bounds on AdaGrad for constrained weakly convex optimization
• A framelet sparse reconstruction method for pansharpening with guaranteed convergence
• Dual descent augmented Lagrangian method and alternating direction method of multipliers

Uses Software

• ALGENCAN

This page was built for publication: Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints

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