%A Kristin P. Bennett & O. L. Mangasarian
%T Robust Linear Programming Discrimination
%D 1991
%R 1054a
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X
A single linear programming formulation is proposed
which generates a plane that minimizes an average sum of weighted distances
to the plane of misclassified points belonging to two
disjoint point sets in $n$-dimensional real
space. When the convex hulls of the two sets are also disjoint, the
plane completely separates the two sets. When the convex hulls
intersect, our linear program, unlike all previously proposed linear
programs, is guaranteed to generate some error-minimizing plane, without
the imposition of extraneous normalization constraints that inevitably
fail to handle certain cases. The effectiveness of the proposed linear
program has been demonstrated by successfully testing it on a number of
databases. In addition, it has been used in conjunction with the
multisurface method of piecewise-linear separation to train a
feed-forward neural network with a single hidden layer.