Cardinality Minimization, Constraints, and Regularization: A Survey
Preprint
Abstract
We survey optimization problems that involve the cardinality of variable vectors in constraints or the objective function. We provide a unified viewpoint on the general problem classes and models, and give concrete examples from diverse application fields such as signal and image processing, portfolio selection, or machine learning. The paper discusses general-purpose modeling techniques and broadly applicable as well as problem-specific exact and heuristic solution approaches. While our perspective is that of mathematical optimization, a main goal of this work is to reach out to and build bridges between the different communities in which cardinality optimization problems are frequently encountered. In particular, we highlight that modern mixed-integer programming, which is often regarded as impractical due to commonly unsatisfactory behavior of black-box solvers applied to generic problem formulations, can in fact produce provably high-quality or even optimal solutions for cardinality optimization problems, even in large-scale real-world settings. Achieving such performance typically draws on the merits of problem-specific knowledge that may stem from different fields of application and, e.g., shed light on structural properties of a model or its solutions, or lead to the development of efficient heuristics; we also provide some illustrative examples.Keywords
All Related Versions
This publication has 268 references indexed in Scilit:
- Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear SystemsCommunications on Pure and Applied Mathematics, 2016
- Necessary and sufficient conditions for linear convergence of ℓ1-regularizationCommunications on Pure and Applied Mathematics, 2010
- Iteratively reweighted least squares minimization for sparse recoveryCommunications on Pure and Applied Mathematics, 2009
- Fast Optimization Methods for L1 Regularization: A Comparative Study and Two New Approaches2007
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraintCommunications on Pure and Applied Mathematics, 2004
- Sparsification of Rectangular MatricesJournal of Symbolic Computation, 1998
- On the Complexity of Approximating Extremal Determinants in MatricesJournal of Complexity, 1995
- Bilinear separation of two sets inn-spaceComputational Optimization and Applications, 1993
- A hierarchical algorithm for making sparse matrices sparserMathematical Programming, 1992
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problemsMathematical Programming, 1976