Geometric rescaling algorithms for conic feasibility

Various well known first order methods, such as Frank-Wolfe or von Neumann's method, can be used to solve conic  feasibility problems, that is, finding a point in the interior of a cone represented by a separation oracle. In the worst case, the running time of these methods depend linearly on Goffin's condition measure of the cone. In particular, when the cone is represented by linear inequalities, these first order methods are not polynomial. We propose a simple polynomial-time algorithm for the conic  feasibility problem.  The algorithm  iterates between simple first order steps and rescaling steps, where rescaling improves natural geometric potentials. The number of iterations of the algorithm depends on the logarithm of Goffin's condition measure of the cone; in particular, for cones represented explicitly by a system of linear inequalities, the method terminates in time polynomial in the encoding size of the input.

Finally, we show how the algorithm can be adapted to the submodular function minimization (SFM) problem, providing weakly polynomial-time algorithms for SFM. The method can be made strongly polynomial for SFM, and indeed we will discuss a very general black-box method to turn non-polynomial-time methods for SFM into strongly polynomial ones.

This is joint work with Daniel Dadush and Laszlo Vegh.