# prove convexity

• February 28th 2010, 02:38 AM
bravegag
prove convexity
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.

Best regards,
bravegag
• February 28th 2010, 05:32 AM
Dinkydoe
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)$.
• February 28th 2010, 06:03 AM
bravegag
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
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 (Worried)

TIA,
Best regards,
Giovanni
• February 28th 2010, 04:43 PM
Dinkydoe
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]$