A three-operator splitting scheme and its optimization applications
From MaRDI portal
Publication:683303
DOI10.1007/S11228-017-0421-ZzbMATH Open1464.47041arXiv1504.01032OpenAlexW2963654173MaRDI QIDQ683303FDOQ683303
Authors: Damek Davis, Wotao Yin 
Publication date: 6 February 2018
Published in: Set-Valued and Variational Analysis (Search for Journal in Brave)
Abstract: Operator splitting schemes have been successfully used in computational sciences to reduce complex problems into a series of simpler subproblems. Since 1950s, these schemes have been widely used to solve problems in PDE and control. Recently, large-scale optimization problems in machine learning, signal processing, and imaging have created a resurgence of interest in operator-splitting based algorithms because they often have simple descriptions, are easy to code, and have (nearly) state-of-the-art performance for large-scale optimization problems. Although operator splitting techniques were introduced over 60 years ago, their importance has significantly increased in the past decade. This paper introduces a new operator-splitting scheme for solving a variety of problems that are reduced to a monotone inclusion of three operators, one of which is cocoercive. Our scheme is very simple, and it does not reduce to any existing splitting schemes. Our scheme recovers the existing forward-backward, Douglas-Rachford, and forward-Douglas-Rachford splitting schemes as special cases. Our new splitting scheme leads to a set of new and simple algorithms for a variety of other problems, including the 3-set split feasibility problems, 3-objective minimization problems, and doubly and multiple regularization problems, as well as the simplest extension of the classic ADMM from 2 to 3 blocks of variables. In addition to the basic scheme, we introduce several modifications and enhancements that can improve the convergence rate in practice, including an acceleration that achieves the optimal rate of convergence for strongly monotone inclusions. Finally, we evaluate the algorithm on several applications.
Full work available at URL: https://arxiv.org/abs/1504.01032
Recommendations
- A new splitting method for monotone inclusions of three operators
- Asymmetric forward-backward-adjoint splitting for solving monotone inclusions involving three operators
- Convergence analysis of an inexact three-operator splitting algorithm
- Three-operator splitting algorithm for a class of variational inclusion problems
- A unified splitting algorithm for composite monotone inclusions
operator splittingconvex optimizationfixed pointaccelerationmonotone inclusionforward backward algorithmDouglas Rachford algorithmthree operators
Numerical mathematical programming methods (65K05) Convex programming (90C25) Monotone operators and generalizations (47H05) Variational and other types of inclusions (47J22) Numerical methods for variational inequalities and related problems (65K15) Fixed-point iterations (47J26)
Cites Work
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Title not available (Why is that?)
- Convex analysis and monotone operator theory in Hilbert spaces
- Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational Inequalities
- A first-order primal-dual algorithm for convex problems with applications to imaging
- Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
- A splitting algorithm for dual monotone inclusions involving cocoercive operators
- On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems
- A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
- Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators
- A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
- A Douglas--Rachford Type Primal-Dual Method for Solving Inclusions with Mixtures of Composite and Parallel-Sum Type Monotone Operators
- Mean Value Methods in Iteration
- Title not available (Why is that?)
- Systems of Structured Monotone Inclusions: Duality, Algorithms, and Applications
- The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
- On weak convergence of the Douglas-Rachford method
- Convergence rate analysis of several splitting schemes
- Compositions and convex combinations of averaged nonexpansive operators
- Coordinate-friendly structures, algorithms and applications
- Backward-forward algorithms for structured monotone inclusions in Hilbert spaces
- Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
- Convergence Rate Analysis of Primal-Dual Splitting Schemes
Cited In (only showing first 100 items - show all)
- Primal dual methods for Wasserstein gradient flows
- A linear algebra perspective on the random multi-block ADMM: the QP case
- Converting ADMM to a proximal gradient for efficient sparse estimation
- On the optimal relaxation parameters of Krasnosel'ski–Mann iteration
- New convergence analysis of a primal-dual algorithm with large stepsizes
- Envelope functions: unifications and further properties
- Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs
- Hybrid Jacobian and Gauss-Seidel proximal block coordinate update methods for linearly constrained convex programming
- PET-MRI joint reconstruction with common edge weighted total variation regularization
- Efficient alternating minimization methods for variational edge-weighted colorization models
- An inertial semi-forward-reflected-backward splitting and its application
- A Three-Operator Splitting Perspective of a Three-Block ADMM for Convex Quadratic Semidefinite Programming and Beyond
- Fast Krasnosel’skiĭ–Mann Algorithm with a Convergence Rate of the Fixed Point Iteration of \(\boldsymbol{{ o} \left(\frac{1}{{ k}} \right)}\)
- A fixed-point proximity algorithm for recovering low-rank components from incomplete observation data with application to motion capture data refinement
- Generalized Kalman smoothing: modeling and algorithms
- Alternating direction method of multipliers for nonconvex log total variation image restoration
- A coordinate-descent primal-dual algorithm with large step size and possibly nonseparable functions
- Convergence and rate analysis of a proximal linearized ADMM for nonconvex nonsmooth optimization
- On the efficiency of random permutation for ADMM and coordinate descent
- On unbounded delays in asynchronous parallel fixed-point algorithms
- A unified convergence rate analysis of the accelerated smoothed gap reduction algorithm
- Operator splitting performance estimation: tight contraction factors and optimal parameter selection
- Linear convergence of primal-dual gradient methods and their performance in distributed optimization
- Asymmetric forward-backward-adjoint splitting for solving monotone inclusions involving three operators
- Convergence rates for an inexact ADMM applied to separable convex optimization
- Cyclic coordinate-update algorithms for fixed-point problems: analysis and applications
- A first-order inexact primal-dual algorithm for a class of convex-concave saddle point problems
- Backward-forward-reflected-backward splitting for three operator monotone inclusions
- Two-step fixed-point proximity algorithms for multi-block separable convex problems
- Multi-step inertial Krasnosel'skiǐ-Mann iteration with new inertial parameters arrays
- Single-forward-step projective splitting: exploiting cocoercivity
- A second-order adaptive Douglas-Rachford dynamic method for maximal \(\alpha\)-monotone operators
- Finding the forward-Douglas-Rachford-forward method
- On the equivalence of the primal-dual hybrid gradient method and Douglas-Rachford splitting
- On the convergence rate of the Krasnosel'skiĭ-Mann iteration
- Reflected three-operator splitting method for monotone inclusion problem
- On the ergodic convergence rates of a first-order primal-dual algorithm
- ADMM for monotone operators: convergence analysis and rates
- A new primal-dual algorithm for minimizing the sum of three functions with a linear operator
- Modified forward-backward splitting method for variational inclusions
- Relaxed forward-backward splitting methods for solving variational inclusions and applications
- Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization
- Three-operator splitting algorithm for a class of variational inclusion problems
- On the Global Linear Convergence of the ADMM with MultiBlock Variables
- A forward-backward splitting method for monotone inclusions without cocoercivity
- Iterative regularization methods with new stepsize rules for solving variational inclusions
- ADMM for multiaffine constrained optimization
- A note on the forward-Douglas-Rachford splitting for monotone inclusion and convex optimization
- Bregman primal-dual first-order method and application to sparse semidefinite programming
- Three new iterative methods for solving inclusion problems and related problems
- Degenerate Preconditioned Proximal Point Algorithms
- An adaptive splitting algorithm for the sum of two generalized monotone operators and one cocoercive operator
- Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
- Forward-partial inverse-half-forward splitting algorithm for solving monotone inclusions
- Dualize, split, randomize: toward fast nonsmooth optimization algorithms
- Four-operator splitting via a forward-backward-half-forward algorithm with line search
- MiKM: multi-step inertial Krasnosel'skiǐ-Mann algorithm and its applications
- Convergence analysis of an inexact three-operator splitting algorithm
- Projective splitting with forward steps
- Novel forward-backward algorithms for optimization and applications to compressive sensing and image inpainting
- Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting
- Faster subgradient methods for functions with Hölderian growth
- Convergence rates of forward-Douglas-Rachford splitting method
- Splitting with near-circulant linear systems: applications to total variation CT and PET
- Regularization proximal method for monotone variational inclusions
- Monotone operator theory in convex optimization
- Convergence Rates for Projective Splitting
- Estimation of graphical models through structured norm minimization
- Multi-step inertial forward-backward-half forward algorithm for solving monotone inclusion
- Inexact alternating direction methods of multipliers for separable convex optimization
- A parameterized three-operator splitting algorithm for non-convex minimization problems with applications
- Learning to optimize: a tutorial for continuous and mixed-integer optimization
- Proximal-based recursive implementation for model-free data-driven fault diagnosis
- Distributed forward-backward methods for ring networks
- Self-adaptive forward-backward splitting algorithm for the sum of two monotone operators in Banach spaces
- A three-operator splitting algorithm with deviations for generalized DC programming
- An accelerated forward-backward-half forward splitting algorithm for monotone inclusion with applications to image restoration
- Forward-reflected-backward splitting algorithms with momentum: weak, linear and strong convergence results
- Three-operator splitting for learning to predict equilibria in convex games
- Stochastic projective splitting
- Solving monotone inclusions involving the sum of three maximally monotone operators and a cocoercive operator with applications
- Three-operator reflected forward-backward splitting algorithm with double inertial effects
- Extrapolated plug-and-play three-operator splitting methods for nonconvex optimization with applications to image restoration
- Approximate first-order primal-dual algorithms for saddle point problems
- A dynamical splitting method for minimizing the sum of three convex functions
- The geometry of monotone operator splitting methods
- Forward-reflected-backward splitting method without cocoercivity for the sum of maximal monotone operators in Banach spaces
- Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists
- A technique with diminishing and non-summable step-size for monotone inclusion problems in Banach spaces
- From Halpern's fixed-point iterations to Nesterov's accelerated interpretations for root-finding problems
- Strengthened splitting methods for computing resolvents
- Fejér-monotone hybrid steepest descent method for affinely constrained and composite convex minimization
- Two new splitting methods for three-operator monotone inclusions in Hilbert spaces
- Tight coefficients of averaged operators via scaled relative graph
- An Efficient Convex Formulation for Reduced-Rank Linear Discriminant Analysis in High Dimensions
- A direct proof of convergence of Davis-Yin splitting algorithm allowing larger stepsizes
- A product space reformulation with reduced dimension for splitting algorithms
- Nonlinear forward-backward splitting with momentum correction
- Convergence analysis of a new forward-reflected-backward algorithm for four operators without cocoercivity
- Preconditioned three-operator splitting algorithm with applications to image restoration
This page was built for publication: A three-operator splitting scheme and its optimization applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q683303)
