EFFICIENCY OF THE ANALYTIC CENTER CUTTING PLANE METHOD FOR CONVEX MINIMIZATION

We consider the analytic center cutting plane method of Sonnevend and of Goffin et al. for minimizing a convex (possibly nondifferentiable) function subject to box constraints. At each iteration, accumulated su bgradient cuts define a polytope that localizes the minimum. The objec tive and its subgradient are evaluated at the analytic center of this polytope to produce a cut that improves the localizing set. While comp lexity results have been recently established far several related meth ods, the question of whether the original method converges has remaine d open. We show that the method converges and establish its efficiency .