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?