Results 1 to 10 of 10

Math Help - convexity in the euclidean vector space

  1. #1
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128

    convexity in the euclidean vector space

    Let S be a convex subset of a Euclidean vector space Rm. Recall the following definition: a function f : S -> R
    is said to be convex if f(x1,...; xm, y) : y >= f(x), x = (x1,...,xm) is a convex set in Rm+1.

    Prove that a function f : S -> R is convex if and only if
    f(λp + (1+λ)q)<= λf(p + (1-λ)f(q) for all p,q in S and for all λ in [0,1]
    (Note: We require the convexity of S simply so that all of the vectors (λp+(1-λ)q) are guaranteed to lie in S. Thus, this requirement should be included in the very definition of convex function.)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jun 2008
    Posts
    29
    Iíll prove half of the problem and leave the other half to you.

    (\implies)
    Suppose f:S\to\mathbb{R} is a convex function, i.e. x_1,\ldots,x_m)\in S,\ x_{m+1}\geq f(x_1,\ldots,x_m)\}" alt="T=\{(x_1,\ldots,x_m,x_{m+1})x_1,\ldots,x_m)\in S,\ x_{m+1}\geq f(x_1,\ldots,x_m)\}" /> is a convex subset of \mathbb{R}^{m+1}.

    Let p=(x_1,\ldots,x_m),q=(y_1,\ldots,y_m)\in S.

    Note that (x_1,\ldots,x_m,f(p)),(y_1,\ldots,y_m,f(q))\in T

    Then, by definition of a convex set, \lambda(x_1,\ldots,x_m,f(p))+(1-\lambda)(y_1,\ldots,y_m,f(q))\in T for all \lambda\in[0,1]

    Thus, for all \lambda\in[0,1], \left(\lambda x_1+(1-\lambda)y_1,\ldots,\lambda x_m+(1-\lambda)y_m,\lambda f(p)+(1-\lambda)f(q)\right)\in T

    \implies\quad\lambda f(p)+(1-\lambda)f(q)\ \geq\ f(\lambda x_1+(1-\lambda)y_1,\ldots,\lambda x_m+(1-\lambda)y_m)

    \color{white}.\hspace{49mm}. =\ f(\lambda(x_1,\ldots,x_m)+(1-\lambda)(y_1,\ldots,y_m))

    \color{white}.\hspace{49mm}. =\ f(\lambda p+(1-\lambda)q)

    The other case (\Longleftarrow) is proved in a similar way.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128
    hey... i have a midterm exam coming up in a few days and it's supposed to consist of homework problems. when i turned this homework in i tried to prove the reverse argument but the instructor just marked the question wrong for the other direction. can someone show me how to prove the converse direction?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jun 2008
    Posts
    29
    First of all, do you understand the proof I gave above of half of the problem? I can show you the proof of the second half of the problem all right, but there's absolutely no point in doing that if you don't understand what I've written so far.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128
    just one small question i have about the proof is:
    when you define T, that can be visualized as the hypergraph(or epigraph) of the function, right?
    i just tried to reverse the argument starting with the inequality we got in the first part, but i wasn't so successful. the exam is tomorrow so it would be great if you could show me how to do the other part. thanks a lot!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2008
    Posts
    29
    Look. I showed you how to do half the problem so as help you get a better understanding of the problem so you can do the problem yourself. I didn't post my solution to help you cheat in your homework.

    Sorry, if you don't at least make an effort to understand what I write, I don't think I can help you any more. And I'm definitely not helping you to cheat in your exam.

    Anyway, I won't show you how to do the next part until I'm satisfied you understand at least something of what's going on in the first part. So let's go through the first part together, shall we?

    To prove the \implies part, you assume that the set T defined above is convex, and then try and show that S is convex.

    How to show that S is convex? Well, you take two points p and q in S, and try and show that \lambda p+(1-\lambda)q\in S for any \lambda\in[0,1]. That's actually the definition of a convex set. Savvy?

    Anyway, p and q are in S, and S is a subset of \mathbb{R}^m. So p and q are m◊1 row vectors. Let p=(x_1,\dots,x_m) and q=(y_1,\dots,y_m) then.

    Next I said that (x_1,\ldots,x_m,f(p)),(y_1,\ldots,y_m,f(q))\in T. Why is this true? You tell me why.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128
    sorry for having trouble understanding the proof... but i mean this class is supposed to be a basic linear algebra course and the professor i think is going very overboard trying to make us learn all this stuff.

    anyway, i tried to work out what your proof meant, and i think (x1,...,xm,f(p)),(y1,...,ym,f(q)) is in T because of the way u defined ur T, ie that x_m+1>=f(x1,...,xm). here f(p)>=f(x1,...,xm) since f is a convex function and x1,...,xm are in S.

    and then the next part seems a lot more simple because that would mean each component of the set {x1,...,xm,f(p)} and {y1,...,ym,f(q)} would be in T, meaning that looking at just the f(p) and f(q) component we can see that the inequality holds.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jun 2008
    Posts
    29
    All right, so you get it. Good.

    To prove the \Longleftarrow part, you want to prove that the set x_1,\ldots,x_m)\in S,\ x_{m+1}\geq f(x_1,\ldots,x_m)\}" alt="T=\{(x_1,\ldots,x_m,x_{m+1})x_1,\ldots,x_m)\in S,\ x_{m+1}\geq f(x_1,\ldots,x_m)\}" /> is convex. So what do you do?

    You take P,Q\in T and try and show that for each \lambda\in [0,1], \lambda P+(1-\lambda)Q\in T.

    Write

    P=(x_1,\ldots,x_m,x_{m+1}), where p=(x_1,\ldots,x_m)\in S and x_{m+1}\ge f(p)
    Q=(y_1,\ldots,y_m,y_{m+1}), where q=(y_1,\ldots,y_m)\in S and y_{m+1}\ge f(q)

    Let \lambda\in[0,1]. By hypothesis, \lambda f(p)+(1-\lambda)f(q)\ge f(\lambda p+(1-\lambda)q).

    Now show that \lambda P+(1-\lambda)Q\in T. You continue.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128
    i think i have it. so,

    λP+(1-λ)Q=(λx1+(1-λ)y1,...,λxm+(1-λ)ym,λf(p)+(1-λ)f(q)) where the last component is >=f(λp+(1-λ)q)
    since x_(m+1)>=f(λp+(1-λ)q), this would imply that λP+(1-λ)Q would be in T as it is of that form.

    is that right?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jun 2008
    Posts
    29
    You're almost there. Just this part is wrong:

    Quote Originally Posted by squarerootof2 View Post
    x_(m+1)>=f(λp+(1-λ)q)
    No: x_{m+1} is only \ge f(p). Just a tiny bit of work still to do here, and you're done.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: August 16th 2011, 03:52 PM
  2. Non-Euclidean Space
    Posted in the Geometry Forum
    Replies: 10
    Last Post: August 2nd 2011, 01:17 AM
  3. Sets > Metric Space > Euclidean Space
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: April 25th 2010, 11:17 PM
  4. Euclidean vector space
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 6th 2009, 06:45 PM
  5. convexity in euclidean vector space
    Posted in the Advanced Algebra Forum
    Replies: 8
    Last Post: July 15th 2008, 12:35 AM

Search Tags


/mathhelpforum @mathhelpforum