×

zbMATH — the first resource for mathematics

Proximal alternating linearized minimization for nonconvex and nonsmooth problems. (English) Zbl 1297.90125
Summary: 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.

MSC:
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
49M37 Numerical methods based on nonlinear programming
65K10 Numerical optimization and variational techniques
47J25 Iterative procedures involving nonlinear operators
49M27 Decomposition methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Attouch, H; Bolte, J, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., 116, 5-16, (2009) · Zbl 1165.90018
[2] Attouch, H; Bolte, J; Redont, P; Soubeyran, A, Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-łojasiewicz inequality, Math. Oper. Res., 35, 438-457, (2010) · Zbl 1214.65036
[3] Attouch, H; Bolte, J; Svaiter, BF, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program. Ser. A, 137, 91-129, (2013) · Zbl 1260.49048
[4] Auslender, A, Méthodes numériques pour la décomposition et la minimisation de fonctions non différentiables, Numerische Mathematik, 18, 213-223, (1971) · Zbl 0215.27504
[5] Auslender, A.: Optimisation—Méthodes numériques. Masson, Paris (1976) · Zbl 0326.90057
[6] Auslender, A, Asymptotic properties of the Fenchel dual functional and applications to decomposition problems, J. Optim. Theory Appl., 73, 427-449, (1992) · Zbl 0794.49026
[7] Auslender, A., Teboulle, M., Ben-Tiba, S.: Coupling the logarithmic-quadratic proximal method and the block nonlinear Gauss-Seidel algorithm for linearly constrained convex minimization. In: Thera, M., Tichastschke, R. (eds.) Lecture Notes in Economics and Mathematical Systems, vol. 477. pp. 35-47 (1998) · Zbl 0944.65066
[8] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011) · Zbl 1218.47001
[9] Beck, A; Teboulle, M, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci, 2, 183-202, (2009) · Zbl 1175.94009
[10] Beck, A., Tetruashvili, L.: On the convergence of block coordinate descent type methods. Preprint (2011) · Zbl 1297.90113
[11] Berry, M; Browne, M; Langville, A; Pauca, P; Plemmons, RJ, Algorithms and applications for approximation nonnegative matrix factorization, Comput. Stat. Data Anal., 52, 155-173, (2007) · Zbl 1452.90298
[12] Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, New Jersey (1989) · Zbl 0743.65107
[13] Blum, M; Floyd, RW; Pratt, V; Rivest, R; Tarjan, R, Time bounds for selection, J. Comput. Syst. Sci., 7, 448-461, (1973) · Zbl 0278.68033
[14] Bolte, J., Combettes, P.L., Pesquet, J.-C.: Alternating proximal algorithm for blind image recovery. In: Proceedings of the 17-th IEEE International Conference on Image Processing,Hong-Kong, ICIP, pp. 1673-1676 (2010) · Zbl 1263.90094
[15] Bolte, J; Daniilidis, A; Ley, O; Mazet, L, Characterizations of łojasiewicz inequalities: subgradient flows, talweg, convexity, Trans. Am. Math. Soc., 362, 3319-3363, (2010) · Zbl 1202.26026
[16] Bolte, J; Daniilidis, A; Lewis, A, The łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17, 1205-1223, (2006) · Zbl 1129.26012
[17] Bolte, J; Daniilidis, A; Lewis, A; Shiota, M, Clarke subgradients of stratifiable functions, SIAM J. Optim., 18, 556-572, (2007) · Zbl 1142.49006
[18] Cichocki, A., Zdunek, R., Phan, A.H., Amari, S.: Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-Way Data Analysis and Blind Source Separation. Wiley, New York (2009)
[19] Grippo, L; Sciandrone, M, On the convergence of the block nonlinear Gauss-Seidel method under convex constraints, Oper. Res. Lett., 26, 127-136, (2000) · Zbl 0955.90128
[20] Heiler, M; Schnorr, C, Learning sparse representations by non-negative matrix factorization and sequential cone programming, J. Mach. Learn. Res, 7, 1385-1407, (2006) · Zbl 1222.68214
[21] Hoyer, PO, Non-negative matrix factorization with sparseness constraints, J. Mach. Learn. Res., 5, 1457-1469, (2004) · Zbl 1222.68218
[22] Kurdyka, K, On gradients of functions definable in o-minimal structures, Annales de l’institut Fourier, 48, 769-783, (1998) · Zbl 0934.32009
[23] Lee, DD; Seung, HS, Learning the part of objects from nonnegative matrix factorization, Nature, 401, 788-791, (1999) · Zbl 1369.68285
[24] Lin, CJ, Projected gradient methods for nonnegative matrix factorization, Neural Comput., 19, 2756-2779, (2007) · Zbl 1173.90583
[25] Łojasiewicz, S.: Une propriété topologique des sous-ensembles analytiques réels, Les Équations aux Dérivées Partielles. Éditions du centre National de la Recherche Scientifique, Paris, 8-89 (1963) · Zbl 0215.27504
[26] Luss, R; Teboulle, M, Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint, SIAM Rev., 55, 65-98, (2013) · Zbl 1263.90094
[27] Mordukhovich, B.: Variational Analysis and Generalized Differentiation. I. Basic Theory, Grundlehren der Mathematischen Wissenschaften, vol. 330. Springer, Berlin (2006) · Zbl 1100.49002
[28] Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New-York (1970) · Zbl 0241.65046
[29] Palomar, D.P., Eldar, Y. (eds.): Convex Optimization in Signal Processing and Communications. Cambridge University Press, UK (2010) · Zbl 1200.90009
[30] Powell, MJD, On search directions for minimization algorithms, Math. Program., 4, 193-201, (1973) · Zbl 0258.90043
[31] Rockafellar, R.T., Wets, R.: Variational Analysis Grundlehren der Mathematischen Wissenschaften, vol. 317. Springer, Berlin (1998)
[32] Sra, S., Nowozin, S., Wright, S.J. (eds.): Optimization for Machine Learning. The MIT Press, Cambridge (2011)
[33] Tseng, P.: Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109, 475-494 (2001) · Zbl 1006.65062
[34] Zangwill, W.I.: Nonlinear Programming: A Unified Approach. Prentice Hall, Englewood Cliffs (1969) · Zbl 0195.20804
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.