PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM

Pontus Giselsson, Stephen Boyd

arXiv:1410.8479v5math.OC

TL;DR

Douglas-Rachford splitting and ADMM have established convergence-rate results, and this paper develops explicit global linear bounds under strong convexity and smoothness assumptions. It shows the bounds are tight for the considered class, optimizes algorithm parameters and metrics, and proposes heuristics for problems that do not meet the assumptions.

  • Problem

    The paper addresses convergence-rate analysis and parameter selection for Douglas-Rachford splitting and ADMM, whose general convergence rate was recently shown to be O(1/k).

    Source: §1 · p. 2

  • Method

    The paper derives rate bounds under strong convexity and smoothness, optimizes algorithm parameters and a metric for those bounds, and proposes heuristic selections when assumptions fail.

    Source: §1 · pp. 2–3

  • Results

    The paper establishes tight global linear convergence bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions, for feasible algorithm parameters.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper presents metric and parameter selection methods, including heuristics for problems that do not satisfy the linear-convergence assumptions.

    Source: §1 · p. 3, §8 · p. 21

    The Douglas-Rachford algorithm with α = 1 is not guaranteed to converge in general because the composition of the reflected proximal operators is nonexpansive.

    Source: §3 · p. 5

Abstract

from arXiv · show

Recently, several convergence rate results for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) have been presented in the literature. In this paper, we show global linear convergence rate bounds for Douglas-Rachford splitting and ADMM under strong convexity and smoothness assumptions. We further show that the rate bounds are tight for the class of problems under consideration for all feasible algorithm parameters. For problems that satisfy the assumptions, we show how to select step-size and metric for the algorithm that optimize the derived convergence rate bounds. For problems with a similar structure that do not satisfy the assumptions, we present heuristic step-size and metric selection methods.

1 Introduction

Douglas-Rachford splitting and ADMM address convex optimization problems, and this paper derives and optimizes explicit global linear convergence bounds under strong convexity and smoothness assumptions. It also gives heuristic metric and parameter selection for problems that do not meet those assumptions.

1 Introduction

  • The motivating class minimizes f(x) + g(x), with proper closed convex functions, and includes applications such as compressed sensing, statistical estimation, model predictive control, and medical imaging.The notation section specifies real vectors and matrices, Hilbert spaces and their induced norms, conjugate functions, adjoints, and operator-related sets and classes.Source: §1 · p. 1, §1.1 · p. 3
  • Douglas-Rachford splitting applied to the Fenchel dual is equivalent to ADMM, while general convergence was known for α ∈ (0, 1) and γ > 0 and only recently had an O(1/k) rate been shown.The introduction situates the paper among prior global and local linear-convergence results.Source: §1 · p. 2
  • The paper derives explicit global linear convergence bounds for Douglas-Rachford splitting and ADMM when f is strongly convex and smooth, and shows the bounds are tight for feasible algorithm parameters.It also describes how to select algorithm parameters to optimize the bounds.Source: §1 · p. 2
  • The convergence bounds depend on problem smoothness and strong convexity parameters, so the paper selects a Euclidean metric matrix M to optimize the rate bound.The metric defines the inner product and induced norm; it is typically chosen to be diagonal.Source: §1 · p. 3
  • For problems that lack the properties needed to ensure linear convergence, the paper presents heuristic metric and parameter selection methods and evaluates them in two numerical examples.The heuristics target applications including model predictive control, statistical estimation, compressed sensing, and medical imaging.Source: §1 · p. 3

2 Background

The background section introduces standard operator and function properties used in the paper. It distinguishes Lipschitz, nonexpansive, contractive, and averaged mappings, and states curvature properties of strongly convex and smooth functions.

2 Background

  • A β-Lipschitz mapping has β = 1 in the nonexpansive case and β ∈ [0, 1) in the contractive case.The section introduces these mapping definitions alongside strong monotonicity and cocoercivity.Source: §2 · p. 4
  • An α-averaged mapping is a convex combination of the identity and a nonexpansive mapping, with α ∈ (0, 1).The definition expresses T as (1 − α)Id + αS for nonexpansive S.Source: §2 · p. 4
  • Strong convexity gives a minimum curvature of at least σ, while smoothness describes maximal curvature; a function that is σ-strongly convex and β-smooth satisfies β ≥ σ.The section introduces strong convexity and smoothness for convex functions.Source: §2 · pp. 4–5

3 Douglas-Rachford splitting

The section develops Douglas–Rachford splitting for minimizing f+g, establishes linear convergence under strong convexity and smoothness, optimizes its rate bound, and proves the bound tight.

3 Douglas-Rachford splitting

  • Douglas–Rachford splitting applies an averaged composition of reflected proximal operators to solve minimize f(x)+g(x), with α∈(0,1) guaranteeing general-case convergence.The iterates approach a fixed point, whose proximal image solves the optimization problem.Source: §3 · p. 5

3.1 Linear convergence

  • The reflected proximal operator is contractive under the paper’s regularity assumptions, yielding the contraction factor used to establish linear convergence.The paper identifies its interpretation of the proximal operator as the key to deriving a tight factor.Source: §3.1 · p. 6
  • Under Assumption 1, Douglas–Rachford converges linearly at rate |1−α|+αδ for the stated γ and α range.The bound is tight for this problem class for every feasible γ and α.Source: §3.1 · p. 7, §3.2 · p. 9
  • The bound is optimized by α=1 and γ=1/√(βσ), making Peaceman–Rachford optimal under Assumption 1.The reflected proximal operator becomes contractive under these assumptions, unlike its general nonexpansive behavior.Source: §3.1 · pp. 7–8

3.2 Tightness of bounds

  • The rate bound is tight for the specified problem class across feasible algorithm parameters; outside the stated α interval, a qualifying problem exists that the algorithm does not solve.The tightness result is also stated to generalize to any real Hilbert space.Source: §3.2 · p. 9

4 ADMM

ADMM is analyzed through its equivalent Douglas–Rachford iteration on the Fenchel dual, where assumptions on the primal problem yield linear convergence bounds. The bounds are tight for the stated problem class and feasible algorithm parameters.

4 ADMM

  • The primal problem minimize f(x) + g(y) subject to Ax + By = c is handled via its negative Fenchel dual, with Douglas–Rachford used for analysis and standard ADMM used in implementation.The stated assumptions include that A is surjective; in the Euclidean case this means A has full row rank.Source: §4 · pp. 9–10

4.1 Linear convergence

  • Under Assumption 2, the dual objective component d1 is strongly convex and smooth, enabling linear-rate analysis of Douglas–Rachford on the dual and equivalently ADMM on the primal.Its dual parameters are ˆβ = ∥A∗∥²/σ and ˆσ = θ²/β, with θ > 0 satisfying ∥A∗µ∥ ≥ θ∥µ∥.Source: §4 · p. 9, §4.1 · pp. 10–11
  • For ADMM under Assumption 2, the rate-bound optimizing parameters are α = 1 and γ = 1/√(ˆβˆσ).The corollary gives an allowed interval for α and permits any γ > 0.Source: §4.1 · p. 11

4.2 Tightness of bounds

  • The ADMM rate bound is tight for the class satisfying Assumption 2 across its specified α and γ values; outside the allowed α interval, some such problem is not solved.The corresponding dual Douglas–Rachford bound is tight as well.Source: §4.2 · p. 12

5 Related work

The paper compares its optimal rate bounds with prior linear-convergence results for Douglas–Rachford splitting and ADMM. It reports tighter bounds in several comparisons and broader scope than the matching bound in.

5 Related work

  • The rate bound in [16] directly analyzes ADMM, and Figure 1 indicates that the paper’s bound is tighter.The comparison is made using dual-problem parameters.Source: §5 · p. 13
  • Corollary 2 gives a tighter rate bound than the fast Douglas–Rachford bound in [40], which is better than that work’s standard-method bound.The comparison is to the fast variant applied to the dual.Source: §5 · p. 14
  • The bound in coincides with Corollary 2, while this work extends the result beyond Euclidean quadratic problems with linear inequality constraints to broader spaces, functions, and both methods.The extension covers arbitrary real Hilbert spaces, general smooth strongly convex f, and any proper, closed, convex g.Source: §5 · p. 14
  • The paper’s bound is tighter than, whose rate curve requires a parameter sweep and small semidefinite programs rather than an explicit bound.The sweep’s quantization level produces steps in the plotted curve.Source: §5 · p. 14

6 Metric selection

For strongly convex, smooth problems, the convergence bound can be optimized by selecting the space—and thus the metric—in which the algorithm runs. When the linear-convergence assumptions fail, the paper proposes metric and parameter heuristics based on conditioning quadratic approximations.

6 Metric selection

  • Under Assumption 3, the dual function d1 is ∥EAH^-1A^T E^T∥²-smooth and λ_min(EAL^-1A^T E^T)-strongly convex, with the latter constant positive.The stated conditions include 1-strong convexity and 1-smoothness of f on specified spaces and surjectivity of A.Source: §6 · p. 14
  • Choosing K = E^T E to optimize the bound for ADMM on the primal (or Douglas–Rachford splitting on the dual) reduces metric selection to a choice of E.The metric changes the smoothness and strong-convexity constants of the dual function; a diagonal K is proposed when the general choice is too expensive for proximal evaluations.Source: §6 · pp. 14, 16

6.1 Heuristic metric selection

  • When the assumptions for linear convergence fail, the heuristic for quadratic problems chooses a diagonal metric to minimize the pseudo condition number of the approximated dual Hessian AQ†A^T.The approximation uses the quadratic part of f; the paper states that this heuristic recovers the optimal metric choice when linear convergence holds.Source: §6.1 · pp. 17–18
  • For an affine-subspace indicator with Q strongly convex on ker L, the heuristic instead minimizes the pseudo condition number of the dual Hessian AP11A^T and selects γ by the stated rule.This is a separate case from the quadratic-part approximation used when the assumptions fail in all three listed ways.Source: §6.1 · p. 18

7 Numerical example

The numerical examples evaluate metric and parameter selection for ADMM in a linearly convergent weighted-Lasso problem and an aircraft-control problem without linear convergence. The results report iteration-bound consistency and benefits from metric selection, while the heuristic γ choice need not match the empirical best.

7.1 A problem with linear convergence

  • For the weighted-Lasso example, actual iteration counts are fairly consistent with the theoretical bounds, and an appropriately chosen metric offers substantial gains.The comparison uses ADMM with α = 1 and varies γ around the theoretically optimal value in the Euclidean and optimal-metric settings.Source: §7.1 · pp. 18–19, Figure 2 · p. 19

7.2 A problem without linear convergence

  • The aircraft-control test is a model predictive control problem for which all three stated conditions guaranteeing linear convergence are violated.The selected diagonal metric is computed offline for reuse across online samples.Source: §7.2 · pp. 20–21
  • About one order of magnitude fewer iterations is achieved on the aircraft-control example with the selected metric than in the Euclidean setting.Over-relaxation performs better than standard ADMM in this example; the proposed γ⋆ is reasonable but does not coincide with the empirically best γ.Source: Figure 3 · p. 20, §7.2 · p. 21

8 Conclusions

The paper concludes that its global linear-convergence bounds for Douglas–Rachford splitting and ADMM are tight and uses them to develop metric and parameter selection methods. An appendix lemma gives a piecewise expression for a contraction factor used in the analysis.

8 Conclusions

  • The paper reports tight global linear-convergence bounds for Douglas–Rachford splitting and ADMM, alongside numerical evaluation of the proposed ADMM metric and parameter selections.The conclusion summarizes the bounds, selection methods, and numerical examples.Source: §8 · p. 21

A A lemma

  • The lemma expresses the factor as max(ψ(γσ), −ψ(γβ)), with the active term switching at γ = 1/√(βσ).The stated factor lies in [0, 1).Source: A A lemma · pp. 25–26

B Proof to Proposition 2

The appendix derives properties of the proximal-conjugate function from strong convexity and smoothness, then uses them to bound the reflected operator’s Lipschitz constant. The resulting expression is a contraction factor for the theorem’s convergence analysis.

B Proof to Proposition 2

  • Strong convexity and smoothness of f imply corresponding smoothness and strong convexity constants for f*γ, which yield a cocoercivity bound for its gradient.The proof derives the cocoercivity constant as 1/(1+γσ) − 1/(1+γβ).Source: B Proof to Proposition 2 · p. 26

C Proof to Theorem 1

  • The reflected operator Rγf has a piecewise Lipschitz bound, switching at γ = 1/√(βσ), and the resulting factor lies in [0, 1).The two expressions are (1−γσ)/(1+γσ) below the switch and (γβ−1)/(1+γβ) above it.Source: C Proof to Theorem 1 · p. 27

D Proof to Theorem 2

The proof establishes a contraction factor for the Douglas–Rachford composition and uses it to identify the relaxation range yielding convergence.

D Proof to Theorem 2

  • Rγg is nonexpansive, while Rγf is δ-contractive, so their composition is δ-contractive.The proof then treats the Douglas–Rachford operator T = (1−α)I + αRγgRγf as having the same fixed point as the composition.Source: D Proof to Theorem 2 · pp. 27–28
  • The Douglas–Rachford operator is contractive for α in (0, 2/(1+δ)).The proof uses δ = max((1−γσ)/(1+γσ), (γβ−1)/(γβ+1)), with δ ∈ [0, 1).Source: D Proof to Theorem 2 · pp. 27–28
  • The proof shows that the factor is less than one exactly when α lies in (0, 2/(1+δ)).This condition concludes the proof for the stated contraction bound.Source: D Proof to Theorem 2 · p. 28

E Proof of Corollary 1

The corollary proof links a fixed point of the reflected-proximal composition to a solution and bounds the resulting iterates using the Lipschitz property of the proximal map.

E Proof of Corollary 1

  • The proximal map proxγf is identified with ∇f*γ, which is 1/(1+γσ)-Lipschitz.The proof takes x⋆ = proxγf(z̄) for a fixed point z̄ of RγgRγf.Source: E Proof of Corollary 1 · p. 28
  • The cited passage states only the right-hand expression, 1/(1+γσ)(|1−α|+δα)^(k+1)∥z0−z̄∥, without identifying a left-hand side.Source: E Proof of Corollary 1 · p. 28
  • The proof applies Theorem 2 to obtain the stated iterate bound.The passage attributes the second and third inequalities to Theorem 2.Source: E Proof of Corollary 1 · p. 28

F Proof of Theorem 3

The proof checks four parameter and initialization cases, showing that their exact rate factors attain Theorem 2’s bound within its convergence range and are at least one outside it.

F Proof of Theorem 3

  • The proof uses separability for g1 and Rγg1 = Id, and notes Rγg2 = −Id with linear Rγf for the g2 cases.It verifies the first case explicitly and leaves the other three to similar arguments.Source: F Proof of Theorem 3 · pp. 28–29
  • With g = g1, λi is σ for α ≤ 1 and γ ≤ 1/√(βσ), and β for α ≥ 1 and γ ≥ 1/√(βσ).The corresponding initializations are z0 = (0, 1) and z0 = (1, 0), respectively.Source: F Proof of Theorem 3 · p. 29
  • With g = g2, λi is β for α ≤ 1 and γ ≥ 1/√(βσ), and σ for α ≥ 1 and γ ≤ 1/√(βσ).The corresponding initializations are z0 = (1, 0) and z0 = (0, 1), respectively.Source: F Proof of Theorem 3 · p. 29
  • For α in (0, 2/(1+δ)), with δ as in (14), exact rate factors (40) for cases (i)–(ii) and (42) for (iii)–(iv) equal Theorem 2’s upper bound; outside this interval, the exact rate is at least one and does not converge.Source: F Proof of Theorem 3 · p. 29
Loading 1410.8479v5…