Thursday, August 9, 2012
Special Seminar in Applied Mathematics
Intrinsic Volumes of Convex Cones -- Part 3 of 3
Dennis Amelunxen, Paderborn Institute for Scientific Computation, Universität Paderborn
While intrinsic volumes of convex bodies (compact convex sets in euclidean space) are long-studied quantities with a rich and well-established theory, the study of intrinsic volumes of spherical convex bodies, or equivalently closed convex cones, is still in its infancy with many fascinating open questions. On the other hand, it has already shown that this theory may be a powerful tool for answering certain questions arising for example in the domain of convex programming. The goal of this lecture series is to provide an access to this theory, to present some recent successful applications, and to highlight the most prominent open questions.
Part 3: Condition of convex programming
In the third lecture we consider the notion of condition, which captures the stability and efficiency of algorithms, in the context of convex programming. We introduce the Grassmann condition, a geometric version of Renegar’s condition number, and describe a probabilistic analysis of it. As a corollary we obtain a full average-case analysis of an algorithm solving the semideﬁnite programming feasibility problem. The theory of intrinsic volumes plays a crucial role in the development of these results.