# Linear programming - convex analysis

• drawar
In summary: Thanks for the detailed explanation, the last part is also very informative, I had not thought about it.
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)?

## 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!

drawar said:

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

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

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

drawar said:
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?)

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

drawar said:
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.)

Last edited:
1 person

## 1. What is linear programming?

Linear programming is a mathematical technique used to find the optimal solution to a problem with linear constraints. It involves maximizing or minimizing a linear objective function while satisfying a set of linear constraints.

## 2. What is convex analysis?

Convex analysis is a branch of mathematics that deals with the study of convex functions and their properties. It involves the analysis of convex sets, convex functions, and their applications in optimization problems.

## 3. How are linear programming and convex analysis related?

Linear programming uses convex analysis to determine the optimal solution to a problem with linear constraints. The objective function and constraints in linear programming must be convex in order for the solution to be optimal.

## 4. What are some real-world applications of linear programming and convex analysis?

Linear programming and convex analysis have a wide range of applications in various fields such as economics, finance, engineering, and operations research. Some examples include production planning, resource allocation, portfolio optimization, and transportation planning.

## 5. What are the limitations of linear programming?

Linear programming is limited to solving problems with linear constraints and a linear objective function. It also assumes that the relationships between variables are known and do not change over time. Additionally, it may not be suitable for complex problems with a large number of variables and constraints.

Replies
3
Views
4K
Replies
6
Views
982
Replies
6
Views
1K
Replies
4
Views
1K
Replies
1
Views
2K
Replies
1
Views
1K
Replies
22
Views
2K
Replies
17
Views
1K
Replies
2
Views
679
Replies
9
Views
2K