Title: An Algorithmic Separating Hyperplane Theorem and Its Applications
Speaker: Bahman Kalantari, Rutgers University
Date: Wednesday, April 3, 2013 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We first prove a new separating hyperplane theorem for compact convex subsets of the Euclidean space, distinct from classical theorems which are essentially existential rather than algorithmic. Next, utilizing this theorem, we develop a substantially generalized version of the Triangle Algorithm to perform either one of the following tasks: (i) To approximate the Euclidean distance between given compact convex subsets K, Kâ by computing a pair (p, pâ) in K x Kâ, where d(p, pâ) is within prescribed tolerance of d(K, Kâ); (ii) When K and Kâ are disjoint, to compute a separating hyperplane; (iii) When K and Kâ are disjoint, to compute a pair of parallel supporting hyperplanes whose distance is within prescribed error of the largest possible margin. The main work in each iteration is the optimization of a linear function over K or Kâ. The resulting algorithm is a fully polynomial-time approximation scheme for such special cases as when each set is the convex hull of a finite point set or the intersection of a finite number of halfspaces. The results find many applications such as in machine learning, statistics, linear, quadratic, and convex programming. The Triangle Algorithm is more general than the existing algorithms, developed only for special cases of the problem, e.g. Gilbert's algorithm (equivalently, Frank-Wolfe, sparse greedy approximation) and distinct from them. Our results can also be used to provide a certain approximation to NP-complete problems when appropriately formulated.