Optimization Online


Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods

Hédy Attouch(attouch***at***math.univ-montp2.fr)
Jérôme Bolte(jerome.bolte***at***tse-fr.eu)
Benar Fux Svaiter(benar***at***impa.br)

Abstract: In view of the minimization of a nonsmooth nonconvex function f, we prove an abstract convergence result for descent methods satisfying a sufficient-decrease assumption, and allowing a relative error tolerance. Our result guarantees the convergence of bounded sequences, under the assumption that the function f satisfies the Kurdyka-Lojasiewicz inequality. This assumption allows to cover a wide range of problems, including nonsmooth semi-algebraic (or more generally tame) minimization. The specialization of our result to different kinds of structured problems provides several new convergence results for inexact versions of the gradient method, the proximal method, the forward-backward splitting algorithm, the gradient projection and some proximal regularization of the Gauss-Seidel method in a nonconvex setting. Our results are illustrated through feasibility problems, or iterative thresholding procedures for compressive sensing.

Keywords: Nonconvex nonsmooth optimization, semi-algebraic optimization, tame optimization, Kurdyka-Lojasiewicz inequality, descent methods, relative error, sufficient decrease, forward-backward splitting, alternating minimization, proximal algorithms, iterative thresholding, block-coordinate methods, o-minimal structures.

Category 1: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 12/22/2010
Entry Accepted: 12/22/2010
Entry Last Modified: 12/22/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society