提出通用分支定界法求解ℓ₀正则化问题，支持自定义损失函数。
A Generic Branch-and-Bound Algorithm for $\ell_0$-Penalized Problems with Supplementary Material
- 基于通用惩罚项设计灵活松弛，突破传统方法限制。
- 理论证明关键量可闭式求解，提升算法效率。
- 开源工具El0ps支持快速接入新任务，性能领先。
本文提出一种通用的分支定界算法，用于求解ℓ₀正则化优化问题。现有方法多针对二次损失，依赖“Big-M”约束或L2正则松弛。我们的方法拓展至更广泛的损失函数，并通过通用惩罚项实现松弛设计的灵活性，涵盖已有技术作为特例。在本文考虑的通用假设下，我们证明了分支定界实现所需的所有关键量均可闭式表达。基于此框架，我们开发了El0ps——一个开源的Python求解器，提供即插即用的工作流，支持用户自定义损失和惩罚项。大量数值实验表明，El0ps在经典实例上达到当前最优性能，并将计算可行性扩展至此前难以处理的问题。
原文摘要 · Abstract (English)
We present a generic Branch-and-Bound procedure designed to solve L0-penalized optimization problems. Existing approaches primarily focus on quadratic losses and construct relaxations using "Big-M" constraints and/or L2-norm penalties. In contrast, our method accommodates a broader class of loss functions and allows greater flexibility in relaxation design through a general penalty term, encompassing existing techniques as special cases. We establish theoretical results ensuring that all key quantities required for the Branch-and-Bound implementation admit closed-form expressions under the general blanket assumptions considered in our work. Leveraging this framework, we introduce El0ps, an open-source Python solver with a plug-and-play workflow that enables user-defined losses and penalties in L0-penalized problems. Through extensive numerical experiments, we demonstrate that El0ps achieves state-of-the-art performance on classical instances and extends computational feasibility to previously intractable ones.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。