COMPLEXITY OF SOME CUTTING PLANE METHODS THAT USE ANALYTIC CENTERS

We consider cutting plane methods for minimizing a convex (possibly no ndifferentiable) function subject to box constraints. At each iteratio n, accumulated subgradient cuts define a polytope that localizes the m inimum. The objective and its subgradient are evaluated at the analyti c center of this polytope to produce one or two cuts that improve the localizing set. We give complexity estimates for several variants of s uch methods. Our analysis is based on the works of Goffin, Luo and Ye.