Complexity of some cutting plane methods that use analytic centers |
| |
Authors: | Krzysztof C. Kiwiel |
| |
Affiliation: | (1) Systems Research Institute, Polish Academy of Sciences, Newelska 6, 01-447 Warsaw, Poland |
| |
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. Research supported by the State Committee for Scientific Research under Grant 8S50502206. |
| |
Keywords: | Nondifferentiable optimization Cutting plane methods Analytic center Potential function |
本文献已被 SpringerLink 等数据库收录! |
|