A PRACTICAL GEOMETRICALLY CONVERGENT CUTTING PLANE ALGORITHM

In this paper we consider a practical variation of the Cheney-Goldstei n-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 geome tric global rate of convergence asymptotically under mild assumptions. Other proofs of the rate of convergence for this type of algorithm re quire restrictive assumptions such as strict convexity of the objectiv e function or a Haar condition. The approach taken here requires only that at each iteration of the algorithm a cut is produced for each con vex constraint.