Skip to main content
Springer Nature Link
Log in

Dynamic bundle methods

  • FULL LENGTH PAPER
  • Published:
Mathematical Programming Submit manuscript

Abstract

Lagrangian relaxation is a popular technique to solve difficult optimization problems. However, the applicability of this technique depends on having a relatively low number of hard constraints to dualize. When there are many hard constraints, it may be preferable to relax them dynamically, according to some rule depending on which multipliers are active. From the dual point of view, this approach yields multipliers with varying dimensions and a dual objective function that changes along iterations. We discuss how to apply a bundle methodology to solve this kind of dual problems. Our framework covers many separation procedures to generate inequalities that can be found in the literature, including (but not limited to) the most violated inequality. We analyze the resulting dynamic bundle method giving a positive answer for its primal-dual convergence properties, and, under suitable conditions, show finite termination for polyhedral problems.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Auslender, A.: How to deal with the unbounded in optimization: Theory and algorithms. Math. Program. 79, 3–18 (1997)

    MathSciNet  Google Scholar 

  2. Barahona, F., Anbil, R.: The volume algorithm: producing primal solutions with a subgradient method. Math. Program. 87(3, Ser. A), 385–399 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  3. Balas, E., Christofides, N.: A restricted Lagrangian approach to the traveling salesman problem. Math. Program. 21(1), 19–46 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  4. Babonneau, F., du Merle, O., Vial, J.-P.: Solving large scale linear multicommodity flow problems with an active set strategy and Proximal-ACCPM. Oper. Res. 54(1), 184–197 (2006)

    Article  MathSciNet  Google Scholar 

  5. Beasley, J.E.: A Lagrangian heuristic for set-covering problems. Naval Res. Logist. 37(1), 151–164 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  6. Bonnans, J.F., Gilbert, J.Ch., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization. Theoretical and Practical Aspects, 2nd edn, p. xiv+490. Universitext. Springer, Berlin (2006)

  7. Belloni, A., Lucena, A.: Improving on the help and karp bound for the STSP via Lagrangian relaxation. Working paper (2002)

  8. Bahiense, L., Maculan, N., Sagastizábal, C.: The volume algorithm revisited. Relation with bundle methods. Math. Program. Ser. A 94(1), 41–69 (2002)

    Article  MATH  Google Scholar 

  9. Belloni, A., Sagastizábal, C.: Numerical assessment of dynamic dual methods (In preparation)

  10. Christofides, N., Beasley, J.E.: Extensions to a lagrangean relaxation approach for the capacitated warehouse location problem. Eur. J. Oper. Res. 12(1), 19–28 (1983)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  12. Escudero, L.F., Guignard, M., Malik, K.: A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships. Ann. Oper. Res. 50, 219–237 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  13. Ermol′ev, Ju.M.: Method for solving nonlinear extremal problems. Kibernetika (Kiev) 2(4), 1–17 (1966)

    MathSciNet  Google Scholar 

  14. Frangioni, A., Gallo, G.: A bundle type dual-ascent approach to linear multicommodity min cost flow problems. INFORMS J. Comput. 11(4), 370–393 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  15. Fischer, I., Gruber, G., Rendl, F., Sotirov, R.: Computational experience with a bundle approach for semidefinite cutting plane relaxations of max-cut and equipartition. Math. Program. 105(2–3, Ser. B), 451–469 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  16. Frangioni, A., Lodi, A., Rinaldi, G.: New approaches for optimizing over the semimetric polytope. Math. Program. 104(2–3, Ser. B), 375–388 (2006)

    MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  18. Gavish, B.: Augmented Lagrangian based algorithms for centralized network design. IEEE Trans. Commun. 33, 1247–1257 (1985)

    Article  MathSciNet  Google Scholar 

  19. Grötschel, M., Jünger, M., Reinelt, G.: A cutting plane algorithm for the linear ordering problem. Oper. Res. 32(6), 1195–1220 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  20. Helmberg, C.: A cutting plane algorithm for large scale semidefinite relaxations. The sharpest cut, pp. 233–256, MPS/SIAM Ser. Optim., SIAM, Philadelphia (2004)

  21. Hunting, M., Faigle, U., Kern, W.: A Lagrangian relaxation approach to the edge-weighted clique problem. Eur. J. Oper. Res. 131(1), 119–131 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  22. Helmberg, C., Kiwiel, K.C.: A spectral bundle method with bounds. Math. Program. 23(2, Ser. A), 173–194 (2002)

    Article  MathSciNet  Google Scholar 

  23. Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Number 305-306 in Grund. der math. Wiss. Springer, Heidelberg (1993) (two volumes)

  24. Held, M., Wolfe, Ph., Crowder, H.P.: Validation of subgradient optimization. Math. Program. 6, 62–88 (1974)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  26. Kiwiel, K.C.: Methods of Descent for Non-Differentiable Optimization. Springer, Berlin (1985)

    Google Scholar 

  27. Kiwiel, K.C.: Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization. Math. Program. 52(2, Ser. B), 285–302 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  28. Kiwiel, K.C.: Approximations in proximal bundle methods and decomposition of convex programs. J. Optim. Theory Appl. 84, 529–548 (1995)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  30. Lucena, A., Beasley, J.E.: Branch and cut algorithms. In: Advances in Linear and Integer Programming, Oxford Lecture Ser. Math. Appl., vol.4, pp. 187–221. Oxford University Press, New York (1996)

  31. Lemaréchal, C., Nemirovskii, A., Nesterov, Yu.: New variants of bundle methods. Math. Program. 69, 111–148 (1995)

    Article  Google Scholar 

  32. Lucena, A.: Steiner problem in graphs: Lagrangean relaxation and cutting-planes. COAL Bull. 21(2), 2–8 (1992)

    Google Scholar 

  33. Lukšan, L., Vlček, J.: A bundle-Newton method for nonsmooth unconstrained minimization. Math. Program. 83(3, Ser. A), 373–391 (1998)

    Article  MATH  Google Scholar 

  34. Lukšan, L., Vlček, J.: Globally convergent variable metric method for convex nonsmooth unconstrained minimization. J. Optim. Theory Appl. 102(3), 593–613 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  35. Lukšan, L., Vlček, J.: NDA: Algorithms for nondifferentiable optimization. Technical report, Institute of Computer Science, Academy of Sciences of the Czech Republic (2000)

  36. Ruszczynski, A., Shapiro, A. (eds.): Stochastic Programming. In: Handbooks in Operations Research and Management Science, vol.10. Elsevier Science, Amsterdam (2003)

  37. Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Math. Program. 109(2/3, Ser.B), 505–524 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  38. Shor, N.: Minimization Methods for Non-Differentiable Functions. Springer, Berlin (1985)

    MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  40. Schramm, H., Zowe, J.: A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results. SIAM J. Optim. 2(1), 121–152 (1992)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Fuqua School of Business, Duke University, 1 Towerview Dr, PO Box 90120, Durham, NC, 27708, USA

    Alexandre Belloni

  2. CEPEL, Electric Energy Research Center, Rio de Janeiro, RJ, Brazil

    Claudia Sagastizábal

  3. IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, 22460-320, Brazil

    Claudia Sagastizábal

Authors
  1. Alexandre Belloni
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Claudia Sagastizábal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Claudia Sagastizábal.

Additional information

Claudia Sagastizábal is on leave from INRIA Rocquencourt, France.

Research supported by CNPq Grant No.303540-03/6.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Belloni, A., Sagastizábal, C. Dynamic bundle methods. Math. Program. 120, 289–311 (2009). https://doi.org/10.1007/s10107-008-0215-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-008-0215-z

Mathematics Subject Classification (2000)

Search

Navigation