1
$\begingroup$

I have a question about 2 inequalities:

For a convex and twice lipschitz continuous differentiable function $f$ with lipschitz constants $L_g$ and $L_H$ for $x,v \in \mathbb{R}^n$ we have: $(1) \; f(x+v) \leq f(x) + \nabla f(x)^Tv + \frac{L_g}{2} || v ||^2, \\ (2) \; f(x+v) \leq f(x) + \nabla f(x)^Tv + \frac{1}{2}v^T {\nabla}^2f(x)v + \frac{L_H}{6}|| v ||^3.$

With the remainder $R_n(x) = \mathcal{O}((x-v)^n)$.

Now I'm not sure how to get these 2 results. My idea for (1) was with the Taylor's theorem (because $\frac{1}{2}$ and $\frac{1}{6}$ looks pretty taylorish for me). So I would get:

$f(x+v) = f(x) + \nabla f(x)^Tv + \mathcal{O}(||v||^2), \\ f(x+v) = f(x) + \nabla f(x)^Tv + \frac{1}{2}v^T {\nabla}^2f(x)v + \mathcal{O}(||v||^2).$

But now I have a problem using lipschitz continuity $|f(x)-f(y)| \leq L|x-y|$ for the remainder $\mathcal{O}(||v||^2)$.

I tried to use the integral form for the remainder $R_n = \frac{1}{n!} \int_v^x (x-t)^n f^{(n+1)}dt$ and got by partial integration $R_2 = \frac{1}{2!} \left[ \frac{-1}{3} (x-v)^3 + \frac{1}{12} (x-v)^4 + \frac{-1}{60}(x-a)^5 + \frac{1}{360}(x-a)^6 \right] $. But I still don't see how I can get the lipschitz constant $L_g$ into this ineuquality.

Maybe someone can help me :)

$\endgroup$

1 Answer 1

2
$\begingroup$

You have to be more precise when using Taylor as you need precise control of the remainder term. Here is the proof for (1): It uses the fundamental theorem. $$\begin{split} f(x+v) - f(x) - \nabla f(x)^Tv &= \int_0^1 (\nabla f(x+sv) - \nabla f(x))^Tv\ ds\\ &\le L_g \int_0^1 s\|v\| \cdot \|v\| \ dx \le \frac{L_g}2\|v\|^2. \end{split} $$ To prove (2), write $$ \nabla f(x+sv) -\nabla f(x)= \int_0^1 \nabla^2 f(x+stv)sv\ dt, $$ then subtract $v^T\nabla^2 f(x)v$ from both sides, and use Lipschitz continuity of $x\mapsto \nabla^2 f(x)$. You end up with some double integral, which evaluates to $\frac16$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .