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.
The method penalizes violations of inequality constraints using a Lagrangian 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.
Read more about Lagrangian Relaxation: Mathematical Description, The LR Solution As A Bound, Iterating Towards A Solution of The Original Problem
Famous quotes containing the word relaxation:
“Worst of all, there is no sign of any relaxation of antisemitism. Logically it has nothing to do with Fascism. But the human race is imitative rather than logical; and as Fascism spreads antisemitism spreads.”
—George Bernard Shaw (1856–1950)