Thread: Proving Concavity

For each

b inRm, let ξ(b) denote the optimal objective function value for
the following linear program:

maximize c' x

subject to

Ax ≤ b
x ≥ 0.

Suppose that

ξ(b) < ∞ for all b. Show that the function ξ(b) is concave (a
function f on Rm is called concave if f(tx+(1−t)y) ≥ tf (x)+(1−t)f(y)

for all x and y in Rm and all 0 < t < 1). Hint: Consider the dual problem.


Isn't there only one objective value? Not one for each b value?

I'm not sure I understand your question. You have a seperate linear programming problem for each choice of . Since the constraint is changing with you may conceivably get a different optimal value.

Thanks for the answer. I was confused about what b was. For some reason I was thinking it was a vector. But I still am unsure about how to prove this.

Well, is a vector, as you can see from the first line of the problem.

To go about proving it, start with the hint. What's the dual problem?

I think the dual is given by

min b'y
st A'y >=c
y>=0

That looks correct. I'm assuming that this question came from Vanderbei's book on Linear Programming. It's given at the end of section 10 which is on convexity analysis. My guess is that the concavity of the optimal value function for the primal prioblem is equivalent to the convexity of the optimal value function for the dual problem. So, how are the optimal values of these two problems related?

Yup, that's the book. According to the Strong Duality Thm, the two values are the same.

That's right. Therefore is the optimal value for the dual problem



Now, what can you say about ? This is the minimum of for 's lying in some fixed region.

By the way, forget my earlier remark concerning convex functions; it's not correct.

Sorry, I'm not sure what we can say about that. I know if the region is convex, that function will be entirely contained in the region.

Think in terms of properties of the minimum (or infimum). I.e., what can you say in general about

?

Sorry I don't know how to use Latex!
I can say min(f + g) >= min(f) + min(g).

That's correct. So apply that fact to .