Prove a function to be Lipschitz

Question

With the condition $$ 0\le f(y)-f(x)-\langle f'(x),y-x\rangle \le \frac{L}{2} \|x-y\|^2, $$ I want to prove $f'(x)$ is Lipschitz with constant $L$ and is convex.

It is easy to see that $f $ is convex from the first inequality. From the second inequality I derived $$ \langle f'(y)-f'(x),y-x\rangle \le L \|y-x\|^2 $$ by exchanging the role of $x$ and $y$ and add the two inequalities. However I don't know what to do next. Could anybody tell me?

Thanks.

@user251257 The original condition is $f(y)-f(x)-\langle f'(x),y-x\rangle \le L/2 |x-y|^2$ and I transformed it as the question says... — Xiangru Lian, Jul 10 '15 at 10:10
I'd suggest that you post the complete question and then add your thoughts and your derivation — user190080, Jul 10 '15 at 10:21
so $f:\mathbb{R}\mapsto\mathbb{R}$ and is everywhere differentiable? — user190080, Jul 10 '15 at 10:45
Something is wrong here. Counterexample: $f(x)=x^2$. It satisfies the condition (with $L=2$) and is not globally Lipschitz. — A.Γ., Jul 10 '15 at 10:54
@A.G. Sorry. There is a typo. I want to prove $f'(x)$ is Lipschitz. — Xiangru Lian, Jul 10 '15 at 13:55
ahh...okay...but then you are pretty much done, aren't you? just factor out (your scalarproduct is actually the product) You forgot a $L$ in your second line — user190080, Jul 10 '15 at 13:58
@user190080 Thanks. The final expression should be $|f'(y)-f'(x)|\le L |y-x|$. I don't know how to derive this. — Xiangru Lian, Jul 10 '15 at 14:07
I hope I didn't miss anything in the answer, just check and if anything doesn't look convincing at all let me know — user190080, Jul 10 '15 at 14:28

user190080 · Answer 1 · 2015-07-10T20:54:30.770

0

EDIT: As it stands, this answer only holds for the 1-dimensional case

so you have

$$ 0<\langle f'(y)-f'(x),y-x\rangle \leq L \|y-x\|^2\\ \Leftrightarrow\\ 0<[f'(y)-f'(x)](y-x) \leq L \|y-x\|^2 $$ and now you do a case study, case $1):y>x$ and case $2):y<x$.

In case $1)$ we get by dividing $(y-x)$ $$ 0<[f'(y)-f'(x)](y-x) \leq L \|y-x\|^2 \\ \Leftrightarrow \\ 0<[f'(y)-f'(x)] \leq L \|y-x\| $$ which is the same as in case $2)$ (because $0<[f'(y)-f'(x)](y-x)$), so you are done.

bests

edited Jul 10 '15 at 20:54

answered Jul 10 '15 at 14:26

user190080

3,701

I think that $x,y\in\mathbb{R}^n$ here with possibly $n\ne 1$. – A.Γ. Jul 10 '15 at 14:46
@A.G. hmmm,maybe, but I asked the OP in one of the above comments and he said it would be an R to R function – user190080 Jul 10 '15 at 15:37
@user190080 It's on $R^n$. Sorry. – Xiangru Lian Jul 10 '15 at 15:38

score 0 · Answer 2 · answered Jul 10 '15 at 20:45

If the function $f$ is twice differentiable then your condition implies $\|f''(x)\|\le L$ which easily gives the Lipschitz condition on $f'$. Look, for example, here, p. 2.

Otherwise, for a convex differentiable $f$ the following statements are equivalent:

$\langle f'(y)-f'(x),y-x\rangle\le L\|y-x\|^2$, $\forall x,y$.
$g(x)=\frac{L}{2}\|x\|^2-f(x)$ is convex.
$\langle f'(y)-f'(x),y-x\rangle\ge \frac{1}{L}\|f'(y)-f'(x)\|^2$, $\forall x,y$.
$\|f'(y)-f'(x)\|\le L\|y-x\|$, $\forall x,y$.

Proof: left as en exercise ;-)

Prove a function to be Lipschitz

2 Answers2