Dynamic bundle methods

• 成果类型: Article
• 署名作者: Belloni, Alexandre; Sagastizabal, Claudia
• 署名单位: Duke University; Eletrobras Cepel
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-008-0215-z
• 发表日期: 2009
• 页码: 289-311
• 关键词: nonsmooth unconstrained minimization; cutting plane algorithm; relaxation approach; volume algorithm; convex-programs; flow problems; approximations; optimization; bounds

摘要

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.