Mètode de Newton (optimització)

Una comparació del descens del gradient (verd) i el mètode de Newton (vermell) per minimitzar una funció (amb mides de pas petites). El mètode de Newton utilitza informació de curvatura (és a dir, la segona derivada) per prendre una ruta més directa.

En càlcul, el mètode de Newton és un mètode iteratiu per trobar les arrels d'una funció diferenciable F, que són solucions de l'equació F (x) = 0. Com a tal, el mètode de Newton es pot aplicar a la derivada f ′ d'una funció f dues vegades diferenciable per trobar les arrels de la derivada (solucions a f ′(x) = 0), també conegudes com els punts crítics de f. Aquestes solucions poden ser mínims, màxims o punts de muntatge; vegeu la secció "Diverses variables" a Punt crític (matemàtiques) i també la secció "Interpretació geomètrica" d'aquest article. Això és rellevant en optimització, que té com a objectiu trobar mínims (globals) de la funció f.

El problema central de l'optimització és la minimització de funcions. Considerem primer el cas de les funcions univariades, és a dir, les funcions d'una única variable real. Més endavant considerarem el cas multivariant més general i més útil pràcticament.

Donada una funció doblement diferenciable $f:\mathbb {R} \to \mathbb {R}$, busquem resoldre el problema d'optimització

$\min _{x\in \mathbb {R} }f(x).$

El mètode de Newton intenta resoldre aquest problema mitjançant la construcció d'una seqüència $\{x_{k}\}$ a partir d'una conjectura inicial (punt de partida) $x_{0}\in \mathbb {R}$ que convergeix cap a un minimitzador $x_{*}$ de $f$ utilitzant una seqüència d'aproximacions de Taylor de segon ordre de $f$ al voltant dels iteracions. L' expansió de Taylor de segon ordre de f al voltant $x_{k}$ és

$f(x_{k}+t)\approx f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}.$

La següent iteració $x_{k+1}$ es defineix de manera que es minimitzi aquesta aproximació quadràtica en $t$, i la configuració $x_{k+1}=x_{k}+t$. Si la segona derivada és positiva, l'aproximació quadràtica és una funció convexa de $t$, i el seu mínim es pot trobar posant la derivada a zero. Des que

$\displaystyle 0={\frac {\rm {d}}{{\rm {d}}t}}\left(f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}\right)=f'(x_{k})+f''(x_{k})t,$

s'aconsegueix el mínim per

$t=-{\frac {f'(x_{k})}{f''(x_{k})}}.$

Ajuntant-ho tot, el mètode de Newton realitza la iteració

$x_{k+1}=x_{k}+t=x_{k}-{\frac {f'(x_{k})}{f''(x_{k})}}.$