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

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

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.

Recommendations

Cites work

Cited in

(11)

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)