prove convexity

Printable View

• Feb 28th 2010, 01: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 $\displaystyle S \subseteq \mathbb{R}^n$ under an affine transformation i.e. the set $\displaystyle f(S)$ for $\displaystyle f(x)=Ax + b$, where $\displaystyle A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$

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

Thanks in advance,
Best regards,
bravegag
• Feb 28th 2010, 04:32 AM
Dinkydoe
The important part is proving that: $\displaystyle S$ convex $\displaystyle \Rightarrow A(S)$ convex. Trivially, the set $\displaystyle A(S)+b$ is convex as well.

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

Now, for you to prove that $\displaystyle A(S)$ is convex, prove that any convex combination $\displaystyle \lambda Ax+(1-\lambda)Ay \in A(S)$.
• Feb 28th 2010, 05:03 AM
bravegag
Hello Dinkydoe,

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

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

Finally by convex definition $\displaystyle \forall\ y\ \mathrm{s.t.}\ y=\lambda y_1 + (1 - \lambda) y_2$ where $\displaystyle y_1, y_2 \subseteq S$ convex and $\displaystyle \lambda \in [0,1]$ then $\displaystyle 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
• Feb 28th 2010, 03:43 PM
Dinkydoe
Your proof is indeed correct:

I think the conclusion you gave:

should rather be:

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

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