Entropic Lower Bound of Cardinality for Sparse Optimization

Quentin Jacquet (1, 2, 3) , Agnes Bialecki (4) , Laurent El Ghaoui (5) , Stéphane Gaubert (1, 3) , Riadh Zorgati (2)

1 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
2 EDF R&D OSIRIS - Optimisation, Simulation, Risque et Statistiques pour les Marchés de l’Energie
3 TROPICAL - TROPICAL
4 EDF R&D - EDF R&D
5 Vin University Vietnam

We introduce a family of cardinality's lower bounds, defined as ratios of norms. We prove that the tightest bound of the family is obtained as a limit case, and involves a Shannon entropy. We then use this entropic lower bound in sparse optimization problems to approximate cardinality requirements. This provides a nonlinear nonconvex relaxed problem, which can be efficiently solved by off-the-shelf nonlinear solvers. In the numerical study, we focus on the case where the optimization is performed on the simplex, and where the classical l1 penalization does not yield sparse solution. The Finance Index Tracking problem is taken as an example and illustrates the efficiency of the proposed approach.

Keywords: Sparse Optimisation; Cardinality; l0-pseudo-norm; Shannon entropy; Index Tracking

Domains: Optimization and Control [math.OC]

Quentin Jacquet, Agnes Bialecki, Laurent El Ghaoui, Stéphane Gaubert, Riadh Zorgati. Entropic Lower Bound of Cardinality for Sparse Optimization. 2022. ⟨hal-03874638v1⟩