# Generalized Lagrange multiplier method

### From Glossary

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.

- Given with , find .
- Test if 0 is in the convex hull of
.
If so, stop ( solves the original mathematical program if 0 is in
; otherwise, search alternative optima; if no maximum
*generates*0 as a member of , then the right-hand side (0) is in a duality gap). - Given , choose to reduce the value of .

- Column generation – maximizing the Lagrangian generates a column in the primal of the randomized program.
- Cutting plane – maximizing the Lagrangian generates a cutting plane in the dual of the randomized program.
- Dantzig-Wolfe decomposition – the master problem is the randomized program; the subproblem is maximizing the Lagrangian.
- Lagrangian duality – GLM solves the Lagrangian dual; (a duality gap occurs when there is no optimal pure strategy in the randomized program).
- Randomized program – This is what GLM solves, and a mixed strategy could have meaning in an application.