Locally-averaged McCormick relaxations for discretization-regularized inverse problems

Titolo

Relaxations di McCormick localmente mediati per problemi inversi regolarizzati mediante discretizzazione

1. Il Problema

Il lavoro affronta il problema dell'identificazione dei coefficienti in equazioni differenziali alle derivate parziali (PDE) a partire da osservazioni indirette e rumorose. Nello specifico, si considera un problema inverso su un dominio limitato $\Omega \subset \mathbb{R}^d$, dove l'obiettivo è recuperare una funzione incognita $w^\dagger$ (ad esempio un potenziale) che soddisfa vincoli di bound a priori.

La funzione $w^\dagger$ non è osservabile direttamente, ma solo attraverso misurazioni indirette $y^\delta \approx y = Tu$, dove $u$ è lo stato che risolve una PDE ellittica non lineare della forma:
$$Au + f_0 u w = f_1$$
con $A$ un operatore lineare limitato e invertibile, e $f_0, f_1$ dati noti.

La formulazione naturale di questo problema è un problema di minimizzazione non convesso e mal posto (ill-posed). La soluzione richiede la minimizzazione di un funzionale di errore (es. $\|Tu - y^\delta\|_Y$) soggetto ai vincoli della PDE e ai limiti su $w$. La sfida principale risiede nel fatto che la dipendenza $w \mapsto u$ attraverso l'equazione di stato rende il problema non convesso, rendendo difficile garantire che gli algoritmi di ottimizzazione basati sul gradiente trovino il minimo globale piuttosto che un minimo locale. Inoltre, la presenza di rumore nei dati ($\delta > 0$) richiede tecniche di regolarizzazione.

2. Metodologia

Gli autori propongono un approccio ibrido che combina la regolarizzazione per discretizzazione con tecniche di ottimizzazione globale basate su rilassamenti convessi.

• Regolarizzazione per Discretizzazione: Il coefficiente incognito $w$ è limitato a uno spazio di approssimazione finito-dimensionale $V_h$ (ad esempio funzioni costanti a tratti su una griglia con passo $h$). Questo trasforma il problema infinito-dimensionale in uno finito, agendo come regolarizzatore.
• Rilassamento di McCormick: Per gestire la non convessità del termine bilineare $uw$ nell'equazione di stato, il termine viene sostituito da una nuova variabile $z$ e vincolato mediante le disuguaglianze di McCormick. Queste disuguaglianze forniscono un inviluppo convesso per il prodotto di due variabili vincolate.
• Media Locale (Local Averaging): Un'innovazione chiave è l'uso della media locale. Invece di applicare le disuguaglianze di McCormick punto per punto (che genererebbero un numero enorme di vincoli, rendendo il problema computazionalmente intrattabile), gli autori introducono una partizione del dominio $\mathcal{Q}_\tau$ e applicano le disuguaglianze su medie locali delle variabili ($P_\tau u$ e $P_\tau w$). Questo riduce drasticamente il numero di vincoli lineari mantenendo la struttura convessa.
• Raffinamento dei Vincoli (OBBT): Per migliorare la qualità del rilassamento, viene utilizzata una procedura di Optimization-Based Bound Tightening (OBBT). Questa tecnica risolve iterativamente programmi lineari per restringere i limiti superiori e inferiori ($u_\ell, u_u, w_\ell, w_u$) delle variabili, rendendo il rilassamento di McCormick più stretto e riducendo l'errore di approssimazione.
• Algoritmo: Il metodo risolve prima il problema rilassato convesso (McCormick con media locale) per ottenere un limite inferiore (dual bound) e una soluzione iniziale. Questa soluzione viene poi utilizzata per inizializzare un solver locale non lineare (L-BFGS-B) sul problema originale discretizzato.

3. Contributi Chiave

1. Quadro Teorico di Convergenza: Gli autori dimostrano che lo schema proposto è un metodo di regolarizzazione convergente. Dimostrano che, bilanciando opportunamente il passo di discretizzazione $h$, il passo di media locale $\tau$ e il livello di rumore $\delta$, si ottiene una stima di errore con un tasso di convergenza computabile.
2. Riduzione della Complessità Computazionale: L'uso della media locale permette di trasformare un problema con infinite disuguaglianze di McCormick (o un numero proibitivo di vincoli discreti) in un problema con un numero finito e gestibile di vincoli lineari, rendendo fattibile l'uso di tecniche di ottimizzazione globale.
3. Analisi dell'Errore: Viene fornita un'analisi dettagliata che quantifica tre fonti di errore:
   • Errore di discretizzazione (dipendente da $h$).
   • Errore di approssimazione dovuto alla media locale (dipendente da $\tau$).
   • Errore propagato dal rumore nei dati ($\delta$).
4. Validazione Numerica: Dimostrazione empirica che l'uso di limiti inferiori stretti (ottenuti tramite OBBT e rilassamento di McCormick) per inizializzare algoritmi locali porta a ricostruzioni significativamente migliori rispetto all'inizializzazione casuale o con vincoli lassi, avvicinandosi alla soluzione globale anche senza eseguire costosi algoritmi di branch-and-bound spaziale completo.

4. Risultati

• Teorici: È stato provato che la scelta dei parametri $h(\delta)$ e $\tau(\delta)$ secondo le leggi di scala derivate (es. $h \sim \delta^{\max(\dots)}$) garantisce una convergenza della soluzione approssimata alla soluzione vera con un tasso di ordine $O(\delta^t)$, dove $t$ dipende dalla regolarità della soluzione e dalla dimensione del dominio.
• Numerici: Gli esperimenti su un problema modello 1D (recupero di un potenziale in un'equazione ellittica) mostrano che:
  • L'inizializzazione basata sul rilassamento di McCormick con OBBT (caso "O") produce errori di ricostruzione ($\|w^\dagger - \hat{w}\|$) nettamente inferiori rispetto all'inizializzazione con vincoli lassi (caso "P") o costanti (caso "N").
  • Man mano che il rumore $\delta$ diminuisce, l'errore di ricostruzione per il caso "O" diminuisce in modo prevedibile, seguendo il tasso teorico, mentre gli altri casi mostrano un comportamento stagnante o errato.
  • Il tempo di calcolo è dominato dalla fase di OBBT, ma il guadagno in accuratezza giustifica il costo, evitando la necessità di un branch-and-bound completo.

5. Significato e Impatto

Questo lavoro è significativo perché colma un divario tra la teoria della regolarizzazione per problemi inversi e le pratiche di ottimizzazione globale computazionale.

• Trattabilità: Rende fattibile la ricerca del minimo globale per problemi inversi non lineari complessi, un compito che finora è stato raramente affrontato in letteratura a causa della non convessità.
• Robustezza: Offre un metodo robusto che non dipende dalla fortuna dell'inizializzazione, fornendo garanzie teoriche sulla convergenza.
• Efficienza: Dimostra che è possibile ottenere stime di ottimalità globale (o quasi) senza il costo proibitivo degli algoritmi di branch-and-bound completi, sfruttando invece la struttura del problema e la regolarizzazione per discretizzazione.
• Applicabilità: Il metodo è potenzialmente applicabile a una vasta gamma di problemi di identificazione di parametri in ingegneria, imaging medico e geofisica, dove la non convessità è una barriera comune.

In sintesi, il paper propone un framework matematicamente solido e computazionalmente efficiente per trasformare problemi inversi mal posti e non convessi in problemi di ottimizzazione risolvibili globalmente, garantendo la convergenza della soluzione ricostruita al valore vero al diminuire del rumore.