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

DOI10.1137/19M1281538MaRDI QIDQ4971015zbMATHOpenAlexFDO

Authors Heinz H. Bauschke, Walaa M. Moursi

Publication date 8 October 2020

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

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

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)

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.

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; zbMATH DE number 3878691
• 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

Cites work

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

Cited in

(10)

• 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
• Linear convergence of the generalized Douglas-Rachford algorithm for feasibility problems
• A customized Douglas-Rachford splitting algorithm for separable convex minimization with linear constraints
• On the minimal displacement vector of the Douglas-Rachford operator
• Finding best approximation pairs for two intersections of closed convex sets
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle

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)