1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear programming - convex analysis

  1. Feb 28, 2014 #1
    1. The problem statement, all variables and given/known data
    Given 2 problems:
    (P1) min min(##x_1,x_2##)
    s.t ##x_1, x_2 \geq 0##

    (P2) min t
    s.t ##t \leq x_1##
    ##t \leq x_2##
    ##x_1, x_2 \geq 0##

    (i) Is the mapping f(##x_1,x_2##)=min(##x_1,x_2##) convex?
    (ii) What are the objectives of (P1) and (P2)?

    2. Relevant equations



    3. The attempt at a solution
    Assume f is indeed convex, then I have to prove the following:
    For every ##(x_1,x_2), (y_1,y_2) \in \mathrm{R}^2##, and ##0 \leq \lambda \leq 1## ,
    ##f(\lambda(x_1,x_2)+(1-\lambda)(y_1,y_2)) \leq \lambda f(x_1,x_2) + (1-\lambda) f(y_1,y_2)## .
    But how can I proceed from here?
    Any help would be much appreciated, thanks!
     
  2. jcsd
  3. Mar 1, 2014 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Start by trying to draw (or at least understand) a plot of z = f(x1,x2). Do not assume anything; gather the facts first.
     
  4. Mar 1, 2014 #3
    Thanks, actually I had tried to plot f(x1,x2) in the first place but with no success, mainly due to the fact that f involves both x1 and x2. I know, however, how to plot f when it involves only x1 (or x2), for example f(x1)=max(2x1,-x1).

    Btw, I've just given it another try after seeing your reply, this time I resort to WolframAlpha as I couldn't find a way to visualize it in R^2: http://www.wolframalpha.com/input/?i=plot+min(x,y) and judging by the graph, the function is indeed concave.

    Then I've tried another tool called GraphToy at http://www.iquilezles.org/apps/graphtoy/ and voila, the plot is totally different from that produced by WolframAlpha, though it still represents a concave function. The graph is nice as it lies completely in R^2 but I don't know how it's drawn. Interestingly, it looks identical to that of f=min(x,0), and the graphs of f=min(x,2y) or f=min(x,3y) are nothing but the same as f=min(x,y).
     
  5. Mar 1, 2014 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    "Niceness" is not a necessary property of a graph; correctness is better. It sounds as if you should abandon GraphToy as not worth using.

    So, now that you think the function is concave, you can set about proving it. (Aren't you glad you did not waste a lot of time trying to prove it is convex?)
     
  6. Mar 2, 2014 #5
    Yeah, it's a real time-saver. Btw, I think a simple counter-example will do but here's how the proof goes: (Please tell me if it needs any correction!)
    $$f(\lambda(x_1,x_2)+(1-\lambda)(y_1,y_2))=f(\lambda x_1+(1-\lambda) y_1,\lambda x_1+(1-\lambda) y_1)\\
    =\mathrm{min}(\lambda x_1+(1-\lambda) y_1,\lambda x_2+(1-\lambda) y_2)\\
    \geq \mathrm{min}(\lambda x_1,\lambda x_2) + \mathrm{min}((1-\lambda) y_1, (1-\lambda) y_2)\\
    =\lambda \mathrm{min}(x_1,x_2) + (1-\lambda) \mathrm{min}(y_1,y_2)\\
    =\lambda f(x_1,x_2) + (1-\lambda) f(y_1,y_2).$$
     
  7. Mar 2, 2014 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    It looks OK. A somewhat different (if longer) approach that I, personally, prefer is:
    (1) Note that ##\min(x_1,x_2) = x_1 + \min(x_2-x_1,0)##---easy to show and almost obvious.
    (2) The single-variable function ##m(t) = \min(t,0)## is concave in ##t##---easy to prove and obvious graphically.
    (3) Since ##m(.)## concave, any function of the form ##m(ax_1 + bx_2)## is a concave function of ##(x_1,x_2)## --- a standard result that is quite easy to prove, and should be part of the toolkit of everybody who uses convexity/concavity.
    (4) Since the functions ##f_1(x_1,x_2) = x_1## and ##f_2(x_1,x_2) = m(x_2-x_1)## are concave in ##(x_1,x_2)##, so is their sum. Again, a standard result.

    Finally, you need to find a pair ##(x_1,x_2)## and a ##\lambda \in (0,1)## that makes the inequality strict, just so that you can eliminate the possibility of convexity. (For example, the linear function satisfies both types of inequalities as equalities; it is both convex and concave. You want to eliminate that possibility for your function.)
     
    Last edited: Mar 2, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Linear programming - convex analysis
  1. Linear programming (Replies: 2)

  2. Linear Programming (Replies: 10)

  3. Linear programming (Replies: 2)

  4. Linear Programming (Replies: 0)

  5. Linear Programming (Replies: 0)

Loading...