Faster Lagrangian-based methods in convex optimization
From MaRDI portal
Abstract: In this paper, we aim at unifying, simplifying and improving the convergence rate analysis of Lagrangian-based methods for convex optimization problems. We first introduce the notion of nice primal algorithmic map, which plays a central role in the unification and in the simplification of the analysis of most Lagrangian-based methods. Equipped with a nice primal algorithmic map, we then introduce a versatile generic scheme, which allows for the design and analysis of Faster LAGrangian (FLAG) methods with new provably sublinear rate of convergence expressed in terms of function values and feasibility violation of the original (non-ergodic) generated sequence. To demonstrate the power and versatility of our approach and results, we show that most well-known iconic Lagrangian-based schemes admit a nice primal algorithmic map, and hence share the new faster rate of convergence results within their corresponding FLAG.
Recommendations
- Fast augmented Lagrangian method in the convex regime with convergence guarantees for the iterates
- Lagrangian methods for composite optimization
- Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization
- Convergence analysis of augmented Lagrangian-fast projected gradient method for convex quadratic problems
- Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming
Cites work
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A proximal-based deomposition method for compositions method for convex minimization problems
- Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis
- Accelerated optimization for machine learning. First-order algorithms. With forewords by Michael I. Jordan, Zongben Xu and Zhi-Quan Luo
- An introduction to continuous optimization for imaging
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Convex Analysis
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- scientific article; zbMATH DE number 3833218 (Why is no real title available?)
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 3309655 (Why is no real title available?)
- Interior Gradient and Proximal Methods for Convex and Conic Optimization
- Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
- Iteration-complexity of first-order augmented Lagrangian methods for convex programming
- Lagrangian methods for composite optimization
- Monotone Operators and the Proximal Point Algorithm
- Multiplier and gradient methods
- On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming
- On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers
- On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
Cited in
(24)- GRPDA revisited: relaxed condition and connection to Chambolle-Pock's primal-dual algorithm
- A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm
- Superfast second-order methods for unconstrained convex optimization
- Lagrangian methods for composite optimization
- scientific article; zbMATH DE number 16627 (Why is no real title available?)
- New primal-dual algorithms for a class of nonsmooth and nonlinear convex-concave minimax problems
- A primal-dual flow for affine constrained convex optimization
- Fast convex optimization via a third-order in time evolution equation
- Reducing the Complexity of Two Classes of Optimization Problems by Inexact Accelerated Proximal Gradient Method
- Fast augmented Lagrangian method in the convex regime with convergence guarantees for the iterates
- A golden ratio proximal alternating direction method of multipliers for separable convex optimization
- From the simplex to the sphere: faster constrained optimization using the Hadamard parametrization
- Accelerated primal-dual methods with adaptive parameters for composite convex optimization with linear constraints
- The exact worst-case convergence rate of the alternating direction method of multipliers
- Non-ergodic convergence rate of an inertial accelerated primal-dual algorithm for saddle point problems
- Exact Lipschitz regularization of convex optimization problems
- Inertial accelerated augmented Lagrangian algorithms with scaling coefficients to solve exactly and inexactly linearly constrained convex optimization problems
- A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate
- An accelerated semi-proximal ADMM with applications to multi-block sparse optimization problems
- Accelerating preconditioned ADMM via degenerate proximal point mappings
- 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
- The augmented Lagrangian methods: overview and recent advances
- A new insight on the prediction-correction framework with applications to several first-order methods
This page was built for publication: Faster Lagrangian-based methods in convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5062120)
