Complexity of some cutting plane methods that use analytic centers

Complexity of some cutting plane methods that use analytic centers

0.00 Avg rating0 Votes
Article ID: iaor1998380
Country: Netherlands
Volume: 74
Issue: 1
Start Page Number: 47
End Page Number: 54
Publication Date: Jul 1996
Journal: Mathematical Programming
Authors:
Keywords: programming: mathematical
Abstract:

We consider cutting plane methods for minimizing a convex (possibly nondifferentiable) function subject to box constraints. At each iteration, accumulated subgradient cuts define a polytope that localizes the minimum. The objective and its subgradient are evaluated at the analytic center of this polytope to produce one or two cuts that improve the localizing set. We give complexity estimates for several variants of such methods. Our analysis is based on the works of Goffin, Luo and Ye.

Reviews

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