Superiorización

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. Dichas perturbaciones están diseñadas para "obligar" al algoritmo perturbado a producir resultados más útiles para la aplicación prevista que los que produce el algoritmo iterativo original. El algoritmo perturbado se denomina versión superiorizada del algoritmo original no perturbado. Si el algoritmo original es computacionalmente eficiente y útil en términos de la aplicación de destino y si las perturbaciones son económicas de calcular, el método puede utilizarse para dirigir iteraciones sin un costo computacional adicional.

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]} la tomografía computarizada por emisión de fotón único , ^[4] la radioterapia ^{[5] [6] [7]} y las pruebas no destructivas , ^[8] por nombrar solo 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]}

Un caso importante de superiorización es cuando el algoritmo original busca la "factibilidad" (en el sentido de que intenta 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 algoritmo iterativo original apuntan a 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 están adaptados 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 "lidera" 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 obstaculiza los métodos de gradiente proyectado y limita su eficacia únicamente a conjuntos factibles que son "simples de proyectar". Los métodos de barrera o de penalización también se basan en la optimización sin restricciones combinada con varios "complementos" que garantizan que se mantengan 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 sin restricciones para la nueva función objetivo regularizada.

En contraste con estos enfoques, la metodología de superiorización puede considerarse como una forma de pensar antípoda. En lugar de adaptar algoritmos de minimización sin restricciones para manejar restricciones, adapta algoritmos de búsqueda de viabilidad para reducir los valores de la función de mérito. Esto se hace mientras se conserva 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 algoritmos iterativos para grandes clases de conjuntos de restricciones y funciones de mérito; estos proporcionan algoritmos para muchas tareas de aplicación.

La metodología de superiorización y la resiliencia a las perturbaciones de los algoritmos se revisan en ^{[13] [14] [15]} ver también. ^[16] El trabajo actual sobre 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 una capacidad incorporada de superiorizar cualquier algoritmo iterativo para cualquier función de mérito.