A CUTTING PLANE ALGORITHM FOR CONVEX-PROGRAMMING THAT USES ANALYTIC CENTERS

An oracle for a convex set S subset of R '' accepts as input any point z in R(n), and if z is an element of S, then it returns 'yes', while if z is not an element of S, then it returns 'no' along with a separating hyperplane. We give a new algorithm that finds a feasible point in S in cases where an oracle is available. Our 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 2(-L) contained in S, and S is contained in a cube of side 2(L+1), then we can show our algorithm converges after O(nL(2)) iterations and performs a total of O(n(4)L(3) + TnL(2)) arithmetic operations, where T is the number of arithmetic operations required for a call Co the oracle. The bound is independent of the number of hyperplanes generated in the algorithm.