Techniques for accelerating branch-and-bound algorithms dedicated to sparse optimization

Abstract

Sparse optimization–fitting data with a low-cardinality linear model–is addressed through the minimization of a cardinality-penalized least-squares function, for which dedicated branch-and-bound algorithms clearly outperform generic mixed-integer-programming solvers. Three acceleration techniques are proposed for such algorithms. Convex relaxation problems at each node are addressed with dual approaches, which can early prune suboptimal nodes. Screening methods are implemented, which fix variables to their optimal value during the node evaluation, reducing the subproblem size. Numerical experiments show that the efficiency of such techniques depends on the node cardinality and on the structure of the problem matrix. Last, different exploration strategies are proposed to schedule the nodes. Best-first search is shown to outperform the standard depth-first search used in the related literature. A new strategy is proposed which first explores the nodes with the lowest least-squares value, which is shown to be the best at finding the optimal solution–without proving its optimality. A C++ solver with compiling and usage instructions is made available. 

Keywords:

• Branch-and-bound
• cardinality
• convex relaxation
• duality
• exploration strategy

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Dataset available at https://gitlab.univ-nantes.fr/samain-g/mimosa-oms-dataset.

2 Terms available at https://opensource.org/licenses/LGPL-3.0.

Additional information

Funding

This work was partially funded by Agence Nationale de la Recherche [grant number ANR-16-CE33-0005-01].

Notes on contributors

Gwenaël Samain

Gwenaël Samain is a PhD student from Ecole Centrale, Nantes, and the Laboratory of Digital Sciences of Nantes, France. Their research focuses on optimization algorithms dedicated to inverse problems in signal and image processing, as well as sufficiency in the computer science field.

Sébastien Bourguignon

Sébastien Bourguignon is an associate professor with Ecole Centrale, Nantes, and the Laboratory of Digital Sciences of Nantes, France. His research interests include inverse problems in signal and image processing, sparse decompositions and related optimization algorithms. His preferred application fields concern ultrasonic imaging and nondestructive testing, astronomical data analysis, and remote sensing.

Jordan Ninin

Jordan Ninin is an associate professor with ENSTA Bretagne and the Lab-STICC laboratory, Brest, France. He is also an associate member of the GERAD research group in Montreal, Canada. His research focuses on exact global optimization algorithms with applications in robotics, control, and signal processing.