Proximal alternating linearized minimization for nonconvex and nonsmooth problems

• 成果类型: Article
• 署名作者: Bolte, Jerome; Sabach, Shoham; Teboulle, Marc
• 署名单位: Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Tel Aviv University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0701-9
• 发表日期: 2014
• 页码: 459-494
• 关键词: nonnegative matrix factorization; CONVERGENCE; algorithms; DECOMPOSITION

摘要

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-Aojasiewicz 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.