2025/06/04 by Clément Elvira, Elvira, Clément, Théo Guyard +3
Computer Science · Decision Sciences · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2506.03974
openalex publication_date 2025/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.