×

zbMATH — the first resource for mathematics

Further properties of the forward-backward envelope with applications to difference-of-convex programming. (English) Zbl 1400.90279
Summary: In this paper, we further study the forward-backward envelope first introduced in [P. Patrinos and A. Bemporad, “Proximal Newton methods for convex composite optimization”, in: Proceedings of the IEEE Conference on Decision and Control, 2358–2363 (2013)] and [L. Stella et al., Comput. Optim. Appl. 67, No. 3, 443–487 (2017; Zbl 1401.90226)] for problems whose objective is the sum of a proper closed convex function and a twice continuously differentiable possibly nonconvex function with Lipschitz continuous gradient. We derive sufficient conditions on the original problem for the corresponding forward-backward envelope to be a level-bounded and Kurdyka-Łojasiewicz function with an exponent of \(\frac{1}{2}\); these results are important for the efficient minimization of the forward-backward envelope by classical optimization algorithms. In addition, we demonstrate how to minimize some difference-of-convex regularized least squares problems by minimizing a suitably constructed forward-backward envelope. Our preliminary numerical results on randomly generated instances of large-scale \(\ell _{1-2}\) regularized least squares problems [P. Yin et al., SIAM J. Sci. Comput. 37, No. 1, A536–A563 (2015; Zbl 1316.90037)] illustrate that an implementation of this approach with a limited-memory BFGS scheme usually outperforms standard first-order methods such as the nonmonotone proximal gradient method in [S. J. Wright et al., IEEE Trans. Signal Process. 57, No. 7, 2479–2493 (2009; Zbl 1391.94442)].

MSC:
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
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., 137, 91-129, (2013) · Zbl 1260.49048
[4] Auslender, A., Teboulle, M.: Asymptotic Cones and Functions in Optimization and Variational Inequalities. Springer, Berlin (2003) · Zbl 1017.49001
[5] 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
[6] Bauschke, HH; Borwein, JM; Combettes, PL, Bregman monotone optimization algorithms, SIAM J. Control Optim., 42, 596-636, (2003) · Zbl 1049.90053
[7] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin (2011) · Zbl 1218.47001
[8] Byrd, RH; Chin, GM; Nocedal, J; Oztoprak, F, A family of second-order methods for convex \(ℓ _1\)-regularized optimization, Math. Program., 159, 435-467, (2016) · Zbl 1350.49046
[9] Candès, EJ; Tao, T, Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 4203-4215, (2005) · Zbl 1264.94121
[10] Chambolle, A, An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20, 89-97, (2004) · Zbl 1366.94056
[11] Chen, X; Lu, Z; Pong, TK, Penalty methods for a class of non-Lipschitz optimization problems, SIAM J. Optim., 26, 1465-1492, (2016) · Zbl 1342.90181
[12] Donoho, DL, Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306, (2006) · Zbl 1288.94016
[13] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems Volume I/II. Springer, Berlin (2003) · Zbl 1062.90002
[14] Fan, J; Li, R, Variable selection via nonconvex penalized likelihood and its oracle properties, J. Am. Stat. Assoc., 96, 1348-1360, (2011) · Zbl 1073.62547
[15] Friedlander, M., Goh, G.: Efficient evaluation of scaled proximal operators. Preprint arXiv:1603.05719 (2016) · Zbl 1360.90198
[16] Gong, P., Zhang, C., Lu, Z., Huang, J.Z., Ye, J.: A general iterative Shrinkage and thresholding algorithm for non-convex regularized optimization problems. Proc. Int. Conf. Mach. Learn. 28, 37-45 (2013) · Zbl 1260.49048
[17] Griesse, R; Lorenz, DA, A semismooth Newton method for Tikhonov functionals with sparsity constraints, Inverse Probl., 24, 035007, (2008) · Zbl 1152.49030
[18] Kan, C; Song, W, The Moreau envelope function and proximal mapping in the sense of the Bregman distance, Nonlinear Anal. Theory Methods Appl., 75, 1385-1399, (2012) · Zbl 1236.49026
[19] Lee, JD; Sun, Y; Saunders, MA, Proximal Newton-type methods for minimizing composite functions, SIAM J. Optim., 24, 1420-1443, (2014) · Zbl 1306.65213
[20] Li, G., Pong, T.K.: Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods. Preprint arXiv:1602.02915 (2016) · Zbl 1366.94048
[21] Lu, Z; Pong, TK; Zhang, Y, An alternating direction method for finding Dantzig selectors, Comput. Stat. Data Anal., 56, 4037-4946, (2012) · Zbl 1255.62096
[22] Luo, ZQ; Tseng, P, On the linear convergence of descent methods for convex essentially smooth minimization, SIAM J. Control Optim., 30, 408-425, (1992) · Zbl 0756.90084
[23] Luo, ZQ; Tseng, P, Error bounds and convergence analysis of feasible descent methods: a general approach, Ann. Oper. Res., 46, 157-178, (1993) · Zbl 0793.90076
[24] Luo, ZQ; Tseng, P, On the convergence rate of dual ascent methods for linearly constrained convex minimization, Math. Oper. Res., 18, 846-867, (1993) · Zbl 0804.90103
[25] Milzarek, A; Ulbrich, M, A semismooth Newton method with multidimensional filter globalization for \(ℓ _1\)-optimization, SIAM J. Optim., 24, 298-333, (2014) · Zbl 1295.49022
[26] Nocedal, J., Wright, S.J.: Numerical Optimization, 1st edn. Springer, Berlin (1999) · Zbl 0930.65067
[27] Noll, D; Rondepierre, A; Bailey, DH (ed.); Bauschke, HH (ed.); Borwein, P (ed.); Garvan, F (ed.); Théra, M (ed.); Vanderwerff, JD (ed.); Wolkowicz, H (ed.), Convergence of linesearch and trust-region methods using the Kurdyka-łojasiewicz inequality, (2013), Berlin · Zbl 1283.65061
[28] Patrinos, P., Bemporad, A.: Proximal Newton methods for convex composite optimization. In: Proceedings of the IEEE Conference on Decision and Control, pp. 2358-2363. (2013) · Zbl 1350.49046
[29] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998) · Zbl 0888.49001
[30] Stella, L., Themelis, A., Patrinos, P.: Forward-backward quasi-Newton methods for nonsmooth optimization problems. Comput. Optim. Appl. (2017). doi:10.1007/s10589-017-9912-y · Zbl 1401.90226
[31] Tseng, P; Yun, S, A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training, Comput. Optim. Appl., 47, 179-206, (2010) · Zbl 1226.90062
[32] Tseng, P; Yun, S, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program. Ser. B, 117, 387-423, (2009) · Zbl 1166.90016
[33] Tseng, P, Approximation accuracy, gradient methods, and error bound for structured convex optimization, Math. Program. Ser. B, 125, 263-295, (2010) · Zbl 1207.65084
[34] Wang, Y., Luo, Z., Zhang, X.: New improved penalty methods for sparse reconstruction based on difference of two norms. Preprint. doi:10.13140/RG.2.1.3256.3369 (2015) · Zbl 1129.26012
[35] Wright, SJ; Nowak, R; Figueiredo, MAT, Sparse reconstruction by separable approximation, IEEE T. Signal Process., 57, 2479-2493, (2009) · Zbl 1391.94442
[36] Xiao, X., Li, Y., Wen, Z., Zhang, L.: Semi-smooth second-order type methods for composite convex programs. Preprint arXiv:1603.07870 (2016) · Zbl 1073.62547
[37] Yin, P; Lou, Y; He, Q; Xin, J, Minimization of \(ℓ _{1-2}\) for compressed sensing, SIAM J. Sci. Comput., 37, a536-a563, (2015) · Zbl 1316.90037
[38] Zhang, C-H, Nearby unbiased variable selection under minimax concave penalty, Ann. Stat., 38, 894-942, (2010) · Zbl 1183.62120
[39] Zhou, Z., So, A.M.-C.: A unified approach to error bounds for structured convex optimization problems. Preprint arXiv:1512.03518 (2015)
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.