On the minimization over sparse symmetric sets: projections, optimality conditions, and algorithms. (English) Zbl 1334.90129
Summary: We consider the problem of minimizing a general continuously differentiable function over symmetric sets under sparsity constraints. These type of problems are generally hard to solve because the sparsity constraint induces a combinatorial constraint into the problem, rendering the feasible set to be nonconvex. We begin with a study of the properties of the orthogonal projection operator onto sparse symmetric sets. Based on this study, we derive efficient methods for computing sparse projections under various symmetry assumptions. We then introduce and study three types of optimality conditions: basic feasibility, \(L\)-stationarity, and coordinatewise optimality. A hierarchy between the optimality conditions is established by using the results derived on the orthogonal projection operator. Methods for generating points satisfying the various optimality conditions are presented, analyzed, and finally tested on specific applications.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C46 | Optimality conditions and duality in mathematical programming |
References:
| [1] | Attouch H, Bolte J, Svaiter BF (2013) Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Programming Ser. A 137(1-2):91-129. CrossRef · Zbl 1260.49048 |
| [2] | Bahmani S, Raj B, Boufounos PT (2013) Greedy sparsity-constrained optimization. J. Machine Learn. Res. 14(1):807-841. · Zbl 1320.90046 |
| [3] | Beck A, Eldar YC (2013) Sparsity constrained nonlinear optimization: Optimality conditions and algorithms. SIAM J. Optim. 23(3): 1480-1509. CrossRef · Zbl 1295.90051 |
| [4] | Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1): 183-202. CrossRef · Zbl 1175.94009 |
| [5] | Blumensath T, Davies ME (2008) Iterative thresholding for sparse approximations. J. Fourier Anal. Appl. 14(5):629-654. CrossRef · Zbl 1175.94060 |
| [6] | Blumensath T, Davies ME (2009) Iterative hard thresholding for compressed sensing. Appl. Comput. Harmonic Anal. 27(3):265-274. CrossRef · Zbl 1174.94008 |
| [7] | Blumensath T, Davies ME (2009) Normalised iterative hard thresholding; guaranteed stability and performance. IEEE J. Selected Topics Signal Processing 4(2):298-309. |
| [8] | Bolte J, Sabach S, Teboulle M (2014) Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Programming Ser. A 146(1-2):459-494. CrossRef · Zbl 1297.90125 |
| [9] | Bruckstein AM, Donoho DL, Elad M (2009) From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51(1):34-81. CrossRef · Zbl 1178.68619 |
| [10] | Candes E, Tao T (2007) The Dantzig selector: Statistical estimation when p is much larger than n. Ann. Statist. 35(6):2313-2351. CrossRef |
| [11] | Candes EJ, Tao T (2005) Decoding by linear programming. IEEE Trans. Inform. Theory 51(12):4203-4215. CrossRef · Zbl 1264.94121 |
| [12] | Cartis C, Thompson A (2013) A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing. Technical Report NA-13/20, Mathematical Institute, University of Oxford, Oxford, UK). · Zbl 1359.94071 |
| [13] | Chen S, Donoho D, Saunders M (1998) Atomic decomposition by basis pursuit. SIAM J. Scientific Comput. 20(1):33-61. CrossRef · Zbl 0919.94002 |
| [14] | Davenport MA, Duarte MF, Eldar YC, Kutyniok G (2011) Introduction to compressed sensing. Preprint:1-68. |
| [15] | David LD, Elad M (2003) Optimally sparse representation in general (nonorthogonal) dictionaries via L1 minimization. Proc. Natl. Acad. Sci. 100(5):2197-2202. CrossRef · Zbl 1064.94011 |
| [16] | Duarte MF, Eldar YC (2011) Structured compressed sensing: From theory to applications. IEEE Trans. Signal Processing 59(9): 4053-4085. CrossRef · Zbl 1392.94188 |
| [17] | Kiwiel KC (2007) On linear-time algorithms for the continuous quadratic knapsack problem. J. Optim. Theory Appl. 134(3):549-554. [English.] CrossRef · Zbl 1145.90077 |
| [18] | Kyrillidis A, Becker S, Cevher V, Koch C (2013) Sparse projections onto the simplex. Preprint, arXiv: 1206.152928. |
| [19] | Lu Z (2013) Iterative hard thresholding methods for l_{0} regularized convex cone programming. Math. Programming Ser. A 147(1-2): 125-154. CrossRef · Zbl 1308.65094 |
| [20] | Lu Z, Zhang Y (2013) Sparse approximation via penalty decomposition methods. SIAM J. Optim. 23(4):2448-2478. CrossRef · Zbl 1295.90056 |
| [21] | Luss R, Teboulle M (2013) Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint. SIAM Rev. 55(1):65-98. CrossRef · Zbl 1263.90094 |
| [22] | Mallat S, Zhang Z (1993) Matching pursuits with time-frequency dictionaries. IEEE Trans. Signal Processing 41(12):3397-3415. CrossRef · Zbl 0842.94004 |
| [23] | More J, Sorensen D (1983) Computing a trust region step. SIAM J. Sci. Statist. Comput. 4(3):553-572. CrossRef · Zbl 0551.65042 |
| [24] | Needell D, Tropp JA (2009) CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmonic Anal. 26(3):301-321. CrossRef · Zbl 1163.94003 |
| [25] | Pan L, Xiu N, Zhou SGradient support projection algorithm for affine feasibility problem with sparsity and nonnegativity. Preprint, http://arxiv-web3.library.cornell.edu/pdf/1406.7178v1.pdf. |
| [26] | Rockafellar RT (1981) The Theory of Subgradients and Its Applications to Problems of Optimization, R&E, Vol. 1 (Heldermann Verlag, Berlin). |
| [27] | Rockafellar RT, Wets RJ-B (1998) Variational analysis. Grundlehren der mathematischen Wissenschaften (Fundamental Principles of Mathematical Sciences), Vol. 317 (Springer, Berlin). CrossRef |
| [28] | Smith NA, Tromble RW (2004) Sampling uniformly from the unit simplex. Technical report, Johns Hopkins University, Baltimore. |
| [29] | Takeda A, Niranjan M, Gotoh J, Kawahara Y (2012) Simultaneous pursuit of out-of-sample performance and sparsity in index tracking portfolios. Comput. Management Sci. 10(1):21-49. CrossRef · Zbl 1296.91257 |
| [30] | Tropp JA, Wright SJ (2010) Computational methods for sparse solution of linear inverse problems. Proc. IEEE 98(6):948-958. CrossRef |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
