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.

我们研究了线性支持向量机（SVM）中的嵌入式特征选择问题，其中采用了基数约束，从而形成了一个完全可解释的选择模型。我们提出了两种混合整数模型，并针对其提出了新的 SDP 松弛策略。通过利用松弛策略的稀疏性模式，我们将问题进行分解，并在一个较小的锥体中获得了等效的松弛策略，使锥形方法具有可伸缩性。为了最大程度地利用分解的松弛策略，我们提出了使用其最优解信息的启发式方法。此外，通过解决一系列混合整数分解的 SDP 问题，我们提出了一种精确的过程。我们报告了在经典基准数据集上的数值实验结果，展示了我们方法的效率和效果。