On Solutions of Sparsity Constrained Optimization
Tóm tắt
In this paper, we mainly study the existence of solutions to sparsity constrained optimization (SCO). Based on the expressions of tangent cone and normal cone of sparsity constraint, we present and characterize two first-order necessary optimality conditions for SCO: N-stationarity and T-stationarity. Then we give the second-order necessary and sufficient optimality conditions for SCO. At last, we extend these results to SCO with nonnegative constraint.
Tài liệu tham khảo
Natarajan, B.K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24, 227–234 (1995)
Negahban, S., Ravikumar, P., Wainwright, M., Yu, B.: A unified framework for highdimensional analysis of m-estimators with decomposable regularizers. Stat. Sci. 27, 538–557 (2012)
Agarwal, A., Negahban, S., Wainwright, M.: Fast global convergence rates of gradient methods for high-dimensional statistical recovery. Adv. Neural Inf. Process. Syst. 23, 37–45 (2010)
Blumensath, T.: Compressed sensing with nonlinear observations and related nonlinear optimisation problems. IEEE Trans. Inf. Theory 59, 3466–3474 (2013)
Jalali, A., Johnson, C.C., Ravikumar, P.K.: On learning discrete graphical models using greedy methods. Adv. Neural Inf. Process. Syst. 24, 1935–1943 (2011)
Tewari, A., Ravikumar, P.K., Dhillon, I.S.: Greedy algorithms for structurally constrained high dimensional problems. Adv. Neural Inf. Process. Syst. 24, 882–890 (2011)
Yuan, X., Li, P., Zhang, T.: Gradient hard thresholding pursuit for sparsity-constrained optimization. ICML (2014)
Bahmani, S., Raj, B., Boufounos, P.: Greedy sparsity-constrained optimization. J. Mach. Learn. Res. 14, 807–841 (2013)
Candès, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51, 4203–4215 (2005)
Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52, 1289–1306 (2006)
Beck, A., Eldar, Y.: Sparsity constrained nonlinear optimization: optimality conditions and algorithms. SIAM J. Optim. 23, 1480–1509 (2013)
Rockafellar, R.T., Wets, R.J.: Variational Analysis. Springer, Berlin (1998)
Attouch, H., Bolte, J., Svaiter, B.F.: 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)
Calamai, P.H., Moŕe, J.J.: Projection gradient methods for linearly constrained problems. J. Math. Program. 39, 93–116 (1987)
Blumensath, T., Davies, M.E.: Iterative thresholding for sparse approximations. J. Fourier Anal. Appl. 14, 626–654 (2008)
Blumensath, T.: Non-linear compressed sensing and its application to beam hardening correction in X-ray tomography. In: Proceedings of Inverse Problems-From Theory to Application. Bristol (2014)
Chen, A.I., Graves, S.C.: Sparsity-constrained transportation problem. arXiv:1402.2309 (2014)
Smith, N.A., Tromble, R.W.: Sampling uniformly from the unit simplex. Technical Report, Johns Hopkins University, 1–6 (2004)
Takeda, A., Niranjan, M., Gotoh, J., Kawahara, Y.: Simultaneous pursuit of out-of-sample performance and sparsity in index tracking portfolios. Comput. Manag. Sci. 10, 21–49 (2012)
Pan, L., Xiu, N., Zhou, S.: Gradient support projection algorithm for affine feasibility problem with sparsity and nonnegativity. http://arxiv-web3.library.cornell.edu/pdf/1406.7178v1
Bauschke, H.H., Luke, D.R., Phan, H.M., Wang, X.: Restricted normal cones and sparsity optimization with affine constraints. Found. Comput. Math. 14, 63–83 (2014)
Lu, Z., Zhang, Y.: Sparse approximation via penalty decomposition methods. SIAM J. Optim. 23, 2448–2478 (2013)