A block coordinate variable metric forward–backward algorithm

Emilie Chouzenoux, Jean-Christophe Pesquet, Audrey Repetti

Research output: Contribution to journalArticle

Abstract

A number of recent works have emphasized the prominent role played by the Kurdyka-Łojasiewicz inequality for proving the convergence of iterative algorithms solving possibly nonsmooth/nonconvex optimization problems. In this work, we consider the minimization of an objective function satisfying this property, which is a sum of two terms: (i) a differentiable, but not necessarily convex, function and (ii) a function that is not necessarily convex, nor necessarily differentiable. The latter function is expressed as a separable sum of functions of blocks of variables. Such an optimization problem can be addressed with the Forward–Backward algorithm which can be accelerated thanks to the use of variable metrics derived from the Majorize–Minimize principle. We propose to combine the latter acceleration technique with an alternating minimization strategy which relies upon a flexible update rule. We give conditions under which the sequence generated by the resulting Block Coordinate Variable Metric Forward–Backward algorithm converges to a critical point of the objective function. An application example to a nonconvex phase retrieval problem encountered in signal/image processing shows the efficiency of the proposed optimization method.

Original languageEnglish
Pages (from-to)1-29
Number of pages29
JournalJournal of Global Optimization
Early online date10 Feb 2016
DOIs
Publication statusE-pub ahead of print - 10 Feb 2016

Keywords

  • Alternating minimization
  • Block coordinate descent
  • Inverse problems
  • Majorize–Minimize algorithm
  • Nonconvex optimization
  • Nonsmooth optimization
  • Phase retrieval
  • Proximity operator

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Optimization
  • Applied Mathematics
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'A block coordinate variable metric forward–backward algorithm'. Together they form a unique fingerprint.

  • Cite this