Forward-Reflected-Backward algorithm with Linesearch

In this article, we aim to solve a monotone inclusion problem involving the sum of a maximally monotone operator and a continuous operator.

While several algorithms exist to solve this problem when the continuous operator is cocoercive or Lipschitz continuous, they typically require the estimation of the global Lipschitz constant, which can be computationally expensive and often imposes overly restrictive step-sizes.

To avoid these limitations and to handle merely continuous operators, linesearch subroutines are employed.

A popular method in this context is the forward-backward-forward (FBF) algorithm (also known as Tseng's splitting), which utilizes a linesearch to guarantee convergence.

However, a drawback of FBF is that the continuous operator must be evaluated twice per iteration.

On the other hand, the forward-reflected-backward (FRB) algorithm proposed by Malitsky and Tam (2020) requires only a single evaluation of the operator per iteration.

Although a linesearch version of FRB exists, its convergence is guaranteed only for locally Lipschitz operators; in fact, we present an example demonstrating that this existing linesearch can fail to terminate when the operator is merely continuous.

In this work, we propose a novel linesearch strategy for FRB that is well defined and guarantees convergence even when the operator is merely continuous.

We also extend the proposed algorithm to handle additional cocoercive and Lipschitz continuous operators.

Finally, we provide numerical experiments on saddle-point problems and image restoration.

The numerical results show that FRB with the proposed linesearch can accelerate the numerical convergence even when the operator is Lipschitz continuous.

In addition, these results show that the proposed method is competitive with linesearch FBF, offering considerable computational advantages in various scenarios.