G-2004-84
Exact Solution of -norm and -norm Plane Separation
Charles Audet, Pierre Hansen, Alejandro Karam, Chi-to Daniel Ng et Sylvain Perron
We consider the problem of separating two sets of points in an n-dimensional real
space with a (hyper)plane that minimizes the sum of Lp-norm distances to the plane
of points lying on the wrong side of it. We propose a new mixed integer programming
formulation for the -norm case, and an implementation of a nonconvex quadratic
programming algorithm for the L2-norm case, based on a branch-and-cut approach.
Computational results are reported for several publicly available data sets and larger
artificial problems. We also explore the accelerating potential of incorporating heuris-
tic bounds in our exact solution approaches.
Paru en novembre 2004 , 17 pages