Locally-averaged McCormick relaxations for discretization-regularized inverse problems

A continuación presento un resumen técnico detallado del artículo "Local-averaged McCormick Relaxations for Discretization-regularized Inverse Problems" (Relajaciones de McCormick promediadas localmente para problemas inversos regularizados por discretización), escrito por Barbara Kaltenbacher y Paul Manns.

1. Planteamiento del Problema

El artículo aborda el problema de la identificación de coeficientes en Ecuaciones Diferenciales Parciales (EDP) a partir de observaciones indirectas y ruidosas. Este es un problema inverso clásico que surge en aplicaciones como imágenes médicas cuantitativas, exploración geofísica y caracterización de materiales.

• Naturaleza del problema: La formulación como ecuación de operador es inherentemente no lineal e mal planteada (ill-posed).
• Modelo específico: Se considera un problema prototípico de recuperación de un potencial $w^\dagger$ en una EDP elíptica con un término bilineal:
  $$Au + f_0 uw = f_1$$
  donde $u$ es el estado, $w$ es el coeficiente desconocido (acotado a priori), y $A$ es un operador lineal invertible.
• Desafíos principales:
  1. No convexidad: La dependencia del estado $u$ respecto al coeficiente $w$ hace que el problema de minimización (basado en mínimos cuadrados) sea no convexo, lo que impide que los métodos de optimización basados en gradientes (como Newton o Gradiente Conjugado) garanticen encontrar el mínimo global.
  2. Ruido y Regularización: Las mediciones $y^\delta$ están contaminadas con ruido de nivel $\delta$. Se requiere una técnica de regularización para obtener soluciones estables.
  3. Optimización Global: Para garantizar la convergencia a la solución verdadera, es necesario encontrar un mínimo global, lo cual es computacionalmente costoso y difícil en espacios de dimensión infinita.

2. Metodología Propuesta

Los autores proponen un esquema híbrido que combina regularización por discretización con optimización global basada en relajaciones convexas.

A. Regularización por Discretización

En lugar de trabajar en el espacio continuo, el coeficiente $w$ se restringe a un espacio de dimensión finita $V_h$ (definido sobre una malla de tamaño $h$). Esto convierte el problema inverso en un problema de optimización finito-dimensional $(I_\delta)$. La discretización actúa como regularizador, permitiendo demostrar tasas de convergencia cuando $h \to 0$ y $\delta \to 0$.

B. Relajación de McCormick

Para abordar la no convexidad del término bilineal $uw$, se utiliza una relajación de McCormick:

1. Se introduce una nueva variable $z$ para aproximar el producto $uw$.
2. Se reemplaza la igualdad no lineal $z = uw$ por un conjunto de cuatro desigualdades lineales (envolvente convexa) que dependen de los límites inferiores y superiores de $u$ y $w$ ($u_\ell, u_u, w_\ell, w_u$).
3. Esto transforma el problema en uno convexo $(McC_\delta)$, que proporciona una cota inferior (dual) del valor óptimo original.

C. Promedio Local (Local Averaging)

Un obstáculo computacional de la relajación de McCormick estándar es que requiere imponer las desigualdades en cada punto del dominio (o nodo de la malla), lo que genera un número prohibitivo de restricciones para mallas finas.

• Innovación: Los autores proponen promediar localmente las variables sobre una partición $\mathcal{Q}_\tau$ (con tamaño $\tau$).
• Se reemplazan las desigualdades puntuales por desigualdades promediadas localmente sobre cada celda $Q_i^\tau$.
• Esto reduce drásticamente el número de restricciones lineales, haciendo el problema $(McC_{\delta\tau})$ computacionalmente tratable mientras se mantiene la propiedad de cota inferior.

D. Afianzamiento de Cotas (Bound Tightening - OBBT)

Las cotas iniciales para $u$ y $w$ suelen ser muy conservadoras (basadas en desigualdades de Sobolev o Poincaré), lo que debilita la relajación.

• Se emplea una técnica de Afianzamiento de Cotas Basada en Optimización (OBBT).
• Se resuelven secuencias de programas lineales para estrechar las cotas $u_\ell, u_u, w_\ell, w_u$, mejorando así la calidad de la relajación de McCormick y reduciendo el error de aproximación.

3. Contribuciones Clave

1. Marco Teórico de Convergencia: Demuestran que el esquema propuesto es un método de regularización válido. Establecen condiciones bajo las cuales la solución del problema relajado y discretizado converge a la solución verdadera del problema inverso cuando $\delta, h, \tau \to 0$.
2. Tasas de Convergencia: Derivan tasas de convergencia explícitas en términos del nivel de ruido $\delta$. La tasa óptima depende de la regularidad de la solución y de la dimensión del problema ($d$) y el orden del operador ($s$).
   • Por ejemplo, para $s=1$ (operador elíptico estándar), la tasa de convergencia en norma $L^2$ es $O(\delta^{1/5})$ bajo ciertas condiciones de dimensión.
3. Relación entre Discretización y Relajación: Analizan rigurosamente la relación de aproximación entre el problema original $(I)$, el problema regularizado $(I_\delta)$, y sus relajaciones convexas $(McC_\delta)$ y $(McC_{\delta\tau})$, cuantificando los errores introducidos por la discretización, el promedio local y la relajación.
4. Estrategia Computacional Eficiente: Proponen un enfoque práctico donde la solución del problema relajado $(McC_{\delta\tau})$ se utiliza para inicializar un solver local no convexo (L-BFGS-B). Esto permite encontrar soluciones cercanas al mínimo global sin necesidad de ejecutar un algoritmo de Branch-and-Bound espacial completo, que sería prohibitivamente costoso.

4. Resultados Numéricos

Los experimentos se realizaron en un problema 1D (recuperación de un potencial en $[0,1]$) con diferentes niveles de ruido ($\delta \in [10^{-1}, 10^{-5}]$).

• Comparación de Inicializaciones: Se compararon tres estrategias para iniciar el solver L-BFGS-B:
  1. O: Solución de la relajación de McCormick con OBBT (cotas ajustadas).
  2. P: Solución de la relajación de McCormick con cotas conservadoras (sin OBBT).
  3. N: Función constante (sin información de cota inferior).
• Hallazgos:
  • La estrategia O (con OBBT) demostró un rendimiento superior, logrando errores de reconstrucción significativamente menores y una tendencia de convergencia clara hacia cero a medida que el ruido disminuía.
  • La estrategia O logró errores de reconstrucción casi una orden de magnitud menores que las estrategias P y N para niveles de ruido bajos ($\delta = 10^{-5}$).
  • La estrategia O cumplió con las tasas de convergencia teóricas predichas, mientras que las otras no mostraron una tendencia de mejora consistente al reducir el ruido.
• Costo Computacional: El cálculo de las cotas ajustadas (OBBT) es el cuello de botella computacional (aumenta el tiempo de ejecución en un orden de magnitud), pero el costo de resolver la relajación convexa en sí es despreciable comparado con la optimización no convexa.

5. Significado e Impacto

Este trabajo es significativo por varias razones:

• Puente entre Teoría y Práctica: Proporciona un marco teórico riguroso para la optimización global en problemas inversos no lineales, algo que a menudo se aborda solo heurísticamente en la literatura.
• Regularización Integrada: Demuestra que la discretización no es solo un paso numérico, sino una herramienta de regularización que, combinada con relajaciones convexas, garantiza la convergencia.
• Viabilidad Computacional: Al utilizar el promedio local y el afianzamiento de cotas, hacen viable el uso de métodos de optimización global (o aproximaciones cercanas a ellas) en problemas de dimensión moderada, evitando la explosión combinatoria de los métodos Branch-and-Bound puros.
• Aplicabilidad: La metodología es generalizable a otros problemas de identificación de coeficientes en EDPs no lineales, ofreciendo una ruta para obtener soluciones confiables y certificadas en aplicaciones críticas como la imagen médica.

En resumen, el artículo presenta un algoritmo robusto que combina la teoría de regularización inversa con técnicas avanzadas de optimización global (relajaciones de McCormick), logrando una convergencia garantizada y un rendimiento numérico superior en la reconstrucción de coeficientes en EDPs.