Arbitrary-norm separating plane

Authors
Citation
Ol. Mangasarian, Arbitrary-norm separating plane, OPER RES L, 24(1-2), 1999, pp. 15-23
Citations number
25
Categorie Soggetti
Engineering Mathematics
Journal title
OPERATIONS RESEARCH LETTERS
ISSN journal
01676377 → ACNP
Volume
24
Issue
1-2
Year of publication
1999
Pages
15 - 23
Database
ISI
SICI code
0167-6377(199902/03)24:1-2<15:ASP>2.0.ZU;2-1
Abstract
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.