A homogenized cutting plane method to solve the convex feasibility problem

E. D. Andersen, J.E. Mitchell, C. Roos, and T. Terlaky

We present a cutting plane algorithm for the feasibility problem that uses a homogenized self-dual approach to regain an approximate center when adding a cut. The algorithm requires a fully polynomial number of Newton steps. One novelty in the analysis of the algorithm is the use of a powerful proximity measure which is widely used in interior point methods but not previously used in the analysis of cutting plane methods. Moreover, a practical implementation of a variant of the homogenized cutting plane for solution of LPs is presented. Computational results with this implementation show that it is possible to solve a problem having several thousand constraints and about one million variables on a standard PC in a moderate amount of time.

ITS/TWI/SSOR, TU Delft, Delft, The Netherlands, and Math Sciences, Rensselaer Polytechnic Institute, Troy NY, August 1998, revised July 1999.

Contact: mitchj@rpi.edu