%A O. L. Mangasarian
%T Arbitrary-Norm Separating Plane
%D May 1997
%R 97-07
%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 to the misclassified-point distance-minimization
problem, the present approach is based on a 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 only,
the problem can be solved in polynomial time by solving
$2n$ linear programs or by solving a bilinear program.
For all other $p$-norms, $p\in(1,\infty]$, a related decision
problem to the minimization problem is NP-complete.
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 is proposed for solving the exact
penalty formulation.