Results 1 to 4 of 4

Thread: prove convexity

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    8

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    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)$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    8
    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

    TIA,
    Best regards,
    Giovanni
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Dinkydoe's Avatar
    Joined
    Dec 2009
    Posts
    411
    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 $\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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Convexity and integrals
    Posted in the Calculus Forum
    Replies: 6
    Last Post: Dec 29th 2010, 12:38 PM
  2. Convexity
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Feb 11th 2010, 04:40 PM
  3. Is Convexity Necessary for Lagrangian
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: Jan 28th 2010, 01:42 AM
  4. Prove Convexity Using Formal Definition
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Nov 10th 2009, 08:37 AM
  5. Quasi-Convexity
    Posted in the Calculus Forum
    Replies: 0
    Last Post: Nov 13th 2008, 02:34 AM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum