LEAST QUANTILE REGRESSION VIA MODERN OPTIMIZATION
LEAST QUANTILE REGRESSION VIA MODERN OPTIMIZATION
复制标题
DOI：
10.1214/14-aos1223
复制
发表时间：
2014-12-01
影响因子：
4.5
通讯作者：
Mazumder, Rahul
中科院分区：
文献类型：
--
作者：
Bertsimas, Dimitris;Mazumder, Rahul
我们使用现代优化方法解决最小二乘分位数（LQS）（特别是最小二乘中位数）回归问题。我们提出了一个混合优化（MIO）制定的LQS问题，使我们能够找到一个可证明的全局最优解的LQS问题。我们的MIO框架具有吸引人的特点，如果我们提前终止算法，我们将获得一个保证其次优性的解决方案。我们还提出了连续优化方法的基础上，一阶次微分方法，序列线性优化和混合组合，它们获得接近最优的解决方案的LQS问题。MIO算法被发现受益于我们的持续优化的方法提供的高质量的解决方案显着。我们进一步表明，MIO方法导致（a）任何数据集的最佳解决方案，其中数据点（y（i），x（i））不一定在一般位置，（B）一个简单的证明，故障点的LQS目标值，适用于任何数据集和（c）的情况下，有多面体约束的回归系数向量的扩展。我们报告了合成和真实世界数据集的计算结果，表明从连续优化方法中温启动的MIO算法在两个小时内解决了小（n = 100）和中等（n = 500）规模的问题，并在大规模（n = 10，000）LQS问题上优于所有公开可用的方法。
We address the Least Quantile of Squares (LQS) (and in particular the Least Median of Squares) regression problem using modern optimization methods. We propose a Mixed Integer Optimization (MIO) formulation of the LQS problem which allows us to find a provably global optimal solution for the LQS problem. Our MIO framework has the appealing characteristic that if we terminate the algorithm early, we obtain a solution with a guarantee on its sub-optimality. We also propose continuous optimization methods based on first-order subdifferential methods, sequential linear optimization and hybrid combinations of them to obtain near optimal solutions to the LQS problem. The MIO algorithm is found to benefit significantly from high quality solutions delivered by our continuous optimization based methods. We further show that the MIO approach leads to (a) an optimal solution for any dataset, where the data-points (y(i), x(i))'s are not necessarily in general position, (b) a simple proof of the breakdown point of the LQS objective value that holds for any dataset and (c) an extension to situations where there are polyhedral constraints on the regression coefficient vector. We report computational results with both synthetic and real-world datasets showing that the MIO algorithm with warm starts from the continuous optimization methods solve small (n = 100) and medium (n = 500) size problems to provable optimality in under two hours, and outperform all publicly available methods for large-scale (n = 10,000) LQS problems.