# Thread: convexity in the euclidean vector space

1. ## convexity in the euclidean vector space

Let S be a convex subset of a Euclidean vector space Rm. Recall the following definition: a function f : S -> R
is said to be convex if f(x1,...; xm, y) : y >= f(x), x = (x1,...,xm) is a convex set in Rm+1.

Prove that a function f : S -> R is convex if and only if
f(λp + (1+λ)q)<= λf(p + (1-λ)f(q) for all p,q in S and for all λ in [0,1]
(Note: We require the convexity of S simply so that all of the vectors (λp+(1-λ)q) are guaranteed to lie in S. Thus, this requirement should be included in the very definition of convex function.)

2. I’ll prove half of the problem and leave the other half to you.

$\displaystyle (\implies)$
Suppose $\displaystyle f:S\to\mathbb{R}$ is a convex function, i.e. $\displaystyle T=\{(x_1,\ldots,x_m,x_{m+1})x_1,\ldots,x_m)\in S,\ x_{m+1}\geq f(x_1,\ldots,x_m)\}$ is a convex subset of $\displaystyle \mathbb{R}^{m+1}$.

Let $\displaystyle p=(x_1,\ldots,x_m),q=(y_1,\ldots,y_m)\in S$.

Note that $\displaystyle (x_1,\ldots,x_m,f(p)),(y_1,\ldots,y_m,f(q))\in T$

Then, by definition of a convex set, $\displaystyle \lambda(x_1,\ldots,x_m,f(p))+(1-\lambda)(y_1,\ldots,y_m,f(q))\in T$ for all $\displaystyle \lambda\in[0,1]$

Thus, for all $\displaystyle \lambda\in[0,1]$, $\displaystyle \left(\lambda x_1+(1-\lambda)y_1,\ldots,\lambda x_m+(1-\lambda)y_m,\lambda f(p)+(1-\lambda)f(q)\right)\in T$

$\displaystyle \implies\quad\lambda f(p)+(1-\lambda)f(q)\ \geq\ f(\lambda x_1+(1-\lambda)y_1,\ldots,\lambda x_m+(1-\lambda)y_m)$

$\displaystyle \color{white}.\hspace{49mm}.$ $\displaystyle =\ f(\lambda(x_1,\ldots,x_m)+(1-\lambda)(y_1,\ldots,y_m))$

$\displaystyle \color{white}.\hspace{49mm}.$ $\displaystyle =\ f(\lambda p+(1-\lambda)q)$

The other case $\displaystyle (\Longleftarrow)$ is proved in a similar way.

3. hey... i have a midterm exam coming up in a few days and it's supposed to consist of homework problems. when i turned this homework in i tried to prove the reverse argument but the instructor just marked the question wrong for the other direction. can someone show me how to prove the converse direction?

4. First of all, do you understand the proof I gave above of half of the problem? I can show you the proof of the second half of the problem all right, but there's absolutely no point in doing that if you don't understand what I've written so far.

5. just one small question i have about the proof is:
when you define T, that can be visualized as the hypergraph(or epigraph) of the function, right?
i just tried to reverse the argument starting with the inequality we got in the first part, but i wasn't so successful. the exam is tomorrow so it would be great if you could show me how to do the other part. thanks a lot!

6. Look. I showed you how to do half the problem so as help you get a better understanding of the problem so you can do the problem yourself. I didn't post my solution to help you cheat in your homework.

Sorry, if you don't at least make an effort to understand what I write, I don't think I can help you any more. And I'm definitely not helping you to cheat in your exam.

Anyway, I won't show you how to do the next part until I'm satisfied you understand at least something of what's going on in the first part. So let's go through the first part together, shall we?

To prove the $\displaystyle \implies$ part, you assume that the set $\displaystyle T$ defined above is convex, and then try and show that $\displaystyle S$ is convex.

How to show that S is convex? Well, you take two points p and q in S, and try and show that $\displaystyle \lambda p+(1-\lambda)q\in S$ for any $\displaystyle \lambda\in[0,1]$. That's actually the definition of a convex set. Savvy?

Anyway, p and q are in S, and S is a subset of $\displaystyle \mathbb{R}^m$. So $\displaystyle p$ and $\displaystyle q$ are m×1 row vectors. Let $\displaystyle p=(x_1,\dots,x_m)$ and $\displaystyle q=(y_1,\dots,y_m)$ then.

Next I said that $\displaystyle (x_1,\ldots,x_m,f(p)),(y_1,\ldots,y_m,f(q))\in T$. Why is this true? You tell me why.

7. sorry for having trouble understanding the proof... but i mean this class is supposed to be a basic linear algebra course and the professor i think is going very overboard trying to make us learn all this stuff.

anyway, i tried to work out what your proof meant, and i think (x1,...,xm,f(p)),(y1,...,ym,f(q)) is in T because of the way u defined ur T, ie that x_m+1>=f(x1,...,xm). here f(p)>=f(x1,...,xm) since f is a convex function and x1,...,xm are in S.

and then the next part seems a lot more simple because that would mean each component of the set {x1,...,xm,f(p)} and {y1,...,ym,f(q)} would be in T, meaning that looking at just the f(p) and f(q) component we can see that the inequality holds.

8. All right, so you get it. Good.

To prove the $\displaystyle \Longleftarrow$ part, you want to prove that the set $\displaystyle T=\{(x_1,\ldots,x_m,x_{m+1})x_1,\ldots,x_m)\in S,\ x_{m+1}\geq f(x_1,\ldots,x_m)\}$ is convex. So what do you do?

You take $\displaystyle P,Q\in T$ and try and show that for each $\displaystyle \lambda\in [0,1]$, $\displaystyle \lambda P+(1-\lambda)Q\in T$.

Write

$\displaystyle P=(x_1,\ldots,x_m,x_{m+1})$, where $\displaystyle p=(x_1,\ldots,x_m)\in S$ and $\displaystyle x_{m+1}\ge f(p)$
$\displaystyle Q=(y_1,\ldots,y_m,y_{m+1})$, where $\displaystyle q=(y_1,\ldots,y_m)\in S$ and $\displaystyle y_{m+1}\ge f(q)$

Let $\displaystyle \lambda\in[0,1]$. By hypothesis, $\displaystyle \lambda f(p)+(1-\lambda)f(q)\ge f(\lambda p+(1-\lambda)q)$.

Now show that $\displaystyle \lambda P+(1-\lambda)Q\in T$. You continue.

9. i think i have it. so,

λP+(1-λ)Q=(λx1+(1-λ)y1,...,λxm+(1-λ)ym,λf(p)+(1-λ)f(q)) where the last component is >=f(λp+(1-λ)q)
since x_(m+1)>=f(λp+(1-λ)q), this would imply that λP+(1-λ)Q would be in T as it is of that form.

is that right?

10. You're almost there. Just this part is wrong:

Originally Posted by squarerootof2
x_(m+1)>=f(λp+(1-λ)q)
No: $\displaystyle x_{m+1}$ is only $\displaystyle \ge f(p)$. Just a tiny bit of work still to do here, and you're done.