Optimization Problems with Cardinality Constraints: Exact and Approximate Solution Methods

The availability of very large and high-dimensional data sets poses great challenges to decision makers in many settings such as medical diagnosis, loan applications, fraud detection, and so on, each of which increasingly relies on machine learning models for automated decision making. The identification of a small number of relevant features of the data to make accurate predictions not only significantly reduces the complexity of the decision, but also dramatically enhances its interpretability, transparency, and fairness, all of which play a fundamental role in explainable artificial intelligence. Such decision problems can be mathematically modelled as optimization problems with cardinality constraints (OPCC), i.e., optimization problems with an upper bound on the number of nonzero components of the decision variable (also known as cardinality, sparsity, or l0-norm). Sparsity plays a vital role in a wide range of applications such as machine learning, data science, signal and image processing, portfolio management, sparse regression, and compressed sensing due to the interpretability, robustness, and ease of implementation of sparse solutions. As such, optimization problems with cardinality constraints arise in a plethora of applications, such as feature selection in machine learning, sparse support vector machines, sparse principal component analysis, and sparse portfolio optimization. Since the l0-norm is a discontinuous, integer-valued, nonconvex, and nonsmooth function, OPCC constitutes a highly challenging class of optimization problems. In pursuit of computational tractability, previous research has focussed on heuristic approaches based on tractable convex surrogates such as the widely popular l1-regularisation. However, this popular approach is only guaranteed to recover an exact solution of OPCC under either very restrictive or difficult-to-verify assumptions. Furthermore, for general OPCC, they can lead to highly inaccurate and grossly misleading solutions. The pervasiveness of OPCC in many critical applications, such as medical decision making, and the drawbacks of popular heuristic approaches necessitate research efforts towards finding optimal or near-optimal feasible solutions. With the notable exception of the sparse portfolio optimization problem, the literature on exact or approximate solution methods for OPCC is in its infancy. The main goal of this project is to close this gap by studying exact and approximate solution methods for OPCC in a unified framework. We aim to achieve this goal through two objectives: (1) Exact Solution Methods: We aim to perform a rigorous comparison of exact formulations of OPCC in terms of robustness, scalability, and optimality gaps considering different modelling options and the use of special types of constraints. (2) Approximate Solution Methods via Convex Relaxations: Since exact solution methods are not scalable, we aim to develop fast and effective feasibility restoration methods for constructing near-optimal feasible solutions of (OPCC) using optimal solutions of various tractable convex relaxations and rigorously analyse the trade-off between solution quality and scalability. This project will lay the foundations for finding optimal or near-optimal solutions for this class of problems in a unified framework. Improved solution accuracy and reliability will have significant benefits for a host of other fields that employ machine learning, artificial intelligence, data science, and business analytics models.