Exact L2-norm plane separation

Charles Audet, Pierre Hansen, Alejandro Karam, Chi To Ng, Sylvain Perron

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

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. Despite recent progress, practical techniques for the exact solution of cases other than the L1and L∞-norm were unavailable. We propose and implement a new approach, based on non-convex quadratic programming, for the exact solution of the L2-norm case. We solve in reasonable computing times artificial problems of up to 20000 points (in 6 dimensions) and 13 dimensions (with 2000 points). We also observe that, for difficult real-life instances from the UCI Repository, computation times are substantially reduced by incorporating heuristic results in the exact solution process. Finally, we compare the classification performance of the planes obtained for the L1, L2and L∞formulations. It appears that, despite the fact that L2formulation is computationally more expensive, it does not give significantly better results than the L1and L∞formulations.
Original languageEnglish
Pages (from-to)483-495
Number of pages13
JournalOptimization Letters
Volume2
Issue number4
DOIs
Publication statusPublished - 1 Aug 2008

Keywords

  • L -norm separation 2
  • Linear discrimination
  • Quadratic programming
  • Separating plane

ASJC Scopus subject areas

  • Control and Optimization

Cite this