Proximal alternating linearized method for nonconvex and nonsmooth problems

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.

Reference

Jérôme Bolte, Shoham Sabach, and Marc Teboulle, “Proximal alternating linearized method for nonconvex and nonsmooth problems”, Mathematical Programming, vol. 146, August 2014, pp. 459–494.