El método de Broyden

Método de búsqueda de raíces de Quasi-Newton para el caso multivariable

En el análisis numérico, el método de Broyden es un método cuasi-newtoniano para hallar raíces en k variables. Fue descrito originalmente por CG Broyden en 1965. ^[1]

El método de Newton para resolver f ( x ) = 0 utiliza la matriz jacobiana , J , en cada iteración. Sin embargo, calcular esta matriz jacobiana puede ser una operación difícil y costosa; para problemas grandes como los que implican resolver las ecuaciones de Kohn-Sham en mecánica cuántica, el número de variables puede ser de cientos de miles. La idea detrás del método de Broyden es calcular la matriz jacobiana completa como máximo solo en la primera iteración y hacer actualizaciones de rango uno en las demás iteraciones.

En 1979, Gay demostró que cuando el método de Broyden se aplica a un sistema lineal de tamaño n × n , termina en 2 n pasos, ^[2] aunque, como todos los métodos cuasi-Newton, puede no converger para sistemas no lineales.

Descripción del método

Solución de ecuaciones no lineales de una sola variable

En el método secante , reemplazamos la primera derivada f ′ en x _n con la aproximación de diferencias finitas :

${\displaystyle f'(x_{n})\simeq {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}},}$

y proceder de manera similar al método de Newton :

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f^{\prime }(x_{n})}}}$

donde n es el índice de iteración.

Resolver un sistema de ecuaciones no lineales

Consideremos un sistema de k ecuaciones no lineales con incógnitas ${\displaystyle k}$

${\displaystyle \mathbf {f} (\mathbf {x} )=\mathbf {0} ,}$

donde f es una función vectorial del vector x

${\displaystyle \mathbf {x} =(x_{1},x_{2},x_{3},\dotsc ,x_{k}),}$

${\displaystyle \mathbf {f} (\mathbf {x} )={\big (}f_{1}(x_{1},x_{2},\dotsc ,x_{k}),f_{2}(x_{1},x_{2},\dotsc ,x_{k}),\dotsc ,f_{k}(x_{1},x_{2},\dotsc ,x_{k}){\big )}.}$

Para estos problemas, Broyden ofrece una variación del método unidimensional de Newton, reemplazando la derivada con una matriz jacobiana aproximada J. La matriz jacobiana aproximada se determina iterativamente basándose en la ecuación secante , una aproximación de diferencias finitas:

${\displaystyle \mathbf {J} _{n}(\mathbf {x} _{n}-\mathbf {x} _{n-1})\simeq \mathbf {f} (\mathbf {x} _{n})-\mathbf {f} (\mathbf {x} _{n-1}),}$

donde n es el índice de iteración. Para mayor claridad, defina

${\displaystyle \mathbf {f} _{n}=\mathbf {f} (\mathbf {x} _{n}),}$

${\displaystyle \Delta \mathbf {x} _{n}=\mathbf {x} _{n}-\mathbf {x} _{n-1},}$

${\displaystyle \Delta \mathbf {f} _{n}=\mathbf {f} _{n}-\mathbf {f} _{n-1},}$

Por lo tanto, lo anterior puede reescribirse como

${\displaystyle \mathbf {J} _{n}\Delta \mathbf {x} _{n}\simeq \Delta \mathbf {f} _{n}.}$

La ecuación anterior está subdeterminada cuando k es mayor que uno. Broyden sugirió utilizar la estimación más reciente de la matriz jacobiana, J _{n −1} , y luego mejorarla exigiendo que la nueva forma sea una solución a la ecuación secante más reciente y que haya una modificación mínima de J _{n −1} :

${\displaystyle \mathbf {J} _{n}=\mathbf {J} _{n-1}+{\frac {\Delta \mathbf {f} _{n}-\mathbf {J} _{n-1}\Delta \mathbf {x} _{n}}{\|\Delta \mathbf {x} _{n}\|^{2}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }.}$

Esto minimiza la norma de Frobenius.

${\displaystyle \|\mathbf {J} _{n}-\mathbf {J} _{n-1}\|_{\rm {F}}.}$

Luego se actualizan las variables utilizando el jacobiano aproximado, lo que se llama un enfoque cuasi-Newton.

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\alpha \mathbf {J} _{n}^{-1}\mathbf {f} (\mathbf {x} _{n}).}$

Si este es el paso de Newton completo, se suele utilizar un método de búsqueda de línea o de región de confianza para controlar . El jacobiano inicial se puede tomar como una matriz unitaria diagonal, aunque lo más común es escalarlo en función del primer paso. ^[3] Broyden también sugirió utilizar la fórmula de Sherman-Morrison ^[4] para actualizar directamente la inversa de la matriz jacobiana aproximada: ${\displaystyle \alpha =1}$ ${\displaystyle \alpha }$

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}.}$

Este primer método se conoce comúnmente como el "método del buen Broyden".

Se puede obtener una técnica similar utilizando una modificación ligeramente diferente de J _{n −1} . Esto produce un segundo método, el llamado "método del mal Broyden":

${\displaystyle \mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\|\Delta \mathbf {f} _{n}\|^{2}}}\Delta \mathbf {f} _{n}^{\mathrm {T} }.}$

Esto minimiza una norma de Frobenius diferente

${\displaystyle \|\mathbf {J} _{n}^{-1}-\mathbf {J} _{n-1}^{-1}\|_{\rm {F}}.}$

En su artículo original, Broyden no pudo lograr que el método incorrecto funcionara, pero hay casos en los que sí lo hace ^[5] para los cuales se han propuesto varias explicaciones. ^{[6] [7]} Se han sugerido muchos otros esquemas cuasi-Newton en optimización, como el BFGS , donde se busca un máximo o mínimo al encontrar ceros de las primeras derivadas (ceros del gradiente en múltiples dimensiones). El jacobiano del gradiente se llama hessiano y es simétrico, lo que agrega más restricciones a su aproximación.

La clase de métodos Broyden

Además de los dos métodos descritos anteriormente, Broyden definió una clase más amplia de métodos relacionados. ^{[1] : 578} En general, los métodos de la clase Broyden se dan en la forma ^{[8] : 150} donde y y para cada . La elección de determina el método. $${\displaystyle \mathbf {J} _{k+1}=\mathbf {J} _{k}-{\frac {\mathbf {J} _{k}s_{k}s_{k}^{T}\mathbf {J} _{k}}{s_{k}^{T}\mathbf {J} _{k}s_{k}}}+{\frac {y_{k}y_{k}^{T}}{y_{k}^{T}s_{k}}}+\phi _{k}\left(s_{k}^{T}\mathbf {J} _{k}s_{k}\right)v_{k}v_{k}^{T},}$$ ${\displaystyle y_{k}:=\mathbf {f} (\mathbf {x} _{k+1})-\mathbf {f} (\mathbf {x} _{k}),}$ ${\displaystyle s_{k}:=\mathbf {x} _{k+1}-\mathbf {x} _{k},}$ $${\displaystyle v_{k}=\left[{\frac {y_{k}}{y_{k}^{T}s_{k}}}-{\frac {\mathbf {J} _{k}s_{k}}{s_{k}^{T}\mathbf {J} _{k}s_{k}}}\right],}$$ ${\displaystyle \phi _{k}\in \mathbb {R} }$ ${\displaystyle k=1,2,...}$ ${\displaystyle \phi _{k}}$

Otros autores han introducido otros métodos en la clase Broyden.

• El método Davidon–Fletcher–Powell (DFP) , que es el único miembro de esta clase que se publicó antes de los dos métodos definidos por Broyden. ^{[1] : 582} Para el método DFP, . ^{[8] : 150} ${\displaystyle \phi _{k}=1}$
• El método iterativo de Anderson, que utiliza un enfoque de mínimos cuadrados para el jacobiano. ^[9]
• Algoritmo de Schubert o algoritmo de Broyden disperso: una modificación para matrices jacobianas dispersas. ^[10]
• El enfoque de Pulay, a menudo utilizado en la teoría funcional de la densidad . ^{[11] [12]}
• Un método de memoria limitada de Srivastava para el problema de búsqueda de raíces que solo utiliza unas pocas iteraciones recientes. ^[13]
• Klement (2014) – utiliza menos iteraciones para resolver algunos sistemas. ^{[14] [15]}
• Métodos multisecantes para problemas de teoría del funcional de la densidad ^{[7] [16]}

Véase también

• Método de la secante
• El método de Newton
• Método de cuasi-Newton
• El método de Newton en optimización
• Fórmula de Davidon-Fletcher-Powell
• Método de Broyden-Fletcher-Goldfarb-Shanno (BFGS)

Referencias

1. Broyden, CG (1965). "Una clase de métodos para resolver ecuaciones simultáneas no lineales". Matemáticas de la computación . 19 (92). Sociedad Matemática Americana: 577–593. doi : 10.1090/S0025-5718-1965-0198670-6 . JSTOR  2003941.
2. Gay, DM (1979). "Algunas propiedades de convergencia del método de Broyden". Revista SIAM sobre análisis numérico . 16 (4). SIAM: 623–630. doi :10.1137/0716047.
3. Shanno, DF; Phua, Kang-Hoh (1978). "Condicionamiento matricial y optimización no lineal". Programación matemática . 14 (1): 149–160. doi :10.1007/BF01588962. ISSN  0025-5610.
4. Sherman, Jack; Morrison, Winifred J. (1950). "Ajuste de una matriz inversa correspondiente a un cambio en un elemento de una matriz dada". Anales de estadística matemática . 21 (1): 124–127. doi :10.1214/aoms/1177729893. ISSN  0003-4851.
5. Kvaalen, Eric (1991). "Un método de Broyden más rápido". BIT Numerical Mathematics . 31 (2). SIAM: 369–372. doi :10.1007/BF01931297.
6. Martínez, José Mario (2000). "Métodos prácticos cuasi-Newton para la resolución de sistemas no lineales". Revista de Matemática Computacional y Aplicada . 124 (1–2): 97–121. doi :10.1016/s0377-0427(00)00434-9. ISSN  0377-0427.
7. Marks, LD; Luke, DR (2008). "Mezcla robusta para cálculos mecánicos cuánticos ab initio". Physical Review B . 78 (7). doi :10.1103/physrevb.78.075114. ISSN  1098-0121.
8. Nocedal, Jorge; Wright, Stephen J. (2006). Optimización numérica. Springer Series en Investigación de Operaciones e Ingeniería Financiera. Springer Nueva York. doi :10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1.
9. Anderson, Donald G. (1965). "Procedimientos iterativos para ecuaciones integrales no lineales". Revista de la ACM . 12 (4): 547–560. doi :10.1145/321296.321305. ISSN  0004-5411.
10. Schubert, LK (1970). "Modificación de un método cuasi-Newton para ecuaciones no lineales con un jacobiano disperso". Matemáticas de la computación . 24 (109): 27–30. doi : 10.1090/S0025-5718-1970-0258276-9 . ISSN  0025-5718.
11. Pulay, Péter (1980). "Aceleración de la convergencia de secuencias iterativas. El caso de la iteración scf". Chemical Physics Letters . 73 (2): 393–398. doi :10.1016/0009-2614(80)80396-4.
12. Kresse, G.; Furthmüller, J. (1996). "Esquemas iterativos eficientes para cálculos de energía total ab initio utilizando un conjunto base de ondas planas". Physical Review B . 54 (16): 11169–11186. doi :10.1103/PhysRevB.54.11169. ISSN  0163-1829.
13. Srivastava, GP (1984). "Método de Broyden para la aceleración de convergencia de campo autoconsistente". Journal of Physics A: Mathematical and General . 17 (6): L317–L321. doi :10.1088/0305-4470/17/6/002. ISSN  0305-4470.
14. Klement, Jan (2014). "Sobre el uso de algoritmos cuasi-Newton de la clase Broyden para la correlación entre modelos y pruebas". Revista de tecnología y gestión aeroespacial . 6 (4): 407–414. doi : 10.5028/jatm.v6i4.373 . ISSN  2175-9146.
15. "Métodos de la clase Broyden – Intercambio de archivos – MATLAB Central". www.mathworks.com . Consultado el 4 de febrero de 2016 .
16. Woods, ND; Payne, MC; Hasnip, PJ (2019). "Cálculo del campo autoconsistente en la teoría funcional de la densidad de Kohn-Sham". Journal of Physics: Condensed Matter . 31 (45): 453001. doi :10.1088/1361-648X/ab31c0. ISSN  0953-8984.

Lectura adicional

• Dennis, JE ; Schnabel, Robert B. (1983). Métodos numéricos para optimización sin restricciones y ecuaciones no lineales . Englewood Cliffs: Prentice Hall. págs. 168–193. ISBN 0-13-627216-9.
• Fletcher, R. (1987). Métodos prácticos de optimización (segunda edición). Nueva York: John Wiley & Sons. pp. 44–79. ISBN 0-471-91547-5.
• Kelley, CT (1995). Métodos iterativos para ecuaciones lineales y no lineales. Sociedad de Matemáticas Industriales y Aplicadas. doi :10.1137/1.9781611970944. ISBN 978-0-89871-352-7.

Enlaces externos

• Explicación básica y sencilla: La historia del arquero ciego