Convergence of Inexact Forward–Backward Algorithms Using the Forward–Backward Envelope

This paper deals with a general framework for inexact forward--backward algorithms aimed at minimizing the sum of an analytic function and a lower semicontinuous, subanalytic, convex term. Such framework relies on an implementable inexactness condition for the computation of the proximal operator, and a linesearch procedure which is possibly performed whenever a variable metric is allowed into the forward--backward step. The main focus of the work is the convergence of the considered scheme without additional convexity assumptions on the objective function. Toward this aim, we employ the recent concept of forward--backward envelope to define a continuously differentiable surrogate function, which coincides with the objective at its stationary points, and satisfies the so-called Kurdyka--\L{}ojasiewicz (KL) property on its domain. We adapt the abstract convergence scheme usually exploited in the KL framework to our inexact forward--backward scheme, and prove the convergence of the iterates to a stationary point of the problem, as well as the convergence rates for the function values. Finally, we show the effectiveness and the flexibility of the proposed framework on a large-scale image restoration test problem.

Citation

S. Bonettini, M. Prato, S. Rebegoldi 2020, Convergence of inexact forward-backward algorithms using the forward-backward envelope. SIAM Journal on Optimization 30(4), 3069-3097

Article

Download

View Convergence of Inexact Forward--Backward Algorithms Using the Forward--Backward Envelope