A New Perspective on Convex Relations of Sparse SVM

TitleA New Perspective on Convex Relations of Sparse SVM
Publication TypeReport
Year of Publication2012
AuthorsGoldberg, N, Leyffer, S, Munson, TS
Date Published02/2012
Other NumbersANL/MCS-P2049-0212

This paper proposes a convex relaxation of a sparse support vector machine (SVM) based on the perspective relaxation of mixed-integer nonlinear programs. We seek to minimize the zero-norm of the hyperplane normal vector with a standard SVM hinge-loss penalty and extend our approach to a zero-one loss penalty. The relaxation that we propose is a second-order cone formulation that can be efficiently solved by standard conic optimization solvers. We compare the optimization properties and classification performance of the second-order cone formulation with previous sparse SVM formulations suggested in the literature. Keywords: SVM, second order cone optimization, sparsity