Linear programming - convex analysis

[drawar]

Homework Statement

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)?

Homework Equations

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!

 

[Ray Vickson]

Homework Statement

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)?

Homework Equations

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!

Start by trying to draw (or at least understand) a plot of z = f(x1,x2). Do not assume anything; gather the facts first.

 

[drawar]

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).

 

[Ray Vickson]

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).

"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?)

 

[drawar]

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).$$

 

[Ray Vickson]

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).$$

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.)