Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Strictly Convex Functions

  1. Jan 30, 2012 #1
    1. The problem statement, all variables and given/known data
    Let S C Rd be open and convex.
    Let f be C1(S).
    Prove that if f is strictly convex, then f(y) > f(x) + grad f(x) o (y-x) for all x,y in S such that x≠y.
    (note: "o" means dot product)


    2. Relevant equations
    Strictly convex functions

    3. The attempt at a solution
    Suppose f is stirctly convex.
    Then for all x,y in S such that x≠y, 0<s<1,
    f[(1-s)x+sy] < (1-s)f(x) + s f(y)
    => f[x+s(y-x)] < f(x) + s[f(y)-f(x)]
    => [f(x+s(y-x)) - f(x)] /s < f(y)-f(x)
    => lim [f(x+s(y-x)) - f(x)] /s lim [f(y)-f(x)]
    s->0------------------------s->0
    (recall from calculus, we know that a strict inequality, IN THE LIMIT, becomes a loose inequality. And that's why I must write ≤ when I take the limit)

    => grad f(x) o (y-x) ≤ f(y)-f(x)
    => f(y) f(x) + grad f(x) o (y-x) for all x,y in S such that x≠y.

    BUT what I actually want to prove is >, not ≥. How can I rigorously justify that it should be >? I'm really running out of ideas regarding proving this subtle point.

    Any help will be much appreciated!
     
  2. jcsd
  3. Jan 30, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Suppose x and y are given points in S, with x ≠ y. What happens if you assume f(y) = f(x) + grad f(x) o (y-x)?

    RGV
     
    Last edited: Jan 30, 2012
  4. Jan 30, 2012 #3
    I was trying to set up something like this and I need to try to reach a contradiction. But the problem is I can't find where the contradiction is. (or in other words, I need to show that f(y) = f(x) + grad f(x) o (y-x) => x=y. But I can't think of a way of showing it...)
    What kind of manipluations do I have to do with f(y) = f(x) + grad f(x) o (y-x)? I have no idea what to do next after assuming f(y) = f(x) + grad f(x) o (y-x).
     
  5. Jan 31, 2012 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Let p = y-x in R^d and consider the univariate function h(t) = f(x + t*p) for real t. We have h'(t) = grad f(x + t*p) ° p, so h'(0) = grad f(x) ° p . One can show from strict convexity (just by manipulating the convexity-defining property) that the ratio [tex] r(s) = \frac{h(s)-h(0)}{s} [/tex] is strictly increasing in s > 0, so for small positive s we have r(1) > r(s). Fix small s0 > 0 and look at the limit of r(s) as s --> 0+. We have r(1) > r(s0) >= limit r(s) = h'(0) = grad f(x) ° p .

    Note: I leave it to you to show that r(s) is a strictly increasing function.

    RGV
     
    Last edited: Jan 31, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook