Convergence Rate Analysis of Primal-Dual Splitting Schemes
From MaRDI portal
convergence ratesproximal point algorithmDouglas-Rachford splittingforward-backward splittingnonexpansive operatorfixed-point algorithmprimal-dual algorithmsaveraged operatorPeaceman-Rachford splittingforward-backward-forward splitting
Numerical mathematical programming methods (65K05) Convex programming (90C25) Monotone operators and generalizations (47H05) Variational and other types of inclusions (47J22) Iterative procedures involving nonlinear operators (47J25) Numerical methods for variational inequalities and related problems (65K15)
Abstract: Primal-dual splitting schemes are a class of powerful algorithms that solve complicated monotone inclusions and convex optimization problems that are built from many simpler pieces. They decompose problems that are built from sums, linear compositions, and infimal convolutions of simple functions so that each simple term is processed individually via proximal mappings, gradient mappings, and multiplications by the linear maps. This leads to easily implementable and highly parallelizable or distributed algorithms, which often obtain nearly state-of-the-art performance. In this paper, we analyze a monotone inclusion problem that captures a large class of primal-dual splittings as a special case. We introduce a unifying scheme and use some abstract analysis of the algorithm to prove convergence rates of the proximal point algorithm, forward-backward splitting, Peaceman-Rachford splitting, and forward-backward-forward splitting applied to the model problem. Our ergodic convergence rates are deduced under variable metrics, stepsizes, and relaxation. Our nonergodic convergence rates are the first shown in the literature. Finally, we apply our results to a large class of primal-dual algorithms that are a special case of our scheme and deduce their convergence rates.
Recommendations
- Local linear convergence analysis of primal-dual splitting methods
- On the convergence rate of a forward-backward type primal-dual splitting algorithm for convex optimization problems
- Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
- Convergence rate analysis of several splitting schemes
- Rate of convergence analysis of dual-based variables decomposition methods for strongly convex problems
- Convergence analysis of approximate primal solutions in dual first-order methods
- Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods
- Convergence rates of forward-Douglas-Rachford splitting method
- Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
- On Dual Convergence and the Rate of Primal Convergence of Bregman’s Convex Programming Method
Cites work
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- A Class of Inexact Variable Metric Proximal Point Algorithms
- A Douglas--Rachford Type Primal-Dual Method for Solving Inclusions with Mixtures of Composite and Parallel-Sum Type Monotone Operators
- A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
- A Variable Metric Extension of the Forward–Backward–Forward Algorithm for Monotone Operators
- A class of randomized primal-dual algorithms for distributed optimization
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science
- A generalized proximal point algorithm and its convergence rate
- A monotone+skew splitting model for composite monotone inclusions in duality
- A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
- A primal–dual fixed point algorithm for convex separable minimization with applications to image restoration
- A splitting algorithm for dual monotone inclusions involving cocoercive operators
- An algorithm for splitting parallel sums of linearly composed monotone operators, with applications to signal recovery
- Convergence analysis for a primal-dual monotone + skew splitting algorithm with applications to total variation minimization
- Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
- Convergence rate analysis of several splitting schemes
- Convex analysis and monotone operator theory in Hilbert spaces
- Convex functions. Constructions, characterizations and counterexamples
- Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
- Image recovery via total variation minimization and related problems
- Monotone Operators and the Proximal Point Algorithm
- NON-STRICTLY CONVEX MINIMIZATION OVER THE FIXED POINT SET OF AN ASYMPTOTICALLY SHRINKING NONEXPANSIVE MAPPING
- On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems
- On the convergence rate of a forward-backward type primal-dual splitting algorithm for convex optimization problems
- On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space
- Perturbation theory for linear operators.
- Planning Algorithms
- Primal-dual decomposition by operator splitting and applications to image deblurring
- Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators
- Proximal methods for hierarchical sparse coding
- Quelques propriétés des opérateurs angle-bornes et n-cycliquement monotones
- Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
- Smooth minimization of non-smooth functions
- Solving monotone inclusions involving parallel sums of linearly composed maximally monotone operators
- Solving systems of monotone inclusions via primal-dual splitting techniques
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Systems of Structured Monotone Inclusions: Duality, Algorithms, and Applications
- Variable metric forward-backward splitting with applications to monotone inclusions in duality
- Variable metric quasi-Fejér monotonicity
Cited in
(33)- Douglas-Rachford splitting and ADMM for pathological convex optimization
- New primal-dual algorithms for a class of nonsmooth and nonlinear convex-concave minimax problems
- On polarization-based schemes for the FFT-based computational homogenization of inelastic materials
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- The degenerate variable metric proximal point algorithm and adaptive stepsizes for primal–dual Douglas–Rachford
- Local linear convergence analysis of primal-dual splitting methods
- A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm
- Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
- Asymmetric forward-backward-adjoint splitting for solving monotone inclusions involving three operators
- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions
- Some extensions of the operator splitting schemes based on Lagrangian and primal–dual: a unified proximal point analysis
- Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists
- Accelerated stochastic algorithms for convex-concave saddle-point problems
- Fast proximity-gradient algorithms for structured convex optimization problems
- On the ergodic convergence rates of a first-order primal-dual algorithm
- A primal-dual optimization strategy for elliptic partial differential equations
- The operator splitting schemes revisited: primal-dual gap and degeneracy reduction by a unified analysis
- A new primal-dual algorithm for minimizing the sum of three functions with a linear operator
- Rate of convergence analysis of dual-based variables decomposition methods for strongly convex problems
- A three-operator splitting scheme and its optimization applications
- On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems
- Forward-backward-half forward dynamical systems for monotone inclusion problems with application to v-GNE
- Convergence analysis of approximate primal solutions in dual first-order methods
- Easily Parallelizable and Distributable Class of Algorithms for Structured Sparsity, with Optimal Acceleration
- On the convergence rate of a forward-backward type primal-dual splitting algorithm for convex optimization problems
- Convergence rate analysis of several splitting schemes
- Fast reflected forward-backward algorithm: achieving fast convergence rates for convex optimization with linear cone constraints
- Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
- Quasi-Nonexpansive Iterations on the Affine Hull of Orbits: From Mann's Mean Value Algorithm to Inertial Methods
- Primal-dual splittings as fixed point iterations in the range of linear operators
- An introduction to continuous optimization for imaging
- Splitting with near-circulant linear systems: applications to total variation CT and PET
This page was built for publication: Convergence Rate Analysis of Primal-Dual Splitting Schemes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2949517)
