# Lagrangian relaxation

### From Glossary

The removal of constraints and putting them into
the objective as in the Lagrangian function.
Specifically, suppose we have

The Lagrangian relaxation is

where ( is unrestricted).

This is a relaxation of the original mathematical program because the constraints have been removed (expanding the feasible region), and for feasible (i.e., satisfying these constraints), the relaxed objective satisfies:

because and

The objective is the usual Lagrangian function when is simply . It provides a foundation for Lagrangian duality and the Generalized Lagrange Multiplier Method.

Note that could retain some constraints, such as in the separable form . Now suppose and Then, the Lagrangian relaxation decomposes into independent mathematical programs for any multiplier value: