La representación compacta de una matriz cuasi-Newton para la hessiana inversa o hessiana directa de una función objetivo no lineal expresa una secuencia de actualizaciones recursivas de la matriz de rango 1 o rango 2 como una actualización de rango o rango de una matriz inicial. [1] [2]
Debido a que se deriva de actualizaciones cuasi-Newton, utiliza diferencias de iteraciones y gradientes en su definición . En particular, para o las matrices rectangulares y los sistemas simétricos cuadrados dependen de la y definen las representaciones cuasi-Newton
Aplicaciones
Debido a la descomposición matricial especial, la representación compacta se implementa en software de optimización de última generación. [3] [4] [5] [6]
Cuando se combina con técnicas de memoria limitada, es una técnica popular para la optimización restringida con gradientes. [7]
Las operaciones de álgebra lineal se pueden realizar de manera eficiente, como productos matriz-vector , soluciones o descomposiciones propias . Se puede combinar con técnicas de búsqueda de línea y región de confianza , y la representación se ha desarrollado para muchas actualizaciones cuasi-Newton. Por ejemplo, el producto matriz-vector con el hessiano cuasi-Newton directo y un vector arbitrario es:
Fondo
En el contexto del método GMRES , Walker [8]
demostró que un producto de transformaciones de Householder (una identidad más rango 1) se puede expresar como una fórmula matricial compacta. Esto condujo a la derivación de una expresión matricial explícita para el producto de matrices identidad más rango 1. [7]
Específicamente, para y cuando
el producto de actualizaciones de rango 1 a la identidad es
La actualización BFGS se puede expresar en términos de productos de los , que tienen una fórmula matricial compacta. Por lo tanto, la recursión BFGS puede explotar estas representaciones de matriz de bloques
Actualizaciones recursivas cuasi-Newton
Una familia paramétrica de actualizaciones cuasi-Newton incluye muchas de las fórmulas más conocidas. [9] Para vectores arbitrarios y tales que y fórmulas de actualización recursivas generales para las estimaciones hessianas inversas y directas son
Al realizar elecciones específicas para los vectores de parámetros y se recuperan métodos bien conocidos.
Representaciones compactas
Recopilando los vectores de actualización de las fórmulas recursivas en matrices, defina
triangular superior
triangular inferior
y diagonal
Con estas definiciones, en Brust se han desarrollado las representaciones compactas de las actualizaciones generales de rango 2 en ( 2 ) y ( 3 ) (incluidas las conocidas actualizaciones cuasi-Newton de la Tabla 1): [11]
y la fórmula para el hessiano directo es
Por ejemplo, cuando la representación en ( 4 ) es la fórmula compacta para la recursión BFGS en ( 1 ).
Representaciones específicas
Antes del desarrollo de las representaciones compactas de ( 2 ) y ( 3 ), se descubrieron representaciones equivalentes para la mayoría de las actualizaciones conocidas (ver Tabla 1).
BFGS
Junto con la representación SR1, la representación compacta BFGS (Broyden-Fletcher-Goldfarb-Shanno) fue la primera fórmula compacta conocida. [7] En particular, la representación inversa está dada por
La representación compacta SR1 (Rango simétrico 1) se propuso por primera vez en [7] . Utilizando las definiciones de y de arriba, la fórmula hessiana inversa se da por
La hessiana directa se obtiene mediante la identidad de Sherman-Morrison-Woodbury y tiene la forma
Manuscrito
El método de la secante simétrica multipunto (MSS) es un método que tiene como objetivo satisfacer múltiples ecuaciones secantes. La fórmula de actualización recursiva fue desarrollada originalmente por Burdakov. [12] La representación compacta para la hessiana directa se derivó en [13]
Otra representación compacta equivalente para la matriz MSS se deriva reescribiéndola
en términos de . [14]
La representación inversa se puede obtener mediante la aplicación de la identidad de Sherman-Morrison-Woodbury.
DFP
Dado que la actualización de DFP (Davidon Fletcher Powell) es dual de la fórmula BFGS (es decir, intercambiando y en la actualización de BFGS ), la representación compacta para DFP se puede obtener inmediatamente a partir de la de BFGS. [15]
BSP
La representación compacta PSB (Powell-Symmetric-Broyden) fue desarrollada para la aproximación hessiana directa. [16] Es equivalente a sustituir en ( 5 )
BFGS estructurado
Para los problemas de optimización estructurada en los que la función objetivo se puede descomponer en dos partes , donde
se conocen los gradientes y el hessiano de pero solo se conoce el gradiente de, existen fórmulas BFGS estructuradas. La representación compacta de estos métodos tiene la forma general de ( 5 ), con y específicos . [17]
BFGS reducido
La representación compacta reducida (RCR) de BFGS es para optimización lineal con restricciones de igualdad , donde está subdeterminado . Además de las matrices, la RCR también almacena las proyecciones de los sobre el espacio nulo de
El uso más común de las representaciones compactas es para la configuración de memoria limitada donde denota el parámetro de memoria, con valores típicos alrededor de (ver, por ejemplo, [18] [7] ). Entonces, en lugar de almacenar el historial de todos los vectores, uno limita esto a los vectores más recientes y posiblemente o . Además, típicamente la inicialización se elige como un múltiplo adaptativo de la identidad , con y . Los métodos de memoria limitada se utilizan con frecuencia para problemas a gran escala con muchas variables (es decir, pueden ser grandes), en los que las matrices de memoria limitada
y (y posiblemente ) son altas y muy delgadas: y .
^ Nocedal, J.; Wright, SJ (2006). Optimización numérica. Springer Series in Operations Research and Financial Engineering. Springer Nueva York, NY. doi :10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1.
^ Brust, JJ (2018). Métodos de regiones de confianza cuasi-Newton a gran escala: solucionadores de alta precisión, inicializaciones densas y extensiones (tesis doctoral). Universidad de California, Merced.
^ ab Byrd, RH; Nocedal, J; Waltz, RA (2006). "KNITRO: Un paquete integrado para optimización no lineal". Optimización no lineal a gran escala . Optimización no convexa y sus aplicaciones. Vol. 83. En: Di Pillo, G., Roma, M. (eds) Optimización no lineal a gran escala. Optimización no convexa y sus aplicaciones, vol. 83.: Springer, Boston, MA. págs. 35-59. doi :10.1007/0-387-30065-1_4. ISBN978-0-387-30063-4.{{cite book}}: CS1 maint: location (link)
^ Zhu, C.; Byrd, RH; Lu, P.; Nocedal, J. (1997). "Algoritmo 778: L-BFGS-B: subrutinas Fortran para optimización a gran escala con restricciones de límites". ACM Transactions on Mathematical Software (TOMS) . 23 (4): 550-560. doi :10.1145/279232.279236.
^ Brust, J.; Burdakov, O.; Erway, J.; Marcia, R. (2022). "Algoritmo 1030: SC-SR1: software MATLAB para métodos de región de confianza SR1 de memoria limitada". ACM Transactions on Mathematical Software (TOMS) . 48 (4): 1-33. doi :10.1145/3550269.
^ Wächter, A.; Biegler, LT (2006). "Sobre la implementación de un algoritmo de búsqueda de línea con filtro de punto interior para programación no lineal a gran escala". Programación matemática . 106 : 25-57. doi :10.1007/s10107-004-0559-y.
^ abcde Byrd, RH; Nocedal, J.; Schnabel, RB (1994). "Representaciones de matrices cuasi-Newton y su uso en métodos de memoria limitada". Programación matemática . 63 (4): 129–156. doi :10.1007/BF01582063. S2CID 5581219.
^ Walker, HF (1988). "Implementación del método GMRES utilizando transformaciones de Householder". Revista SIAM sobre computación científica y estadística . 9 (1): 152–163. doi :10.1137/0909010.
^ Dennis, Jr, JE; Moré, JJ (1977). "Métodos, motivación y teoría quasi-newtoniana". SIAM Review . 19 (1): 46-89. doi :10.1137/1019005. hdl :1813/6056.{{cite journal}}: CS1 maint: multiple names: authors list (link)
^
^ Brust, JJ (2024). "Representaciones compactas útiles para el ajuste de datos". arXiv : 2403.12206 [math.OC].
^ Burdakov, OP (1983). "Métodos del tipo secante para sistemas de ecuaciones con matriz jacobiana simétrica". Análisis funcional numérico y optimización . 6 (2): 1–18. doi :10.1080/01630568308816160.
^ Burdakov, OP; Martínez, JM; Pilotta, EA (2002). "Un método secante simétrico multipunto de memoria limitada para optimización con restricciones de límites". Annals of Operations Research . 117 : 51–70. doi :10.1023/A:1021561204463.
^ Brust, JJ; Erway, JB; Marcia, RF (2024). "Métodos de regiones de confianza que cambian de forma utilizando matrices secantes simétricas multipunto". Optimization Methods and Software : 1–18. arXiv : 2209.12057 . doi :10.1080/10556788.2023.2296441.
^ Erway, JB; Jain, V.; Marcia, RF (2013). Sistemas DFP de memoria limitada desplazada . En 2013, Conferencia Asilomar sobre señales, sistemas y computadoras. IEEE. págs. 1033–1037.
^ Kanzow, C.; Steck, D. (2023). "Regularización de métodos cuasi-Newton de memoria limitada para minimización no convexa a gran escala". Computación de programación matemática . 15 (3): 417–444. doi :10.1007/s12532-023-00238-4.
^ Brust, J. J; Di, Z.; Leyffer, S.; Petra, CG (2021). "Representaciones compactas de matrices BFGS estructuradas". Optimización computacional y aplicaciones . 80 (1): 55–88. doi :10.1007/s10589-021-00297-0.
^ ab Brust, J. J; Marcia, RF; Petra, CG; Saunders, MA (2022). "Optimización a gran escala con restricciones de igualdad lineal utilizando representación compacta reducida". Revista SIAM de Computación Científica . 44 (1): A103–A127. arXiv : 2101.11048 . Código Bibliográfico :2022SJSC...44A.103B. doi :10.1137/21M1393819.
^ "Algoritmos recopilados del ACM (CALGO)". calgo.acm.org .
^ "TOMS Alg. 1030". calgo.acm.org/1030.zip .
^ Zhu, C.; Byrd, Richard H.; Lu, Peihuang; Nocedal, Jorge (1997). "L-BFGS-B: Algoritmo 778: L-BFGS-B, rutinas FORTRAN para optimización restringida a gran escala". ACM Transactions on Mathematical Software . 23 (4): 550–560. doi : 10.1145/279232.279236 . S2CID 207228122.