Polynomial interior point cutting plane methods

Polynomial interior point cutting plane methods

0.00 Avg rating0 Votes
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:
Keywords: interior point methods, cutting plane algorithms
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 of calls to a separation oracle. Long-step versions of the algorithms for solving convex optimization problems are presented.

Reviews

Required fields are marked *. Your email address will not be published.