Proximal alternating linearized minimization for nonconvex and nonsmooth problems

Jerome Bolte 1 Shoham Sabach 2 Marc Teboulle 2
1 C&O - Equipe combinatoire et optimisation
UPMC - Université Pierre et Marie Curie - Paris 6, CNRS - Centre National de la Recherche Scientifique : FRE3232
Abstract : We introduce a proximal alternating linearized minimization (PALM) algorithm for solving a broad class of nonconvex and nonsmooth minimization problems. Building on the powerful Kurdyka-Łojasiewicz property, we derive a self-contained convergence analysis framework and establish that each bounded sequence generated by PALM globally converges to a critical point. Our approach allows to analyze various classes of nonconvex-nonsmooth problems and related nonconvex proximal forward-backward algorithms with semi-algebraic problem's data, the later property being shared by many functions arising in a wide variety of fundamental applications. A by-product of our framework also shows that our results are new even in the convex setting. As an illustration of the results, we derive a new and simple globally convergent algorithm for solving the sparse nonnegative matrix factorization problem.
Type de document :
Article dans une revue
Mathematical Programming, Springer Verlag, 2014, 146 (1-2), pp.459-494. 〈10.1007/s10107-013-0701-9〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00916090
Contributeur : Estelle Bouzat <>
Soumis le : lundi 9 décembre 2013 - 17:28:55
Dernière modification le : mercredi 21 mars 2018 - 18:57:28

Identifiants

Collections

Citation

Jerome Bolte, Shoham Sabach, Marc Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, Springer Verlag, 2014, 146 (1-2), pp.459-494. 〈10.1007/s10107-013-0701-9〉. 〈hal-00916090〉

Partager

Métriques

Consultations de la notice

541