%A O. L. Mangasarian
%T Arbitrary-Norm Separating Plane
%D May 1997. Revised April 1998 & September 1998
%R 97-07R
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X
A plane separating two point sets in $n$-dimensional
real space is constructed such that
it minimizes the sum of arbitrary-norm distances of misclassified points
to the plane. In contrast to previous approaches that
used surrogates for distance-minimization,
the present work is based on a precise norm-dependent explicit closed form
for the projection of a point on a plane.
This projection is used to formulate the separating-plane
problem as a minimization of a convex function on a unit sphere
in a norm dual to that of the arbitrary norm used. For the $1$-norm,
the problem can be solved in polynomial time by solving
$2n$ linear programs or by solving a bilinear program.
For a general $p$-norm, the minimization problem can be
transformed via an exact penalty formulation to minimizing
the sum of a convex function and a bilinear function
on a convex set. For the one and infinity norms, a finite successive
linearization algorithm can be used for solving the exact
penalty formulation.