Lagrangian relaxation

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.Suppose we are given a linear programming problem, with x ∈ R n {displaystyle xin mathbb {R} ^{n}}   and A ∈ R m , n {displaystyle Ain mathbb {R} ^{m,n}}  , of the following form:Of particular use is the property that for any fixed set of λ ~ {displaystyle { ilde {lambda }}}   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 x ^ {displaystyle {hat {x}}}   be the optimal solution to the original problem, and let x ¯ {displaystyle {ar {x}}}   be the optimal solution to the Lagrangian relaxation. We can then see that 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 problemThe augmented Lagrangian method is quite similar in spirit to the Lagrangian relaxation method, but adds an extra term, and updates the dual parameters λ {displaystyle lambda }   in a more principled manner. It was introduced in the 1970s and has been used extensively.