A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization

Опубликовано 22 июня 2016, 0:12

In this talk, I will present a new algorithm for finding a point in a convex set given a separation oracle. In particular, given a separation oracle for a convex set K in Rn that is contained in a box of radius R, I will show how to either compute a point in K or prove that K does not contain a ball of radius eps using an expected O(n log(nR/eps)) evaluations of the oracle and additional time O~(n 3 ). This improves upon the O~(n 3 .373) additional time of the previous fastest algorithm achieved over 25 years ago by Vaidya. As an example, I will show how to use it to obtain a faster algorithm for the following problems: 1. Submodular Function Minimization 2. Submodular Flow 3. Matroid Intersection 4. Semidefinite Programming