A Practical Geometrically Convergent Cutting Plane Algorithm

In this paper we consider a practical variation of the Cheney–Goldstein–Kelley cutting plane algorithm which solves linear relaxations using the lexicographic dual simplex method and allows for the deletion of inactive cuts. The algorithm presented can be shown to exhibit a geometric global rate of convergence asymptotically under mild assumptions. Other proofs of the rate of convergence for this type of algorithm require restrictive assumptions such as strict convexity of the objective function or a Haar condition. The approach taken here requires only that at each iteration of the algorithm a cut is produced for each convex constraint.