An algorithmic separating hyperplane theorem and its applications (Q1728094)

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.