A Novel Robust Optimization Model for Nonlinear Support Vector Machine

In this paper, we present new optimization models for Support Vector Machine (SVM), with the aim of separating data points in two or more classes. The classification task is handled by means of nonlinear classifiers induced by kernel functions and consists in two consecutive phases: first, a classical SVM model is solved, followed by a linear search procedure, aimed at minimizing the total number of misclassified data points. To address the problem of data perturbations and protect the model against uncertainty, we construct bounded-by-norm uncertainty sets around each training data and apply robust optimization techniques. We rigorously derive the robust counterpart extension of the deterministic SVM approach, providing computationally tractable reformulations. Closed-form expressions for the bounds of the uncertainty sets in the feature space have been formulated for typically used kernel functions. Finally, extensive numerical results on real-world datasets show the benefits of the proposed robust approach in comparison with various SVM alternatives in the machine learning literature.