Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
From MaRDI portal
Abstract: Motivated by big data applications, first-order methods have been extremely popular in recent years. However, naive gradient methods generally converge slowly. Hence, much efforts have been made to accelerate various first-order methods. This paper proposes two accelerated methods towards solving structured linearly constrained convex programming, for which we assume composite convex objective. The first method is the accelerated linearized augmented Lagrangian method (LALM). At each update to the primal variable, it allows linearization to the differentiable function and also the augmented term, and thus it enables easy subproblems. Assuming merely weak convexity, we show that LALM owns convergence if parameters are kept fixed during all the iterations and can be accelerated to if the parameters are adapted, where is the number of total iterations. The second method is the accelerated linearized alternating direction method of multipliers (LADMM). In addition to the composite convexity, it further assumes two-block structure on the objective. Different from classic ADMM, our method allows linearization to the objective and also augmented term to make the update simple. Assuming strong convexity on one block variable, we show that LADMM also enjoys convergence with adaptive parameters. This result is a significant improvement over that in [Goldstein et. al, SIIMS'14], which requires strong convexity on both block variables and no linearization to the objective or augmented term. Numerical experiments are performed on quadratic programming, image denoising, and support vector machine. The proposed accelerated methods are compared to nonaccelerated ones and also existing accelerated methods. The results demonstrate the validness of acceleration and superior performance of the proposed methods over existing ones.
Recommendations
- An accelerated linearized alternating direction method of multipliers
- An accelerated augmented Lagrangian method for linearly constrained convex programming with the rate of convergence \(O\left({1/{k^2}} \right)\)
- Fast first-order methods for minimizing convex composite functions
- An accelerated proximal augmented Lagrangian method and its application in compressive sensing
- Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems
Cites work
- A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
- A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
- 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 New Alternating Minimization Algorithm for Total Variation Image Reconstruction
- A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
- A variational perspective on accelerated methods in optimization
- Accelerated Bregman method for linearly constrained \(\ell _1-\ell _2\) minimization
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Accelerated linearized Bregman method
- Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
- Accelerated, parallel, and proximal coordinate descent
- Adaptive restart for accelerated gradient schemes
- An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems
- An accelerated linearized alternating direction method of multipliers
- An optimal method for stochastic composite optimization
- Excessive Gap Technique in Nonsmooth Convex Minimization
- Fast alternating direction optimization methods
- Fast alternating linearization methods for minimizing the sum of two convex functions
- Gradient methods for minimizing composite functions
- 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 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Inexact accelerated augmented Lagrangian methods
- On the global and linear convergence of the generalized alternating direction method of multipliers
- On the linear convergence of the alternating direction method of multipliers
- Optimal primal-dual methods for a class of saddle point problems
- Proximal gradient method for huberized support vector machine
- Smooth minimization of non-smooth functions
Cited in
(59)- Distributed adaptive dynamic programming for data-driven optimal control
- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- Two proximal splitting methods for multi-block separable programming with applications to stable principal component pursuit
- Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
- Acceleration of primal-dual methods by preconditioning and simple subproblem procedures
- Iteration complexity analysis of a partial LQP-based alternating direction method of multipliers
- An inexact symmetric ADMM algorithm with indefinite proximal term for sparse signal recovery and image restoration problems
- Fast primal-dual algorithm via dynamical system for a linearly constrained convex optimization problem
- On lower iteration complexity bounds for the convex concave saddle point problems
- Proportional-integral projected gradient method for conic optimization
- Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems
- Convergence analysis on an accelerated proximal point algorithm for linearly constrained optimization problems
- Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
- Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
- An adaptive primal-dual framework for nonsmooth convex minimization
- Analysis of fully preconditioned alternating direction method of multipliers with relaxation in Hilbert spaces
- Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
- An accelerated augmented Lagrangian method for linearly constrained convex programming with the rate of convergence \(O\left({1/{k^2}} \right)\)
- MAGMA: multilevel accelerated gradient mirror descent algorithm for large-scale convex composite minimization
- Fast first-order methods for composite convex optimization with backtracking
- Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
- Proximal ADMM with larger step size for two-block separable convex programming and its application to the correlation matrices calibrating problems
- Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
- Fast first-order methods for minimizing convex composite functions
- Accelerated dual-averaging primal–dual method for composite convex minimization
- A primal-dual flow for affine constrained convex optimization
- 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
- A new Lagrangian-based first-order method for nonconvex constrained optimization
- Inexact generalized ADMM with relative error criteria for linearly constrained convex optimization problems
- Accelerated primal-dual methods with adaptive parameters for composite convex optimization with linear constraints
- Distributed event-triggered algorithm for convex optimization with coupled constraints
- Non-ergodic convergence rate of an inertial accelerated primal-dual algorithm for saddle point problems
- O(1/k^2) convergence rates of (dual-primal) balanced augmented Lagrangian methods for linearly constrained convex programming
- Inertial accelerated augmented Lagrangian algorithms with scaling coefficients to solve exactly and inexactly linearly constrained convex optimization problems
- Exploring new frontiers in vertical federated learning: the role of saddle point reformulation
- An inexact linearized augmented Lagrangian method for the linearly composite convex programming
- Linearized alternating direction method of multipliers with adaptive stepsize
- Convergence analysis of the indefinite proximal augmented Lagrange method under strongly convex conditions
- A practical and optimal first-order method for large-scale convex quadratic programming
- Fast primal-dual algorithm with Tikhonov regularization for a linear equality constrained convex optimization problem
- Accelerated primal-dual methods for strongly convex objective functions in continuous and discrete time
- Fast reflected forward-backward algorithm: achieving fast convergence rates for convex optimization with linear cone constraints
- Exponential convergence rates of a second-order dynamic system and algorithm for a linear equality constrained optimization problem
- Revisiting parallel splitting augmented Lagrangian method: tight convergence and ergodic convergence rate
- 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
- A fast primal-dual algorithm via dynamical system with variable mass for linearly constrained convex optimization
- An indefinite proximal Peaceman-Rachford splitting method-based algorithm integrating the generalization acceleration technique for separable convex programming problems in image restoration
- Accelerating preconditioned ADMM via degenerate proximal point mappings
- An inexact symmetric proximal ADMM with convex combination proximal centers for separable convex programming
- An improved proximal primal-dual ALM-based algorithm with convex combination proximal centers for equality-constrained convex programming in basis pursuit practical problems
- Hypodifferentials of nonsmooth convex functions and their applications to nonsmooth convex optimization
- Inertial accelerated primal-dual algorithms for non-smooth convex optimization problems with linear equality constraints
- On the O(1/K^2) ergodic convergence of ADMM with dual step size from 0 to 2
- Accelerated linearized alternating direction method of multipliers with Nesterov extrapolation
- The augmented Lagrangian methods: overview and recent advances
- Survey on first-order algorithms for solving functional constrained optimization problems
This page was built for publication: Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4976160)
