Bundle method

From Glossary

Jump to: navigation, search

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: kth 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

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

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

\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

\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

\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.

Personal tools