Retour

Exact Solution of -norm and -norm Plane Separation

Charles Audet, Pierre Hansen, Alejandro Karam, Chi-to Daniel Ng et Sylvain Perron

référence BibTeX

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 $L_\infty$-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.

, 17 pages

Publication

Exact $$l_2$$-norm plane separation
, , et
Optimization Letters, 2(4), 483–495, 2008 référence BibTeX