How Does Strict Convexity Influence the Gradient Inequality?

[kingwinner]

Homework Statement

Let S C R^d be open and convex.
Let f be C¹(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)

Homework Equations

Strictly convex functions

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!

 

[Ray Vickson]

Homework Statement

Let S C R^d be open and convex.
Let f be C¹(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)

Homework Equations

Strictly convex functions

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!

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

 

[kingwinner]

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

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.[/color] 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).

 

[Ray Vickson]

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.[/color] 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).

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 r(s) = \frac{h(s)-h(0)}{s} 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