A Mixed-Integer Fractional Optimization Approach to Best Subset Selection
A Mixed-Integer Fractional Optimization Approach to Best Subset Selection
复制标题
DOI：
10.1287/ijoc.2020.1031
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
A. Gómez;O. Prokopyev
中科院分区：
文献类型：
--
作者：
A. Gómez;O. Prokopyev
我们考虑了线性回归中的最佳子集选择问题--即根据某个预先定义的标准，找到与数据最匹配的回归变量的简约子集。我们主要关注交叉验证方法的替代方法，这些方法不需要数据划分，并涉及在统计文献中广泛研究的一系列信息标准。我们表明，感兴趣的问题可以用分数混合整数优化来建模，这可以通过利用现代优化求解器中的最新进展来解决。所提出的算法涉及求解一系列混合整数二次优化问题(或其凸化)，并且可以用现成的求解器来实现。在我们的计算实验中，我们报告了在优化和统计性能方面令人鼓舞的结果。贡献总结：本文考虑了带信息准则的特征选择问题。我们表明，通过采用分数优化的观点(非线性优化和运筹学中的一个著名领域)，有可能利用混合整数二次优化技术的最新进展来解决长期以来被认为难以解决的传统统计问题。我们给出了大量的计算实验，包括合成数据和真实数据，说明新的分数优化方法比文献中现有的方法快了几个数量级。
We consider the best subset selection problem in linear regression—that is, finding a parsimonious subset of the regression variables that provides the best fit to the data according to some predefined criterion. We are primarily concerned with alternatives to cross-validation methods that do not require data partitioning and involve a range of information criteria extensively studied in the statistical literature. We show that the problem of interest can be modeled using fractional mixed-integer optimization, which can be tackled by leveraging recent advances in modern optimization solvers. The proposed algorithms involve solving a sequence of mixed-integer quadratic optimization problems (or their convexifications) and can be implemented with off-the-shelf solvers. We report encouraging results in our computational experiments, with respect to both the optimization and statistical performance. Summary of Contribution: This paper considers feature selection problems with information criteria. We show that by adopting a fractional optimization perspective (a well-known field in nonlinear optimization and operations research), it is possible to leverage recent advances in mixed-integer quadratic optimization technology to tackle traditional statistical problems long considered intractable. We present extensive computational experiments, with both synthetic and real data, illustrating that the new fractional optimization approach is orders of magnitude faster than existing approaches in the literature.