An improved cutting plane method for convex optimization, convex-concave games, and its applications
Haotian Jiang, Yin Tat Lee, Zhao Song, Sam Chiu-wai Wong · 2020
Given a separation oracle for a convex set K ⊂ ℝ n that is contained in a box of radius R, the goal is to either compute a point in K or prove that K does not contain a ball of radius є. We propose a new cutting plane algorithm that uses an optimal O(n log(κ)) evaluations of the oracle and an additional O(n 2) time per evaluation, where κ = nR/є.