An optimal variant of Kelley's cutting-plane method

作者：Drori Yoel; Teboulle Marc^*

来源：Mathematical Programming, 2016, 160(1-2): 321-351.

DOI：10.1007/s10107-016-0985-7

• Nonsmooth convex optimization
• Kelley's cutting-plane method
• Bundle and subgradient methods
• Duality
• Complexity
• Rate of convergence

We propose a new variant of Kelley's cutting-plane method for minimizing a nonsmooth convex Lipschitz-continuous function over the Euclidean space. We derive the method through a constructive approach and prove that it attains the optimal rate of convergence for this class of problems.

• 出版日期2016-11