# An algorithmic separating hyperplane theorem and its applications

Research output: Contribution to journalArticle

1 Citation (Scopus)

### 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, referred as distance duality, is distinct from classical separation theorems. Next, utilizing the theorem we develop a substantially generalized and stronger version of the Triangle Algorithm, originally designed for the convex hull membership problem. If δ =d(K,K ), the Euclidean distance between the sets, ρ the maximum of their diameters, and ε a prescribed tolerance, the Triangle Algorithm approximates δ , or induces a separating hyperplane, or approximates optimal supporting hyperplanes. Specifically, it computes (p,p )∈K×K satisfying any of the following conditions desired: (1) d(p,p )≤εd(p,v), v∈K, or d(p,p )≤εd(p ,v ), v ∈K (when δ =0); (2) the orthogonal bisector of pp separates K from K ; (3) d(p,p )−δ ≤εd(p,p ) (when δ >0); (4) the supporting hyperplanes orthogonal to pp satisfy δ −d(H,H )≤εd(p,p ). The corresponding number of iterations to solve these are, O(1∕ε 2 ), O(ρ 2 ∕δ 2 ), and O(ρ 2 ∕δ 2 ε) for the last two, all independent of K,K . The complexity in each iteration of the first two tasks is computing for a given pair of iterates (p,p )∈K×K a pivot, i.e. v∈K with d(p,v)≥d(p ,v), or v ∈K with d(p ,v )≥d(p,v ). For the last two the complexity of each iteration is either computing a pivot, or supporting hyperplanes (H,H ) orthogonal to pp . In the worst-case the complexity of each iteration is solving a linear program over K or K . 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. In separate work we describe computational comparison between Triangle Algorithm, Frank–Wolfe, Gilbert's Algorithm, SMO, and more. Future work includes extensions to unbounded convex sets, non-Euclidean norms, also combinatorial and NP-complete problems.

Original language English (US) 59-82 24 Discrete Applied Mathematics 256 https://doi.org/10.1016/j.dam.2018.05.009 Published - Mar 15 2019

### Fingerprint

Hyperplane
Iteration
Triangle
Theorem
Pivot
Convex Hull
Bisector
Separation Theorem
Linear programming
Approximate Algorithm
Computing
Computational complexity
Euclidean Distance
Polytopes
Intersect
Linear Program
Iterate
Convex Sets

### All Science Journal Classification (ASJC) codes

• Discrete Mathematics and Combinatorics
• Applied Mathematics

### Keywords

• Approximation algorithms
• Convex hull
• Convex sets
• Duality
• Frank–Wolfe
• Gilbert's algorithm
• Linear programming
• Separating hyperplane theorem
• Support vector machines

### Cite this

@article{6515b6a7058e4045b97a2f1d031be022,
title = "An algorithmic separating hyperplane theorem and its applications",
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, referred as distance duality, is distinct from classical separation theorems. Next, utilizing the theorem we develop a substantially generalized and stronger version of the Triangle Algorithm, originally designed for the convex hull membership problem. If δ ∗ =d(K,K ′ ), the Euclidean distance between the sets, ρ ∗ the maximum of their diameters, and ε a prescribed tolerance, the Triangle Algorithm approximates δ ∗ , or induces a separating hyperplane, or approximates optimal supporting hyperplanes. Specifically, it computes (p,p ′ )∈K×K ′ satisfying any of the following conditions desired: (1) d(p,p ′ )≤εd(p,v), v∈K, or d(p,p ′ )≤εd(p ′ ,v ′ ), v ′ ∈K ′ (when δ ∗ =0); (2) the orthogonal bisector of pp ′ separates K from K ′ ; (3) d(p,p ′ )−δ ∗ ≤εd(p,p ′ ) (when δ ∗ >0); (4) the supporting hyperplanes orthogonal to pp ′ satisfy δ ∗ −d(H,H ′ )≤εd(p,p ′ ). The corresponding number of iterations to solve these are, O(1∕ε 2 ), O(ρ ∗ 2 ∕δ ∗ 2 ), and O(ρ ∗ 2 ∕δ ∗ 2 ε) for the last two, all independent of K,K ′ . The complexity in each iteration of the first two tasks is computing for a given pair of iterates (p,p ′ )∈K×K ′ a pivot, i.e. v∈K with d(p,v)≥d(p ′ ,v), or v ′ ∈K ′ with d(p ′ ,v ′ )≥d(p,v ′ ). For the last two the complexity of each iteration is either computing a pivot, or supporting hyperplanes (H,H ′ ) orthogonal to pp ′ . In the worst-case the complexity of each iteration is solving a linear program over K or K ′ . 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. In separate work we describe computational comparison between Triangle Algorithm, Frank–Wolfe, Gilbert's Algorithm, SMO, and more. Future work includes extensions to unbounded convex sets, non-Euclidean norms, also combinatorial and NP-complete problems.",
keywords = "Approximation algorithms, Convex hull, Convex sets, Duality, Frank–Wolfe, Gilbert's algorithm, Linear programming, Quadratic programming, Separating hyperplane theorem, Support vector machines",
author = "Bahman Kalantari",
year = "2019",
month = "3",
day = "15",
doi = "10.1016/j.dam.2018.05.009",
language = "English (US)",
volume = "256",
pages = "59--82",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

In: Discrete Applied Mathematics, Vol. 256, 15.03.2019, p. 59-82.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An algorithmic separating hyperplane theorem and its applications

AU - Kalantari, Bahman

PY - 2019/3/15

Y1 - 2019/3/15

N2 - 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, referred as distance duality, is distinct from classical separation theorems. Next, utilizing the theorem we develop a substantially generalized and stronger version of the Triangle Algorithm, originally designed for the convex hull membership problem. If δ ∗ =d(K,K ′ ), the Euclidean distance between the sets, ρ ∗ the maximum of their diameters, and ε a prescribed tolerance, the Triangle Algorithm approximates δ ∗ , or induces a separating hyperplane, or approximates optimal supporting hyperplanes. Specifically, it computes (p,p ′ )∈K×K ′ satisfying any of the following conditions desired: (1) d(p,p ′ )≤εd(p,v), v∈K, or d(p,p ′ )≤εd(p ′ ,v ′ ), v ′ ∈K ′ (when δ ∗ =0); (2) the orthogonal bisector of pp ′ separates K from K ′ ; (3) d(p,p ′ )−δ ∗ ≤εd(p,p ′ ) (when δ ∗ >0); (4) the supporting hyperplanes orthogonal to pp ′ satisfy δ ∗ −d(H,H ′ )≤εd(p,p ′ ). The corresponding number of iterations to solve these are, O(1∕ε 2 ), O(ρ ∗ 2 ∕δ ∗ 2 ), and O(ρ ∗ 2 ∕δ ∗ 2 ε) for the last two, all independent of K,K ′ . The complexity in each iteration of the first two tasks is computing for a given pair of iterates (p,p ′ )∈K×K ′ a pivot, i.e. v∈K with d(p,v)≥d(p ′ ,v), or v ′ ∈K ′ with d(p ′ ,v ′ )≥d(p,v ′ ). For the last two the complexity of each iteration is either computing a pivot, or supporting hyperplanes (H,H ′ ) orthogonal to pp ′ . In the worst-case the complexity of each iteration is solving a linear program over K or K ′ . 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. In separate work we describe computational comparison between Triangle Algorithm, Frank–Wolfe, Gilbert's Algorithm, SMO, and more. Future work includes extensions to unbounded convex sets, non-Euclidean norms, also combinatorial and NP-complete problems.

AB - 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, referred as distance duality, is distinct from classical separation theorems. Next, utilizing the theorem we develop a substantially generalized and stronger version of the Triangle Algorithm, originally designed for the convex hull membership problem. If δ ∗ =d(K,K ′ ), the Euclidean distance between the sets, ρ ∗ the maximum of their diameters, and ε a prescribed tolerance, the Triangle Algorithm approximates δ ∗ , or induces a separating hyperplane, or approximates optimal supporting hyperplanes. Specifically, it computes (p,p ′ )∈K×K ′ satisfying any of the following conditions desired: (1) d(p,p ′ )≤εd(p,v), v∈K, or d(p,p ′ )≤εd(p ′ ,v ′ ), v ′ ∈K ′ (when δ ∗ =0); (2) the orthogonal bisector of pp ′ separates K from K ′ ; (3) d(p,p ′ )−δ ∗ ≤εd(p,p ′ ) (when δ ∗ >0); (4) the supporting hyperplanes orthogonal to pp ′ satisfy δ ∗ −d(H,H ′ )≤εd(p,p ′ ). The corresponding number of iterations to solve these are, O(1∕ε 2 ), O(ρ ∗ 2 ∕δ ∗ 2 ), and O(ρ ∗ 2 ∕δ ∗ 2 ε) for the last two, all independent of K,K ′ . The complexity in each iteration of the first two tasks is computing for a given pair of iterates (p,p ′ )∈K×K ′ a pivot, i.e. v∈K with d(p,v)≥d(p ′ ,v), or v ′ ∈K ′ with d(p ′ ,v ′ )≥d(p,v ′ ). For the last two the complexity of each iteration is either computing a pivot, or supporting hyperplanes (H,H ′ ) orthogonal to pp ′ . In the worst-case the complexity of each iteration is solving a linear program over K or K ′ . 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. In separate work we describe computational comparison between Triangle Algorithm, Frank–Wolfe, Gilbert's Algorithm, SMO, and more. Future work includes extensions to unbounded convex sets, non-Euclidean norms, also combinatorial and NP-complete problems.

KW - Approximation algorithms

KW - Convex hull

KW - Convex sets

KW - Duality

KW - Frank–Wolfe

KW - Gilbert's algorithm

KW - Linear programming

KW - Separating hyperplane theorem

KW - Support vector machines

UR - http://www.scopus.com/inward/record.url?scp=85048341839&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85048341839&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2018.05.009

DO - 10.1016/j.dam.2018.05.009

M3 - Article

AN - SCOPUS:85048341839

VL - 256

SP - 59

EP - 82

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -