Proof that given function is convex

[PhDeezNutz]

Homework Statement

Given $f: \mathbb{R}^n \rightarrow \mathbb{R}$ where $f\left(\vec{x}\right) = \| \vec{x} \|^2$ prove that $f$ is convex

Relevant Equations

Definition of convex function

A function $f: \mathcal{C} \subset \mathbb{R}^n \rightarrow \mathbb{R}$ is convex on convex set $\mathcal{C}$ if $\forall \vec{x}, \vec{y} \in \mathcal{C}$

$f\left(\left( 1 - \lambda \right) \vec{x} + \lambda \vec{y} \right) \leq \left( 1 - \lambda \right) f \left(\vec{x} \right) + \lambda f \left( y \right)$

where $\lambda \in \left[ 0,1 \right]$

Also the triangle inequality

$\left\| \vec{a} + \vec{b} \right\|^2 \leq \left\| \vec{a} \right\|^2 + \left\| \vec{b} \right\|^2$

Part 1

$\left\| \vec{y} \right\|^2 \leq \left\| \vec{y} \right\|^2$ and since $\lambda \in \left[ 0,1 \right] \Rightarrow \lambda^2 \leq \lambda$

So

$\lambda^2 \left\| \vec{y} \right\|^2 \leq \lambda \left\| \vec{y} \right\|^2$

Part 2

$\left\| \vec{x} \right\|^2 \leq \left\| \vec{x} \right\|^2$ and since $\lambda \in \left[ 0,1 \right]$ we have $1 - \lambda \leq 1 \Rightarrow \left( 1 - \lambda \right)^2 \leq \left( 1 - \lambda \right)$

So

$\left( 1 - \lambda \right)^2 \left\| \vec{x} \right\|^2 \leq \left(1 - \lambda \right) \left\| \vec{x} \right\|^2$

Part 3 (adding Parts 1 and 2)

$\left( 1 -\lambda \right)^2 \left\| \vec{x} \right\|^2 + \lambda^2 \left\| \vec{y} \right\|^2 \leq \left( 1 - \lambda \right) \left\| \vec{x} \right\|^2 + \lambda \left\| \vec{y} \right\|^2$

Part 4 (Invoking the triangle inequality)

$\left\| \left(1 - \lambda \right) \vec{x} + \lambda \vec{y} \right\|^2 \leq \left( 1 -\lambda \right)^2 \left\| \vec{x} \right\|^2 + \lambda^2 \left\| \vec{y} \right\|^2 \leq \left( 1 - \lambda \right) \left\| \vec{x} \right\|^2 + \lambda \left\| \vec{y} \right\|^2$Taking the first and last part of the above inequality we have

$\left\| \left(1 - \lambda \right) \vec{x} + \lambda \vec{y} \right\|^2 \leq \left( 1 - \lambda \right) \left\| \vec{x} \right\|^2 + \lambda \left\| \vec{y} \right\|^2$

Therefore $f\left(\vec{x}\right) = \left\| \vec{x} \right\|^2$ is convex

 

[PeroK]

Looks okay to me. The steps are all there. Technically, the proof should start with "Let $\lambda \in [0, 1]$ and $\vec x, \vec y \in \mathbb R^n$" and show explicitly that $$f\left(\left( 1 - \lambda \right) \vec{x} + \lambda \vec{y} \right) \leq \left( 1 - \lambda \right) f \left(\vec{x} \right) + \lambda f \left( \vec y \right)$$

 

[PhDeezNutz]

Looks okay to me. The steps are all there. Technically, the proof should start with "Let $\lambda \in [0, 1]$ and $\vec x, \vec y \in \mathbb R^n$" and show explicitly that $$f\left(\left( 1 - \lambda \right) \vec{x} + \lambda \vec{y} \right) \leq \left( 1 - \lambda \right) f \left(\vec{x} \right) + \lambda f \left( \vec y \right)$$

You'll have to forgive me I am but a filthy physics major . I'm starting to self [URL='https://www.physicsforums.com/insights/self-study-basic-high-school-mathematics/']study mathematics[/URL] because there were some parts of grad school that seemed extremely hand wavy to me. I'll have to learn proof etiquette.

Thank you for reviewing my proof.

 

[PeroK]

You'll have to forgive me I am but a filthy physics major . I'm starting to self [URL='https://www.physicsforums.com/insights/self-study-basic-high-school-mathematics/']study mathematics[/URL] because there were some parts of grad school that seemed extremely hand wavy to me. I'll have to learn proof etiquette.

Thank you for reviewing my proof.

That makes sense and your proof was a lot more coherent than many we see on here!

 

[PhDeezNutz]

I’m trying to follow this proof of $x^4$ being strictly convex but I don’t understand how they got rid of the cross terms with step $\left( 2 \right)$

 

[PeroK]

View attachment 293510

I’m trying to follow this proof of $x^4$ being strictly convex but I don’t understand how they got rid of the cross terms with step $\left( 2 \right)$

The cross terms are non-negative.

 

[PhDeezNutz]

The cross terms are non-negative.

I’m confused. To me that is precisely the reason we can’t get rid of them in the end. Let me be more explicit.

$\left\| \lambda \vec{x} + \left( 1 - \lambda \right)\vec{y} \right\|^4 = \left( \left\| \lambda \vec{x} \left( 1 - \lambda \right) \vec{y} \right\|^2 \right)^2 \leq \left( \lambda \left\| \vec{x}\right\|^2 + \left(1 - \lambda \right) \left\| \vec{y} \right\|^2 \right)^2$

Where I've used the fact that $\left\| \vec{x} \right\|^2$ is convex to get to the $/leq$ inequality

To me the only thing I can do now is "foil it out"

$= \lambda^2 \left\| \vec{x} \right\|^4 + 2 \lambda \left( 1 - \lambda \right) \left\| \vec{x} \right\|^2 \left\| \vec{y} \right\|^2 + \left( 1 - \lambda \right)^2 \left\| \vec{y} \right\|^4$

We know that both $\lambda , \left(1 - \lambda \right) \lt 1 \Rightarrow \lambda^2 , \left( 1 - \lambda \right)^2 \lt \lambda, 1 - \lambda$

$\lt \lambda \left\| \vec{x} \right\|^4 + 2 \lambda \left( 1 - \lambda \right) \left\| \vec{x} \right\|^2 \left\| \vec{y} \right\|^2 + \left( 1 - \lambda \right) \left\| \vec{y} \right\|^4$

So all in all

$\left\| \lambda \vec{x} + \left( 1 - \lambda \right) \right\|^4 \lt \lambda \left\| \vec{x} \right\|^4 + 2 \lambda \left( 1 - \lambda \right) \left\| \vec{x} \right\|^2 \left\| \vec{y} \right\|^2 + \left( 1 - \lambda \right) \left\| \vec{y} \right\|^4$

Don't know how to get rid of the middle cross term $2 \lambda \left( 1 - \lambda \right) \left\| \vec{x} \right\|^2 \left\| \vec{y} \right\|^2$

 

[PeroK]

You're right. They are simply applying the convex property of $x^2$ twice. There's no expansion needed.

 

[PeroK]

PS It's cometimes easier to generalise things. Suppose $f: \mathbb R_+ \rightarrow \mathbb R_+$ is convex and increasing, then $f \circ f$ is convex and increasing:

Let $t \in [0, 1]$ and $x, y \in \mathbb R_+$. We have:

$$f(tx + (1-t)y) \le tf(x) + (1-t)f(y) \ \ (\text{as} \ f \ \text{is convex})$$$$\Rightarrow \ f[f(tx + (1-t)y)] \le f[tf(x) + (1-t)f(y)] \ \ (\text{as} \ f \ \text{is increasing})$$ $$\le tf[f(x)] + (1-t)f[f(y)] \ \ (\text{as} \ f \ \text{is convex and} \ f(x), f(y) \in \mathbb R_+)$$$$\therefore f \circ f(tx + (1-t)y) \le tf \circ f(x) + (1-t)f \circ f(y)$$$$\therefore f \circ f \ \text{is convex}$$It's easy to show that $f \circ f$ in increasing, although not a bad exercise, in fact.

 

[PhDeezNutz]

You're right. They are simply applying the convex property of $x^2$ twice. There's no expansion needed.

I actually see it now. Wow this has confused me for several days.All we needed to do was make a change of variables

$\left\| \vec{x} \right\|^2 \mapsto X \in \mathbb{R}$

$\left\| \vec{y} \right\|^2 \mapsto Y \in \mathbb{R}$

and repeat the argument and replace $X$ and $Y$ at the end.

Can't believe I didn't see it until now. Thank you for your help.