Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints
From MaRDI portal
Publication:2148118
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 to yield an -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.
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
Cites work
- A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
- A globally and quadratically convergent primal–dual augmented Lagrangian algorithm for equality constrained optimization
- A Globally Convergent Augmented Lagrangian Algorithm for Optimization with General Constraints and Simple Bounds
- A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization
- A sequential optimality condition related to the quasi-normality constraint qualification and its algorithmic consequences
- An adaptive augmented Lagrangian method for large-scale constrained optimization
- Augmented Lagrangian methods under the constant positive linear dependence constraint qualification
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points
- Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
- Clarke Subgradients of Stratifiable Functions
- Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
- Complexity and performance of an augmented Lagrangian algorithm
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Convergence properties of a second order augmented Lagrangian method for mathematical programs with complementarity constraints
- Convergence Properties of an Augmented Lagrangian Algorithm for Optimization with a Combination of General Equality and Linear Constraints
- Efficiency of minimizing compositions of convex functions and smooth maps
- Geometry of subanalytic and semialgebraic sets
- Global convergence of ADMM in nonconvex nonsmooth optimization
- Global minimization using an augmented Lagrangian method with variable lower-level constraints
- scientific article; zbMATH DE number 1817650 (Why is no real title available?)
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 1201576 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 7626714 (Why is no real title available?)
- scientific article; zbMATH DE number 3309655 (Why is no real title available?)
- scientific article; zbMATH DE number 3371284 (Why is no real title available?)
- Kurdyka-Łojasiewicz exponent via inf-projection
- Local convergence of exact and inexact augmented Lagrangian methods under the second-order sufficient optimality condition
- Multiplier and gradient methods
- Nearly unbiased variable selection under minimax concave penalty
- Numerical comparison of augmented Lagrangian algorithms for nonconvex problems
- Numerical Optimization
- On Augmented Lagrangian Methods with General Lower-Level Constraints
- On gradients of functions definable in o-minimal structures
- On Nonconvex Decentralized Gradient Descent
- On Penalty and Multiplier Methods for Constrained Minimization
- On semi- and subanalytic geometry
- On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
- Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
- Parallel multi-block ADMM with \(o(1/k)\) convergence
- Perturbed proximal primal-dual algorithm for nonconvex nonsmooth optimization
- Practical augmented Lagrangian methods for constrained optimization
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- Proximité et dualité dans un espace hilbertien
- Second-order negative-curvature methods for box-constrained and general constrained optimization
- Stochastic model-based minimization of weakly convex functions
- Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
- The boundedness of penalty parameters in an augmented Lagrangian method with constrained subproblems
- The method of penalty estimates for conditional extremum problems
- The multiplier method of Hestenes and Powell applied to convex programming
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
- Trust Region Methods
- Universality of deep convolutional neural networks
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
- Variational Analysis
Cited in
(13)- Block coordinate type methods for optimization and learning
- 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
- A framelet sparse reconstruction method for pansharpening with guaranteed convergence
- Dual descent augmented Lagrangian method and alternating direction method of multipliers
- High probability bounds on AdaGrad for constrained weakly convex optimization
- A note on the KL property of the augmented Lagrangian for conic programming
- Wasserstein gradient flows for Moreau envelopes of f-divergences in reproducing kernel Hilbert spaces
- Full splitting algorithms for fractional programs with structured numerators and denominators
- An accelerated semi-proximal ADMM with applications to multi-block sparse optimization problems
- First-order methods for nonsmooth nonconvex functional constrained optimization with or without Slater points
- An improved proximal primal-dual ALM-based algorithm with convex combination proximal centers for equality-constrained convex programming in basis pursuit practical problems
- Blind hyperspectral and multispectral images fusion: a unified tensor fusion framework from coupled inverse problem perspective
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)
