The Volumetric Cutting Plane Method for Convex Programming

By Kurt Anstreicher

Abstract. We consider a simplified and strengthened version of Vaidya's volumetric cutting plane method for finding a point in a convex set . At each step the algorithm has a system of linear inequality constraints which defines a polyhedron , and an interior point . The algorithm then either drops one constraint, or calls an oracle to check if , and if not obtain a new constraint that separates x from C. Following the addition or deletion of a constraint, the algorithm takes a small number of Newton steps for the volumetric barrier . Progress of the algorithm is measured in terms of changes in . The algorithm is terminated when either it is discovered that , or becomes large enough to demonstrate that the volume of C must be below some prescribed amount. The complexity of the algorithm compares favorably with that of the ellipsoid method, especially in terms of the number of calls to the separation oracle. Compared to Vaidya's original analysis, we decrease the maximum number of constraints used to define P from to 200n. We also consider a ``central cut" version of the algorithm that reduces the maximum number of constraints to 25n.