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: | Kiwiel Krzysztof C. |
Keywords: | programming: mathematical |
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.