prove convexity

**bravegag** · February 28th 2010, 01:38 AM

Hello,

I need to prove the following but I am struggling to see where to start:

The image of a convex set $S \subseteq \mathbb{R}^n$ under an affine transformation i.e. the set $f(S)$ for $f(x)=Ax + b$ , where $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$

However, I know how to prove $f(x)=Ax + b$ convex.

Thanks in advance,
Best regards,
bravegag

**Dinkydoe** · February 28th 2010, 04:32 AM

The important part is proving that: $S$ convex $\Rightarrow A(S)$ convex. Trivially, the set $A(S)+b$ is convex as well.

S is convex, meaning for all $x,y\in S$ and any $\lambda \in [0,1]$ we have $\lambda x+(1-\lambda)y\in S$ .

Now, for you to prove that $A(S)$ is convex, prove that any convex combination $\lambda Ax+(1-\lambda)Ay \in A(S)$ .

**bravegag** · February 28th 2010, 05:03 AM

Hello Dinkydoe,

Thank you for your answer! I ended with this below as proof ... does it make sense to you?

Proof: $S\ \mathrm{convex}\ \Rightarrow\ A(S)\ \mathrm{convex}$ . Now to prove that $A(S)$ is convex, I need to prove that any convex combination $\lambda<br /> Ax+(1-\lambda)Ay \in A(S)$
Let $y_1 \in f(S),\ y_2 \in f(S)$ and $y_1=f(x_1),\ y_2=f(x_2)$ . Then applying the Convex definition:
$A(\lambda x_1 + (1 - \lambda)x_2) + b$
$=\lambda Ax_1 + (1 - \lambda)Ax_2 + b$ substituting $Ax=y - b$
$=\lambda(y_1 - b) + (1 - \lambda)(y_2 - b) + b$
$=\lambda y_1 + y_2 - \lambda y_2$
$=\lambda y_1 + (1 - \lambda) y_2$

Finally by convex definition $\forall\ y\ \mathrm{s.t.}\ y=\lambda y_1 + (1 - \lambda) y_2$ where $y_1, y_2 \subseteq S$ convex and $\lambda \in [0,1]$ then $y \subseteq S$ is convex too.

I am not a mathematician but interested to learn the course Convex Optimization ... a bit too many proofs for a poor programmer like me

TIA,
Best regards,
Giovanni

**Dinkydoe** · February 28th 2010, 03:43 PM

Your proof is indeed correct:

I think the conclusion you gave:

Finally by convex definition

where

convex and

then

is convex too.

should rather be:

For any $y_1,y_2\in f(S)$ we have $\lambda y_1+(1-\lambda)y_2\in f(S)$ for any $\lambda\in [0,1]$

Since that's what you've shown, and I think that's what you mean

Thread: prove convexity

LinkBack

Thread Tools

Display

prove convexity

Similar Math Help Forum Discussions

Convexity and integrals

Convexity

Is Convexity Necessary for Lagrangian

Prove Convexity Using Formal Definition

Quasi-Convexity

Search Tags