# Bundle method

### From Glossary

A class of nonsmooth-optimization methods for the numerical minimization of a
convex function, . At the
th iteration the technique uses the available
information contained in a *bundle* that is
obtained from an oracle; here each is a
subgradient of at
.

Important applications are Lagrangian relaxation and
column generation applied to a *primal* problem

In this context, for a given ,

results from the maximization of the Lagrange function; each
is , with maximizing
the Lagrangian at .
Minimizing is the *dual* problem.

If minimizing , a basic method to construct the next iterate uses the cutting-plane paradigm: one minimizes the piecewise-linear function

which can be viewed as a model of (in fact
). Minimizing
is a linear program, which is called the restricted
master program in the context of column generation. One of the deficiencies
of this method is *instability* -i.e. the sequence usually
oscillates uncontrollably. Several possibilities exist to stabilize
the process; one, adopted in the bundle approach, replaces the
minimization of by the quadratic program

Here the positive is a *stability parameter* that is usually
adjusted at each iteration, and the *stability center* is