Article ID: | iaor20042322 |
Country: | United Kingdom |
Volume: | 18 |
Issue: | 5 |
Start Page Number: | 507 |
End Page Number: | 539 |
Publication Date: | Oct 2003 |
Journal: | Optimization Methods & Software |
Authors: | Mitchell John E. |
Keywords: | interior point methods, cutting plane algorithms |
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 of calls to a separation oracle. Long-step versions of the algorithms for solving convex optimization problems are presented.