Feature selection in linear SVMs via hard cardinality constraint: a
  scalable SDP decomposition approach
Immanuel Bomze Federico D'Onofrio Laura Palagi Bo Peng
In this paper, we study the embedded feature selection problem in linear
Support Vector Machines (SVMs), in which a cardinality constraint is employed,
leading to a fully explainable selection model. The problem is NP-hard due to
the presence of the cardinality constraint, even though the original linear SVM
amounts to a problem solvable in polynomial time. To handle the hard problem,
we first introduce two mixed-integer formulations for which novel SDP
relaxations are proposed. Exploiting the sparsity pattern of the relaxations,
we decompose the problems and obtain equivalent relaxations in a much smaller
cone, making the conic approaches scalable. To make the best usage of the
decomposed relaxations, we propose heuristics using the information of its
optimal solution. Moreover, an exact procedure is proposed by solving a
sequence of mixed-integer decomposed SDPs. Numerical results on classical
benchmarking datasets are reported, showing the efficiency and effectiveness of
our approach.