Randomized Methods for Solving Convex Problems: Some Theory and Some Computational Experience

Daniel J. Epstein Department of Industrial and Systems Engineering Seminar"Randomized Methods for Solving Convex Problems: Some Theory and Some Computational Experience"Robert M. FreundTheresa Seley Professor in Management Sciences, MIT Sloan School of ManagementABSTRACT: In contrast to conventional continuous optimization algorithms whose iterates are computed and analyzed deterministically, randomized methods rely on stochastic processes and random number/vector generation as part of the algorithm and/or its analysis. Whereas randomization in algorithms has been a part of research in discrete optimization for at least the last 20 years, randomization has played at most a minor role in algorithms for continuous convex optimization, at least until recently. This talk will focus on two recent randomization-based algorithms for convex optimization: a method by Bertsimas and Vempala based on cuts at the center of mass, and a new method by Belloni and Freund that "pre-conditions" a standard interior-point algorithm using random walks. For the latter, we report very promising computational results on medium-sized conic problems. FRIDAY, OCTOBER 5, 2007, GERONTOLOGY BUILDING (GER)ROOM 309, 2:00–3:00 PMBIO: Professor Freund primarily does research on the theory and applications of continuous optimization models. Professor Freund's theoretical work includes interior-point methods for linear optimization and nonlinear optimization, complexity theory of algorithms for convex optimization and condition measures for conic and non-conic convex optimization in particular. Freund has also worked on large-scale applications of optimization in pattern classification, data mining, and adaptive conjoint analysis, among others. He has made contributions to convex analysis, combinatorics, and fixed-point theory as well. He is former Co-Editor of Mathematical Programming A and currently an Associate Editor of Mathematical Programming A, and currently Co-Director of MIT's new Program in Computation for Design and Optimization (CDO)(2004-present).

Location: Ethel Percy Andrus Gerontology Center (GER) - 309

Audiences: Everyone Is Invited

Contact: Georgia Lum