Quasi-Newton Methods for Monotone Inclusions: Efficient Resolvent Calculus and Primal-Dual Algorithms\ast

We introduce two quasi-Newton forward-backward splitting algorithms to solve a class of monotone inclusion problems. The bottleneck is the evaluation of the resolvent operator. Changing the metric makes its computation even harder, and this is even true for a simple operator whose resolvent is known for the standard metric. To fully exploit the advantage of adapting the metric, we develop a new efficient resolvent calculus for a low-rank perturbed standard metric, which accounts exactly for quasi-Newton metrics. Moreover, we prove the convergence of our algorithms, including linear convergence rates in case one of the two considered operators is strongly monotone. As a by-product of our general monotone inclusion framework, we introduce two variants of the quasi-Newton primaldual hybrid gradient method (PDHG) for solving saddle point problems. The favorable performance of these two quasi-Newton PDHG methods is demonstrated on several numerical experiments in image processing.