Results 1 to 4 of 4

Math Help - 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 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
    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: 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).
    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: 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
    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 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
    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: December 29th 2010, 12:38 PM
  2. Convexity
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: February 11th 2010, 04:40 PM
  3. Is Convexity Necessary for Lagrangian
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: January 28th 2010, 01:42 AM
  4. Prove Convexity Using Formal Definition
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 10th 2009, 08:37 AM
  5. Quasi-Convexity
    Posted in the Calculus Forum
    Replies: 0
    Last Post: November 13th 2008, 02:34 AM

Search Tags


/mathhelpforum @mathhelpforum