Variable Metric Three Operator Splitting

Abstract

To minimize the sum $f+g+h$ of three convex functions when $f$ is differentiable with a Lipschitz-continuous gradient, we present a proximal algorithm, variable-metric three operator splitting (VMTOS), a generalization of the three operator splitting (TOS) scheme of Davis and Yin. We establish convergence guarantees by controlling changes in the metric. The smallest saddle-point residual among the first $k$ primal-dual iterates is $\tilde{O}(k^{-1/2})$. When $f$ and the convex conjugate $h^{\ast }$ are strongly convex and the accepted metrics and their inverses are uniformly bounded, the rate improves to $\tilde{O}({\beta }^k)$ for some $\beta \in (0,1)$. We develop a practical Barzilai--Borwein update for diagonal metrics that satisfies our bound on metric changes. Under the same strong convexity assumptions, this update guarantees the required uniform metric bounds, yielding R-linear convergence. Numerical experiments on benchmark optimization problems show that VMTOS is competitive with other proximal algorithms.