Metric selection in fast dual forward-backward splitting
From MaRDI portal
Publication:901087
DOI10.1016/J.AUTOMATICA.2015.09.010zbMATH Open1330.49032arXiv1410.8479OpenAlexW2173413132MaRDI QIDQ901087FDOQ901087
Authors: Pontus Giselsson, Stephen Boyd 
Publication date: 23 December 2015
Published in: Automatica (Search for Journal in Brave)
Abstract: Recently, several convergence rate results for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) have been presented in the literature. In this paper, we show global linear convergence rate bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions. We further show that the rate bounds are tight for the class of problems under consideration for all feasible algorithm parameters. For problems that satisfy the assumptions, we show how to select step-size and metric for the algorithm that optimize the derived convergence rate bounds. For problems with a similar structure that do not satisfy the assumptions, we present heuristic step-size and metric selection methods.
Full work available at URL: https://arxiv.org/abs/1410.8479
Recommendations
- A fast splitting method tailored for Dantzig selector
- Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM
- The Variable Metric Forward-Backward Splitting Algorithm Under Mild Differentiability Assumptions
- Forward-backward splitting with Bregman distances
- Convergence analysis of a variable metric forward-backward splitting algorithm with applications
- Variable metric forward-backward splitting with applications to monotone inclusions in duality
- Fast approximation in subspaces by doubling metric decomposition
- Continuous metric selection and multivariate approximation
- Fast multiple-splitting algorithms for convex optimization
- A fast splitting method for efficient split Bregman iterations
preconditioningmodel predictive controldistributed optimizationmetric selectionfirst order optimization algorithms
Cites Work
- CVXGEN: a code generator for embedded convex optimization
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Concerning nonnegative matrices and doubly stochastic matrices
- Embedded Online Optimization for Model Predictive Control at Megahertz Rates
- Linear Matrix Inequalities in System and Control Theory
- Smooth minimization of non-smooth functions
- Title not available (Why is that?)
- Gradient methods for minimizing composite functions
- Title not available (Why is that?)
- Partitioning procedures for solving mixed-variables programming problems
- A first-order primal-dual algorithm for convex problems with applications to imaging
- Rate Analysis of Inexact Dual First-Order Methods Application to Dual Decomposition
- An Accelerated Dual Gradient-Projection Algorithm for Embedded Linear Model Predictive Control
- Nonlinear control of constrained linear systems via predictive reference management
- Title not available (Why is that?)
- The Decomposition Algorithm for Linear Programs
- Computational complexity of inexact gradient augmented Lagrangian methods: application to constrained MPC
- An <formula formulatype="inline"><tex Notation="TeX">$O(1/k)$</tex> </formula> Gradient Method for Network Resource Allocation Problems
- Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
- An online active set strategy to overcome the limitations of explicit MPC
- Accelerated gradient methods and dual decomposition in distributed model predictive control
- Certification aspects of the fast gradient method for solving the dual of parametric convex programs
- A Generalized Accelerated Proximal Gradient Approach for Total-Variation-Based Image Restoration
- On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems
- Minimizing Condition Number via Convex Programming
Cited In (12)
- Envelope functions: unifications and further properties
- Soft inequality constraints in gradient method and fast gradient method for quadratic programming
- Stochastic matrix-free equilibration
- Backward-forward-reflected-backward splitting for three operator monotone inclusions
- Massively parallelizable proximal algorithms for large‐scale stochastic optimal control problems
- Preconditioning of a generalized forward-backward splitting and application to optimization on graphs
- OSQP: an operator splitting solver for quadratic programs
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Local Decay of Residuals in Dual Gradient Method with Soft State Constraints
- On closed-loop dynamics of ADMM-based MPC
- Plug-and-Play Unplugged: Optimization-Free Reconstruction Using Consensus Equilibrium
- Parameter selection and preconditioning for a graph form solver
Uses Software
This page was built for publication: Metric selection in fast dual forward-backward splitting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q901087)
