An algorithmic separating hyperplane theorem and its applications

DOI10.1016/J.DAM.2018.05.009MaRDI QIDQ1728094zbMATH OpenOpenAlexWikidataFDO

Publication date 21 February 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.0356

approximation algorithms convex hull convex sets duality Frank-Wolfe Gilbert's algorithm linear programming quadratic programming separating hyperplane theorem support vector machines

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Abstract: We first prove a new separating hyperplane theorem characterizing when a pair of compact convex subsets

K, K^{'}

of the Euclidean space intersect, and when they are disjoint. The theorem is distinct from classical separation theorems. It generalizes the {it distance duality} proved in our earlier work for testing the membership of a distinguished point in the convex hull of a finite point set. Next by utilizing the theorem, we develop a substantially generalized and stronger version of the {it Triangle Algorithm} introduced in the previous work to perform any of the following three tasks: (1) To compute a pair

(p, p^{'}) i n K i m e s K^{'}

, where either the Euclidean distance

d (p, p^{'})

is to within a prescribed tolerance, or the orthogonal bisecting hyperplane of the line segment

p p^{'}

separates the two sets; (2) When

K

and

K^{'}

are disjoint, to compute

(p, p^{'}) i n K i m e s K^{'}

so that

d (p, p^{'})

approximates

d (K, K^{'})

to within a prescribed tolerance; (3) When

K

and

K^{'}

are disjoint, to compute a pair of parallel supporting hyperplanes

H, H^{'}

so that

d (H, H^{'})

is to within a prescribed tolerance of the optimal margin. The worst-case complexity of each iteration is solving a linear objective over

K

or

K^{'}

. The resulting algorithm is a fully polynomial-time approximation scheme for such important special cases as when

K

and

K^{'}

are convex hulls of finite points sets, or the intersection of a finite number of halfspaces. The results find many theoretical and practical applications, such as in machine learning, statistics, linear, quadratic and convex programming. In particular, in a separate article we report on a comparison of the Triangle Algorithm and SMO for solving the hard margin problem. In future work we extend the applications to combinatorial and NP-complete problems.

Review text

The aim of this paper is to present a new theory and algorithms for testing the intersection or separation of two arbitrary compact convex sets. First the article considers the algorithmic separation of two convex subsets \(K\) and \(K'\) of \(\mathbb R^m\), assumed to be compact. A new separating hyperplane theorem is proved and it is used to present a conceptually simple algorithm that achieves several distinct tasks. Utilizing the theorem, referred as distance duality, a substantially generalized and stronger version of the Triangle Algorithm, originally designed for the convex hull membership problem, is developed. Special cases include when \(K\) and \(K'\) are convex hulls of finite sets, or polytopes described as the intersection of halfspaces. The corresponding problems include, linear and quadratic programming, SVM and more.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: An algorithmic separating hyperplane theorem and its applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1728094)