PaperlayerView exact revision on arXiv

Source-linked AI summary

Douglas-Rachford splitting and ADMM for nonconvex optimization: tight convergence results

Andreas Themelis, Panagiotis Patrinos

arXiv:1709.05747v4math.OC

TL;DR

The paper addresses restrictive assumptions in existing nonconvex ADMM theory and develops convergence guarantees for DRS using the Douglas-Rachford envelope (DRE). Its DRS results cover relaxation parameters in (0,4) and are tight for parameters in (0,2].

  • Problem

    The cited ADMM theory requires Lipschitz-continuous minimizers of all subproblems, excluding cases such as discrete variables or rank constraints.

    Source: §1.2.1 · p. 3

  • Method

    The paper uses the Douglas-Rachford envelope to develop nonconvex DRS convergence results and proves a primal equivalence between DRS and ADMM.

    Source: §1.1 · p. 2, §3 · p. 8

  • Results

    DRS convergence results cover relaxation parameters λ ∈ (0, 4) and are tight for λ ∈ (0, 2].

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    The DRS results require no a priori assumption that accumulation points exist and cover relaxation parameters beyond λ ∈ {1, 2}.

    Source: §1.1 · p. 2

    The cited prior ADMM theory assumes Lipschitz-continuous minimizers of all subproblems, ruling out some discrete-variable and rank-constrained cases.

    Source: §1.2.1 · p. 3

Abstract

from arXiv · show

Although originally designed and analyzed for convex problems, the alternating direction method of multipliers (ADMM) and its close relatives, Douglas-Rachford splitting (DRS) and Peaceman-Rachford splitting (PRS), have been observed to perform remarkably well when applied to certain classes of structured nonconvex optimization problems. However, partial global convergence results in the nonconvex setting have only recently emerged. In this paper we show how the Douglas-Rachford envelope (DRE), introduced in 2014, can be employed to unify and considerably simplify the theory for devising global convergence guarantees for ADMM, DRS and PRS applied to nonconvex problems under less restrictive conditions, larger prox-stepsizes and over-relaxation parameters than previously known. In fact, our bounds are tight whenever the over-relaxation parameter ranges in $(0,2]$. The analysis of ADMM uses a universal primal equivalence with DRS that generalizes the known duality of the algorithms.

1. Introduction

The paper develops global convergence guarantees for DRS, PRS, and ADMM on structured nonconvex problems, using the Douglas–Rachford envelope (DRE) and a primal equivalence between DRS and ADMM. Its analysis broadens prior conditions and stepsize ranges, with bounds tight for relaxation parameters in (0, 2].

1. Introduction

  • DRS splits a two-function objective and addresses each component separately; its relaxed form includes classical DRS at λ = 1 and PRS at λ = 2.A fixed point yields a first-order necessary condition, which is sufficient when both functions are convex.Source: §1 · p. 1

1.1. Contributions.

  • The contributions include tight nonconvex DRS convergence results, primal equivalence of DRS and ADMM for arbitrary problems and relaxation parameters, and new ADMM guarantees.The generalized DRE is an exact, continuous, real-valued merit function computable from quantities obtained during DRS or ADMM iterations; adaptive implementations tune stepsizes and penalties without prior Lipschitz-modulus knowledge.Source: §1.1 · pp. 2–3

1.2.1. ADMM.

  • For ADMM, the paper derives convergence results from its universal primal equivalence with DRS, while prior bounds vary in restrictiveness and assumptions.The cited analysis in considers Lipschitz-differentiable f and identity B, and its β > 2L bound is more conservative than the paper’s except in a worst-case scenario.Source: §1.1 · p. 2, §1.2.1 · p. 3

1.2. Comparisons & related work.

  • Earlier DRS global analyses were limited in relaxation choices or problem conditions, while some ADMM results required restrictive assumptions or covered only convex or smooth functions.The paper also generalizes earlier primal equivalence results beyond the convex case and λ = 1.Source: §1.2.1 · p. 3, §1.2.2 · p. 4

1.2.2. Douglas-Rachford splitting.

  • For DRS and PRS, the analysis covers relaxation parameters λ ∈ (0, 4), larger stepsize ranges, and PRS without a strong-convexity-modulus restriction; bounds are optimal for λ ∈ (0, 2].The DRE’s lower boundedness supports vanishing fixed-point residuals without coercivity assumptions; the Figure 1 comparison uses σ/L on the x-axis and maximum convergent stepsize on the y-axis.Source: §1.2.2 · p. 4, Figure 1 · p. 5

2. Background

The background establishes notation and properties used in the convergence analysis, including smoothness and hypoconvexity, proximal mappings, and Moreau envelopes.

2.1. Notation.

  • The notation section defines extended-real functions, level sets and level boundedness, set-valued mappings, and regular, limiting, and horizon subdifferentials.It also defines smoothness through a Lipschitz-continuous gradient and relates smooth functions to hypoconvexity.Source: §2.1 · pp. 5–6

2.2. Smoothness and hypoconvexity.

  • A σ-hypoconvex function generalizes convexity: σ = 0 gives convexity, while σ > 0 gives σ-strong convexity.For smooth functions, the gradient-based bounds connect the hypoconvexity parameter σ and smoothness modulus L to quadratic bounds on function differences.Source: §2.2 · p. 6

2.3. Proximal mapping.

  • The proximal mapping maps an input to minimizers of the function plus a quadratic term, and the Moreau envelope is the corresponding minimum-value function.For smooth functions and stepsizes below the stated threshold, the proximal mapping is single-valued and has stated monotonicity and cocoercivity properties.Source: §2.2 · p. 7, §2.3 · p. 7
  • For a prox-bounded lower-semicontinuous function, the proximal mapping is nonempty- and compact-valued below its prox-boundedness threshold.For the smooth-function setting, the proximal mapping is Lipschitz and invertible, with the inverse also Lipschitz as stated in the passage.Source: §2.3 · p. 7

3. Douglas-Rachford envelope

The Douglas-Rachford envelope (DRE) connects DRS to the forward-backward envelope and serves a similar role to an exact penalty function for forward-backward splitting. Under Assumption I, it is strictly continuous and, for γ < 1/Lϕ1, shares minimization and level-boundedness properties with the original objective.

3. Douglas-Rachford envelope

  • The DRS v-update minimizes a majorization model of the original objective, replacing its smooth function with a quadratic upper bound.The envelope is defined by the value of this v-update minimization problem.Source: §3 · p. 8
  • The DRE serves a role for DRS similar to the forward-backward envelope’s exact-penalty role for forward-backward splitting.The DRE is the value of the minimization problem defining the DRS v-update and is closely connected to the forward-backward envelope.Source: §3 · p. 8

3.1. Properties. γ

  • Under Assumption I, the DRE is real-valued and strictly continuous for γ < 1/Lϕ1.Source: §3.1 · p. 9
  • For γ < 1/Lϕ1, the DRE and original objective have equivalent infima, minimizers under an invertible change of variable, and level-boundedness.The stated DRS stepsizes are well defined for γ in (0, 1/Lϕ1).Source: §3 · p. 8, §3.1 · p. 9

4. Convergence of Douglas-Rachford splitting

This section establishes DRS descent and convergence guarantees across relaxation parameters, including an adaptive-stepsize variant, and examines tight parameter bounds through examples and a necessary-and-sufficient convergence condition for PRS.

4. Convergence of Douglas-Rachford splitting

  • The DRS decrease property for the Douglas–Rachford envelope extends to arbitrary relaxation parameters λ ∈ (0, 4), with tight stepsize ranges provided when λ ∈ (0, 2]; its residual vanishes without coercivity.Source: §4 · p. 10
  • Under Theorem 4.1’s stepsize and relaxation conditions, DRS iterates have a square-summable residual, shared cluster points that are stationary, and are bounded when ϕ has bounded level sets.If ϕ is level bounded and ϕ1 and ϕ2 are semialgebraic, the two iterate sequences converge to the same stationary point.Source: §4 · pp. 13–14

4.1. Adaptive variant.

  • Adaptive DRS reduces its stepsize when sufficient decrease fails; reductions occur only finitely often, and under level boundedness and semialgebraicity its sequences converge to the same stationary point.The adaptive test also requires function evaluations at each iteration, in addition to recomputing u and v after a stepsize decrease.Source: §4.1 · pp. 14–15

4.2. Tightness of the results.

  • For any L > 0 and σ ∈ [−L, L], there exist ϕ1, ϕ2 such that for all s0, γ ≥ 1/L, and λ > 0, DRS iterates have ∥sk − sk+1∥ ↛ 0.Source: §4.2 · p. 16
  • A second example shows that λ > 2(1 + γσ) prevents the residual from vanishing, except when the starting point is a DRS fixed point; together the bounds imply λ ∈ (0, 4) when ϕ2 is nonconvex.For λ > 2, the text also states that γ must exceed (λ − 2)/(2σϕ1), when ϕ1 is strongly convex.Source: §4.2 · pp. 16–17
  • The stated DRS stepsize bound is tight for ensuring convergence.Source: §4.2 · p. 17
  • PRS converges if and only if ϕ1 is strongly convex and γ < 1/Lϕ1.Source: §4.2 · p. 17

5. Alternating direction method of multipliers

The section uses image functions to establish a primal equivalence between ADMM and DRS, transfer convergence guarantees to ADMM, and develop an adaptive variant. It also examines conditions for lower semicontinuity and smoothness of image functions.

5. Alternating direction method of multipliers

  • Image functions preserve properness and inherit strong convexity with modulus σ_h/∥C∥² when h is proper, lower semicontinuous, and σ_h-strongly convex.The section introduces image functions as a tool for expressing ADMM in DRS form.Source: §5 · pp. 17–18

5.1. A universal equivalence of DRS and ADMM.

  • Theorem 5.5 establishes a primal equivalence between DRS and ADMM for any relaxation λ when ADMM subproblems have solutions, linking their iterates through image functions.The equivalence extends beyond the previously noted λ = 1 case; under additional smoothness and penalty conditions, the theorem also relates the DRE to the ADMM augmented Lagrangian.Source: §5.1 · pp. 18–19

5.2. Convergence of the ADMM.

  • Under Assumption II, ADMM’s augmented Lagrangian decreases, cluster points satisfy the KKT conditions with the same limiting cost, and specified sequences are bounded under level-boundedness conditions.Theorem 5.6 additionally ensures boundedness of the full iterate sequence when f is continuously differentiable with Lipschitz gradient.Source: §5.2 · p. 20
  • If Φ is level bounded and f and g are semialgebraic, ADMM converges in (Axk, yk, Bzk), the sequence identified by the primal equivalence.The equivalence does not establish convergence of the full (xk, yk, zk) sequence.Source: §5.2 · pp. 21–22

5.3. Adaptive variant.

  • With a lower-bounded penalty sequence, adaptive ADMM cluster points satisfy the KKT conditions and attain the limiting cost; further boundedness and convergence follow under additional conditions.The additional conditions are that β exceeds L(Af) at some iteration and Φ is level bounded; semialgebraicity then ensures convergence of (Axk, yk, Bzk).Source: §5.3 · pp. 22–23

5.4.1. Lower semicontinuity of the image function.

  • A sufficient condition for (Bg) to be lower semicontinuous requires nearby image values to have minimizers that exist and remain bounded in distance, without requiring uniqueness.The stated criterion also does not require bounded sets of minimizers; it requires only that minimizers not be arbitrarily far away.Source: §5.4.1 · p. 23
  • For lower semicontinuous g, (Bg) is lower semicontinuous if and only if g(z̄ + d) ≥ inf_{d∈ker B} g(z̄ + d) for every z̄ in dom g; level boundedness of g suffices.The equivalence characterizes when the image function inherits lower semicontinuity from g.Source: §5.4.1 · p. 24
  • A constructed sequence shows that (Bg) can fail lower semicontinuity at Bz.Source: §5.4.1 · p. 24
  • Conditions ensuring nonempty minimizer sets suffice for lower semicontinuity but are not necessary: (Bg)(s) = -|s| is lsc despite empty minimizers at s = 0.Source: §5.4.1 · p. 24

5.4.2. Smoothness of the image function.

  • Smoothness relative to A is a minimal requirement for ensuring smoothness of (Af), since f can be represented locally as q(Ax) with smooth q.Source: §5.4.2 · p. 25
  • For surjective A and lsc f under uniform level-boundedness, (Af) is smooth if f is smooth relative to A or is C1,1 with single-valued Lipschitz minimizers.In the relative-smoothness case, (Af) inherits the constants L_f,A and σ_f,A.Source: §5.4.2 · p. 25
  • For convex C1,1 f, L(Af) = L_f σ+(A⊤A) and σ(Af) = σ_f/∥A∥2.Source: §5.4.2 · p. 25

6. Conclusive remarks

The paper establishes convergence results for nonconvex DRS and ADMM across relaxation parameters, with tight bounds in specified regimes. Its analysis uses the DRE and a primal equivalence between DRS and ADMM.

6. Conclusive remarks

  • Convergence is established for nonconvex DRS and ADMM across relaxation parameters λ ∈ (0, 4), with larger prox-stepsizes and relaxation ranges than previously known.The bounds are tight for λ ∈ (0, 2] and when the differentiable function is nonconvex.Source: §6 · p. 26
  • The analysis also establishes that λ < 4 is necessary, and that λ > 2 requires a lower bound on the stepsize.Source: §6 · p. 26
  • The theory uses the DRE as a continuous, real-valued exact penalty function and a primal equivalence between DRS and ADMM for nonconvex problems.The paper presents the DRE as a better Lyapunov function for DRS than the augmented Lagrangian because of its closer connection to the cost function and DRS iterations.Source: §6 · p. 26

Appendix A. Proofs of Section 2

The proof invokes a subdifferential characterization of smoothness to establish continuous differentiability and then obtain the claimed hypoconvexity.

Appendix A. Proofs of Section 2

Proof of Lemma 2.1

The proof derives smoothness inequalities for hypoconvex functions and uses convexity-based arguments to establish properties of their subdifferentials.

Proof of Lemma 2.1

  • When σ is not nonnegative, the proof shifts h by a quadratic term, noting that continuous differentiability is preserved under this shift.Source: Proof of Lemma 2.1 · p. 27
  • Convexity and the quadratic upper bound on h imply that its subdifferential is everywhere single-valued, yielding continuous differentiability.Source: Proof of Lemma 2.1 · p. 27
  • For an L-smooth, σ-hypoconvex function, the proof combines convex smoothness with inequality (A.1) to derive the stated lower bound on h(y).The argument applies for σ ≤ 0 and uses a bound involving both ∥y − x∥² and ∥∇h(y) − ∇h(x)∥².Source: Proof of Lemma 2.1 · p. 27

Proof of Proposition 2.3

The proposition's proof uses strong convexity of a regularized function to characterize its proximal map, then derives regularity properties of the Moreau envelope.

Proof of Proposition 2.3

  • Strong convexity of h plus the quadratic term makes proximal minimizers unique and characterizes them by stationarity.Source: Proof of Proposition 2.3 · p. 27
  • The proof relates proximal outputs at two inputs through strong convexity and smoothness of the regularized function.It uses this relation to obtain strong monotonicity and a bound on the proximal map.Source: Proof of Proposition 2.3 · p. 28
  • The Moreau envelope is differentiable, with its gradient expressed using the proximal map, and the proof derives its smoothness and hypoconvexity bounds.Source: Proof of Proposition 2.3 · p. 28

Proof of Proposition 5.2.

The proof characterizes the image function through constrained minimization over preimages and shows that the penalized minimizer is globally optimal. It also establishes attainment and uniqueness for image-function values on their domain.

Proof of Proposition 5.2.

  • When s lies outside C dom h, the image function is infinite; on its domain, its value at Cxβ equals the infimum of h over points with that image.The proof uses the fact that adding any v in ker C preserves Cxβ and that h(xβ) ≤ h(xβ + v).Source: Proof of Proposition 5.2 · p. 28
  • The optimality of xβ gives h(xβ) + β/2∥Cxβ − s̄∥² ≤ h(x) + β/2∥Cx − s̄∥² for every x.The proof obtains this inequality from the image-function relation and the optimality of xβ.Source: Proof of Proposition 5.2 · p. 28
  • For each s in dom(Ch), strong convexity gives a unique xs with Cxs = s and (Ch)(s) = h(xs).For vs in ∂(Ch)(s), the proof also establishes Cᵀvs ∈ ∂h(xs).Source: Proof of Proposition 5.4 · p. 29

Proof of Proposition 5.4

The proof transfers the strong-convexity inequality for h at the minimizing preimages to the image function by identifying their function values.

Proof of Proposition 5.4

  • For s′ in dom(Ch), the inequality lower-bounds h(xs′) by h(xs), a subgradient term, and a quadratic term in ∥s′ − s∥.The inequality is stated for vs ∈ ∂(Ch)(s).Source: Proof of Proposition 5.4 · p. 29
  • The quadratic term supplies the strong-convexity contribution in the inequality between the minimizing preimages.The bound includes σh and ∥C∥².Source: Proof of Proposition 5.4 · p. 29
  • Using h(xs) = (Ch)(s) and h(xs′) = (Ch)(s′) transfers the inequality to Ch, establishing strong convexity of the image function.Source: Proof of Proposition 5.4 · p. 29
Loading 1709.05747v4…