# Lagrangian Duality in Linear Programming

• May 15th 2011, 11:33 AM
veronicak5678
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)

• May 16th 2011, 01:05 PM
Ackbeet
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]?$
• May 16th 2011, 03:46 PM
veronicak5678
I am fairly certain it is the first way.
• May 16th 2011, 05:41 PM
Ackbeet
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?
• May 16th 2011, 05:58 PM
veronicak5678
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?
• May 17th 2011, 01:56 AM
Ackbeet
That's what I would say. The outside operation would only affect your answer if the result of the inner brackets depended on x.
• May 17th 2011, 12:27 PM
veronicak5678
Got it. Thanks for your help!
• May 17th 2011, 12:42 PM
Ackbeet
You're welcome!