Dynamic Bundle Methods

Alexandre Belloni (bellonimit.edu)
Claudia Sagastizábal (sagastizimpa.br)

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 show finite termination for polyhedral problems.

Keywords: Bundle Methods; Lagrangian Relaxation; Relax and Cut;

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Operations Research Center Working Paper 370-04

Download: [PDF]

Entry Submitted: 08/05/2004
Entry Accepted: 08/05/2004
Entry Last Modified: 03/16/2007

Modify/Update this entry