Variable metric forward-backward algorithm for composite minimization problems

Research output: Contribution to journalArticlepeer-review

14 Downloads (Pure)

Abstract

We present a forward-backward-based algorithm to minimize a sum of a differentiable function and a nonsmooth function, both being possibly nonconvex. The main contribution of this work is to consider the challenging case where the nonsmooth function corresponds to a sum of nonconvex functions, resulting from composition between a strictly increasing, concave, differentiable function and a convex nonsmooth function. The proposed variable metric composite function forward-backward (C2FB) algorithm circumvents the explicit, and often challenging, computation of the proximity operator of the composite functions through a majorize-minimize approach. Precisely, each composite function is majorized using a linear approximation of the differentiable function, which allows one to apply the proximity step only to the sum of the nonsmooth functions. We prove the convergence of the algorithm iterates to a critical point of the objective function leveraging the Kurdyka-Łojasiewicz inequality. The convergence is guaranteed even if the proximity operators are computed inexactly, considering relative errors. We show that the proposed approach is a generalization of reweighting methods, with convergence guarantees. In particular, applied to the log-sum function, our algorithm reduces to a generalized version of the celebrated reweighted \ell 1 method. Finally, we show through simulations on an image processing problem that the proposed C2FB algorithm necessitates fewer iterations to converge and leads to better critical points compared with traditional reweighting methods and classic forward-backward algorithms.

Original languageEnglish
Pages (from-to)1215-1241
Number of pages27
JournalSIAM Journal on Optimization
Volume31
Issue number2
Early online date6 May 2021
DOIs
Publication statusPublished - 2021

Keywords

  • Composite minimization problem
  • Forward-backward algorithm
  • Inverse problems
  • Majorize-minimize method
  • Nonconvex optimization
  • Nonsmooth optimization
  • Proximity operator
  • Reweighting algorithm

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Variable metric forward-backward algorithm for composite minimization problems'. Together they form a unique fingerprint.

Cite this