Arbitrary-norm separating plane

A plane separating two point sets in n-dimensional real space is constructe d such that it minimizes the sum of arbitrary-norm distances of misclassifi ed points to the plane. In contrast to previous approaches that used surrog ates 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. T his projection is used to formulate the separating-plane problem as a minim ization of a convex function on a unit sphere in a norm dual to that of the arbitrary norm used. For the l-norm, the problem can be solved in polynomi al 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 bilin ear function on a convex set. For the one and infinity norms, a finite succ essive linearization algorithm can be used for solving the exact penalty fo rmulation. (C) 1999 Elsevier Science B.V. All rights reserved.