Lagrangian relaxation

From Wikipedia, the free encyclopedia

Lagrangian relaxation is a relaxation technique which works by moving hard constraints into the objective so as to exact a penalty on the objective if they are not satisfied.

[edit] Mathematical description

Given an LP problem x\in \mathbb{R}^n and A\in \mathbb{R}^{m,n} on the following form:


max cTx
s.t.
Ax \le b

If we split the constraints in A such that A_1\in \mathbb{R}^{m_1,n}, A_2\in \mathbb{R}^{m_2,n} and m1 + m2 = m we may write the system:

max cTx
s.t.
(1) A_1 x \le b_1
(2) A_2 x \le b_2

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

max cTx + λT(b2 − A2x)
s.t.
(1) A_1 x \le b_1

If we let \lambda=(\lambda_1,\ldots,\lambda_{m_2}) be nonnegative weights, we get penalized if we violate the constraint (2) on the other hand if we want to maintain a linear objective, we may see that we are rewarded for satisfying the objective strictly. The above system is called the Lagrangian Relaxation of our original problem.

Languages