Bregman Forward-Backward Operator Splitting
- PDF / 501,522 Bytes
- 21 Pages / 439.642 x 666.49 pts Page_size
- 63 Downloads / 252 Views
Bregman Forward-Backward Operator Splitting ` 1 · Patrick L. Combettes1 Minh N. Bui Received: 7 May 2020 / Accepted: 1 October 2020 / © Springer Nature B.V. 2020
Abstract We establish the convergence of the forward-backward splitting algorithm based on Bregman distances for the sum of two monotone operators in reflexive Banach spaces. Even in Euclidean spaces, the convergence of this algorithm has so far been proved only in the case of minimization problems. The proposed framework features Bregman distances that vary over the iterations and a novel assumption on the single-valued operator that captures various properties scattered in the literature. In the minimization setting, we obtain rates that are sharper than existing ones. Keywords Banach space · Bregman distance · Forward-backward splitting · Legendre function · Monotone operator Mathematics Subject Classification (2010) 47H05 · 47N10 · 90C25
1 Introduction Throughout, X is a reflexive real Banach space with topological dual X ∗ . We are concerned with the following monotone inclusion problem (see Section 2.1 for notation and definitions). ∗
∗
Problem 1.1 Let A : X → 2X and B : X → 2X be maximally monotone, let f ∈ 0 (X ) be essentially smooth, and let Df be the Bregman distance associated with f . Set C = (int dom f ) ∩ dom A and S = (int dom f ) ∩ zer(A + B). Suppose that C ⊂ int dom B,
Dedicated to Terry Rockafellar on the occasion of his 85th birthday This work was supported by the National Science Foundation under grant DMS-1818946. Patrick L. Combettes
[email protected] Minh N. B`ui [email protected] 1
Department of Mathematics, North Carolina State University, Raleigh, NC 27695-8205, USA
` P.L. Combettes M.N. Bui,
S = ∅, B is single-valued on int dom B, and there exist δ1 ∈ [0, 1[, δ2 ∈ [0, 1], and κ ∈ [0, +∞[ such that (∀x ∈ C)(∀y ∈ C)(∀z ∈ S )(∀y ∗ ∈ Ay)(∀z∗ ∈ Az) y − x, By − Bz κDf (x, y) + y − z, δ1 (y ∗ − z∗ ) + δ2 By − Bz .
(1.1)
The objective is to find x ∈ int dom f such that 0 ∈ Ax + Bx.
(1.2)
The central problem (1.2) has extensive connections with various areas of mathematics and its applications. In Hilbert spaces, if B is cocoercive, a standard method for solving (1.2) is the forward-backward algorithm, which operates with the update xn+1 = (Id +γ A)−1 (xn − γ Bxn ) [17]. This iteration is not applicable beyond Hilbert spaces since A maps to X ∗ = X . In addition, there has been a significant body of work (see, e.g., [3, 6, 8, 12, 13, 16, 18, 19, 23]) showing the benefits of replacing standard distances by Bregman distances, even in Euclidean spaces. Given a sequence (γn )n∈N in ]0, +∞[ and a suitable sequence of differentiable convex functions (fn )n∈N , we propose to solve (1.2) via the iterative scheme −1 (∀n ∈ N) xn+1 = ∇fn + γn A ∇fn (xn ) − γn Bxn , (1.3) which consists of first applying a forward (explicit) step involving B and then a backward (implicit) step involving A. Let us note that the convergence of such an iterative process has not yet been established, even in finite-dimensional spaces
Data Loading...
