# A Generic Branch-and-Bound for $l_0$-Penalized Problems

* Théo Guyard (Inria and Insa, CNRS, IRMAR - UMR CNRS 6625, Rennes, France)

* Cédric Herzet (Ensai, CNRS, CREST - UMR 9194, Rennes, France)

* Clément Elvira (CentraleSupelec, CNRS, IETR - UMR 6164, Rennes, France)

* Ayşe-Nur Arslan (Inria, CNRS, IMB - UMR 5251 Bordeaux, France, France)

**Keywords:** Sparse modeling, $l_0$-penalized problems, branch-and-bound.

**Abstract:** Sparse modeling arises in various applied mathematical fields such as machine learning or signal processing [1]. In this context, addressing $l_0$-penalized problems of the form

$$ \mathbf{x}^* \in \arg \min_{\mathbf{x}} f(\mathbf{x}) + \lambda \|\mathbf{x}\|_0 + h(\mathbf{x}) $$

is of particular interest. The function $f(\cdot)$ is a loss linked to the considered model, the $l_0$-norm enforces sparsity in the optimizer by counting the number of non-zeros in its input and the penalty term $h(\cdot)$ promotes other desirable properties that may be relevant for the application at hand. Problems involving the $l_0$-norm are NP-hard in the general case but they can be tackled using mixed-integer optimization methods. On the one hand, off-the-shelf solvers can handle a large variety of instances [2] but suffer from bad numerical performance since they are not fully able to exploit the sparse structure of the problem. On the other hand, specialized Branch-and-Bound (BnB) methods achieve more reasonable solving time but can only address specific instances of the problem, namely with a quadratic loss function and a penalty term either encoding a Big-M constraint [3] and/or an $l_2$-norm [4].

We propose a generic framework for specialized BnB solvers that can handle any instance of $l_0$-penalized problems verifying some mild hypotheses and which achieves competitive numerical performance. Through new theoretical results, we show that all the ingredients required for its implementation can be obtained in closed form, even though we do not require the explicit expression of $f(\cdot)$ and $h(\cdot)$. Interestingly, we show that our approach encompasses prior works as a special case. Capitalizing on the genericity of our framework, we provide E10ps, a flexible implementation of our BnB solver with a plug-and-play workflow allowing user-defined functions $f(\cdot)$ and $h(\cdot)$ to best fit the practitioner's needs. Through different experiments, we show that our solver achieves state-of-the-art performance on classical instances of the problem and can address new instances for which no specialized solvers exist so far and that have therefore been out of computational reach. Our contribution thus paves the way for new application opportunities.

## References

[1] Tropp, J. et al., Computational methods for sparse solution of linear inverse problems, *Proceedings of the IEEE*, 98(6), 948-958, 2010.

[2] Bourguignon, S. et al., Exact sparse approximation problems via mixed-integer programming: Formulations and computational performance, *IEEE Transactions on Signal Processing*, 64(6), 1405-1419, 2016.

[3] Ben Mhenni, R. et al., Global optimization for sparse solution of least squares problems, *Optimization Methods and Software*, 37(5), 1740-1769, 2022.

[4] Hazimeh, H., et al., Sparse regression at scale: Branch-and-bound rooted in first-order optimization, *Mathematical Programming*, 196(1-2), 347-388, 2022.