Vés al contingut

Mètode de Newton (optimització)

De la Viquipèdia, l'enciclopèdia lliure
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.[1] 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.[2]

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.[3]

Donada una funció doblement diferenciable , busquem resoldre el problema d'optimització [4]

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

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

s'aconsegueix el mínim per

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

Referències

[modifica]
  1. Polyak, B. T. «Newton’s method and its use in optimization» (en anglès). European Journal of Operational Research, 181, 3, 16-09-2007, pàg. 1086–1096. DOI: 10.1016/j.ejor.2005.06.076. ISSN: 0377-2217.
  2. Alto, Valentina. «Optimization algorithms: the Newton Method» (en anglès). https://medium.com,+31-10-2019.+[Consulta: 3 gener 2023].
  3. «Calculus I - Newton's Method» (en anglès). https://tutorial.math.lamar.edu.+[Consulta: 3 gener 2023].
  4. «Newton's Method» (en anglès). https://calcworkshop.com.+[Consulta: 3 gener 2023].