Bundle method

A class of nonsmooth-optimization methods for the numerical minimization of a convex function, $LaTeX: \theta : \mathbb{R}^n \rightarrow \mathbb{R}$. At the $LaTeX: k$th iteration the technique uses the available information contained in a bundle $LaTeX: (\theta(v^1), g_1, \ldots , \theta(v^k), g_k)$ that is obtained from an oracle; here each $LaTeX: g_i$ is a subgradient of $LaTeX: \theta$ at $LaTeX: v^i$.

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

$LaTeX: \max \{ p(x) : x \in X, \; h(x) = 0 \}.$

In this context, for a given $LaTeX: v \in \mathbb{R}n$,

$LaTeX: \theta(u) = \max \{ p(x) - v^T h(x) : x \in X \}$

results from the maximization of the Lagrange function; each $LaTeX: g_i$ is $LaTeX: -h(x_i)$, with $LaTeX: x^i$ maximizing the Lagrangian at $LaTeX: v^i$. Minimizing $LaTeX: \theta$ is the dual problem.

If minimizing $LaTeX: \theta(v)$, a basic method to construct the next iterate $LaTeX: v^{k+1}$ uses the cutting-plane paradigm: one minimizes the piecewise-linear function

$LaTeX: \theta_k(v) = \max \{ \theta (v^i) + g_i^T (v - v^i) : i = 1, ... ,k \},$

which can be viewed as a model of $LaTeX: \theta$ (in fact $LaTeX: \theta_k \le \theta$). Minimizing $LaTeX: \theta_k$ 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 $LaTeX: v^k$ usually oscillates uncontrollably. Several possibilities exist to stabilize the process; one, adopted in the bundle approach, replaces the minimization of $LaTeX: \theta_k$ by the quadratic program

$LaTeX: \min_v \{ \theta_k(v) + (1/(2t)) |v - C|^2 \}.$

Here the positive $LaTeX: t$ is a stability parameter that is usually adjusted at each iteration, and the stability center $LaTeX: C$ is

some $LaTeX: v^i$ ($LaTeX: i \le k$) taken from the bundle, typically one that gave the best $LaTeX: \theta$-value.