Back

G-91-21

Novel Approaches to the Discrimination Problem

and

BibTeX reference

We consider the problem of determining a hyperplane that separates, as "well" as possible, two finite sets of points in Rn. We 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, we investigate the computational complexity of the corresponding mathematical programs, give equivalent formulations, suggest solution algorithms and present preliminary numerical results.

, 22 pages