Results 1 to 12 of 12

Math Help - Proving Concavity

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    225

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    May 2010
    From
    Los Angeles, California
    Posts
    274
    Thanks
    1
    I'm not sure I understand your question. You have a seperate linear programming problem for each choice of b. Since the constraint is changing with b you may conceivably get a different optimal value.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2008
    Posts
    225
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    May 2010
    From
    Los Angeles, California
    Posts
    274
    Thanks
    1
    Well, b 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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2008
    Posts
    225
    I think the dual is given by

    min b'y
    st A'y >=c
    y>=0
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    May 2010
    From
    Los Angeles, California
    Posts
    274
    Thanks
    1
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2008
    Posts
    225
    Yup, that's the book. According to the Strong Duality Thm, the two values are the same.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    May 2010
    From
    Los Angeles, California
    Posts
    274
    Thanks
    1
    That's right. Therefore \xi^*(b) is the optimal value for the dual problem

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

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

    By the way, forget my earlier remark concerning convex functions; it's not correct.
    Last edited by ojones; May 28th 2011 at 06:39 PM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Aug 2008
    Posts
    225
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    May 2010
    From
    Los Angeles, California
    Posts
    274
    Thanks
    1
    Think in terms of properties of the minimum (or infimum). I.e., what can you say in general about

    \text{min}_{y\in D}[f(y)+g(y)]?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Aug 2008
    Posts
    225
    Sorry I don't know how to use Latex!
    I can say min(f + g) >= min(f) + min(g).
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    May 2010
    From
    Los Angeles, California
    Posts
    274
    Thanks
    1
    That's correct. So apply that fact to \xi^*(tb_1+(1-t)b_2)=\text{min} \, (tb_1+(1-t)b_2)^Ty .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving concavity of a 2 variable function
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: February 25th 2011, 03:42 PM
  2. Concavity
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 4th 2009, 03:49 PM
  3. concavity
    Posted in the Calculus Forum
    Replies: 7
    Last Post: March 13th 2008, 05:56 PM
  4. concavity
    Posted in the Calculus Forum
    Replies: 3
    Last Post: November 24th 2007, 03:49 PM
  5. a bit of concavity
    Posted in the Calculus Forum
    Replies: 3
    Last Post: September 24th 2007, 10:33 PM

Search Tags


/mathhelpforum @mathhelpforum