Novel approaches to the discrimination problem

The authors consider the problem of determining a hyperplane that separates, as ‘well’ as possible, two finite sets of points in Rⁿ. They analyze two criteria for judging the quality of a candidate hyperplane (i) the maximal distance of a misclassified point to the hyperplane (ii) the number of misclassified points. In each case, the authors investigate the computational complexity of the corresponding mathematical programs, give equivalent formulations, suggest solution algorithms and present preliminary numerical results.