×

zbMATH — the first resource for mathematics

A globally convergent algorithm for nonconvex optimization based on block coordinate update. (English) Zbl 1378.65126
A block prox-linear (BPL) method for nonconvex smooth and nonsmooth optimization is presented. Assuming cyclic updates of the blocks it is proved that the whole sequence generated by the BPL method converges to a critical point (global convergence). Its asymptotic convergence rate is given, too. The efficiency of this method is numerically demonstrated by numerical tests on nonnegative matrices and tensor factorization problems.

MSC:
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
Software:
GradSamp
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aharon, M; Elad, M; Bruckstein, A, K-SVD: an algorithm for designing overcomplete dictionaries for sparse representation, IEEE Trans. Signal Process., 54, 4311-4322, (2006) · Zbl 1375.94040
[2] Allen, G.: Sparse higher-order principal components analysis. In: International Conference on Artificial Intelligence and Statistics, pp. 27-36. (2012) · Zbl 0990.68123
[3] 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
[4] Attouch, H; Bolte, J; Redont, P; Soubeyran, A, Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-lojasiewicz inequality, Math. Oper. Res., 35, 438-457, (2010) · Zbl 1214.65036
[5] 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., 137, 91-129, (2013) · Zbl 1260.49048
[6] Bagirov, AM; Jin, L; Karmitsa, N; Al Nuaimat, A; Sultanova, N, Subgradient method for nonconvex nonsmooth optimization, J. Optim. Theory Appl., 157, 416-435, (2013) · Zbl 1282.90133
[7] 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
[8] Beck, A; Tetruashvili, L, On the convergence of block coordinate descent type methods, SIAM J. Optim., 23, 2037-2060, (2013) · Zbl 1297.90113
[9] Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[10] Blumensath, T; Davies, ME, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27, 265-274, (2009) · Zbl 1174.94008
[11] Bolte, J; Daniilidis, A; Lewis, A, The lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17, 1205-1223, (2007) · Zbl 1129.26012
[12] 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
[13] Bolte, J; Sabach, S; Teboulle, M, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math., 146, 459-494, (2014) · Zbl 1297.90125
[14] Breheny, P; Huang, J, Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection, Ann. Appl. Stat., 5, 232-253, (2011) · Zbl 1220.62095
[15] Burke, JV; Lewis, AS; Overton, ML, A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM J. Optim., 15, 751-779, (2005) · Zbl 1078.65048
[16] Chang, KW; Hsieh, CJ; Lin, CJ, Coordinate descent method for large-scale l2-loss linear support vector machines, J. Mach. Learn. Res., 9, 1369-1398, (2008) · Zbl 1225.68157
[17] Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: IEEE International Conference on Acoustics, Speech and Signal Processing, 2008. ICASSP 2008, pp. 3869-3872. IEEE (2008) · Zbl 0827.68054
[18] Chen, X, Smoothing methods for nonsmooth, nonconvex minimization, Math. Program., 134, 71-99, (2012) · Zbl 1266.90145
[19] Donoho, D., Stodden, V.: When does non-negative matrix factorization give a correct decomposition into parts. In: Advances in Neural Information Processing Systems, vol. 16. (2003) · Zbl 0940.65070
[20] Fan, J; Li, R, Variable selection via nonconcave penalized likelihood and its oracle properties, J. Am. Stat. Assoc., 96, 1348-1360, (2001) · Zbl 1073.62547
[21] Fuduli, A; Gaudioso, M; Giallombardo, G, Minimizing nonconvex nonsmooth functions via cutting planes and proximity control, SIAM J. Optim., 14, 743-756, (2004) · Zbl 1079.90105
[22] Ghadimi, S; Lan, G, Accelerated gradient methods for nonconvex nonlinear and stochastic programming, Math. Program., 156, 59-99, (2016) · Zbl 1335.62121
[23] Grippo, L; Sciandrone, M, Globally convergent block-coordinate techniques for unconstrained optimization, Optim. Methods Softw., 10, 587-637, (1999) · Zbl 0940.65070
[24] Hildreth, C, A quadratic programming procedure, Naval Res. Logist. Q., 4, 79-85, (1957)
[25] Ho, N., Van Dooren, P., Blondel, V.: Descent methods for nonnegative matrix factorization. In: Numerical Linear Algebra in Signals, Systems and Control, pp. 251-293. Springer, Netherlands (2011) · Zbl 1251.65049
[26] Hong, M., Wang, X., Razaviyayn, M., Luo, Z.Q.: Iteration complexity analysis of block coordinate descent methods. arXiv preprint arXiv:1310.6957 (2013) · Zbl 1202.26026
[27] Hoyer, P, Non-negative matrix factorization with sparseness constraints, J. Mach. Learn. Res., 5, 1457-1469, (2004) · Zbl 1222.68218
[28] Kim, J; He, Y; Park, H, Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework, J. Global Optim., 58, 285-319, (2014) · Zbl 1321.90129
[29] Kolda, T; Bader, B, Tensor decompositions and applications, SIAM Rev., 51, 455, (2009) · Zbl 1173.65029
[30] Kruger, AY, On Fréchet subdifferentials, J. Math. Sci., 116, 3325-3358, (2003) · Zbl 1039.49021
[31] Kurdyka, K.: On gradients of functions definable in o-minimal structures. Ann. Inst. Fourier. 48(3), 769-783 (1998) · Zbl 0934.32009
[32] Lai, MJ; Xu, Y; Yin, W, Improved iteratively reweighted least squares for unconstrained smoothed \(ℓ _q\) minimization, SIAM J. Numer. Anal., 51, 927-957, (2013) · Zbl 1268.49038
[33] Lee, D; Seung, H, Learning the parts of objects by non-negative matrix factorization, Nature, 401, 788-791, (1999) · Zbl 1369.68285
[34] Li, G., Pong, T.K.: Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methods. arXiv preprint arXiv:1602.02915 (2016) · Zbl 1220.62095
[35] Ling, Q., Xu, Y., Yin, W., Wen, Z.: Decentralized low-rank matrix completion. In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2012, pp. 2925-2928. IEEE (2012) · Zbl 1297.90125
[36] Łojasiewicz, S, Sur la géométrie semi-et sous-analytique, Ann. Inst. Fourier (Grenoble), 43, 1575-1595, (1993) · Zbl 0803.32002
[37] Lu, Z., Xiao, L.: Randomized block coordinate non-monotone gradient method for a class of nonlinear programming. arXiv preprint arXiv:1306.5918 (2013) · Zbl 1039.49021
[38] Lu, Z; Xiao, L, On the complexity analysis of randomized block-coordinate descent methods, Math. Program., 152, 615-642, (2015) · Zbl 1321.65100
[39] Luo, ZQ; Tseng, P, On the convergence of the coordinate descent method for convex differentiable minimization, J. Optim. Theory Appl., 72, 7-35, (1992) · Zbl 0795.90069
[40] Mairal, J., Bach, F., Ponce, J., Sapiro, G.: Online dictionary learning for sparse coding. In: Proceedings of the 26th Annual International Conference on Machine Learning, pp. 689-696. ACM (2009) · Zbl 1242.62087
[41] Mohan, K; Fazel, M, Iterative reweighted algorithms for matrix rank minimization, J. Mach. Learn. Res., 13, 3441-3473, (2012) · Zbl 1436.65055
[42] Natarajan, BK, Sparse approximate solutions to linear systems, SIAM J. Comput., 24, 227-234, (1995) · Zbl 0827.68054
[43] Nesterov, Y, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 22, 341-362, (2012) · Zbl 1257.90073
[44] Nesterov, Y.: Introductory lectures on convex optimization: a basic course, vol. 87. Springer Science & Business Media, Berlin (2013) · Zbl 1086.90045
[45] Nocedal, J., Wright, S.J.: Numerical Optimization, Springer Series in Operations Research and Financial Engineering., 2nd edn. Springer, New York (2006)
[46] O’Donoghue, B., Candes, E.: Adaptive restart for accelerated gradient schemes. Found. Comput. Math. 15(3), 715-732 (2013) · Zbl 1320.90061
[47] Paatero, P; Tapper, U, Positive matrix factorization: a non-negative factor model with optimal utilization of error estimates of data values, Environmetrics, 5, 111-126, (1994)
[48] Peng, Z; Wu, T; Xu, Y; Yan, M; Yin, W, Coordinate friendly structures, algorithms and applications, Ann. Math. Sci. Appl., 1, 57-119, (2016) · Zbl 1432.65076
[49] Razaviyayn, M; Hong, M; Luo, ZQ, A unified convergence analysis of block successive minimization methods for nonsmooth optimization, SIAM J. Optim., 23, 1126-1153, (2013) · Zbl 1273.90123
[50] Recht, B; Fazel, M; Parrilo, P, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 471-501, (2010) · Zbl 1198.90321
[51] Richtárik, P; Takáč, M, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function, Math. Program., 144, 1-38, (2014) · Zbl 1301.65051
[52] Rockafellar, R., Wets, R.: Variational Analysis, vol. 317. Springer, Berlin (2009) · Zbl 0888.49001
[53] Saha, A; Tewari, A, On the nonasymptotic convergence of cyclic coordinate descent methods, SIAM J. Optim., 23, 576-601, (2013) · Zbl 1270.90032
[54] Shi, H.J.M., Tu, S., Xu, Y., Yin, W.: A primer on coordinate descent algorithms. arXiv preprint arXiv:1610.00040 (2016) · Zbl 1175.94009
[55] Tseng, P, Convergence of a block coordinate descent method for nondifferentiable minimization, J. Optim. Theory Appl., 109, 475-494, (2001) · Zbl 1006.65062
[56] Tseng, P; Yun, S, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program., 117, 387-423, (2009) · Zbl 1166.90016
[57] Welling, M; Weber, M, Positive tensor factorization, Pattern Recogn. Lett., 22, 1255-1261, (2001) · Zbl 0990.68123
[58] Wen, Z; Yin, W; Zhang, Y, Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Math. Program. Comput., 4, 333-361, (2012) · Zbl 1271.65083
[59] Xu, Y, Alternating proximal gradient method for sparse nonnegative Tucker decomposition, Math. Program. Comput., 7, 39-70, (2015) · Zbl 1320.49019
[60] Xu, Y; Akrotirianakis, I; Chakraborty, A, Proximal gradient method for huberized support vector machine, Pattern Anal. Appl., 19, 989-1005, (2016)
[61] Xu, Y; Yin, W, A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM J. Imaging Sci., 6, 1758-1789, (2013) · Zbl 1280.49042
[62] Xu, Y; Yin, W, A fast patch-dictionary method for whole image recovery, Inverse Probl. Imaging, 10, 563-583, (2016) · Zbl 1395.94071
[63] Zhang, CH, Nearly unbiased variable selection under minimax concave penalty, Ann. Stat., 38, 894-942, (2010) · Zbl 1183.62120
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.