In the field of mathematical optimization, Lagrangian relaxation is a relaxation method which approximates

Approximation theory

In mathematics, approximation theory is concerned with how functions can best be approximated with simpler functions, and with quantitatively characterizing the errors introduced thereby...

 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.

The method penalizes violations of inequality constraints using a Lagrangian multiplier, which imposes a cost on violations. When the Lagrangian multiplier is nonnegative and nonzero, some inequality constraint can be violated. In practice, the Lagrangian relaxed problem can 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

Dual problem

In constrained optimization, it is often possible to convert the primal problem to a dual form, which is termed a dual problem. Usually dual problem refers to the Lagrangian dual problem but other dual problems are used, for example, the Wolfe dual problem and the Fenchel dual problem...

.

Mathematical description

Given a linear programming problem and of the following form:

max
s.t.

If we split the constraints in such that ,
and we may write the system:

max
s.t.
(1)
(2)

We may introduce the constraint (2) into the objective:

max
s.t.
(1)

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.

The LR solution as a bound

Of particular use is the property that for any fixed set of values, the optimal result to the Lagrangian Relaxation problem will be no smaller than the optimal result to the original problem. To see this, let be the optimal solution to the original problem, and let be the optimal solution to the Lagrangian Relaxation. We can then see that

The first inequality is true because is feasible in the original problem and the second inequality is true because is the optimal solution to the Lagrangian Relaxation.

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

min

s.t.

where we define as

max
s.t.
(1)

A Lagrangian Relaxation algorithm thus proceeds to explore the range of feasible values while seeking to minimize the result returned by the inner problem. Each value returned by is a candidate upper bound to the problem, the smallest of which is kept as the best upper bound. If we additionally employ a heuristic, probably seeded by the values returned by , 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.

Books

• Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. ISBN 1-886529-00-0.||unused_data=authorlink2=Claude Lemaréchal}}||unused_data=authorlink2=Claude Lemaréchal}} )}}