Skip to main content
Log in

Convex proximal bundle methods in depth: a unified analysis for inexact oracles

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. 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)

    Article  MathSciNet  Google Scholar 

  2. Cheney, E., Goldstein, A.: Newton’s method for convex programming and Tchebycheff approximations. Numer. Math. 1, 253–268 (1959)

    Article  MATH  MathSciNet  Google Scholar 

  3. Correa, R., Lemaréchal, C.: Convergence of some algorithms for convex minimization. Math. Program. 62(2), 261–275 (1993)

    Article  MATH  Google Scholar 

  4. 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

  5. Émiel, G., Sagastizábal, C.: Incremental-like bundle methods with application to energy planning (corrigendum). Optimization Online Report 2147 (2009)

  6. Émiel, G., Sagastizábal, C.: Incremental-like bundle methods with application to energy planning. Comput. Opt. Appl. 46(2), 305–332 (2010)

    Article  MATH  Google Scholar 

  7. Frangioni, A.: Generalized bundle methods. SIAM J. Optim. 13(1), 117–156 (2003)

    Article  MathSciNet  Google Scholar 

  8. Frangioni, A.: Private communication (2008)

  9. Gaudioso, M., Giallombardo, G., Miglionico, G.: An incremental method for solving convex finite min–max problems. Math. Oper. Res. 31(1), 173–187 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  10. Goffin, J.-L., Haurie, A., Vial, J-Ph: Decomposition and nondifferentiable optimization with the projective algorithm. Manag. Sci. 38(2), 284–302 (1992)

    Article  MATH  Google Scholar 

  11. Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3), 673–696 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  12. Hintermüller, M.: A proximal bundle method based on approximate subgradients. Comput. Optim. Appl. 20(3), 245–266 (2001). doi:10.1023/A:1011259017643

    Article  MATH  MathSciNet  Google Scholar 

  13. Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, Heidelberg (1993). (Two volumes)

    Google Scholar 

  14. Kelley, J.E.: The cutting plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8, 703–712 (1960)

    Article  MathSciNet  Google Scholar 

  15. Kiwiel, K.C.: A proximal bundle method with approximate subgradient linearizations. SIAM J. Optim. 16(4), 1007–1023 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  16. Kiwiel, K.C.: Bundle Methods for Convex Minimization with Partially Inexact Oracles. Technical Report, Systems Research Institute, Polish Academy of Sciences (April 2010)

  17. Marsten, R.E., Hogan, W.W., Blankenship, J.W.: The boxstep method for large-scale optimization. Oper. Res. 23(3), 389–405 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  18. Oustry, F.: A second-order bundle method to minimize the maximum eigenvalue function. Math. Program. 89(1), 1–33 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  19. Sagastizábal, C.: Composite proximal bundle method. Math. Program. 140(1), 189–233 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  20. Solodov, M.V.: On approximations with finite precision in bundle methods for nonsmooth optimization. J. Opt. Theory Appl. 119(1), 151–165 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  21. 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)

    Article  MATH  MathSciNet  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to C. Sagastizábal.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-014-0809-6

Mathematics Subject Classification

Navigation