Generalized Lagrange multiplier method

From Glossary

Jump to: navigation, search

The Generalized Lagrange Multiplier method (GLM) solves a sequence of Lagrangian optimization (relaxation) problems, searching the multiplier space by some method to seek a minimum of the maximum Lagrangian function.

  1. Given LaTeX: (u, v) with LaTeX: u \ge 0, find LaTeX: x \in \arg\!\max \{f(x) - u^T g(x) - v^T h(x) : x \in X\} = L^*(u,v).
  2. Test if 0 is in the convex hull of LaTeX: S(x, u, v) := \{(b, c): g(x) \le b, \; h(x) = c,\; u^T g(x) =u^T b\}. If so, stop (LaTeX: x solves the original mathematical program if 0 is in LaTeX: S(x, u, v); otherwise, search alternative optima; if no maximum generates 0 as a member of LaTeX: S, then the right-hand side (0) is in a duality gap).
  3. Given LaTeX: (x, u, v), choose LaTeX: (u', v') to reduce the value of LaTeX: L^*(u, v).

This can be viewed from several vantages:

Personal tools