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 问题，我们提出了一种精确的过程。我们报告了在经典基准数据集上的数值实验结果，展示了我们方法的效率和效果。

通过硬基数约束的线性支持向量机特征选择：一种可扩展的 SDP 分解方法

Feature selection in linear SVMs via hard cardinality constraint: a  scalable SDP decomposition approach

We study the Lovasz number theta along with two further SDP relaxations
theta1, theta1/2 of the independence number and the corresponding relaxations
of the chromatic number on random graphs G(n,p). We prove that these
relaxations are concentrated about their means Moreover, extending a result of
Juhasz, we compute the asymptotic value of the relaxations for essentially the
entire range of edge probabilities p. As an application, we give an improved
algorithm for approximating the independence number in polynomial expected
time, thereby extending a result of Krivelevich and Vu. We also improve on the
analysis of an algorithm of Krivelevich for deciding whether G(n,p) is
k-colorable.

研究在随机图 G (n,p) 上的独立数和色数及其相应的松弛值，提出了一种改进的算法来近似计算独立数，同时对于判断 G (n,p) 是否可着色的算法提出了改进方法，并计算了边概率 p 范围内松弛值的渐近值。