Groupe d’études et de recherche en analyse des décisions

G-91-21

Novel Approaches to the Discrimination Problem

et

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