Método Bregman

Algoritmo iterativo para resolver ciertos problemas de optimización convexa que involucran regularización

El método 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 por filas que accede a las funciones de restricción una por una y 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 la norma, donde converge muy rápidamente debido a un efecto de cancelación de errores. ^[3] ${\displaystyle \ell _{1}}$

Algoritmo

Para poder utilizar el método de Bregman, uno debe enmarcar el problema de interés como encontrar , donde es una función regularizadora tal como . ^[3] ${\displaystyle \min _{u}J(u)+f(u)}$ ${\displaystyle J}$ ${\displaystyle \ell _{1}}$

La distancia de Bregman se define como donde pertenece al subdiferencial de en (que denotamos ). ^{[3] [4]} Se realiza la iteración , con una constante a elegir por el usuario (y la minimización realizada por un algoritmo de optimización convexa ordinario), ^[3] o , con elegido cada vez para ser miembro de . ^[4] ${\displaystyle D^{p}(u,v):=J(u)-(J(v)+\langle p,u-v\rangle )}$ ${\displaystyle p}$ ${\displaystyle J}$ ${\displaystyle u}$ ${\displaystyle \partial J(u)}$ ${\displaystyle u_{k+1}:=\min _{u}(\alpha D(u,u_{k})+f(u))}$ ${\displaystyle \alpha }$ ${\displaystyle u_{k+1}:=\min _{u}(D^{p_{k}}(u,u_{k})+f(u))}$ ${\displaystyle p_{k}}$ ${\displaystyle \partial J(u_{k})}$

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 que existen coeficientes distintos de cero en el gradiente de las 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 de tipo regularización exacto; si supera un cierto umbral, el valor óptimo de es precisamente la solución óptima de . ^{[3] [5]} ${\displaystyle \min _{x:Ax=b}(|x|_{1}+{\frac {1}{2\alpha }}|x|_{2}^{2})}$ ${\displaystyle \min _{y}(-b^{t}y+{\frac {\alpha }{2}}|A^{t}y-{\text{Proj}}_{[-1,1]^{n}}(A^{t}y)|^{2})}$ ${\displaystyle \alpha }$ ${\displaystyle x}$ ${\displaystyle \min _{x:Ax=b}|x|_{1}}$

Aplicaciones

El método Bregman o sus generalizaciones se pueden aplicar a:

• Eliminación de ruido o desenfocado de imágenes ^[3] (incluida la eliminación de ruido de variación total ^[4] )
• Reconstrucción de imagen de RM ^{[ aclaración necesaria ] [3]}
• Imágenes por resonancia magnética ^{[1] [6]}
• Radar ^[1]
• Imágenes hiperespectrales ^[7]
• Detección comprimida ^[5]
• Desviaciones absolutas mínimas o regresión lineal regularizada ^[8] ${\displaystyle \ell _{1}}$
• Selección de covarianza (aprendizaje de una matriz de covarianza dispersa) ^[8]
• Completamiento de matrices ^[9]
• Minimización del riesgo estructural ^[8]

Generalizaciones y desventajas

El método tiene vínculos con el método de multiplicadores y el método de ascenso dual (a través del llamado método de dirección alterna de Bregman de multiplicadores , ^{[10] [7]} generalizando el método de dirección alterna de multiplicadores ^[8] ) y existen múltiples generalizaciones.

Una desventaja del método es que solo es demostrablemente convergente si la función objetivo es estrictamente convexa. En caso de que esto no se pueda asegurar, 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 Rudin-Osher-Fatemi de eliminación de ruido de imágenes ^{[ aclaración necesaria ]} , el método Bregman converge demostrablemente. ^[11]

Algunas generalizaciones del método Bregman incluyen:

• Método de espacio de escala inversa ^{[ aclaración necesaria ] [3]}
• Bregman linealizado ^[3]
• Bregman logístico ^[3]
• Bregman dividido ^[3]

Bregman linealizado

En el método de Bregman linealizado, se linealizan las funciones objetivo intermedias reemplazando el segundo término con (que aproxima el segundo término cerca de ) y agregando el término de penalización para una constante . El resultado es mucho más manejable computacionalmente, especialmente en problemas de tipo búsqueda de base . ^{[4] [5]} En el caso de un problema de búsqueda de base genérico , se puede expresar la iteración como para cada componente , donde definimos . ^[4] ${\displaystyle D^{p}(u,u_{k})+f(u)}$ ${\displaystyle f(u_{k})+\langle f'(u_{k}),u-u_{k}\rangle }$ ${\displaystyle u_{k}}$ ${\displaystyle {\frac {1}{2\delta }}|u-u_{k}|_{2}^{2}}$ ${\displaystyle \delta }$ ${\displaystyle \min \mu |u|_{1}+{\frac {1}{2}}|Au-f|_{2}^{2}}$ ${\displaystyle v_{k+1}:=v_{k}+A^{t}(f-Au_{k}),u_{k+1,i}:=\delta ~{\text{shrink}}(v_{k,i},\mu )}$ ${\displaystyle i}$ ${\displaystyle {\text{shrink}}(y,a):={\begin{cases}y-a,&y\in (a,\infty )\\0,&y\in [-a,a]\\y+a,&y\in (-\infty ,-a)\end{cases}}}$

A veces, cuando se ejecuta el método de Bregman linealizado, hay períodos de "estancamiento" donde el residuo ^{[ aclaración necesaria ]} es casi constante. Para aliviar este problema, se puede utilizar el método de Bregman linealizado con retroceso , donde esencialmente se detecta el comienzo de un período de estancamiento, luego se predice y se salta hasta el final del mismo. ^{[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ínea, L-BGFS , los pasos de Barzilai-Borwein o el método de Nesterov; este último se ha propuesto como el método Bregman linealizado acelerado . ^{[5] [9]}

Bregman dividido

El método Split Bregman resuelve problemas de la forma , donde y son ambos convexos, ^[4] particularmente problemas de la forma . ^[6] Comenzamos por reescribirlo como el problema de optimización restringida , luego lo relajamos en donde es una constante. Al definir , se reduce el problema a uno que se puede resolver con el algoritmo Bregman ordinario. ^{[4] [6]} ${\displaystyle \min _{u}|\Phi (u)|_{1}+H(u)}$ ${\displaystyle \Phi }$ ${\displaystyle H}$ ${\displaystyle \min _{u}|\Phi u|_{1}+|Ku-f|^{2}}$ ${\displaystyle \min _{u:d=\Phi (u)}|d|_{1}+H(u)}$ ${\displaystyle \min _{u,d}|d|_{1}+H(u)+{\frac {\lambda }{2}}|d-\Phi (u)|_{2}^{2}}$ ${\displaystyle \lambda }$ ${\displaystyle J(u,d):=|d|+H(u)}$

El método Split Bregman se ha generalizado a la optimización sobre números complejos utilizando derivadas de Wirtinger . ^[1]

Referencias

1. Xiong, Kai; Zhao, Guanghui; Shi, Guangming; Wang, Yingbin (12 de septiembre de 2019). "Un algoritmo de optimización convexa para detección comprimida en un dominio complejo: el método de Bregman dividido con valores complejos". Sensores . 19 (20) (publicado el 18 de octubre de 2019): 4540. Bibcode :2019Senso..19.4540X. doi : 10.3390/s19204540 . PMC  6832202 . PMID  31635423.
2. Bregman L. "Un método de relajación para hallar un punto común de conjuntos convexos y su aplicación a problemas de optimización". Dokl. Akad. Nauk SSSR, v. 171, n.º 5, 1966, págs. 1019-1022. (Traducción al inglés: Soviet Math. Dokl., v. 7, 1966, págs. 1578-1581)
3. Yin, Wotao (8 de diciembre de 2009). "Los métodos de Bregman: revisión y nuevos resultados" (PDF) . Archivado (PDF) desde el original el 13 de junio de 2010. Consultado el 16 de abril de 2021 .
4. Bush, Jacqueline (10 de junio de 2011). «Tesis de grado de la Universidad de California, Santa Bárbara: Algoritmos de Bregman» (PDF) . Universidad de California en Santa Bárbara . Archivado (PDF) del original el 30 de noviembre de 2016. Consultado el 16 de abril de 2021 .
5. Yin, Wotao (28 de mayo de 2009). "Análisis y generalizaciones del método de Bregman linealizado" (PDF) . Revista SIAM sobre ciencias de la imagen . 3 (4): 856–877. doi :10.1137/090760350 . Consultado el 16 de abril de 2021 .
6. Goldstein, Tom; Osher, Stanley (2 de junio de 2008). "El método Split Bregman para problemas regularizados en L1". SIAM J. Imaging Sci . 2 (2): 323–343. doi :10.1137/080725891 . Consultado el 22 de abril de 2021 .
7. Jiang, Chunzhi (mayo de 2015). "Comparación del método ADMM de penalización variable con el método Split Bregman en problemas de imágenes hiperespectrales". Archivado desde el original el 23 de marzo de 2020. Consultado el 20 de abril de 2021 .
8. 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 alternada de multiplicadores". Fundamentos y tendencias en aprendizaje automático . 3 : 1–122. CiteSeerX 10.1.1.722.981 . doi :10.1561/2200000016. 
9. Huang, Bo; Ma, Shiqian; Goldfarb, Donald (27 de junio de 2011). "Método de Bregman linealizado acelerado". Journal of Scientific Computing . 54 (2–3). Plenum Press (publicado el 1 de febrero de 2013): 428–453. arXiv : 1106.5413 . doi :10.1007/s10915-012-9592-9. ISSN  0885-7474. S2CID  14781930.
10. Wang, Huahua; Banerjee, Arindam (13 de junio de 2013). "Método de dirección alternada de Bregman de multiplicadores". NIPS'14: Actas de la 27.ª Conferencia internacional sobre sistemas de procesamiento de información neuronal . 2 : 2816–2824. arXiv : 1306.3203 .
11. Jia, Rong-Qing (3 de octubre de 2008). "Análisis de convergencia del método Bregman para el modelo variacional de eliminación de ruido de imágenes" (PDF) . Análisis armónico computacional y aplicado . 27 (3) (publicado en noviembre de 2009): 367–379. doi : 10.1016/j.acha.2009.05.002 . Consultado el 22 de abril de 2021 .