In the field of mathematical optimization, Lagrangian relaxation is a relaxation method which approximates a difficult problem of constrained optimization by a simpler problem. A solution to the relaxed problem is an approximate solution to the original problem, and provides useful information.
Contents
- Mathematical description
- The LR solution as a bound
- Iterating towards a solution of the original problem
- Related methods
- References
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. In practice, this relaxed problem can often be solved more easily than the original problem.
The problem of maximizing the Lagrangian function of the dual variables (the Lagrangian multipliers) is the Lagrangian dual problem.
Mathematical description
Given a linear programming problem
If we split the constraints in
We may introduce the constraint (2) into the objective:
If we let
The LR solution as a bound
Of particular use is the property that for any fixed set of
The first inequality is true because
Iterating towards a solution of the original problem
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. Thus we can address the original problem by instead exploring the partially dualized problem
where we define
A Lagrangian Relaxation algorithm thus proceeds to explore the range of feasible
Related methods
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 doesn't use dual variables but rather removes the constraints and instead penalizes deviations from the constraint. The method is conceptually simple but usually Augmented Lagrangian methods are preferred in practice since the penalty method suffers from ill-conditioning issues.