A fixed-center spherical separation algorithm with kernel transformations for classification problems

We consider a special case of the optimal separation, via a sphere, of two discrete point sets in a finite dimensional Euclidean space. In fact we assume that the center of the sphere is fixed. In this case the problem reduces to the minimization of a convex and nonsmooth function of just one variable, which can be solved by means of an “ad hoc” method in O(p log p) time, where p is the dataset size. The approach is suitable for use in connection with kernel transformations of the type adopted in the support vector machine (SVM) approach. Despite of its simplicity the method has provided interesting results on several standard test problems drawn from the binary classification literature. This research has been partially supported by the Italian “Ministero dell’Istruzione, dell’Università e della Ricerca Scientifica”, under PRIN project Numerical Methods for Global Optimization and for some classes of Nonsmooth Optimization Problems (2005017083.002).