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 a framework relies on an implementable inexactness condition for the computation of the proximal operator and on a linesearch procedure, which is possibly performed whenever a variable metric is allowed into the forward--backward step. The main focus of this 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--Łojasiewicz (KL) property on its domain. We adapt the abstract convergence scheme usually exploited in the KL framework to our inexact forward--backward scheme, prove the convergence of the iterates to a stationary point of the problem, and prove 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.

Convergence of Inexact Forward--Backward Algorithms Using the Forward--Backward Envelope / Bonettini, S.; Prato, M.; Rebegoldi, S.. - In: SIAM JOURNAL ON OPTIMIZATION. - ISSN 1052-6234. - STAMPA. - 30:(2020), pp. 3069-3097. [10.1137/19M1254155]

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

Rebegoldi, S.
2020

Abstract

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 a framework relies on an implementable inexactness condition for the computation of the proximal operator and on a linesearch procedure, which is possibly performed whenever a variable metric is allowed into the forward--backward step. The main focus of this 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--Łojasiewicz (KL) property on its domain. We adapt the abstract convergence scheme usually exploited in the KL framework to our inexact forward--backward scheme, prove the convergence of the iterates to a stationary point of the problem, and prove 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.
2020
30
3069
3097
Goal 9: Industry, Innovation, and Infrastructure
Bonettini, S.; Prato, M.; Rebegoldi, S.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1213632
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 9
social impact