6
$\begingroup$

I've just started reading Nocedal and Wright's book on Numerical Optimization. On page 14 there is a formula for the value of the gradient in some point (equation 2.5) that I cannot derive myself.

Given formula 2.4: $$f(x + p) = f(x) + \nabla f(x+tp)^T p$$ how does one derive formula 2.5: $$\nabla f(x+p) = \nabla f(x) + \int_0 ^ 1 \nabla^2 f(x+tp) p dt$$ ?

$\endgroup$

2 Answers 2

8
$\begingroup$

So, I guess I managed to figure it out.

Expressing $f(x+p)$ using Taylor's formula with the remainder expressed in the integral form gives:

$$f(x+p) = f(x) + \int_x^{x+p} \nabla f(u) du$$

Here we can make a variable substitution as follows: $x+tp = u$ which gives: $pdt = du$. Hence this form: $$f(x+p) = f(x) + \int_0^1 \nabla f(x+tp) p dt$$ But this formula holds for every differentiable function $f$. If $f$ is twice differentiable, the formula holds for $\nabla f$ as well. Hence: $$\nabla f(x+p) = \nabla f(x) + \int_0^1 \nabla^2 f(x+tp) p dt$$

$\endgroup$
2
1
$\begingroup$

This is for 1-dimension but you can get the flavor of what's occuring in (2.4), (2.5), and (2.6).

Nocedal and Wright initially suppose one continuou derivative. This allows them to write (by fundamental theorem of calculus): $$f(x+p) - f(x) = \int_x^{x+p} f'(u)\,du$$ Following Tudor, make the substitution $u=x+tp$ and $du=p\,dt$ to obtain $$f(x+p) - f(x) = p\int_0^1f'(x+tp)\,dt$$ Colley's book on Vector Calculus p260 states without proof the following fact (which is a modification of mean value theorem for integrals): For continuous functions $g$ and $h$ such that $h$ is always greater or less than 0 on the interval of interest we have: $$\int_a^bg(t)h(t)dt=g(z)\int_a^bh(t)dt$$ for some $z\in[a,b]$. Using Colley's fact we can establish (2.4) - by letting $g(t)=f'(x+tp)$ and $h(t)=1$ and manipulating the RHS of Tudor's substitution. $$p\int_0^1f'(x+tp)\,dt=p\,f'(x+tp)\int_0^11dt = pf'(x+tp)$$ where in the middle and RHS $t\in[0,1]$ (by Colley's fact). Thus $$f(x+p) - f(x) = pf'(x+tp)$$ for some $t\in[0,1]$ -- establishing (2.4) in 1D.

A similar procedure can be followed for (2.5). Nocedal and Wright now assume $f$ has 2 continuous derivatives. In particular $f'$ is continuous, using Fundamental Theorem of Calculus, write (after making Tudor's u-sub): $$f'(x+p) - f'(x) = p\int_0^1f''(x+tp)\,dt$$ Establishing (2.5) in 1D, as Tudor did.

To get (2.6) continue from Tudor's u-sub above and integrate by parts: $$f(x+p) - f(x) = p\int_0^1f'(x+tp)\,dt=ptf'(x+tp)\Big|_{t=0}^{t=1}-p^2\int_0^1tf''(x+tp)dt \\ = pf'(x+p)- p^2\int_0^1tf''(x+tp)dt$$ Now substitute (2.5) in to eliminate $f'(x+p)$ $$=p\Big(p\int_0^1f''(x+tp)\,dt + f'(x)\Big)- p^2\int_0^1tf''(x+tp)dt$$ Rearrange: $$=pf'(x) + p^2\int_0^1(1-t)f''(x+tp)dt$$ Use Colley's fact: $$=pf'(x) + p^2f''(x+zp)\int_0^1(1-t)dt$$ Where $z\in[0,1]$. Evaluate integral to obtain finally: $$f(x+p)-f(x)=pf'(x) + \frac{p^2}{2}f''(x+zp)$$ Where $z\in[0,1]$. Establishing (2.6) in 1D. Presumably higher dimensions work out by keeping track of the row and column vectors.

$\endgroup$

You must log in to answer this question.

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