Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
From MaRDI portal
Abstract: Augmented Lagrangian method (ALM) has been popularly used for solving constrained optimization problems. Practically, subproblems for updating primal variables in the framework of ALM usually can only be solved inexactly. The convergence and local convergence speed of ALM have been extensively studied. However, the global convergence rate of inexact ALM is still open for problems with nonlinear inequality constraints. In this paper, we work on general convex programs with both equality and inequality constraints. For these problems, we establish the global convergence rate of inexact ALM and estimate its iteration complexity in terms of the number of gradient evaluations to produce a solution with a specified accuracy. We first establish an ergodic convergence rate result of inexact ALM that uses constant penalty parameters or geometrically increasing penalty parameters. Based on the convergence rate result, we apply Nesterov's optimal first-order method on each primal subproblem and estimate the iteration complexity of the inexact ALM. We show that if the objective is convex, then gradient evaluations are sufficient to guarantee an -optimal solution in terms of both primal objective and feasibility violation. If the objective is strongly convex, the result can be improved to . Finally, by relating to the inexact proximal point algorithm, we establish a nonergodic convergence rate result of inexact ALM that uses geometrically increasing penalty parameters. We show that the nonergodic iteration complexity result is in the same order as that for the ergodic result. Numerical experiments on quadratically constrained quadratic programming are conducted to compare the performance of the inexact ALM with different settings.
Recommendations
- On the convergence of inexact augmented Lagrangian methods for problems with convex constraints
- Iteration-Complexity of First-Order Augmented Lagrangian Methods for Convex Conic Programming
- Iteration-complexity of first-order augmented Lagrangian methods for convex programming
- Inexact accelerated augmented Lagrangian methods
- On the complexity of an augmented Lagrangian method for nonconvex optimization
Cites work
- A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
- A dual approach to solving nonlinear programming problems by unconstrained optimization
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A simple parallel algorithm with an \(O(1/t)\) convergence rate for general convex programs
- Accelerated Bregman method for linearly constrained \(\ell _1-\ell _2\) minimization
- Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
- Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
- An accelerated linearized alternating direction method of multipliers
- Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods
- Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Computational complexity of inexact gradient augmented Lagrangian methods: application to constrained MPC
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Gradient methods for minimizing composite functions
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 3309655 (Why is no real title available?)
- Inexact accelerated augmented Lagrangian methods
- Introductory lectures on convex optimization. A basic course.
- Iteration complexity analysis of multi-block ADMM for a family of convex minimization without strong convexity
- Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
- Iteration-complexity of first-order augmented Lagrangian methods for convex programming
- Multiplier and gradient methods
- New Proximal Point Algorithms for Convex Minimization
- Nonlinear Programming
- Numerical comparison of augmented Lagrangian algorithms for nonconvex problems
- On alternating direction methods of multipliers: a historical perspective
- On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
- On the convergence of the exponential multiplier method for convex programming
- On the Convergence of the Proximal Point Algorithm for Convex Minimization
- On the global and linear convergence of the generalized alternating direction method of multipliers
- On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
- Penalty/Barrier Multiplier Methods for Convex Programming Problems
- Randomized primal-dual proximal block coordinate updates
- Rate Analysis of Inexact Dual First-Order Methods Application to Dual Decomposition
- Subgradient methods for saddle-point problems
- The multiplier method of Hestenes and Powell applied to convex programming
Cited in
(49)- Adaptive primal-dual stochastic gradient method for expectation-constrained convex stochastic programs
- Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints
- Augmented Lagrangian optimization under fixed-point arithmetic
- An adaptive primal-dual framework for nonsmooth convex minimization
- On the convergence of inexact augmented Lagrangian methods for problems with convex constraints
- scientific article; zbMATH DE number 5077058 (Why is no real title available?)
- New primal-dual algorithms for a class of nonsmooth and nonlinear convex-concave minimax problems
- On the complexity of an augmented Lagrangian method for nonconvex optimization
- First-order methods for problems with \(O(1)\) functional constraints can have almost the same convergence rate as for unconstrained problems
- Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
- Computational complexity of inexact gradient augmented Lagrangian methods: application to constrained MPC
- Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization
- On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
- Reducing the Complexity of Two Classes of Optimization Problems by Inexact Accelerated Proximal Gradient Method
- Iteration Complexity of an Inner Accelerated Inexact Proximal Augmented Lagrangian Method Based on the Classical Lagrangian Function
- Iteration-complexity of first-order augmented Lagrangian methods for convex programming
- An adaptive sampling augmented Lagrangian method for stochastic optimization with deterministic constraints
- An accelerated inexact dampened augmented Lagrangian method for linearly-constrained nonconvex composite optimization problems
- Distributed strategies for mixed equilibrium problems: continuous-time theoretical approaches
- A linear algebra perspective on the random multi-block ADMM: the QP case
- Iteration-Complexity of First-Order Augmented Lagrangian Methods for Convex Conic Programming
- Stochastic inexact augmented Lagrangian method for nonconvex expectation constrained optimization
- An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems
- Variance reduced moving balls approximation method for smooth constrained minimization problems
- Inexact and stochastic generalized conditional gradient with augmented Lagrangian and proximal step
- Accelerated primal-dual methods with adaptive parameters for composite convex optimization with linear constraints
- A proximal augmented Lagrangian method for linearly constrained nonconvex composite optimization problems
- An inexact majorized proximal alternating direction method of multipliers for diffusion tensors
- An augmented Lagrangian method for state constrained linear parabolic optimal control problems
- Optimal inexactness schedules for tunable oracle-based methods
- Nonsmooth projection-free optimization with functional constraints
- Global convergence analysis of the power proximal point and augmented Lagrangian method
- Randomly projected convex clustering model: motivation, realization, and cluster recovery guarantees
- Sparse SVM with hard-margin loss: a Newton-augmented Lagrangian method in reduced dimensions
- ALM-PU: positive and unlabeled learning with constrained optimization
- A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
- Complexity analysis of inexact cubic-regularized primal-dual methods for finding second-order stationary points
- The majorization minimization algorithm for solving nonconvex generalized Nash equilibrium problems
- A smoothed augmented Lagrangian framework for convex optimization with nonsmooth constraints
- Convergence rate of inexact augmented Lagrangian method with practical relative error criterion for composite convex programming
- Mirror descent methods with a weighting scheme for outputs for optimization problems with functional constraints
- A golden ratio primal-dual algorithm for a class of nonsmooth saddle point problems
- An exact penalty function optimization method and its application in stress constrained topology optimization and scenario based reliability design problems
- Faster augmented Lagrangian method with inertial steps for solving convex optimization problems with linear constraints
- Accelerated linearized alternating direction method of multipliers with Nesterov extrapolation
- An adaptive parameter-free and projection-free restarting level set method for constrained convex optimization under the error bound condition
- The augmented Lagrangian methods: overview and recent advances
- Survey on first-order algorithms for solving functional constrained optimization problems
- Inexact accelerated augmented Lagrangian methods
This page was built for publication: Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220658)
