Polynomial interior point cutting plane methods

Download the paper, postscript or pdf.


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


Polynomial cutting plane methods based on the logarithmic barrier function and on the volumetric center are surveyed. These algorithms construct a linear programming relaxation of the feasible region, find an appropriate approximate center of the region, and call a separation oracle at this approximate center to determine whether additional constraints should be added to the relaxation. Typically, these cutting plane methods can be developed so as to exhibit polynomial convergence. The volumetric cutting plane algorithm achieves the theoretical minimum number of calls to a separation oracle. Long-step versions of the algorithms for solving convex optimization problems are presented.

Optimization Methods and Software, 18(5), pages 507-534, 2003.

Download the paper, postscript or pdf.

Return to my list of papers.