### DIMACS Theoretical Computer Science Seminar

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.

See: http://paul.rutgers.edu/~yixinxu/theory-spring13.html