Projective splitting with forward steps
- PDF / 877,751 Bytes
- 40 Pages / 439.37 x 666.142 pts Page_size
- 98 Downloads / 215 Views
Series A
Projective splitting with forward steps Patrick R. Johnstone1 · Jonathan Eckstein1 Received: 20 July 2018 / Accepted: 7 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020
Abstract This work is concerned with the classical problem of finding a zero of a sum of maximal monotone operators. For the projective splitting framework recently proposed by Combettes and Eckstein, we show how to replace the fundamental subproblem calculation using a backward step with one based on two forward steps. The resulting algorithms have the same kind of coordination procedure and can be implemented in the same block-iterative and highly flexible manner, but may perform backward steps on some operators and forward steps on others. Prior algorithms in the projective splitting family have used only backward steps. Forward steps can be used for any Lipschitz-continuous operators provided the stepsize is bounded by the inverse of the Lipschitz constant. If the Lipschitz constant is unknown, a simple backtracking linesearch procedure may be used. For affine operators, the stepsize can be chosen adaptively without knowledge of the Lipschitz constant and without any additional forward steps. We close the paper by empirically studying the performance of several kinds of splitting algorithms on a large-scale rare feature selection problem. Mathematics Subject Classification 49M27 · 47H05 · 47J25
1 Introduction n , consider the problem of finding z ∈ H For a collection of real Hilbert spaces {Hi }i=0 0 such that
0∈
n
G i∗ Ti (G i z),
(1)
i=1
B
Patrick R. Johnstone [email protected] Jonathan Eckstein [email protected]
1
Department of Management Sciences and Information Systems, Rutgers Business School, Rutgers University, Newark, New Brunswick, USA
123
P. R. Johnstone, J. Eckstein
where G i : H0 → Hi are linear and bounded operators, Ti : Hi → 2Hi are maximal monotone operators and additionally there exists a subset IF ⊆ {1, . . . , n} such that for all i ∈ IF the operator Ti is Lipschitz continuous. An important instance of this problem is
min
x∈H0
n
f i (G i x),
(2)
i=1
where every f i : Hi → R is closed, proper and convex, with some subset of the functions also being differentiable with Lipschitz-continuous gradients. Under appropriate constraint qualifications, (1) and (2) are equivalent. Problem (2) arises in a host of applications such as machine learning, signal and image processing, inverse problems, and computer vision; see [4,9,12] for some examples. Operator splitting algorithms are now a common way to solve structured monotone inclusions such as (1). Until recently, there were three underlying classes of operator splitting algorithms: forward– backward [29], Douglas/Peaceman–Rachford [25], and forward–backward–forward [35]. In [14], Davis and Yin introduced a new operator splitting algorithm which does not reduce to any of these methods. Many algorithms for more complicated monotone inclusions and optimization pro
Data Loading...
