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
Abstract
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/є.
Topics & Concepts
OracleRegular polygonBall (mathematics)CombinatoricsPlane (geometry)RADIUSCutting-plane methodConvex bodyMathematicsConvex setSet (abstract data type)Point (geometry)Convex optimizationMathematical optimizationAlgorithmGeometryComputer scienceSoftware engineeringComputer securityProgramming languageInteger programmingComplexity and Algorithms in GraphsComputational Geometry and Mesh GenerationMachine Learning and Algorithms