Conformal Predictive Programming for Chance Constrained Optimization

Sintesi Tecnica: Programmazione Predittiva Conforme per l'Ottimizzazione con Vincoli di Probabilità

Definizione del Problema
Il documento affronta i problemi di Ottimizzazione con Vincoli di Probabilità (Chance Constrained Optimization, CCO), che consistono nel minimizzare una funzione di costo $J(x)$ soggetta a vincoli che devono essere soddisfatti con un'alta probabilità ($1-\delta$) rispetto a un vettore casuale $Y$. Formalmente, il problema è:
$$\min_{x \in X} J(x) \quad \text{s.t.} \quad P(f(x, Y) \leq 0) \geq 1 - \delta$$
dove $f$ è una funzione Borel misurabile e $Y$ segue una distribuzione sconosciuta $P_Y$. La sfida principale nel risolvere un CCO è che la distribuzione $P_Y$ è tipicamente sconosciuta e, anche se nota, la valutazione del vincolo di probabilità richiede la risoluzione di integrali complessi e spesso intrattabili. Gli approcci esistenti basati sul campionamento, come l'Approccio degli Scenari (Scenario Approach, SA) e l'Approssimazione della Media Campionaria (Sample Average Approximation, SAA), spesso si affidano a forti assunzioni strutturali (ad esempio, la convessità di $J$, $f$ e $X$) per fornire garanzie a priori. Quando tali assunzioni non sono soddisfatte, o quando le garanzie a priori sono troppo conservative o computazionalmente costose da calcolare (ad esempio, richiedendo l'identificazione dei vincoli di supporto), i metodi esistenti faticano a fornire garanzie di ammissibilità a posteriori affidabili.

Metodologia: Programmazione Predittiva Conforme (CPP)
Gli autori propongono la Programmazione Predittiva Conforme (Conformal Predictive Programming, CPP), un framework che trasforma il problema CCO stocastico in un problema di ottimizzazione deterministico utilizzando la Predizione Conforme (Conformal Prediction, CP). La CPP opera in due fasi distinte:

1. Fase di Ottimizzazione (Riformulazione dei Quantili):
   Invece di utilizzare il vincolo di probabilità grezzo, la CPP lo sostituisce con un vincolo di quantile definito su un dataset di ottimizzazione $\{Y^{(1)}, \dots, Y^{(K)}\}$. Il problema viene riformulato come:
   $$\min_{x \in X} J(x) \quad \text{s.t.} \quad \hat{Q}_{\alpha(K)}(f(x, Y^{(1)}), \dots, f(x, Y^{(K)})) \leq 0$$
   Qui, $\hat{Q}_{\alpha(K)}$ è il quantile empirico a un determinato livello di confidenza $\alpha(K)$. Gli autori dimostrano che questa riformulazione è un'istanza della SAA, permettendo alla CPP di ereditare le garanzie a priori dalla letteratura SAA per specifiche classi di problemi (ad esempio, vincoli separabili).

2. Fase di Calibrazione (Garanzie A Posteriori):
   Per fornire garanzie di ammissibilità a posteriori rigorose senza fare affidamento su assunzioni strutturali come la convessità, la CPP utilizza un secondo dataset di calibrazione indipendente $\{Y^{(K+1)}, \dots, Y^{(K+L)}\}$.

   • Garanzie Marginali: Utilizzando il Lemma dei Quantili della CP, la CPP calcola un quantile $C_m$ sui dati di calibrazione. Il Teorema 3.4 stabilisce che la soluzione $x^*(K)$ soddisfa $P(f(x^*(K), Y) \leq C_m) \geq 1-\delta$ rispetto alla misura del prodotto dei dati.
   • Garanzie Condizionali: Utilizzando un livello di confidenza ristretto durante il calcolo del quantile (Conditional Quantile Lemma), la CPP fornisce garanzie che valgono con un'alta confidenza ($1-\beta$) condizionata al dataset di calibrazione.
   • Spostamento del Quantile (Quantile Shift): Per affrontare i casi in cui il limite calcolato $C$ è positivo, gli autori propongono un metodo di "spostamento del quantile" (Teorema 3.6). Questo calcola una probabilità di fallimento aggiustata $\delta^*$ basata sul numero di vincoli soddisfatti nel set di calibrazione, garantendo che $P(f(x^*(K), Y) \leq 0) \geq 1-\delta^*$ con alta confidenza.

Contributi Chiave

• Nuovo Framework: L'introduzione della CPP come approccio basato sul campionamento che richiede limitate assunzioni strutturali sul problema CCO.
• Garanzie Statistiche: La fornitura di garanzie di ammissibilità a posteriori sia condizionali che marginali. A differenza della SA standard, queste garanzie non dipendono dalla dimensione della variabile decisionale $n$, riducendo la conservatività per problemi ad alta dimensionalità.
• Modularità e Versatilità: Il framework è progettato per incorporare facilmente varie varianti di Predizione Conforme. Gli autori dimostrano questo estendendo la CPP a:
  • CPP Robusta (RCPP): Gestisce i cambiamenti di distribuzione (ad esempio, gap sim-to-real) utilizzando la predizione conforme robusta e set di ambiguità.
  • CPP Mondriana (MCPP): Affronta i vincoli di probabilità condizionati alla classe (MCCO), assicurando che le garanzie di sicurezza valgano per specifici sottogruppi della distribuzione della variabile casuale.
• Connessione con la Teoria Esistente: Il documento stabilisce che la CPP eredita le garanzie a priori dalla SAA e che le sue garanzie condizionali a posteriori convergono asintoticamente ai limiti di Chernoff.

Risultati e Casi di Studio
Gli autori validano la CPP attraverso casi di studio numerici che coinvolgono problemi sia convessi che non convessi, nonché un compito di controllo ottimale stocastico.

• Ottimizzazione Convessa e Non Convessa: Negli esperimenti che confrontano la CPP con l'Approccio degli Scenari (SA) per problemi non convessi, la CPP ha mostrato prestazioni competitive. In particolare, mentre i metodi SA non convessi (ad esempio, [18, 26]) richiedono passaggi computazionalmente costosi per trovare i sottoinsiemi di supporto irriducibili per le garanzie a posteriori (impiegando circa 10 secondi nello studio), il calcolo dello spostamento del quantile della CPP è significativamente più veloce (tempo lineare).
• Copertura Empirica: Gli esperimenti hanno confermato che la copertura empirica delle soluzioni converge ai limiti teorici ($1-\delta$ o $1-\delta^*$). Gli istogrammi dei limiti calcolati erano centrati vicino allo zero, indicando che la riformulazione del quantile approssima efficacemente il vincolo di probabilità originale.
• Estensioni Robusta e Mondriana: In un problema di controllo ottimale stocastico (navigazione robotica), la RCPP ha gestito con successo un cambiamento di distribuzione (simulando un cambiamento nella varianza del rumore), ottenendo una copertura empirica superiore (0.96) rispetto alla baseline della CPP standard (0.80). Allo stesso modo, la Mondrian CPP ha mantenuto con successo le garanzie di copertura per specifici gruppi di magnitudo del disturbo dove la CPP standard era fallita.

Significato e Rivendicazioni
Il documento sostiene che la CPP offra un framework computazionalmente efficiente ed estensibile per i problemi CCO in cui le assunzioni standard (convessità, distribuzioni note) non sono disponibili o difficili da verificare. Il suo significato primario risiede nel fornire certificati di ammissibilità indipendenti dalla dimensione. A differenza dell'Approccio degli Scenari, dove le garanzie diventano più deboli all'aumentare del numero di variabili decisionali, le garanzie della CPP rimangono robuste indipendentemente dalla dimensionalità, a patto che sia disponibile un secondo dataset di calibrazione. Gli autori sottolineano come questo approccio colmi il divario tra il rigore teorico della predizione conforme e le necessità pratiche di controllo e pianificazione sotto incertezza, offrendo un'alternativa pratica ai metodi che si basano su analisi strutturali complesse o che producono soluzioni eccessivamente conservative.