Linear convergence of modified Frank-Wolfe algorithms for ellipsoid optimization algorithms

Other Talks
Tuesday, September 22, 2009 - 11:00am for 1 hour (actually 50 minutes)
ISyE Executive Classroom, Main Building
Michael J. Todd – School of Operations Research and Information Engineering, Cornell University
We discuss the convergence properties of first-order methods for two problems that arise in computational geometry and statistics: the minimum-volume enclosing ellipsoid problem and the minimum-area enclosing ellipsoidal cylinder problem for a set of m points in R^n. The algorithms are old but the analysis is new, and the methods are remarkably effective at solving large-scale problems to high accuracy.