La superiorización es un método iterativo para la optimización restringida . Se utiliza para mejorar la eficacia de un método iterativo cuya convergencia es resistente a ciertos tipos de perturbaciones. Tales perturbaciones están diseñadas para "forzar" al algoritmo perturbado a producir resultados más útiles para la aplicación prevista que los producidos por el algoritmo iterativo original. El algoritmo perturbado se denomina versión superiorizada del algoritmo no perturbado original. Si el algoritmo original es computacionalmente eficiente y útil en términos de la aplicación de destino y si las perturbaciones no son costosas de calcular, el método puede usarse para dirigir iteraciones sin costo de cálculo adicional.
Areas de aplicación
La metodología de superiorización es muy general y se ha utilizado con éxito en muchas aplicaciones prácticas importantes, como la reconstrucción iterativa de imágenes a partir de sus proyecciones, [1] [2] [3] tomografía computarizada por emisión de fotón único , [4] radioterapia [5 ] [6] [7] y pruebas no destructivas , [8] solo por nombrar algunas. Un número especial de la revista Inverse Problems [9] está dedicado a la superiorización, tanto a la teoría [10] [11] [12] como a las aplicaciones. [3] [6] [7]
Reducción de la función objetiva y relación con la optimización restringida
Un caso importante de superiorización es cuando el algoritmo original es "búsqueda de factibilidad" (en el sentido de que se esfuerza por encontrar algún punto en una región factible que sea compatible con una familia de restricciones) y las perturbaciones que se introducen en el iterativo original. El algoritmo tiene como objetivo reducir (no necesariamente minimizar) una función de mérito dada. En este caso, la superiorización tiene un lugar único en la teoría y la práctica de la optimización .
Muchos métodos de optimización con restricciones se basan en métodos de optimización sin restricciones que se adaptan para hacer frente a las restricciones. Tal es, por ejemplo, la clase de métodos de gradiente proyectado en los que el paso interno de minimización sin restricciones "conduce" el proceso y se realiza una proyección sobre todo el conjunto de restricciones (la región factible) después de cada paso de minimización para recuperar la viabilidad. Esta proyección sobre el conjunto de restricciones es en sí misma un problema de optimización no trivial y la necesidad de resolverlo en cada iteración dificulta los métodos de gradiente proyectado y limita su eficacia a conjuntos factibles que son "simples de proyectar". Los métodos de barrera o de penalización también se basan en una optimización sin restricciones combinada con varios "complementos" que garantizan que se conserven las restricciones. Los métodos de regularización incorporan las restricciones en una función objetivo "regularizada" y proceden con métodos de solución no restringidos para la nueva función objetivo regularizada.
En contraste con estos enfoques, la metodología de superiorización puede verse como una forma de pensar antípoda. En lugar de adaptar algoritmos de minimización sin restricciones para manejar las restricciones, adapta algoritmos de búsqueda de viabilidad para reducir los valores de la función de mérito. Esto se hace conservando la naturaleza de búsqueda de viabilidad del algoritmo y sin pagar un alto precio computacional. Además, se han desarrollado enfoques de propósito general para superiorizar automáticamente los algoritmos iterativos para grandes clases de conjuntos de restricciones y funciones de mérito; estos proporcionan algoritmos para muchas tareas de la aplicación.
Otras fuentes
La metodología de superiorización y la resistencia a las perturbaciones de los algoritmos se revisan en, [13] [14] [15] ver también. [16] El trabajo actual sobre la superiorización se puede apreciar en una página de Internet que se actualiza continuamente. [17] SNARK14 [18] es un paquete de software para la reconstrucción de imágenes 2D a partir de proyecciones 1D que tiene la capacidad incorporada de superiorizar cualquier algoritmo iterativo para cualquier función de mérito.
Referencias
- ^ GT Herman, Fundamentos de la tomografía computarizada: reconstrucción de imágenes a partir de proyecciones, Springer-Verlag, Londres, Reino Unido, segunda edición, 2009. doi : 10.1007 / 978-1-84628-723-7
- ^ ES Helou, MVW Zibetti y EX Miqueles, Superiorización de algoritmos de optimización incremental para reconstrucción estadística de imágenes tomográficas, Problemas inversos, vol. 33 (2017), 044010. doi : 10.1088 / 1361-6420 / 33/4/044010
- ^ a b Q. Yang, W. Cong y G. Wang, Reconstrucción de imágenes de TC multienergía basada en la superiorización, Problemas inversos, vol. 33 (2017), 044014. doi : 10.1088 / 1361-6420 / aa5e0a
- ^ S. Luo y T. Zhou, Superiorización del algoritmo EM y su aplicación en tomografía computarizada por emisión de fotón único (SPECT), Problemas inversos e imágenes, vol. 8, págs. 223–246, (2014). doi : 10.3934 / ipi.2014.8.223
- ^ R. Davidi, Y. Censor, RW Schulte, S. Geneser y L. Xing, Algoritmos de superiorización y búsqueda de viabilidad aplicados a la planificación inversa del tratamiento en radioterapia, Matemáticas contemporáneas, vol. 636, págs. 83–92, (2015). doi : 10.1090 / conm / 636/12729
- ^ a b E. Bonacker, A. Gibali, KH. Küfer y P. Süss, Aceleración de la optimización lexicográfica por superiorización y sus aplicaciones al tratamiento de radioterapia del cáncer, Problemas inversos, vol. 33 (2017), 044012. doi : 10.1088 / 1361-6420 / 33/4/044012
- ^ a b J. Zhu y S. Penfold, Superiorización de la variación total en la reconstrucción de TC de energía dual para la planificación del tratamiento de la terapia de protones, Problemas inversos, vol. 33 (2017), 044013. doi : 10.1088 / 1361-6420 / 33/4/04401
- ^ MJ Schrapp y GT Herman, Fusión de datos en tomografía computarizada de rayos X utilizando un enfoque de superiorización, Revisión de instrumentos científicos, vol. 85, 053701 (9pp), (2014). doi : 10.1063 / 1.4872378
- ^ Superiorización: teoría y aplicaciones, número especial de la revista Inverse Problems, volumen 33, número 4, abril de 2017
- ^ H. Él y HK. Xu, Metodología de superiorización y resiliencia de perturbación de mapeos promediados, Problemas inversos, Vol. 33 (2017), 044007. doi : 10.1088 / 1361-6420 / 33/4/044007
- ^ HK. Xu, Técnicas de superiorización y resiliencia a perturbaciones limitadas para el método de gradiente escalado proyectado, Problemas inversos, vol. 33 (2017), 044008. doi : 10.1088 / 1361-6420 / 33/4/044008
- ^ Nikazad, Touraj y Mokhtar Abbasi. "Un tratamiento unificado de algunos métodos iterativos de punto fijo perturbados con un grupo infinito de operadores". Problemas inversos 33.4 (2017): 044002. doi : 10.1088 / 1361-6420 / 33/4/044002
- ^ GT Herman, E. Garduño, R. Davidi e Y. Censor, Superiorización: una heurística de optimización para la física médica, Física médica, vol. 39, págs. 5532–5546, (2012). doi : 10.1118 / 1.4745566
- ^ GT Herman, Superiorización para el análisis de imágenes, en: Análisis combinatorio de imágenes, Notas de la conferencia en Ciencias de la Computación Vol. 8466, Springer, 2014, págs. 1-7. doi : 10.1007 / 978-3-319-07148-0_1
- ^ Y. Censor, superiorización débil y fuerte: entre la búsqueda de viabilidad y la minimización, Analele Stiintifice ale Universitatii Ovidius Constanta-Seria Matematica, vol. 23, págs. 41–54, (2015). doi : 10.1515 / auom-2015-0046
- ^ Y. Censor, R. Davidi, GT Herman, RW Schulte y L. Tetruashvili, minimización de subgrado proyectada versus superiorización, Journal of Optimization Theory and Applications, vol. 160, págs. 730–747, (2014). doi : 10.1007 / s10957-013-0408-3
- ^ "Superiorización" . math.haifa.ac.il .
- ^ "Snark14 - Inicio" . turing.iimas.unam.mx .