Thread: Lagrangian Duality in Linear Programming

1. Lagrangian Duality in Linear Programming

For real numbers x and y, compute

max min (x-y) and
(x >=0) (y >=0)

min max (x-y)
(y>=0) (x>=0)

2. Question: for the first problem, e.g., are you doing this:

$\max_{x\ge 0}\left[\min_{y\ge 0}(x-y)\right],$ or this:

$\max_{x\ge 0, y\ge 0}\left[\min_{x\ge 0,y\ge 0}(x-y)\right]?$

3. I am fairly certain it is the first way.

4. Ok. Then let's take the first one. For positive y and any fixed x, the minimum inside the brackets is going to be negative infinity. Taking the maximum of a bunch of negative infinities is just negative infinity. Hence, I'd say the first one is negative infinity.

Using an analogous reasoning method, what do you suppose the second one will be?

5. So for the other, for a fixed y, the inside of the brackets would be positive infinity, then the min of that would still be positive infinity?

6. That's what I would say. The outside operation would only affect your answer if the result of the inner brackets depended on x.

7. Got it. Thanks for your help!

8. You're welcome!