A cutting plane algorithm for convex programming that uses analytic centers

An oracle for a convex set accepts as input any point z in , and if , then it returns ‘yes’, while if , then it returns ‘no’ along with a separating hyperplane. The authors give a new algorithm that finds a feasible point in S in cases where an oracle is available. The present algorithm uses the analytic center of a polytope as test point, and successively modifies the polytope with the separating hyperplanes returned by the oracle. The key to establishing convergence is that hyperplanes judged to be ‘unimportant’ are pruned from the polytope. If a ball of radius is contained in S, and S is contained in a cube of side , then the authors can show the present algorithm converges after iterations and performs a total of arithmetic operations, where T is the number of arithmetic operations required for a call to the oracle. The bound is independent of the number of hyperplanes generated in the algorithm. An important application in which an oracle is available is minimizing a convex function over S.