Thread: 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

It seems to me this problem belongs more in the Discrete Math forum, as that's where linear programming usually falls.