On the Behavior of the Douglas--Rachford Algorithm for Minimizing a Convex Function Subject to a Linear Constraint

DOI10.1137/19M1281538zbMATH Open1451.90117arXiv1908.05406OpenAlexW3088059505MaRDI QIDQ4971015FDOQ4971015

Authors: Heinz H. Bauschke, Walaa M. Moursi 

Publication date: 8 October 2020

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: The Douglas-Rachford algorithm (DRA) is a powerful optimization method for minimizing the sum of two convex (not necessarily smooth) functions. The vast majority of previous research dealt with the case when the sum has at least one minimizer. In the absence of minimizers, it was recently shown that for the case of two indicator functions, the DRA converges to a best approximation solution. In this paper, we present a new convergence result on the the DRA applied to the problem of minimizing a convex function subject to a linear constraint. Indeed, a normal solution may be found even when the domain of the objective function and the linear subspace constraint have no point in common. As an important application, a new parallel splitting result is provided. We also illustrate our results through various examples.

Full work available at URL: https://arxiv.org/abs/1908.05406

Recommendations

• The Douglas-Rachford algorithm in the affine-convex case
• On the asymptotic behavior of the Douglas-Rachford and proximal-point algorithms for convex optimization
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• The Douglas-Rachford algorithm in the absence of convexity
• scientific article
• Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
• A convergent relaxation of the Douglas-Rachford algorithm
• On the Douglas-Rachford algorithm
• An algorithm for linearly constrained convex nondifferentiable minimization problems
• On the minimization of a quasi-concave function subject to linear constraints

zbMATH Keywords

least squares solutionDouglas-Rachford splittingparallel splitting methodprojection operatorconvex optimization problemproximal mappingnormal probleminconsistent constrained optimization

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Convex programming (90C25) Perturbations of nonlinear operators (47H14)

Cites Work

• Infeasibility detection in the alternating direction method of multipliers for convex optimization
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Convex Analysis
• Title not available (Why is that?)
• Iterative construction of the resolvent of a sum of maximal monotone operators
• On the order of the operators in the Douglas-Rachford algorithm
• Title not available (Why is that?)
• Attouch-Théra duality revisited: Paramonotonicity and operator splitting
• The Douglas-Rachford algorithm in the affine-convex case
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Dykstra's alternating projection algorithm for two sets
• On weak convergence of the Douglas-Rachford method
• Title not available (Why is that?)
• Convex analysis and monotone operator theory in Hilbert spaces
• Nearly convex sets: fine properties and domains or ranges of subdifferentials of convex functions
• Near equality, near convexity, sums of maximally monotone operators, and averages of firmly nonexpansive mappings
• Title not available (Why is that?)
• Generalized solutions for the sum of two maximally monotone operators
• On the Douglas-Rachford algorithm
• The Douglas-Rachford algorithm for two (not necessarily intersecting) affine subspaces
• A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
• On the range of the Douglas-Rachford operator
• Douglas-Rachford splitting and ADMM for pathological convex optimization

Cited In (10)

• Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
• On the Douglas–Rachford Algorithm for Solving Possibly Inconsistent Optimization Problems
• Douglas–Rachford algorithm for control-constrained minimum-energy control problems
• On the asymptotic behavior of the Douglas-Rachford and proximal-point algorithms for convex optimization
• Stadium norm and Douglas-Rachford splitting: a new approach to road design optimization
• A note on the Douglas-Rachford splitting method for optimization problems involving hypoconvex functions
• A customized Douglas-Rachford splitting algorithm for separable convex minimization with linear constraints
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• Finding best approximation pairs for two intersections of closed convex sets
• On the minimal displacement vector of the Douglas-Rachford operator

This page was built for publication: On the Behavior of the Douglas--Rachford Algorithm for Minimizing a Convex Function Subject to a Linear Constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4971015)