Speaker: Irwin Pressman, Carleton University Time: Tuesday, November 12, 2:30 p.m. Place: HP4369, School of Math and Stats, Carleton University Title: A hit-and-run method for finding the extreme points of a finite set Abstract: Given a finite set ${\mathcal F} $ of $q$ points in $\Re^d$, we describe a hit-and-run algorithm, for any dimension Euclidean space, for finding the extreme points of the convex hull of ${\mathcal F}.$ We define the region ${\mathcal {R(F)}} \subseteq \Re^{\frac{d(d+3)}{2}}$ that corresponds to the space of ellipsoids containing the set ${\mathcal F}$. We develop a dual relationship between points in $\Re^d$ and convex constraints in the space of ellipsoids that effectively turns the problem {\it inside-out}; redundant points of ${\mathcal F}$ correspond to redundant constraints. We show that $p \in {\mathcal F} $ is an extreme point if and only if its corresponding constraint is necessary in ${\mathcal {R(F)}}.$ A semidefinite hit-and-run algorithm for detecting necessary constraints that searches along the coordinate directions is presented. Each search along a single coordinate direction requires ${\bf O}(qd+d^2)$ flops. The algorithm also estimates the distribution of the points on the convex hull, and finds the layers of the data. This approach is useful for approximation of the convex hull. The ellipsoidal geometry of interest because we develop a simple, but practical, approach for using ellipsoids instead of hyperplanes for separating space.