CAM Colloquium: Javier Pena (Carnegie Mellon) - On the Role of Separation in Convex Optimization
Friday, February 22, 2013 at 3:30pm
Frank H. T. Rhodes Hall, 655
Separating hyperplane theorems are fundamental properties of convex sets and provide a foundational cornerstone in optimization. On the one hand, separation is closely tied to duality theory and to various kinds of optimality conditions. On the other hand, some algorithmic schemes in optimization, such as the classical relaxation method (1950s) and the Ellipsoid method (1970s), rely primarily on the availability of a suitable “separation oracle”. For a convex set C, a separation oracle is a procedure that given any point x, either attests that x belongs to C or generates a hyperplane separating x from C.
This talk will present an overview of separation-based algorithms for convex optimization. We will highlight some of the geometric intuition underlying these algorithms. We will also discuss some interesting recent advances in this class of algorithms. Some of these advances concern connections between the relaxation method and currently popular first-order methods for large-scale convex optimization. Some other advances involve randomization and periodic rescaling for faster convergence.