64
Views
0
CrossRef citations to date
0
Altmetric
Special Issue: Advances in Continuous Optimization

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

ORCID Icon, ORCID Icon & ORCID Icon
Pages 84-101 | Received 07 Mar 2022, Accepted 24 Oct 2023, Published online: 21 Nov 2023
 

Abstract

We tackle the sparsity constrained optimization problem by resorting to polyhedral k-norm as a valid tool to emulate the 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(nlogn) 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.

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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.