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 Plantilla:Math, que són solucions de l'equació Plantilla:Math. Com a tal, el mètode de Newton es pot aplicar a la derivada Plantilla:Math d'una funció Plantilla:Math dues vegades diferenciable per trobar les arrels de la derivada (solucions a Plantilla:Math), també conegudes com els punts crítics de Plantilla:Math. 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ó Plantilla:Math.

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:ℝ\to ℝ$, busquem resoldre el problema d'optimització

$\underset{x\in ℝ}{\min }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 ℝ$ 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 Plantilla:Math al voltant $x_k$ és

$f(x_k+t)\approx f(x_k)+f^{\prime }(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

$0=\frac{\mathrm{d}}{\mathrm{d}t}(f(x_k)+f^{\prime }(x_k)t+\frac{1}{2}{f}^{″}(x_k)t^2)=f^{\prime }(x_k)+f^{″}(x_k)t,$

s'aconsegueix el mínim per

$t=-\frac{f^{\prime }(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^{\prime }(x_k)}{f^{″}(x_k)}.$