A homogenized cutting plane method to solve the convex feasibility problem

Chapter 10 in Optimization Methods and Applications, edited by X. Q. Yang et al., Kluwer Academic Publishers, April 2001. Download the paper: postscript or pdf.

Authors:

Erling Andersen
ITS / TWI / SSOR,
Delft University of Technology,
Delft, The Netherlands.
e.d.andersen@twi.tudelft.nl

John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj@rpi.edu

Kees Roos
ITS / TWI / SSOR,
Delft University of Technology,
Delft, The Netherlands.
c.roos@twi.tudelft.nl

Tamas Terlaky
ITS / TWI / SSOR,
Delft University of Technology,
Delft, The Netherlands.
t.terlaky@twi.tudelft.nl

Abstract:

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.

Download the paper: postscript or pdf.

Return to my list of papers.