A three-operator splitting scheme and its optimization applications

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

zbMATH Keywords

operator splittingconvex optimizationfixed pointaccelerationmonotone inclusionforward backward algorithmDouglas Rachford algorithmthree operators

Mathematics Subject Classification ID

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)

• 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
• Cocoercivity, smoothness and bias in variance-reduced stochastic gradient methods
• A parameterized three-operator splitting algorithm and its expansion
• Inertial splitting methods without prior constants for solving variational inclusions of two operators
• Double inertial proximal gradient algorithms for convex optimization problems and applications
• A numerical algorithm for inverse problem from partial boundary measurement arising from mean field game problem
• A generalized forward-backward splitting operator: degenerate analysis and applications
• Automated tight Lyapunov analysis for first-order methods
• Forward-primal-dual-half-forward algorithm for splitting four operators
• A strong law of large numbers for random monotone operators
• A three-operator splitting algorithm for nonconvex sparsity regularization
• Learnable Douglas-Rachford iteration and its applications in DOT imaging
• Primal-dual fixed point algorithm based on adapted metric method for solving convex minimization problem with application
• Recovery of a time-dependent bottom topography function from the shallow water equations via an adjoint approach
• Single-step algorithm for variational inequality problems in 2-uniformly convex Banach spaces
• A Variable Metric Forward-Reflected-Douglas-Rachford Method for Solving Monotone Inclusions
• Iteration complexity of an inexact Douglas-Rachford method and of a Douglas-Rachford-Tseng's F-B four-operator splitting method for solving monotone inclusions
• Inertial-relaxed splitting for composite monotone inclusions
• Distributed continuous-time proximal algorithm for nonsmooth resource allocation problem with coupled constraints
• Dual descent augmented Lagrangian method and alternating direction method of multipliers
• A two-level distributed algorithm for nonconvex constrained optimization
• An envelope for Davis-Yin splitting and strict saddle-point avoidance
• Direct covariance matrix estimation with compositional data
• Proximal variable smoothing method for three-composite nonconvex nonsmooth minimization with a linear operator
• 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

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)