Source-linked AI summary
Inertial Douglas-Rachford splitting for monotone inclusion problems
Radu Ioan Bot, Ernö Robert Csetnek, Christopher Hendrich
TL;DR
The paper addresses monotone inclusion problems involving sums, linear compositions, and parallel sums of maximally monotone operators. It develops inertial Krasnosel’skiĭ–Mann and Douglas–Rachford schemes, extends them through a product-space primal-dual approach, and reports favorable numerical performance in clustering and location theory. Convergence is weak in general and strong under uniform monotonicity, while the methods retain broader applicability than certain competing primal-dual formulations.
Problem
Splitting methods are needed for monotone inclusions and nondifferentiable convex optimization while evaluating each operator separately, including when operators are linearly composed or combined by parallel sums.
Method
The paper formulates an inertial Krasnosel’skiĭ–Mann method, derives an inertial Douglas–Rachford algorithm, and uses a product-space approach for primal-dual inclusions and convex optimization.
Results
The algorithms have weak convergence generally and strong convergence under uniform monotonicity; experiments report better performance than noninertial Douglas–Rachford and faster performance than FBF and FB in clustering.
Takeaways & Limitations
The resulting schemes separately access maximally monotone mappings via resolvents and can address inclusion structures that classical Douglas–Rachford cannot handle directly.
Takeaways & Limitations
The convergence analysis imposes α1 = 0, although x0 = x1 can alternatively remove that requirement.
Abstract
from arXiv · showhide
We propose an inertial Douglas-Rachford splitting algorithm for finding the set of zeros of the sum of two maximally monotone operators in Hilbert spaces and investigate its convergence properties. To this end we formulate first the inertial version of the Krasnosel'skiĭ--Mann algorithm for approximating the set of fixed points of a nonexpansive operator, for which we also provide an exhaustive convergence analysis. By using a product space approach we employ these results to the solving of monotone inclusion problems involving linearly composed and parallel-sum type operators and provide in this way iterative schemes where each of the maximally monotone mappings is accessed separately via its resolvent. We consider also the special instance of solving a primal-dual pair of nonsmooth convex optimization problems and illustrate the theoretical results via some numerical experiments in clustering and location theory.
1 Introduction and preliminaries
The paper frames splitting methods for maximally monotone inclusions as useful tools for nondifferentiable convex optimization, then develops convergence foundations for its inertial algorithms. It uses nonexpansive fixed-point and monotone-operator results to support Douglas–Rachford analysis and extensions.
- Splitting algorithms separately evaluate operators and apply to nondifferentiable convex optimization problems in areas including imaging, classification, clustering, and location theory.
- The paper studies Douglas–Rachford splitting for zeros of sums of two maximally monotone operators through its connection with Krasnosel’skiĭ–Mann fixed-point iteration.
- It introduces an inertial Krasnosel’skiĭ–Mann scheme and uses its convergence analysis to derive inertial Douglas–Rachford and primal-dual methods.
- A product-space approach targets linearly composed and parallel-sum inclusions, where primal-dual methods access each maximally monotone mapping separately through its resolvent.
- The preliminaries define monotone, maximally monotone, uniformly monotone, strongly monotone, nonexpansive, resolvent, and fixed-point concepts used throughout the paper.
- The convergence toolkit includes demiclosedness, an inertial quasi-Fejér-type sequence lemma, and Opial’s weak-convergence principle.
2 An inertial Douglas–Rachford splitting algorithm
The paper first establishes an inertial Krasnosel’skiĭ–Mann scheme for nonexpansive operators, then applies it to an inertial Douglas–Rachford method for maximally monotone inclusions. The method has weak convergence generally and strong convergence under uniform monotonicity.
- Inertial Krasnosel’skiĭ–Mann scheme: The inertial Krasnosel’skiĭ–Mann scheme is formulated on affine subsets because its iterations use affine combinations.
- Inertial Krasnosel’skiĭ–Mann scheme: Under the stated parameter conditions, the inertial Krasnosel’skiĭ–Mann iterates converge weakly to a fixed point of the nonexpansive operator.
- Inertial Douglas–Rachford algorithm: The inertial Douglas–Rachford iteration applies the resolvents JγB and JγA to produce y_n, z_n, and the next iterate x_{n+1}.
- Inertial Douglas–Rachford algorithm: For maximally monotone A and B with zer(A + B) nonempty, the algorithm yields weak convergence properties for the generated sequences and identifies the limit through JγB.
- Inertial Douglas–Rachford algorithm: If either A or B is uniformly monotone, y_n and z_n converge strongly to the unique point in zer(A + B).
- Special cases: Setting α = 0 recovers the classical Douglas–Rachford algorithm, while taking Bx = 0 reduces the scheme to an inertial proximal-point method.
3 Solving monotone inclusion problems involving mixtures of linearly composed and parallel-sum type operators
The paper applies an inertial Douglas–Rachford framework in product spaces to primal-dual monotone inclusions with linearly composed and parallel-sum operators. Under stated assumptions, the resulting iterates converge weakly, and uniform monotonicity strengthens convergence to the unique primal-dual solution.
- Problem and algorithm: The proposed primal-dual scheme targets inclusions combining linearly composed operators and parallel sums, whose resolvents are generally unavailable in closed form.The product-space formulation separates access to the maximally monotone mappings through their resolvents.
- Problem and algorithm: The primal-dual problem is formulated with a maximally monotone operator A, maximally monotone B_i and D_i, and nonzero continuous linear maps L_i.The associated primal and dual solutions satisfy the coupled inclusion system involving A and (B_i □ D_i)(L_i x − r_i).
- Convergence results: The generated primal-dual iterates converge weakly to a primal-dual solution, while auxiliary sequences converge weakly to the corresponding solution components.The theorem states weak convergence for (x_n, v_1,n, ..., v_m,n), (p_1,n, p_2,1,n, ..., p_2,m,n), and (z_1,n, z_2,1,n, ..., z_2,m,n).
- Convergence results: If A and the relevant B_i^-1 operators are uniformly monotone, the primal-dual and auxiliary sequences converge strongly to the unique primal-dual solution.Uniform monotonicity is transferred to the product-space operator used in the convergence argument.
- Product-space formulation: The product-space construction rewrites the structured system as a Douglas–Rachford problem involving maximally monotone operators on an augmented Hilbert space.The construction uses a skew-symmetric coupling operator and a strongly positive metric transformation.
4 Convex optimization problems
The paper specializes inertial Douglas–Rachford splitting to primal-dual convex optimization problems with linearly composed and parallel-sum operators. Under stated assumptions, the resulting iterates converge weakly, and uniformly convex cases yield strong convergence to the unique primal-dual solution.
- Algorithm: The inertial Douglas–Rachford primal-dual algorithm is obtained by combining the general splitting result with the convex optimization formulation.Algorithm 15 uses inertial extrapolation, proximal mappings, and parameters τ, σ_i, α_n, and λ_n.
- Problem formulation: The section formulates a primal-dual pair of convex optimization problems using proper, convex, lower-semicontinuous functions and bounded linear operators.The associated monotone inclusions use subdifferentials A = ∂f, B_i = ∂g_i, and D_i = ∂l_i.
- Optimization interpretation: A primal-dual solution yields optimal solutions for both the primal and dual problems, with coincident optimal objective values.Thus, the formulation establishes strong duality under the stated inclusion conditions.
- Convergence: Under the theorem’s assumptions, the generated primal-dual sequences converge weakly to a primal-dual solution.The weak convergence statements apply to the primary iterates and auxiliary sequences.
- Convergence: If f and the conjugate functions g_i* are uniformly convex, the relevant sequences converge strongly to the unique primal-dual solution.The paper also relates uniform convexity of g_i* to strong convexity and Lipschitz differentiability properties of g_i.
5 Numerical experiments
The experiments apply the proposed methods to clustering and generalized Heron problems, evaluating convergence by root-mean-square error and comparing computational performance. The inertial Douglas–Rachford method performs competitively, outperforming alternatives for clustering while showing negligible differences from noninertial methods on the reported Heron instances.
- Clustering: The clustering objective uses weighted distances between data points and cluster centers, with γ controlling when centers coalesce into clusters.The weights are selected using a K-nearest-neighbors strategy; the experiments use K = 10 and γ values chosen to separate the two half moons.
- Clustering: The half-moon experiment contains two interlocking groups of 100 points in R2 and evaluates iterates at RMSE tolerances ε = 10^-4 and ε = 10^-8.The choices γ = 4 for p = 1 and γ = 5.2 for p = 2 produce correct separation of the input data into two half moons.
- The generalized Heron problem: The generalized Heron problem minimizes the sum of distances from a point in a closed convex set to given closed convex sets.It is represented within the paper’s primal-dual framework using an indicator function for the constraint set, distance terms, and indicator functions for the target sets.
- The generalized Heron problem: Algorithm 15 and the noninertial Douglas–Rachford method perform well on the reported Heron instances, with almost negligible computational differences.When n = 3, the subgradient approach becomes better and surpasses both primal-dual methods; empty table cells indicate more than 60 seconds to meet the stopping criterion.