Dual formulation of the sparsity constrained optimization problem: application to classification

Abstract

We tackle the sparsity constrained optimization problem by resorting to polyhedral k-norm as a valid tool to emulate the ${\ell }_0$-pseudo-norm. The main novelty of the approach is the use of the dual of the k-norm, which allows to obtain a formulation amenable for a relaxation that can be efficiently handled by block coordinate methods. The advantage of the approach is that it does not require the solution of difference-of-convex programmes, unlike other k-norm based methods available in the literature. In fact, our block coordinate approach requires, at each iteration, the solution of two convex programmes, one of which can be solved in $O(\mathrm{nlog}n)$ time. We apply the method to feature selection within the framework of Support Vector Machine classification, and we report the results obtained on some benchmark test problems.

Keywords:

• Sparse optimization
• cardinality constraint
• polyhedral k-norm
• block coordinate methods

Disclosure statement

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

Notes

1 We have adopted the method available in the Python scikit-learn library.

Additional information

Notes on contributors

M. Gaudioso

M. Gaudioso is professor emeritus at University of Calabria (Rende, Italy), where he has been professor of operations research until his retirement in 2019. His research interests include nondifferentiable optimization, mathematical programming for machine learning, and application of optimization methods to logistics.

G. Giallombardo

G. Giallombardo is an associate professor of operations research at University of Calabria (Rende, Italy). His current research activities are focused on numerical nonsmooth optimization, on optimization models and algorithms for statistical learning, and on the application of optimization to engineering and logistics systems.

J.-B. Hiriart-Urruty

J.-B. Hiriart-Urruty, has been professor at the Paul Sabatier university (Toulouse, France) from 1981 to 2015. Since, he is professor emeritus of that university. His interests in research included variational analysis (convex, nonsmooth, applied), and optimization. He also takes an active interest in issues of mathematics education and popularization of science.