Publications

N. Goldberg, S. Leyffer, T. Munson, "A New Perspective on Convex Relations of Sparse SVM," Preprint ANL/MCS-P2049-0212, February 2012. [pdf]

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