Abstract
We give efficiency estimates for proximal bundle methods for finding f*≔minXf, where f and X are convex. We show that, for any accuracy ∈<0, these methods find a point xk∈X such that f(xk)−f*≤∈ after at most k=O(1/∈3) objective and subgradient evaluations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Kiwiel, K. C., Proximity Control in Bundle Methods for Convex Nondifferentiable Minimization, Mathematical Programming, Vol. 46, pp. 105–122, 1990.
Correa, R., and LemareĆhal, C., Convergence of Some Algorithms for Convex Minimization, Mathematical Programming, Vol. 62, pp. 261–275, 1993.
Kiwiel, K. C., Approximations in Proximal Bundle Methods and Decomposition of Convex Programs, Journal of Optimization Theory and Applications, Vol. 84, pp. 529–548, 1995.
Kiwiel, K. C., Restricted Step and Levenberg-Marquardt Techniques in Proximal Bundle Methods for Nonconvex Nondifferentiable Optimization, SIAM Journal on Optimization, Vol. 6, pp. 227–249, 1996.
Schramm, H., and Zowe, J., A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results, SIAM Journal on Optimization, Vol. 2, pp. 121–152, 1992.
Hiriart-Urruty, J. B., and LemareĆhal, C., Convex Analysis and Minimization Algorithms, Springer Verlag, Berlin, Germany, 1993.
Wolfe, P., A Method of Conjugate Subgradients for Minimizing Nondifferentiable Functions, Mathematical Programming Study, Vol. 3, pp. 145–173, 1975.
Kiwiel, K. C., Proximal Level Bundle Methods for Convex Nondifferentiable Optimization, Saddle-Point Problems, and Variational Inequalities, Mathematical Programming, Vol. 69, pp. 89–109, 1995.
Kiwiel, K. C., The Efficiency of Subgradient Projection Methods for Convex Optimization, Part 1: General Level Methods, SIAM Journal on Control and Optimization, Vol. 34, pp. 660–676, 1996.
LemareĆhal, C., Nemirovskii, A. S., and Nesterov, YU, E., New Variants of Bundle Methods, Mathematical Programming, Vol. 69, pp. 111–147, 1995.
Kiwiel, K. C., Efficiency of the Analytic Center Cutting Plane Method for Convex Minimization, SIAM Journal on Optimization, Vol. 7, pp. 336–346, 1997.
Nesterov, YU. E., Complexity Estimates of Some Cutting Plane Methods Based on the Analytic Barrier, Mathematical Programming, Vol. 69, pp. 149–176, 1995.
Kiwiel, K. C., Larsson, T., and Lindberg, P. O., The Efficiency of Ballstep Subgradient Level Methods for Convex Optimization, Mathematics of Operations Research, Vol. 24, pp. 237–254, 1999.
Kiwiel, K. C., A Cholesky Dual Method for Proximal Piecewise Linear Programming, Numerische Mathematik, Vol. 68, pp. 325–340, 1994.
Kiwiel, K. C., Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, Springer Verlag, Berlin, Germany, Vol. 1133, 1985.
Kiwiel, K. C., Rosa, C. H., and RuszczyŃski, A., Proximal Decompositionvia Alternating Linearization, SIAM Journal on Optimization, Vol. 9, pp. 668–689, 1999.
Frangioni, A., Dual Ascent Methods and Multicommodity Flow Problems, PhD Thesis, Dipartimento di Informatica, Universitá di Pisa, Pisa, Italy, 1997.
Nemirovskii, A. S., and Yudin, D. B., Problem Complexity and Method Efficiency in Optimization, Nauka, Moscow, 1979 (in Russian); English Translation by Wiley, New York, NY, 1983.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kiwiel, K.C. Efficiency of Proximal Bundle Methods. Journal of Optimization Theory and Applications 104, 589–603 (2000). https://doi.org/10.1023/A:1004689609425
Issue Date:
DOI: https://doi.org/10.1023/A:1004689609425