In the field of mathematical optimization, Lagrangian relaxation is a relaxation method which approximates a difficult problem of constrained optimization by a simpler problem.
The method penalizes violations of inequality constraints using a Lagrange multiplier, which imposes a cost on violations.
These added costs are used instead of the strict inequality constraints in the optimization.
Suppose we are given a linear programming problem, with
we may write the system: We may introduce the constraint (2) into the objective: If we let
be nonnegative weights, we get penalized if we violate the constraint (2), and we are also rewarded if we satisfy the constraint strictly.
The above system is called the Lagrangian relaxation of our original problem.
values, the optimal result to the Lagrangian relaxation problem will be no smaller than the optimal result to the original problem.
be the optimal solution to the original problem, and let
be the optimal solution to the Lagrangian relaxation.
is feasible in the original problem and the second inequality is true because
is the optimal solution to the Lagrangian relaxation.
The above inequality tells us that if we minimize the maximum value we obtain from the relaxed problem, we obtain a tighter limit on the objective value of our original problem.
as A Lagrangian relaxation algorithm thus proceeds to explore the range of feasible
values while seeking to minimize the result returned by the inner
If we additionally employ a heuristic, probably seeded by the
, to find feasible solutions to the original problem, then we can iterate until the best upper bound and the cost of the best feasible solution converge to a desired tolerance.
The augmented Lagrangian method is quite similar in spirit to the Lagrangian relaxation method, but adds an extra term, and updates the dual parameters
The penalty method does not use dual variables but rather removes the constraints and instead penalizes deviations from the constraint.