El algoritmo de Gauss-Newton se utiliza para resolver problemas de mínimos cuadrados no lineales . Es una modificación del método de Newton para encontrar un mínimo de una función . A diferencia del método de Newton, el algoritmo de Gauss-Newton sólo se puede utilizar para minimizar una suma de valores de funciones al cuadrado, pero tiene la ventaja de que no se requieren segundas derivadas, que pueden ser difíciles de calcular. [1]
Los problemas de mínimos cuadrados no lineales surgen, por ejemplo, en la regresión no lineal , donde los parámetros en un modelo se buscan de manera que el modelo esté en buen acuerdo con las observaciones disponibles.
El método lleva el nombre de los matemáticos Carl Friedrich Gauss e Isaac Newton , y apareció por primera vez en la obra de Gauss de 1809 Theoria motus corporum coelestium in sectionibus conicis solem ambientum . [2]
Descripción
Dadas m funciones r = ( r 1 ,…, r m ) (a menudo llamadas residuales) de n variables β = ( β 1 ,…, β n ), con m ≥ n , el algoritmo de Gauss-Newton encuentra iterativamente el valor de la variables que minimizan la suma de cuadrados [3]
Comenzando con una suposición inicial para el mínimo, el método procede por las iteraciones
donde, si r y β son vectores columna , las entradas de la matriz jacobiana son
y el simbolo denota la matriz transpuesta .
Si m = n , la iteración se simplifica a
que es una generalización directa del método de Newton en una dimensión.
En el ajuste de datos, donde el objetivo es encontrar los parámetros β tales que una función de modelo dada y = f ( x , β ) se ajuste mejor a algunos puntos de datos ( x i , y i ), las funciones r i son los residuos :
Entonces, el método de Gauss-Newton se puede expresar en términos del jacobiano J f de la función f como
Tenga en cuenta que es el pseudoinverso izquierdo de.
Notas
La suposición m ≥ n en el enunciado del algoritmo es necesaria, ya que de lo contrario la matriz J r T J r no es invertible y las ecuaciones normales no se pueden resolver (al menos de forma única).
El algoritmo de Gauss-Newton se puede derivar aproximando linealmente el vector de funciones r i . Usando el teorema de Taylor , podemos escribir en cada iteración:
con . La tarea de encontrar Δ minimizando la suma de cuadrados del lado derecho; es decir,
es un problema lineal de mínimos cuadrados , que se puede resolver explícitamente, dando las ecuaciones normales en el algoritmo.
Las ecuaciones normales son n ecuaciones lineales simultáneas en los incrementos desconocidos Δ. Pueden resolverse en un solo paso, utilizando la descomposición de Cholesky o, mejor, la factorización QR de J r . Para sistemas grandes, un método iterativo , como el método de gradiente conjugado , puede ser más eficiente. Si hay una dependencia lineal entre las columnas de J r , las iteraciones fallarán, ya que J r T J r se vuelve singular.
Cuándo es complejo : C nC debe usarse la forma conjugada:.
Ejemplo
En este ejemplo, el algoritmo de Gauss-Newton se utilizará para ajustar un modelo a algunos datos minimizando la suma de cuadrados de errores entre los datos y las predicciones del modelo.
En un experimento de biología que estudia la relación entre la concentración de sustrato [ S ] y la velocidad de reacción en una reacción mediada por enzimas, se obtuvieron los datos de la siguiente tabla.
I 1 2 3 4 5 6 7 [ S ] 0,038 0,194 0,425 0,626 1.253 2.500 3.740 Velocidad 0,050 0,127 0,094 0.2122 0.2729 0.2665 0.3317
Se desea encontrar una curva (función modelo) de la forma
que se ajuste mejor a los datos en el sentido de mínimos cuadrados, con los parámetros y estar determinado.
Denotamos por y los valores de [ S ] y tasa respectivamente, con. Dejar y . Lo encontraremos y tal que la suma de los cuadrados de los residuos
se minimiza.
El jacobiano del vector de residuos con respecto a las incógnitas es un matriz con el -th fila que tiene las entradas
Comenzando con las estimaciones iniciales de y , después de cinco iteraciones del algoritmo de Gauss-Newton, los valores óptimos y son obtenidas. La suma de los cuadrados de los residuos disminuyó del valor inicial de 1,445 a 0,00784 después de la quinta iteración. El gráfico de la figura de la derecha muestra la curva determinada por el modelo para los parámetros óptimos con los datos observados.
Propiedades de convergencia
Se puede demostrar [4] que el Δ incremento es una dirección de descenso de S , y, si las converge el algoritmo, entonces el límite es un punto estacionario de S . Sin embargo, la convergencia no está garantizada, ni siquiera la convergencia local como en el método de Newton , o la convergencia en las condiciones habituales de Wolfe. [5]
La tasa de convergencia del algoritmo de Gauss-Newton puede aproximarse a la cuadrática . [6] El algoritmo puede converger lentamente o no converger en absoluto si la estimación inicial está lejos del mínimo o de la matrizestá mal acondicionado . Por ejemplo, considere el problema con ecuaciones y variable, dada por
El óptimo está en . (En realidad, el óptimo está en por , porque , pero .) Si , entonces el problema es lineal y el método encuentra el óptimo en una iteración. Si | λ | <1, entonces el método converge linealmente y el error disminuye asintóticamente con un factor | λ | en cada iteración. Sin embargo, si | λ | > 1, entonces el método ni siquiera converge localmente. [7]
Derivación del método de Newton
En lo que sigue, el algoritmo de Gauss-Newton se derivará del método de Newton para la optimización de funciones mediante una aproximación. Como consecuencia, la tasa de convergencia del algoritmo de Gauss-Newton puede ser cuadrática bajo ciertas condiciones de regularidad. En general (en condiciones más débiles), la tasa de convergencia es lineal. [8]
La relación de recurrencia para el método de Newton para minimizar una función S de parámetros es
donde g denota el vector gradiente de S , y H indica la matriz de Hesse de S .
Desde , el gradiente viene dado por
Los elementos del hessiano se calculan diferenciando los elementos del gradiente, , con respecto a :
El método de Gauss-Newton se obtiene ignorando los términos de la derivada de segundo orden (el segundo término en esta expresión). Es decir, la arpillera se aproxima a
dónde son entradas del Jacobian J r . El gradiente y el hessiano aproximado se pueden escribir en notación matricial como
Estas expresiones se sustituyen en la relación de recurrencia anterior para obtener las ecuaciones operativas
La convergencia del método de Gauss-Newton no está garantizada en todos los casos. La aproximación
que debe mantenerse para poder ignorar los términos de la derivada de segundo orden puede ser válido en dos casos, para los cuales se espera una convergencia: [9]
- Los valores de la función son pequeñas en magnitud, al menos alrededor del mínimo.
- Las funciones son solo "levemente" no lineales, de modo que es de magnitud relativamente pequeña.
Versiones mejoradas
Con el método de Gauss-Newton, la suma de los cuadrados de los residuos S puede que no disminuya en cada iteración. Sin embargo, dado que Δ es una dirección de descenso, a menos que es un punto estacionario, sostiene que para todo lo suficientemente pequeño . Por lo tanto, si ocurre divergencia, una solución es emplear una fracción del vector de incremento Δ en la fórmula de actualización:
- .
En otras palabras, el vector de la subasta es demasiado largo, pero todavía señala "cuesta abajo", por lo que ir sólo una parte de la forma en que va a disminuir la función objetivo S . Un valor óptimo parase puede encontrar utilizando un algoritmo de búsqueda de líneas , es decir, la magnitud dese determina encontrando el valor que minimiza S , usualmente usando un método de búsqueda directa en el intervaloo una búsqueda de línea de retroceso como la búsqueda de Armijo-line . Típicamente,debe elegirse de modo que satisfaga las condiciones de Wolfe o las de Goldstein . [10]
En los casos en los que la dirección del vector de desplazamiento es tal que la fracción óptima α es cercana a cero, un método alternativo para manejar la divergencia es el uso del algoritmo de Levenberg-Marquardt , un método de región de confianza . [3] Las ecuaciones normales se modifican de tal manera que el vector de incremento gira hacia la dirección de descenso más pronunciado ,
donde D es una matriz diagonal positiva. Tenga en cuenta que cuando D es la matriz identidad I y, luego , por lo tanto, la dirección de Δ se acerca a la dirección del gradiente negativo.
El llamado parámetro de Marquardt también se puede optimizar mediante una búsqueda de línea, pero esto es ineficiente, ya que el vector de desplazamiento debe recalcularse cada vez está cambiado. Una estrategia más eficiente es la siguiente: Cuando se produce divergencia, aumente el parámetro Marquardt hasta que haya una disminución en S . Luego, retenga el valor de una iteración a la siguiente, pero reduzca si es posible hasta que se alcance un valor de corte, cuando el parámetro de Marquardt se puede establecer en cero; la minimización de S se convierte entonces en una minimización estándar de Gauss-Newton.
Optimización a gran escala
Para la optimización a gran escala, el método de Gauss-Newton es de especial interés porque a menudo (aunque ciertamente no siempre) es cierto que la matriz es más escasa que la arpillera aproximada. En tales casos, el cálculo del paso en sí mismo normalmente deberá realizarse con un método iterativo aproximado apropiado para problemas grandes y dispersos, como el método de gradiente conjugado .
Para que este tipo de enfoque funcione, se necesita al menos un método eficiente para calcular el producto.
para algún vector p . Con almacenamiento de matriz escasa , en general es práctico almacenar las filas deen forma comprimida (por ejemplo, sin entradas cero), lo que dificulta el cálculo directo del producto anterior debido a la transposición. Sin embargo, si uno define c i como la fila i de la matriz, se cumple la siguiente relación simple:
para que cada fila contribuya de forma aditiva e independiente al producto. Además de respetar una práctica estructura de almacenamiento escasa, esta expresión es muy adecuada para cálculos paralelos . Tenga en cuenta que cada fila c i es el gradiente del correspondiente r i residual ; Teniendo esto en cuenta, la fórmula anterior enfatiza el hecho de que los residuos contribuyen al problema independientemente unos de otros.
Algoritmos relacionados
En un método cuasi-Newton , como el debido a Davidon, Fletcher y Powell o Broyden-Fletcher-Goldfarb-Shanno ( método BFGS ) una estimación de la hessiana completa se construye numéricamente usando primeras derivadas sólo para que después de n ciclos de refinamiento el método se aproxime mucho al método de Newton en el desempeño. Tenga en cuenta que los métodos cuasi-Newton pueden minimizar las funciones generales de valor real, mientras que Gauss-Newton, Levenberg-Marquardt, etc. sólo se ajusta a problemas de mínimos cuadrados no lineales.
Otro método para resolver problemas de minimización utilizando solo las primeras derivadas es el descenso de gradiente . Sin embargo, este método no tiene en cuenta las segundas derivadas ni siquiera aproximadamente. En consecuencia, es muy ineficiente para muchas funciones, especialmente si los parámetros tienen interacciones fuertes.
Notas
- ^ Mittelhammer, Ron C .; Miller, Douglas J .; Juez, George G. (2000). Fundamentos econométricos . Cambridge: Cambridge University Press. págs. 197-198. ISBN 0-521-62394-4.
- ^ Floudas, Christodoulos A .; Pardalos, Panos M. (2008). Enciclopedia de Optimización . Saltador. pag. 1130. ISBN 9780387747583.
- ↑ a b Björck (1996)
- ^ Björck (1996), p. 260.
- ^ Mascarenhas (2013), "The divergence of the BFGS and Gauss Newton Methods", Programación matemática , 147 (1): 253–276, arXiv : 1309.7922 , doi : 10.1007 / s10107-013-0720-6
- ^ Björck (1996), p. 341, 342.
- ^ Fletcher (1987), p. 113.
- ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 4 de agosto de 2016 . Consultado el 25 de abril de 2014 .CS1 maint: copia archivada como título ( enlace )
- ^ Nocedal (1999), p. 259.
- ^ Nocedal, Jorge. (1999). Optimización numérica . Wright, Stephen J., 1960-. Nueva York: Springer. ISBN 0387227423. OCLC 54849297 .
Referencias
- Björck, A. (1996). Métodos numéricos para problemas de mínimos cuadrados . SIAM, Filadelfia. ISBN 0-89871-360-9.
- Fletcher, Roger (1987). Métodos prácticos de optimización (2ª ed.). Nueva York: John Wiley & Sons . ISBN 978-0-471-91547-8..
- Nocedal, Jorge; Wright, Stephen (1999). Optimización numérica . Nueva York: Springer. ISBN 0-387-98793-2.
enlaces externos
- Probabilidad, estadística y estimación El algoritmo se detalla y se aplica al experimento de biología discutido como ejemplo en este artículo (página 84 con las incertidumbres sobre los valores estimados).
Implementaciones
- Artelys Knitro es un solucionador no lineal con una implementación del método Gauss-Newton. Está escrito en C y tiene interfaces para C ++ / C # / Java / Python / MATLAB / R.