Proving Concavity

• May 26th 2011, 01:10 PM
veronicak5678
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+(1t)y) tf (x)+(1t)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?
• May 27th 2011, 04:57 PM
ojones
I'm not sure I understand your question. You have a seperate linear programming problem for each choice of $\displaystyle b$. Since the constraint is changing with $\displaystyle b$ you may conceivably get a different optimal value.
• May 27th 2011, 06:15 PM
veronicak5678
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.
• May 27th 2011, 09:34 PM
ojones
Well, $\displaystyle b$ is a vector, as you can see from the first line of the problem.

• May 28th 2011, 08:44 AM
veronicak5678
I think the dual is given by

min b'y
st A'y >=c
y>=0
• May 28th 2011, 01:46 PM
ojones
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?
• May 28th 2011, 02:06 PM
veronicak5678
Yup, that's the book. According to the Strong Duality Thm, the two values are the same.
• May 28th 2011, 06:19 PM
ojones
That's right. Therefore $\displaystyle \xi^*(b)$ is the optimal value for the dual problem

$\displaystyle$\begin{eqnarray*}\text{min} & b^Ty\\ \text{subject to} & A^Ty\ge c\\&y\ge 0.\end{eqnarray*}

Now, what can you say about $\displaystyle \xi^*(tb_1+(1-t)b_2)$? This is the minimum of $\displaystyle (tb_1+(1-t)b_2)^Ty$ for $\displaystyle y$'s lying in some fixed region.

By the way, forget my earlier remark concerning convex functions; it's not correct.
• May 29th 2011, 02:54 PM
veronicak5678
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.
• May 29th 2011, 03:06 PM
ojones
Think in terms of properties of the minimum (or infimum). I.e., what can you say in general about

$\displaystyle \text{min}_{y\in D}[f(y)+g(y)]$?
• May 29th 2011, 03:53 PM
veronicak5678
Sorry I don't know how to use Latex!
I can say min(f + g) >= min(f) + min(g).
• May 29th 2011, 10:17 PM
ojones
That's correct. So apply that fact to $\displaystyle \xi^*(tb_1+(1-t)b_2)=\text{min} \, (tb_1+(1-t)b_2)^Ty$.