Mètode de Newton (optimització)

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.

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.

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})}}.$