Convergence Rate Analysis of Primal-Dual Splitting Schemes
From MaRDI portal
averaged operatorconvergence ratesDouglas-Rachford splittingfixed-point algorithmforward-backward splittingforward-backward-forward splittingnonexpansive operatorPeaceman-Rachford splittingprimal-dual algorithmsproximal point algorithm
Monotone operators and generalizations (47H05) Variational and other types of inclusions (47J22) Iterative procedures involving nonlinear operators (47J25) Numerical mathematical programming methods (65K05) Numerical methods for variational inequalities and related problems (65K15) Convex programming (90C25)
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
- A Class of Inexact Variable Metric Proximal Point Algorithms
- A class of randomized primal-dual algorithms for distributed optimization
- A Douglas--Rachford Type Primal-Dual Method for Solving Inclusions with Mixtures of Composite and Parallel-Sum Type Monotone Operators
- 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 Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
- 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
- A Variable Metric Extension of the Forward–Backward–Forward Algorithm for Monotone 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
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- 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
(35)- Proximal alternating penalty algorithms for nonsmooth constrained convex optimization
- Rate of convergence analysis of dual-based variables decomposition methods for strongly convex problems
- A new primal-dual algorithm for minimizing the sum of three functions with a linear operator
- Forward-backward-half forward dynamical systems for monotone inclusion problems with application to v-GNE
- A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm
- Douglas-Rachford splitting and ADMM for pathological convex optimization
- On polarization-based schemes for the FFT-based computational homogenization of inelastic materials
- On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems
- Asymmetric forward-backward-adjoint splitting for solving monotone inclusions involving three operators
- Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions
- Primal-dual splittings as fixed point iterations in the range of linear operators
- Convergence analysis of approximate primal solutions in dual first-order methods
- Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
- On the ergodic convergence rates of a first-order primal-dual algorithm
- Easily Parallelizable and Distributable Class of Algorithms for Structured Sparsity, with Optimal Acceleration
- Quasi-Nonexpansive Iterations on the Affine Hull of Orbits: From Mann's Mean Value Algorithm to Inertial Methods
- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
- On the convergence rate of a forward-backward type primal-dual splitting algorithm for convex optimization problems
- New primal-dual algorithms for a class of nonsmooth and nonlinear convex-concave minimax problems
- Accelerated stochastic algorithms for convex-concave saddle-point problems
- A primal-dual optimization strategy for elliptic partial differential equations
- Splitting with near-circulant linear systems: applications to total variation CT and PET
- Convergence rate analysis of several splitting schemes
- An introduction to continuous optimization for imaging
- Local linear convergence analysis of primal-dual splitting methods
- Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists
- Some extensions of the operator splitting schemes based on Lagrangian and primal–dual: a unified proximal point analysis
- The operator splitting schemes revisited: primal-dual gap and degeneracy reduction by a unified analysis
- A three-operator splitting scheme and its optimization applications
- Fast reflected forward-backward algorithm: achieving fast convergence rates for convex optimization with linear cone constraints
- The degenerate variable metric proximal point algorithm and adaptive stepsizes for primal–dual Douglas–Rachford
- Asynchronous distributed generalized Nash equilibrium computation for aggregative games with coupling constraint
- Primal-dual algorithm for weakly convex functions under sharpness conditions
- Fast proximity-gradient algorithms for structured convex optimization problems
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)
