# Lagrangian duality applied to lineair programs

• Jun 7th 2010, 07:26 AM
Arno
Lagrangian duality applied to lineair programs
Hi all,

I'm trying to understand the connection between Lagrangian duality and the dual of a linear program.

Let's say we want to maximize cx, subject to Ax<=b and x >= 0

Now, the lagrangian dual would be:

g(y) = Maximize cx + y(b-Ax) to x, subject to x>=0

Or, after some rearranging:

g(y) = Maximize yb +(c-Ay)x, subject to x >= 0

Obviously, the only solution which is not infinity, is where (c-Ay)<=0
In that case, g(y) = yb, and the optimal x(y) is 0

If we then minimize this lagranguan dual, we actually get the dual of the linear program as expected:

minimize g(y)=by, subject to y>=0 and Ac>=0

However, what I don't understand is that the optimal x(y) of the lagranguan dual function g(y) is 0, because this would mean that the original linear program has its optimum at x=0, which off course is not necessarily the case.

I'm probably forgetting something, and I have the feeling that my confusion has something to do with the fact that only non-basic variables will be zero in the optimal lineair program.

Anyway who can help me out here?

Tnx!
Kind regards,
Varno
• Jun 7th 2010, 07:47 AM
Ackbeet
It seems to me this problem belongs more in the Discrete Math forum, as that's where linear programming usually falls.