zbMATH — the first resource for mathematics

Smoothing projected Barzilai-Borwein method for constrained non-Lipschitz optimization. (English) Zbl 1357.90117
Summary: We present a smoothing projected Barzilai-Borwein (SPBB) algorithm for solving a class of minimization problems on a closed convex set, where the objective function is nonsmooth nonconvex, perhaps even non-Lipschitz. At each iteration, the SPBB algorithm applies the projected gradient strategy that alternately uses the two Barzilai-Borwein stepsizes to the smooth approximation of the original problem. Nonmonotone scheme is adopted to ensure global convergence. Under mild conditions, we prove convergence of the SPBB algorithm to a scaled stationary point of the original problem. When the objective function is locally Lipschitz continuous, we consider a general constrained optimization problem and show that any accumulation point generated by the SPBB algorithm is a stationary point associated with the smoothing function used in the algorithm. Numerical experiments on $$\ell _2$$-$$\ell _p$$ problems, image restoration problems, and stochastic linear complementarity problems show that the SPBB algorithm is promising.

MSC:
 90C26 Nonconvex programming, global optimization
Software:
 [1] Barzilai, J; Borwein, JM, Two-point step size gradient methods, IMA J. Numer. Anal., 8, 141-148, (1988) · Zbl 0638.65055 [2] 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 [3] Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077 [4] Bian, W; Chen, X, Smoothing neural network for constrained non-Lipschitz optimization with applications, IEEE Trans. Neural Netw. Lean. Syst., 23, 399-411, (2012) [5] Bian, W; Chen, X, Worst-case complexity of smoothing quadratic regularization methods for non-Lipschitzian optimization, SIAM J. Optim., 23, 1718-1741, (2013) · Zbl 1282.90175 [6] Bian, W; Chen, X, Neural network for nonsmooth, nonconvex constrained minimization via smooth approximation, IEEE Trans. Neural Netw. Lean. Syst., 25, 545-556, (2014) [7] Bian, W., Chen, X., Ye, Y.: Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization. Math. Program. (2014). doi:10.1007/s10107-014-0753-5 · Zbl 1318.90075 [8] Birgin, EG; Martínez, JM; Raydan, M, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim., 10, 1196-1211, (2000) · Zbl 1047.90077 [9] 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 [10] Calamai, PH; Moré, JJ, Projected gradient methods for linearly constrained problems, Math. Program., 39, 93-116, (1987) · Zbl 0634.90064 [11] Candès, EJ; Romberg, J, Quantitative robust uncertainty principles and optimally sparse decompositions, Found. Comput. Math., 6, 227-254, (2006) · Zbl 1102.94020 [12] Candès, EJ; Romberg, J; Tao, T, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 489-509, (2006) · Zbl 1231.94017 [13] Candès, EJ; Tao, T, Near-optimal signal recovery from random projections: universal encoding strategies, IEEE Trans. Inf. Theory, 52, 5406-5425, (2006) · Zbl 1309.94033 [14] Candès, EJ; Wakin, MB; Boyd, SP, Enhancing sparsity by reweighted $$ℓ _1$$ minimization, J. Fourier Anal. Appl., 14, 877-905, (2008) · Zbl 1176.94014 [15] Cartis, C; Gould, NI; Toint, PL, On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming, SIAM J. Optim., 21, 1721-1739, (2011) · Zbl 1236.90118 [16] Chartrand, R, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14, 707-710, (2007) [17] Chartrand, R.: Nonconvex regularization for shape preservation. In: IEEE International Conference on Image Processing (ICIP) (2007) [18] Chartrand, R.: Fast algorithms for nonconvex compressive sensing: MRI reconstruction from very few data. In: IEEE International Symposium on Biomedical Imaging (ISBI) (2009) [19] Chartrand, R., Yin, W.: Iteratively reweighted algorithms for compressive sensing. In: IEEE international conference on Acoustics, speech, and signal processing (ICASSP) (2008) · Zbl 1329.90138 [20] Chen, B; Chen, X, A global and local superlinear continuation-smoothing method for $$P_0$$ and $$R_0$$ NCP or monotone NCP, SIAM J. Optim., 9, 624-645, (1999) · Zbl 0955.90132 [21] Chen, C; Mangasarian, OL, A class of smoothing functions for nonlinear and mixed complementarity problems, Comput. Optim. Appl., 5, 97-138, (1996) · Zbl 0859.90112 [22] Chen, SS; Donoho, DL; Saunders, MA, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 33-61, (1998) · Zbl 0919.94002 [23] Chen, X, Smoothing methods for nonsmooth, nonconvex minimization, Math. Program., 134, 71-99, (2012) · Zbl 1266.90145 [24] Chen, X; Fukushima, M, Expected residual minimization method for stochastic linear complementarity problems, Math. Oper. Res., 30, 1022-1038, (2005) · Zbl 1162.90527 [25] Chen, X; Ge, D; Wang, Z; Ye, Y, Complexity of unconstrained $$l_2$$-$$l_p$$ minimization, Math. Program., 143, 371-383, (2014) · Zbl 1285.90039 [26] Chen, X; Ng, MK; Zhang, C, Non-Lipschitz $$ℓ _{p}$$-regularization and box constrained model for image restoration, IEEE Trans. Signal Process., 21, 4709-4721, (2012) · Zbl 1373.94080 [27] Chen, X; Niu, L; Yuan, Y, Optimality conditions and smoothing trust region Newton method for non-Lipschitz optimization, SIAM J. Optim., 23, 1528-1552, (2013) · Zbl 1291.90238 [28] Chen, X; Xu, F; Ye, Y, Lower bound theory of nonzero entries in solutions of $$ℓ _2$$-$$ℓ _p$$ minimization, SIAM J. Sci. Comput., 32, 2832-2852, (2010) · Zbl 1242.90174 [29] Chen, X; Zhang, C; Fukushima, M, Robust solution of monotone stochastic linear complementarity problems, Math. Program., 117, 51-80, (2009) · Zbl 1165.90012 [30] Chen, X; Zhou, W, Smoothing nonlinear conjugate gradient method for image restoration using nonsmooth nonconvex minimization, SIAM J. Imaging Sci., 3, 765-790, (2010) · Zbl 1200.65031 [31] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001 [32] Curtis, FE; Overton, ML, A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization, SIAM J. Optim., 22, 474-500, (2012) · Zbl 1246.49031 [33] Dai, YH; Fletcher, R, Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming, Numer. Math., 100, 21-47, (2005) · Zbl 1068.65073 [34] Dai, YH; Hager, WW; Schittkowski, K; Zhang, H, The cyclic Barzilai-Borwein method for unconstrained optimization, IMA J. Numer. Anal., 26, 604-627, (2006) · Zbl 1147.65315 [35] Dai, YH; Liao, LZ, $$R$$-linear convergence of the Barzilai and Borwein gradient method, IMA J. Numer. Anal., 22, 1-10, (2002) · Zbl 1002.65069 [36] Donoho, DL, Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306, (2006) · Zbl 1288.94016 [37] 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 [38] Fang, H; Chen, X; Fukushima, M, Stochastic $$R_0$$ matrix linear complementarity problems, SIAM J. Optim., 18, 482-506, (2007) · Zbl 1151.90052 [39] Figueiredo, MA; Nowak, RD; Wright, SJ, Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signal Process., 1, 586-597, (2007) [40] Fletcher, R, On the Barzilai-Borwein method, (2005), New York · Zbl 1118.90318 [41] Garmanjani, R; Vicente, LN, Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization, IMA J. Numer. Anal., 33, 1008-1028, (2013) · Zbl 1272.65050 [42] Ge, D; Jiang, X; Ye, Y, A note on the complexity of $$l_p$$ minimization, Math. Program., 129, 285-299, (2011) · Zbl 1226.90076 [43] Grippo, L; Sciandrone, M, Nonmonotone globalization techniques for the Barzilai-Borwein gradient method, Comput. Optim. Appl., 23, 143-169, (2002) · Zbl 1028.90061 [44] Huang, Y; Liu, H, On the rate of convergence of projected Barzilai-Borwein methods, Optim. Method Softw., 30, 880-892, (2015) · Zbl 1338.90300 [45] Huang, Y; Liu, H; Cong, W, A note on the smoothing quadratic regularization method for non-Lipschitz optimization, Numer. Algorithm, 69, 863-874, (2015) · Zbl 1329.90138 [46] Huang, Y., Liu, H., Yu, T.: Smoothing projected cyclic Barzilai-Borwein method for stochastic linear complementarity problems. Int. J. Comput. Math. (2014). doi:10.1080/00207160.2015.1040780 · Zbl 1343.65069 [47] Huang, Y; Liu, H; Zhou, S, A Barzilai-Borwein type method for stochastic linear complementarity problems, Numer. Algorithm, 67, 477-489, (2014) · Zbl 1327.90312 [48] Huang, Y; Liu, H; Zhou, S, A Barzilai-Borwein type method for minimizing composite functions, Numer. Algorithm, 69, 819-838, (2015) · Zbl 1321.65099 [49] Huang, Y; Liu, H; Zhou, S, Quadratic regularization projected Barzilai-Borwein method for nonnegative matrix factorization, Data Min. Knowl. Disc., 29, 1665-1684, (2015) [50] Huang, Y; Liu, H; Zhou, S, An efficient monotone projected Barzilai-Borwein method for nonnegative matrix factorization, Appl. Math. Lett., 45, 12-17, (2015) · Zbl 1325.15007 [51] Jiang, B; Dai, YH, Feasible Barzilai-Borwein-like methods for extreme symmetric eigenvalue problems, Optim. Method Softw., 28, 756-784, (2013) · Zbl 1302.90209 [52] Jiang, B; Dai, YH, A framework of constraint preserving update schemes for optimization on Stiefel manifold, Math. Program., 153, 535-575, (2015) · Zbl 1325.49037 [53] Kleywegt, AJ; Shapiro, A; Homem-De-Mello, T, The sample average approximation method for stochastic discrete optimization, SIAM J. Optim., 12, 479-502, (2002) · Zbl 0991.90090 [54] Lin, GH; Fukushima, M, Stochastic equilibrium problems and stochastic mathematical programs with equilibrium constraints: a survey, Pac. J. Optim., 6, 455-482, (2010) · Zbl 1200.65052 [55] Liu, H; Huang, Y; Li, X, New reformulation and feasible semismooth Newton method for a class of stochastic linear complementarity problems, Appl. Math. Comput., 217, 9723-9740, (2011) · Zbl 1232.65090 [56] Liu, H; Huang, Y; Li, X, Partial projected Newton method for a class of stochastic linear complementarity problems, Numer. Algorithm, 58, 593-618, (2011) · Zbl 1232.65091 [57] Liu, YF; Dai, YH; Ma, S, Joint power and admission control: non-convex $$l_q$$ approximation and an effective polynomial time deflation approach, IEEE Trans. Signal Process., 63, 3641-3656, (2015) · Zbl 1394.94340 [58] Liu, Y.F., Ma, S., Dai, Y.H., Zhang, S.: A smoothing SQP framework for a class of composite $$l_q$$ minimization over polyhedron. Math. Program. (2015). doi:10.1007/s10107-015-0939-5 · Zbl 1346.90684 [59] Lu, Z, Iterative reweighted minimization methods for $$ℓ _p$$ regularized unconstrained nonlinear programming, Math. Program., 147, 277-307, (2014) · Zbl 1308.90170 [60] Mourad, N; Reilly, JP, Minimizing nonconvex functions for sparse vector reconstruction, IEEE Trans. Signal Process., 58, 3485-3496, (2010) · Zbl 1391.90492 [61] Nesterov, Yu, Smooth minimization of non-smooth functions, Math. Program., 103, 127-152, (2005) · Zbl 1079.90102 [62] Nesterov, Yu, Modified Gauss-Newton scheme with worst case guarantees for global performance, Optim. Method Softw., 22, 469-483, (2007) · Zbl 1136.65051 [63] Nesterov, Yu, Gradient methods for minimizing composite functions, Math. Program., 140, 125-161, (2013) · Zbl 1287.90067 [64] Nikolova, M; Ng, MK; Tam, CP, Fast nonconvex nonsmooth minimization methods for image restoration and reconstruction, IEEE Trans. Image Process., 19, 3073-3088, (2010) · Zbl 1371.94277 [65] Nikolova, M; Ng, MK; Zhang, S; Ching, WK, Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization, SIAM J. Imaging Sci., 1, 2-25, (2008) · Zbl 1207.94017 [66] Raydan, M, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim., 7, 26-33, (1997) · Zbl 0898.90119 [67] Tibshirani, R, Regression shrinkage and selection via the lasso, J. R. Stat. Soc. B, 58, 267-288, (1996) · Zbl 0850.62538 [68] Toint, PHL, Global convergence of a class of trust region methods for nonconvex minimization in Hilbert space, MA J. Numer. Anal., 8, 231-252, (1988) · Zbl 0698.65043 [69] Wright, SJ; Nowak, RD; Figueiredo, MA, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57, 2479-2493, (2009) · Zbl 1391.94442 [70] Zhang, C; Chen, X, Smoothing projected gradient method and its application to stochastic linear complementarity problems, SIAM J. Optim., 20, 627-649, (2009) · Zbl 1204.65073 [71] Zhou, GL; Caccetta, L, Feasible semismooth Newton method for a class of stochastic linear complementarity problems, J. Optim. Theory Appl., 139, 379-392, (2008) · Zbl 1191.90085