Ellipsoidal Separation for Classification Problems

We state the problem of the optimal separation via an ellipsoid in R-n of a discrete set of points from another discrete set of points. Our formulation requires the minimization of a convex nonsmooth (piecewise affine) function under the constraint that the matrix of the decision variables is positive definite. We describe a heuristic algorithm of the local search type embedding some ideas coming from nonsmooth optimization. Finally, we present the numerical results obtained by running our method on some standard test problems drawn from the binary classification literature.