×

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:
GradSamp; PDCO
PDF BibTeX Cite
Full Text: DOI
References:
[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
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.