AdONE Seminar: Prof. Stefan Weltge (TUM)

We consider the problem of maximizing a linear functional over a general convex body K given by a separation oracle. While the standard cutting plane algorithm performs well in practice, no bounds on the number of oracle calls can be given. In contrast, methods with strong theoretical guarantees, such as the ellipsoid method, are often impractical. We give a new simple method with weaker theoretical bounds but that performs considerably better in practice. It is based on classical Von Neumann and Frank-Wolfe algorithms, and requires O(R^4/(rɛ)^2) calls to the oracle to find an additive ɛ-approximate solution, where it is assumed that K contains a ball of radius r and is contained inside the origin centered ball of radius R. We evaluate our method on instances from combinatorial optimization, semidefinite programming, and machine learning. In terms of oracle calls, we observe that it is comparable to the standard cutting plane method and often even faster.

This is joint work with Daniel Dadush, Christopher Hojny, and Sophie Huiberts