Polynomial interior point cutting plane methods
Download the paper,
postscript or pdf.
Author:
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj@rpi.edu
Abstract:
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.