Dynamic bundle methods

Published

Journal Article

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. © 2008 Springer-Verlag.

Full Text

Duke Authors

Cited Authors

  • Belloni, A; Sagastizábal, C

Published Date

  • September 1, 2009

Published In

Volume / Issue

  • 120 / 2

Start / End Page

  • 289 - 311

Electronic International Standard Serial Number (EISSN)

  • 1436-4646

International Standard Serial Number (ISSN)

  • 0025-5610

Digital Object Identifier (DOI)

  • 10.1007/s10107-008-0215-z

Citation Source

  • Scopus