Rate of Convergence of the Bundle Method

Abstract

We prove that the bundle method for nonsmooth optimization achieves solution accuracy $\epsilon$ in at most $\mathcal{O}(\ln (1/\epsilon )/\epsilon )$ iterations, if the function is strongly convex. The result is true for the versions of the method with multiple cuts and with cut aggregation.

arXiv commentarXiv admin note: text overlap with arXiv:1511.01716