Abstract
The last few years have seen the advent of a new generation of bundle methods, capable to handle inexact oracles, polluted by “noise”. Proving convergence of a bundle method is never simple and coping with inexact oracles substantially increases the technicalities. Besides, several variants exist to deal with noise, each one needing an ad hoc proof to show convergence. We state a synthetic convergence theory, in which we highlight the main arguments and specify which assumption is used to establish each intermediate result. The framework is comprehensive and generalizes in various ways a number of algorithms proposed in the literature. Based on the ingredients of our synthetic theory, we consider various bundle methods adapted to oracles for which high accuracy is possible, yet it is preferable not to make exact calculations often, because they are too time consuming.
Similar content being viewed by others
References
BenAmor, M.T., Desrosiers, J., Frangioni, A.: On the choice of explicit stabilizing terms in column generation. Discret. Appl. Math. 157(6), 1167–1184 (2009)
Cheney, E., Goldstein, A.: Newton’s method for convex programming and Tchebycheff approximations. Numer. Math. 1, 253–268 (1959)
Correa, R., Lemaréchal, C.: Convergence of some algorithms for convex minimization. Math. Program. 62(2), 261–275 (1993)
de Oliveira, W., Sagastizábal, C.: Level bundle methods for oracles with on-demand accuracy. Optim. Methods Softw. 29(6), 1180–1209 (2014). doi:10.1080/10556788.2013.871282
Émiel, G., Sagastizábal, C.: Incremental-like bundle methods with application to energy planning (corrigendum). Optimization Online Report 2147 (2009)
Émiel, G., Sagastizábal, C.: Incremental-like bundle methods with application to energy planning. Comput. Opt. Appl. 46(2), 305–332 (2010)
Frangioni, A.: Generalized bundle methods. SIAM J. Optim. 13(1), 117–156 (2003)
Frangioni, A.: Private communication (2008)
Gaudioso, M., Giallombardo, G., Miglionico, G.: An incremental method for solving convex finite min–max problems. Math. Oper. Res. 31(1), 173–187 (2006)
Goffin, J.-L., Haurie, A., Vial, J-Ph: Decomposition and nondifferentiable optimization with the projective algorithm. Manag. Sci. 38(2), 284–302 (1992)
Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3), 673–696 (2000)
Hintermüller, M.: A proximal bundle method based on approximate subgradients. Comput. Optim. Appl. 20(3), 245–266 (2001). doi:10.1023/A:1011259017643
Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, Heidelberg (1993). (Two volumes)
Kelley, J.E.: The cutting plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8, 703–712 (1960)
Kiwiel, K.C.: A proximal bundle method with approximate subgradient linearizations. SIAM J. Optim. 16(4), 1007–1023 (2006)
Kiwiel, K.C.: Bundle Methods for Convex Minimization with Partially Inexact Oracles. Technical Report, Systems Research Institute, Polish Academy of Sciences (April 2010)
Marsten, R.E., Hogan, W.W., Blankenship, J.W.: The boxstep method for large-scale optimization. Oper. Res. 23(3), 389–405 (1975)
Oustry, F.: A second-order bundle method to minimize the maximum eigenvalue function. Math. Program. 89(1), 1–33 (2000)
Sagastizábal, C.: Composite proximal bundle method. Math. Program. 140(1), 189–233 (2013)
Solodov, M.V.: On approximations with finite precision in bundle methods for nonsmooth optimization. J. Opt. Theory Appl. 119(1), 151–165 (2003)
van Ackooij, W., Sagastizábal, C.: Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems. SIAM J. Optim. 24(2), 733–765 (2014)
Acknowledgments
Research partly done during a postdoctoral visit of the first author at Inria. The authors are grateful to the reviewers for many insightful comments.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
de Oliveira, W., Sagastizábal, C. & Lemaréchal, C. Convex proximal bundle methods in depth: a unified analysis for inexact oracles. Math. Program. 148, 241–277 (2014). https://doi.org/10.1007/s10107-014-0809-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-014-0809-6