%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.