Towards a Practical Volumetric Cutting Plane Method for Convex Programming

Kurt M. Anstreicher

We consider the volumetric cutting plane method for finding a point in a convex set $\Ccal\subset\Re^n$ that is characterized by a separation oracle. We prove polynomiality of the algorithm with each added cut placed directly through the current point, and show that this ``central cut" version of the method can be implemented using no more than $25n$ constraints at any time.