Source-linked AI summary
A Douglas-Rachford type primal-dual method for solving inclusions with mixtures of composite and parallel-sum type monotone operators
Radu Ioan Bot, Christopher Hendrich
TL;DR
Many convex optimization problems with nondifferentiable objectives reduce to inclusions involving mixtures of monotone operators. The paper proposes two inexact Douglas–Rachford primal-dual algorithms that process linear and set-valued operators separately; in a location experiment, they reach the reported accuracies in fewer than 50 iterations, unlike the compared subgradient method.
Problem
Many convex optimization problems with likely nondifferentiable objectives can be reduced to inclusions involving mixtures of monotone set-valued operators.
Source: §1 · p. 1Method
Two inexact Douglas–Rachford primal-dual algorithms process set-valued operators individually via resolvents and bounded linear operators via explicit forward steps on the operators or their adjoints.
Source: §1 · pp. 1–2Results
Both algorithms reach accuracies for objective values and iterates in fewer than 50 iterations on the generalized Heron problem, while the compared subgradient methods do not reach them after 10 million iterations.
Source: §4.1 · p. 25Takeaways & Limitations
The Douglas–Rachford approach allows general maximal monotone operators in the parallel sums without assuming Lipschitz continuity or cocoercivity.
Source: §1 · p. 2The convergence error condition Σ λ_n||a_n|| < ∞ does not itself require the errors to be summable or to converge to zero.
Source: §2.1 · p. 12
Abstract
from arXiv · showhide
In this paper we propose two different primal-dual splitting algorithms for solving inclusions involving mixtures of composite and parallel-sum type monotone operators which rely on an inexact Douglas-Rachford splitting method, however applied in different underlying Hilbert spaces. Most importantly, the algorithms allow to process the bounded linear operators and the set-valued operators occurring in the formulation of the monotone inclusion problem separately at each iteration, the latter being individually accessed via their resolvents. The performances of the primal-dual algorithms are emphasized via some numerical experiments on location and image deblurring problems.
1 Introduction and preliminaries
Many convex optimization and signal-processing problems with nondifferentiable objectives can be formulated as inclusions involving mixtures of monotone operators. The paper introduces two inexact Douglas–Rachford primal-dual methods that process set-valued operators through resolvents and bounded linear operators through explicit steps.
1 Introduction and preliminaries
- Convex optimization and signal- and image-processing problems with potentially nondifferentiable objectives can be reduced to inclusions involving mixtures of monotone set-valued operators.Source: §1 · p. 1
- The two methods process set-valued operators individually through resolvents and bounded linear operators through explicit forward steps on the operators or their adjoints.Both are primal-dual, iterative, and error-tolerant methods for inclusions mixing composite and parallel-sum monotone operators.Source: §1 · p. 1
- Inexact variants allow summable implementation errors because resolvents of maximally monotone operators may lack closed-form expressions.Source: §1 · p. 2
- Most algorithm steps can run independently, and under qualification conditions, subdifferential inclusions are equivalent to primal-dual convex optimization problems.The formulation captures varied primal problems and corresponding conjugate duals; many relevant subdifferential resolvents are proximal mappings with closed forms.Source: §1 · p. 2
- The Douglas–Rachford approach assumes neither Lipschitz continuity nor cocoercivity, allowing general maximal monotone operators in parallel sums and relaxing assumptions in [10,14].Earlier approaches discussed use Lipschitzian operators in or cocoercive operators in.Source: §1 · p. 2
- Even when two operators are maximally monotone, their sum or parallel sum need not be maximally monotone.Source: §1 · p. 4
2 Algorithms and convergence results
This section presents two primal-dual algorithms for the inclusion pair and establishes convergence results for their iterates, including weak convergence and stronger convergence under additional conditions.
2.1 A first primal-dual algorithm
- The first algorithm accesses the resolvents of A and each B_i^-1 separately, while processing each L_i and its adjoint twice.The method is fully decomposable, and many steps can be executed in parallel.Source: §2.1 · pp. 5, 12
- The generated primal-dual sequence converges weakly to a solution; in finite dimensions, proximal points converge strongly when the specified error sequences tend to zero.Under stronger assumptions, the proximal points converge strongly to the unique primal-dual solution.Source: §2.1 · p. 6
- The convergence proof reformulates the scheme as an inexact Douglas-Rachford method in a specific Hilbert space.The theorem also establishes vanishing residual terms; under uniform monotonicity, the proximal points converge strongly to the unique solution.Source: §2.1 · pp. 6, 11, 12
- Summability of λ_n∥a_n∥ alone does not ensure that the errors a_n are summable or converge to zero.This caveat qualifies the error-sequence assumptions in the convergence theorem.Source: §2.1 · p. 12
- In the stated special cases, Algorithm 2.1 differs from [10, Theorem 3.1], [6, Theorem 3.1] (m = 1), and [14, Theorem 3.1].For the convex-optimization case discussed in Example 2.1, it also differs from [11, Algorithm 3.1] and [7, Algorithm 1].Source: §2.1 · p. 13
2.2 A second primal-dual algorithm
- Unlike Algorithm 2.1, Algorithm 2.2 evaluates each operator Li and its adjoint only once per iteration.Algorithm 2.1 processes each operator and adjoint twice.Source: §2.2 · p. 13
- The iterates (x_n, v_{1,n}, ..., v_{m,n}), indexed by n ≥ 0, converge strongly to a primal-dual solution of Problem 2.1.Source: §2.2 · p. 14
- In Algorithm 2.2, choosing (y1,0, ..., ym,0) = (0, ..., 0) makes both sequences (y1,n, ..., ym,n)n≥0 and (v1,n, ..., vm,n)n≥0 vanish in this particular situation.Source: §2.2 · p. 17
- In a stated special case, Algorithm 2.2 matches [14, Eq. (3.3)] but differs from [10, Theorem 3.1] and [6, Theorem 3.1] (m = 1).The comparison assumes Di(0) = Gi, Di(v) = ∅ for v ≠ 0, zero di,n errors, and zero initial y values.Source: §2.2 · p. 18
- For the convex-optimization case, Algorithm 2.2 is equivalent to [11, Algorithm 3.1] and, with exact implementations, equals [7, Algorithm 1].Its variable relaxation parameters in (0, 2) relax [7]’s requirement that they be constant in (0, 1].Source: §2.2 · p. 18
3 Application to convex minimization problems
The paper specializes its two primal-dual splitting schemes to convex minimization problems in Hilbert spaces. Under stated error and step-size conditions, the schemes yield primal-dual optimal solutions, with strong convergence available under additional assumptions.
Problem formulation and primal-dual relation
- Both schemes connect solutions of the primal-dual inclusions to optimal solutions of the convex primal and dual problems, with coincident optimal values.The application uses subdifferentials of the objective functions and bounded linear operators in the inclusion formulation.Source: §3 · pp. 18–19
Convergence conditions
- Algorithm 3.1 permits summable weighted errors, while its strong-convergence conclusions require additional conditions on errors, dimension, or step lengths.The theorem’s assumptions include summability of weighted error norms; a separate strong-convergence result specifies a positive lower bound on step lengths.Source: §3 · pp. 19–20
Algorithm 3.1
- Algorithm 3.1 converges weakly to a primal-dual solution; in finite dimensions, its iterates converge strongly to primal and dual optima when the specified errors vanish.Under further conditions, the corresponding proximal points converge strongly to the unique optima, with equality of primal and dual values.Source: §3 · pp. 19–20
Algorithm 3.2
- Algorithm 3.2 adds auxiliary dual variables and proximal updates, and its iterates converge weakly to primal and dual optima with equal values.In finite-dimensional spaces, the primal and dual iterates converge strongly; under additional conditions, proximal points converge strongly to unique optima.Source: §3 · pp. 20–21
Special case
- When each l_i is the indicator of zero and the auxiliary initialization is zero, Algorithm 3.2 reduces to an iteration with vanishing auxiliary sequences.The paper states that the corresponding convergence assertions hold for step lengths satisfying the specified condition.Source: §3 · p. 21
4 Numerical experiments
The experiments apply the algorithms to generalized Heron problems and image deblurring. In the Heron examples, both algorithms reach stated accuracies in fewer than 50 iterations, far fewer than the reported subgradient-method comparisons.
4.1 The generalized Heron problem
- The generalized Heron problem minimizes the sum of distances to closed convex sets over a nonempty closed convex constraint set.The examples include squares with disc, ball, and line constraints.Source: §4.1 · pp. 22, 24
- Both algorithms reach six-decimal accuracy for objective values and iterates in fewer than 50 iterations in Example 4.1, while the compared subgradient method needs more than a million iterations.The comparison uses the same starting point for the subgradient method.Source: §4.1 · p. 24
- Both algorithms solve the problem in few steps; specifically, Algorithm 3.1 achieves accuracies up to 5 decimal places for objective function values and iterates in less than 20 iterations.Source: §4.1 · p. 25
- Algorithms 3.1 and 3.2 achieve accuracies for both objective-function values and iterates in fewer than 50 iterations; by comparison, subgradient-type methods fail to provide these accuracies even after 10 million iterations [13, Example 5.4].Source: §4.1 · p. 25
4.2 Image deblurring
- The image-deblurring experiment regularizes a nondifferentiable objective using discrete isotropic total variation and a four-level Haar wavelet transform, with Gaussian blur and added white Gaussian noise.Figure 4.4 tracks objective values and ISNR for DR1, DR2, and FBF; Figure 4.5 shows a clean image, its blurred and noisy version, and an Algorithm 3.1 reconstruction.Source: §4.2 · p. 26, Figure 4.4 · p. 28, Figure 4.5 · p. 28