Journal of Convex Analysis 16 (2009), No. 3, 727--748
Copyright Heldermann Verlag 2009
Iterative Construction of the Resolvent of a Sum of Maximal Monotone Operators
Patrick L. Combettes
UPMC Université Paris 06, Lab. J.-L. Lions - UMR 7598, 75005 Paris, France
plc@math.jussieu.fr
We propose two inexact parallel splitting algorithms for computing the resolvent of a weighted sum of maximal monotone operators in a Hilbert space and show their strong convergence. We start by establishing new results on the asymptotic behavior of the Douglas-Rachford splitting algorithm for the sum of two operators. These results serve as a basis for the first algorithm. The second algorithm is based on an extension of a recent Dykstra-like method for computing the resolvent of the sum of two maximal monotone operators. Under standard qualification conditions, these two algorithms provide a means for computing the proximity operator of a weighted sum of lower semicontinuous convex functions. We show that a version of the second algorithm performs the same task without requiring any qualification condition. In turn, this provides a parallel splitting algorithm for qualification-free strongly convex programming.
Keywords: Dykstra's algorithm, Douglas-Rachford algorithm, maximal monotone operator, method of partial inverses, operator splitting, proximity operator, resolvent.
MSC: 47H05; 47J25, 49M29, 65K05, 90C25
[ Fulltext-pdf (191 KB)] for subscribers only.