1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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)]
    (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)?

    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.

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