El método de Bregman es un algoritmo iterativo para resolver ciertos problemas de optimización convexa que involucran regularización . [1] La versión original se debe a Lev M. Bregman , quien la publicó en 1967. [2]
El algoritmo es un método de acción de fila que accede a las funciones de restricción una por una y el método es particularmente adecuado para grandes problemas de optimización donde las restricciones se pueden enumerar de manera eficiente [ cita requerida ] . El algoritmo funciona particularmente bien para regularizadores como elnorma, donde converge muy rápidamente debido a un efecto de cancelación de error. [3]
Algoritmo
Para poder utilizar el método de Bregman, uno debe enmarcar el problema de interés como encontrar , dónde es una función regularizadora como . [3]
La distancia de Bregman se define como dónde pertenece al subdiferencial de a (que denotamos ). [3] [4] Uno realiza la iteración, con una constante a elegir por el usuario (y la minimización realizada por un algoritmo de optimización convexo ordinario), [3] , o, con elegido cada vez para ser miembro de . [4]
El algoritmo comienza con un par de variables primarias y duales. Luego, para cada restricción se realiza una proyección generalizada sobre su conjunto factible, actualizando tanto la variable dual de la restricción como todas las variables primarias para las cuales hay coeficientes distintos de cero en el gradiente de funciones de restricción. En caso de que el objetivo sea estrictamente convexo y todas las funciones de restricción sean convexas, el límite de esta proyección iterativa converge al par dual primario óptimo. [ cita requerida ]
En el caso de un problema de tipo búsqueda de base, el método de Bregman es equivalente al descenso de gradiente ordinario en el problema dual. [5] En este caso también se produce un efecto exacto del tipo de regularización; Si excede un cierto umbral, el valor óptimo de es precisamente la solución óptima de . [3] [5]
Aplicaciones
El método de Bregman o sus generalizaciones se pueden aplicar a:
- Eliminación de ruido o eliminación de imágenes borrosas [3] (incluida la eliminación de ruido de la variación total [4] )
- Reconstrucción de la imagen de RM [se necesita aclaración ] [3]
- Imágenes por resonancia magnética [1] [6]
- Radar [1]
- Imágenes hiperespectrales [7]
- Detección comprimida [5]
- Desviaciones mínimas absolutas o-regresión lineal regularizada [8]
- Selección de covarianza (aprendizaje de una matriz de covarianza escasa) [8]
- Completar la matriz [9]
- Minimización de riesgos estructurales [8]
Generalizaciones e inconvenientes
El método tiene vínculos con el método de multiplicadores y el método de doble ascenso (a través del llamado método de multiplicadores de dirección alterna de Bregman , [10] [7] generalizando el método de dirección alterna de multiplicadores [8] ) y existen múltiples generalizaciones.
Un inconveniente del método es que solo es demostrablemente convergente si la función objetivo es estrictamente convexa. En caso de que esto no pueda garantizarse, como en el caso de programas lineales o programas cuadráticos no estrictamente convexos, se han desarrollado métodos adicionales como los métodos de gradiente proximal . [ cita requerida ] En el caso del modelo de eliminación de ruido de imágenes de Rudin-Osher-Fatemi [ aclaración necesaria ] , el método de Bregman converge de manera probada. [11]
Algunas generalizaciones del método Bregman incluyen:
- Método del espacio de escala inversa [ aclaración necesaria ] [3]
- Bregman linealizado [3]
- Logística Bregman [3]
- Split Bregman [3]
Bregman linealizado
En el método de Bregman linealizado, se linealizan las funciones objetivo intermedias reemplazando el segundo término con (que se aproxima al segundo término cerca ) y agregando el término de penalización por una constante . El resultado es mucho más manejable desde el punto de vista computacional, especialmente en problemas del tipo de búsqueda de bases . [4] [5] En el caso de un problema de seguimiento de base genérico, se puede expresar la iteración como para cada componente , donde definimos . [4]
A veces, cuando se ejecuta el método de Bregman linealizado, hay períodos de "estancamiento" en los que la [ aclaración necesaria ] residual es casi constante. Para aliviar este problema, se puede usar el método de Bregman linealizado con patadas , donde esencialmente se detecta el comienzo de un período de estancamiento, luego se predice y se salta hasta el final. [4] [5]
Dado que el Bregman linealizado es matemáticamente equivalente al descenso de gradiente, se puede acelerar con métodos para acelerar el descenso de gradiente, como la búsqueda de líneas, L-BGFS , pasos de Barzilai-Borwein o el método Nesterov ; el último se ha propuesto como el método de Bregman linealizado acelerado . [5] [9]
Split Bregman
El método Split Bregman resuelve problemas de la forma , dónde y son ambos convexos, [4] particularmente problemas de la forma. [6] Empezamos reescribiéndolo como el problema de optimización restringido., luego relájate en dónde es una constante. Definiendo, se reduce el problema a uno que pueda resolverse con el algoritmo de Bregman ordinario. [4] [6]
El método Split Bregman se ha generalizado a la optimización sobre números complejos utilizando derivados de Wirtinger . [1]
Referencias
- ^ a b c d Xiong, Kai; Zhao, Guanghui; Shi, Guangming; Wang, Yingbin (12 de septiembre de 2019). "Un algoritmo de optimización convexa para la detección comprimida en un dominio complejo: el método de Bregman dividido de valores complejos" . Sensors (Basilea) (publicado el 18 de octubre de 2019). 19 (20): 4540. Bibcode : 2019Senso..19.4540X . doi : 10.3390 / s19204540 . PMC 6832202 . PMID 31635423 .
- ^ Bregman L. "Un método de relajación para encontrar un punto común de conjuntos convexos y su aplicación a problemas de optimización". Dokl. Akad. Nauk SSSR, v. 171, núm. 5, 1966, págs. 1019-1022. (Traducción al inglés: Soviet Math. Dokl., V. 7, 1966, págs. 1578-1581)
- ^ a b c d e f g h yo j k Yin, Wotao (8 de diciembre de 2009). "Los métodos de Bregman: revisión y nuevos resultados" (PDF) . Consultado el 16 de abril de 2021 .
- ^ a b c d e f g h Bush, Jacqueline (10 de junio de 2011). "Universidad de California, tesis senior de Santa Bárbara: algoritmos de Bregman" (PDF) . Universidad de California Santa Bárbara . Consultado el 16 de abril de 2021 .
- ^ a b c d e f Yin, Wotao (28 de mayo de 2009). "Análisis y generalizaciones del método de Bregman linealizado" (PDF) . Revista SIAM de Ciencias de la Imagen . 3 (4): 856–877. doi : 10.1137 / 090760350 . Consultado el 16 de abril de 2021 .
- ^ a b c Goldstein, Tom; Osher, Stanley (2 de junio de 2008). "El método Split Bregman para problemas regularizados L1" . SIAM J. Imaging Sci . 2 (2): 323–343. doi : 10.1137 / 080725891 . Consultado el 22 de abril de 2021 .
- ^ a b Jiang, Chunzhi (mayo de 2015). "Comparación de ADMM de penalización variable con el método de Bregman dividido en problemas de imágenes hiperespectrales" . Consultado el 20 de abril de 2021 .
- ^ a b c d Boyd, Stephen; Parikh, Neal; Chu, Eric; Peleato, Borja; Eckstein, Jonathan (19 de noviembre de 2010). "Optimización distribuida y aprendizaje estadístico mediante el método de dirección alterna de multiplicadores" . Fundamentos y Tendencias en Machine Learning . 3 : 1–122. CiteSeerX 10.1.1.722.981 . doi : 10.1561 / 2200000016 . Consultado el 20 de abril de 2021 .
- ^ a b Huang, Bo; Ma, Shiqian; Goldfarb, Donald (27 de junio de 2011). "Método de Bregman linealizado acelerado" (PDF) . Revista de Computación Científica . Plenum Press (publicado el 1 de febrero de 2013). 54 (2–3): 428–453. arXiv : 1106.5413 . doi : 10.1007 / s10915-012-9592-9 . ISSN 0885-7474 . Consultado el 22 de abril de 2021 .
- ^ Wang, Huahua; Banerjee, Arindam (13 de junio de 2013). "Método de multiplicadores de dirección alterna de Bregman" . NIPS'14: Actas de la 27ª Conferencia Internacional sobre Sistemas de Procesamiento de Información Neural . 2 : 2816–2824. arXiv : 1306.3203 . Consultado el 20 de abril de 2021 .
- ^ Jia, Rong-Qing (3 de octubre de 2008). "Análisis de convergencia del método de Bregman para el modelo variacional de eliminación de ruido de imágenes" (PDF) . Análisis armónico computacional y aplicado (publicado en noviembre de 2009). 27 (3): 367–379. doi : 10.1016 / j.acha.2009.05.002 . Consultado el 22 de abril de 2021 .