An adaptive primal-dual framework for nonsmooth convex minimization
From MaRDI portal
Publication:2220901
DOI10.1007/S12532-019-00173-3zbMATH Open1452.90246arXiv1808.04648OpenAlexW2983683136WikidataQ126855440 ScholiaQ126855440MaRDI QIDQ2220901FDOQ2220901
Authors: Ahmet Alacaoglu, Olivier Fercoq, Volkan Cevher, Quoc Tran Dinh 
Publication date: 25 January 2021
Published in: Mathematical Programming Computation (Search for Journal in Brave)
Abstract: We propose a new self-adaptive, double-loop smoothing algorithm to solve composite, nonsmooth, and constrained convex optimization problems. Our algorithm is based on Nesterov's smoothing technique via general Bregman distance functions. It self-adaptively selects the number of iterations in the inner loop to achieve a desired complexity bound without requiring the accuracy a priori as in variants of Augmented Lagrangian methods (ALM). We prove -convergence rate on the last iterate of the outer sequence for both unconstrained and constrained settings in contrast to ergodic rates which are common in ALM as well as alternating direction method-of-multipliers literature. Compared to existing inexact ALM or quadratic penalty methods, our analysis does not rely on the worst-case bounds of the subproblem solved by the inner loop. Therefore, our algorithm can be viewed as a restarting technique applied to the ASGARD method in cite{TranDinh2015b} but with rigorous theoretical guarantees or as an inexact ALM with explicit inner loop termination rules and adaptive parameters. Our algorithm only requires to initialize the parameters once, and automatically update them during the iteration process without tuning. We illustrate the superiority of our methods via several examples as compared to the state-of-the-art.
Full work available at URL: https://arxiv.org/abs/1808.04648
Recommendations
- Adaptive smoothing algorithms for nonsmooth composite convex minimization
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- New primal-dual algorithms for a class of nonsmooth and nonlinear convex-concave minimax problems
- Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization
- Smoothing alternating direction methods for fully nonsmooth constrained convex optimization
augmented Lagrangiannonsmooth convex optimizationself-adaptive methodrestartingprimal-dual first-order methods
Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Cites Work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- Title not available (Why is that?)
- Smooth minimization of non-smooth functions
- Adaptive restart for accelerated gradient schemes
- On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
- Title not available (Why is that?)
- Excessive Gap Technique in Nonsmooth Convex Minimization
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Compressed sensing
- Multiplier and gradient methods
- Proximal splitting methods in signal processing
- A first-order primal-dual algorithm for convex problems with applications to imaging
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Proximal Minimization Methods with Generalized Bregman Functions
- Application of a Smoothing Technique to Decomposition in Convex Optimization
- Computational complexity of inexact gradient augmented Lagrangian methods: application to constrained MPC
- Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers
- Iteration-complexity of first-order penalty methods for convex programming
- A splitting algorithm for dual monotone inclusions involving cocoercive operators
- Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
- Convex functions. Constructions, characterizations and counterexamples
- A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
- Atomic decomposition by basis pursuit
- Sparse and stable Markowitz portfolios
- Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
- Convex analysis and monotone operator theory in Hilbert spaces
- Double smoothing technique for large-scale linearly constrained convex optimization
- Smoothing and first order methods: a unified framework
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
- A double smoothing technique for solving unconstrained nondifferentiable convex optimization problems
- A variable smoothing algorithm for solving convex optimization problems
- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming
- Title not available (Why is that?)
- Iteration-complexity of first-order augmented Lagrangian methods for convex programming
- Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming
- A note on the convergence of ADMM for linearly constrained convex optimization problems
- Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
- An accelerated linearized alternating direction method of multipliers
- Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
- First-order algorithms for convex optimization with nonseparable objective and coupled constraints
- Accelerated alternating direction method of multipliers: an optimal \(O(1 / K)\) nonergodic analysis
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- Title not available (Why is that?)
- Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming
Cited In (23)
- Convergence properties of a randomized primal-dual algorithm with applications to parallel MRI
- An inexact proximal path-following algorithm for constrained convex minimization
- New primal-dual algorithms for a class of nonsmooth and nonlinear convex-concave minimax problems
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- Adaptive Catalyst for Smooth Convex Optimization
- Forward-reflected-backward method with variance reduction
- First-order methods for convex optimization
- Adaptive regularization minimization algorithms with nonsmooth norms
- A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm
- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- Adaptive FISTA for Nonconvex Optimization
- Cyclic Coordinate Dual Averaging with Extrapolation
- On the convergence of stochastic primal-dual hybrid gradient
- Non-ergodic convergence rate of an inertial accelerated primal-dual algorithm for saddle point problems
- An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimization
- Near-optimal tensor methods for minimizing the gradient norm of convex functions and accelerated primal–dual tensor methods
- Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
- Smoothing alternating direction methods for fully nonsmooth constrained convex optimization
- Optimal ecological transition path of a credit portfolio distribution, based on multidate Monge-Kantorovich formulation
- A primal-dual smoothing framework for max-structured non-convex optimization
- A new randomized primal-dual algorithm for convex optimization with fast last iterate convergence rates
- Adaptive smoothing algorithms for nonsmooth composite convex minimization
- An adaptive competitive penalty method for nonsmooth constrained optimization
Uses Software
This page was built for publication: An adaptive primal-dual framework for nonsmooth convex minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220901)
