Optimization under uncertainty: understanding orders and testing programs with specifications

1. Il Problema

Il problema centrale affrontato è l'ottimizzazione di una funzione $f$ su un insieme finito, in contesti dove l'incertezza impedisce l'uso di un ordinamento totale standard. Nella programmazione funzionale classica, trovare il minimo (o massimo) di una funzione con codominio totalmente ordinato è ben definito. Tuttavia, in campi come la scienza del clima, l'economia e l'ingegneria, sorgono due tipi fondamentali di incertezza che complicano questo processo:

1. Incertezza basata sul valore (Value-based uncertainty): Si verifica quando l'obiettivo non è un singolo valore scalare, ma un vettore di obiettivi multipli (es. costi economici vs. impatto ambientale) che non possono essere ridotti a un unico numero senza perdere informazioni. In questo caso, il codominio è parzialmente ordinato, portando a un problema di ottimizzazione multi-obiettivo (MOO) dove non esiste un unico "migliore", ma un insieme di soluzioni Pareto-ottimali.
2. Incertezza funtoriale (Functorial uncertainty): Si verifica quando il risultato di una decisione non è un valore certo, ma una distribuzione di possibili risultati (es. incertezza epistemica sui parametri o aleatoria nei sistemi stocastici). Qui la funzione $f$ restituisce valori in un tipo $U\ B$ (dove $U$ è un "funtore di incertezza" come liste, distribuzioni di probabilità, intervalli), rendendo necessario confrontare strutture complesse invece di valori atomici.

Il paper evidenzia che le soluzioni attuali spesso adottano approcci "ad-hoc" (come l'uso dell'valore atteso per ridurre l'incertezza funtoriale a un singolo numero), che possono nascondere complessità critiche, ignorare la struttura dell'incertezza o portare a decisioni subottimali e non robuste.

2. Metodologia

Gli autori utilizzano la programmazione funzionale (in particolare Haskell) come strumento principale per:

• Specificare formalmente i problemi di ottimizzazione.
• Implementare algoritmi generici.
• Testare sistematicamente le implementazioni contro le specifiche utilizzando il property-based testing (QuickCheck).

L'approccio si basa su tre pilastri:

1. Definizione di Relazioni d'Ordine: Estensione delle relazioni di ordinamento da valori scalari a strutture complesse (vettori e funtori).
2. Generalizzazione degli Algoritmi: Adattamento delle funzioni min e argmin per gestire ordini parziali e strutture incerte.
3. Verifica delle Proprietà: Uso di test automatizzati per garantire che le implementazioni rispettino le proprietà matematiche desiderate (es. correttezza, monotonia).

3. Contributi Chiave

A. Ottimizzazione Multi-Obiettivo (MOO)

• Definizione Formale: Gli autori definiscono l'ottimalità di Pareto in termini di relazioni di dominanza ($\prec$) su vettori. Un elemento è Pareto-ottimo se non è dominato da nessun altro elemento nell'insieme.
• Algoritmo "Bump": Viene introdotta una funzione ricorsiva bump che costruisce il fronte di Pareto incrementando un insieme di candidati. Questa funzione è testata per garantire che mantenga l'indifferenza (non-dominanza reciproca) e la copertura degli elementi dominati.
• Generalizzazione: Le funzioni paretoMin e argparetoMin generalizzano min e argmin per gestire vettori con ordini parziali.
• Scoperta: Viene dimostrato che l'insieme dei punti Pareto-ottimali nello spazio dei controlli (input) può occupare una regione bidimensionale anche quando il fronte Pareto nello spazio degli obiettivi è una curva unidimensionale, indicando una robustezza strutturale delle soluzioni.

B. Ottimizzazione sotto Incertezza Funtoriale

• Modellazione: L'incertezza è modellata tramite funtori (es. List, Maybe, distribuzioni di probabilità, intervalli). La funzione obiettivo restituisce $U\ B$.
• Relazione di Dominanza Strutturale ($\prec_u$): Viene definita una relazione di "migliore in senso universale": un'incertezza $ub_1$ è strettamente migliore di $ub_2$ se ogni possibile esito di $ub_1$ è migliore di ogni possibile esito di $ub_2$.
• Funzioni di Misura ($\mu$): Per risolvere il problema, è necessario una funzione di misura $\mu: U\ B \to C$ (dove $C$ è ordinato) che riduca l'incertezza a un valore confrontabile.
• Condizioni di Monotonia (M1 e M2):
  • M1 (Monotonia Puntuale): Se gli elementi di una struttura aumentano, la misura non deve diminuire. Gli autori dimostrano che M1 è insufficiente (es. funzioni costanti o basate sulla lunghezza soddisfano M1 ma falliscono nell'ottimizzazione).
  • M2 (Monotonia Strutturale): Se $ub_1 \prec_u ub_2$ (dominanza strutturale), allora $\mu(ub_1) < \mu(ub_2)$.
  • Risultato Cruciale: Viene dimostrato che M2 è la condizione necessaria e sufficiente affinché l'algoritmo di minimizzazione minu restituisca soluzioni che non sono strutturalmente dominate da altre opzioni disponibili.
• Validazione: Vengono testate diverse misure (valore atteso, minimo, massimo, media) su diversi funtori (liste, distribuzioni semplici, intervalli, PDF). Si scopre che misure popolari come la larghezza di un intervallo o funzioni costanti violano M2 e portano a risultati errati, mentre misure come il valore atteso (per distribuzioni) o il minimo (per intervalli) soddisfano M2.

C. Ruolo della Programmazione Funzionale e Testing

• Il paper dimostra come la programmazione funzionale permetta di separare chiaramente la logica di ottimizzazione dalla gestione dell'incertezza.
• L'uso di QuickCheck permette di falsificare automaticamente misure di rischio inappropriate (es. mostrando che una funzione di misura basata sulla larghezza di un intervallo porta a scegliere opzioni con valori peggiori).

4. Risultati

• Algoritmi Generici: Sono stati implementati e testati algoritmi generici per minu e argminu che funzionano correttamente su qualsiasi "Uncertainty Functor" che soddisfi le condizioni di M2.
• Correttezza delle Misure: È stato identificato un criterio rigoroso (M2) per selezionare le funzioni di misura appropriate in contesti di incertezza. Questo evita l'uso acritico dell'valore atteso, che assume neutralità al rischio.
• Applicazioni Simulate:
  • Fusione Nucleare (ITER): Ottimizzazione dei parametri di iniezione di gas per evitare correnti di fuga, mostrando come il fronte Pareto approssimato da campionamento formi regioni bidimensionali robuste.
  • Politica Climatica: Analisi di come diverse attitudini al rischio (caso peggiore vs. valore atteso) portino a fronti Pareto geometricamente diversi e a decisioni di policy contraddittorie, anche con gli stessi dati empirici.

5. Significato e Implicazioni

Il lavoro ha un impatto significativo sia pedagogico che pratico:

1. Rigore Matematico nell'Incertezza: Fornisce un quadro teorico solido per comprendere "quali ordini applicare" in diversi contesti di incertezza, spostando il dibattito da approcci euristici a definizioni formali.
2. Affidabilità del Software: Dimostra come le specifiche formali e il testing basato sulle proprietà possano garantire la correttezza di algoritmi di ottimizzazione complessi, un aspetto spesso trascurato nelle librerie numeriche tradizionali.
3. Decisioni Trasparenti: Nel contesto delle politiche climatiche, il paper evidenzia che i conflitti tra esperti o stakeholder spesso derivano non da dati diversi, ma da diverse (e spesso implicite) scelte di funzioni di misura dell'incertezza. Rendere esplicite queste scelte (tramite M2) permette un dibattito democratico più razionale.
4. Generalità: L'approccio è indipendente dal dominio specifico, applicabile a qualsiasi problema decisionale che coinvolga trade-off multipli o incertezza strutturale, offrendo una via per costruire sistemi "sempre più corretti" (increasingly correct) attraverso la verifica formale.

In sintesi, il paper propone un cambio di paradigma: invece di ridurre l'incertezza a un singolo numero in modo arbitrario, si deve modellare l'incertezza strutturalmente e scegliere funzioni di misura che rispettino la dominanza universale, garantendo così che le soluzioni ottimizzate siano robuste e matematicamente fondate.