Conformal Predictive Programming for Chance Constrained Optimization

Resumo Técnico: Programação Preditiva Conforme para Otimização com Restrições de Chance

Enunciado do Problema
O artigo aborda problemas de Otimização com Restrições de Chance (CCO - Chance Constrained Optimization), que envolvem a minimização de uma função de custo $J(x)$ sujeita a restrições que devem ser satisfeitas com alta probabilidade ($1-\delta$) sobre um vetor aleatório $Y$. Formalmente, o problema é:
$$\min_{x \in X} J(x) \quad \text{sujeito a} \quad P(f(x, Y) \leq 0) \geq 1 - \delta$$
onde $f$ é uma função de Borel mensurável e $Y$ segue uma distribuição desconhecida $P_Y$. O principal desafio na resolução de CCO é que a distribuição $P_Y$ é tipicamente desconhecida e, mesmo que seja conhecida, a avaliação da restrição de probabilidade exige a resolução de integrais complexas e frequentemente intratáveis. Abordagens baseadas em amostragem existentes, como a Abordagem de Cenários (SA - Scenario Approach) e a Aproximação de Média de Amostras (SAA - Sample Average Approximation), frequentemente dependem de fortes suposições estruturais (ex: convexidade de $J$, $f$ e $X$) para fornecer garantias a priori. Quando essas suposições não se sustentam, ou quando as garantias a priori são excessivamente conservadoras ou computacionalmente caras para calcular (ex: exigindo a identificação de restrições de suporte), os métodos existentes têm dificuldade em fornecer garantias de viabilidade a posteriori confiáveis.

Metodologia: Programação Preditiva Conforme (CPP)
Os autores propõem a Programação Preditiva Conforme (CPP), um framework que transforma o problema estocástico de CCO em um problema de otimização determinístico utilizando Predição Conforme (CP - Conformal Prediction). A CPP opera em duas fases distintas:

1. Etapa de Otimização (Reformulação de Quantil):
   Em vez de usar a restrição de chance bruta, a CPP a substitui por uma restrição de quantil definida sobre um conjunto de dados de otimização $\{Y^{(1)}, \dots, Y^{(K)}\}$. O problema é reformulado como:
   $$\min_{x \in X} J(x) \quad \text{sujeito a} \quad \hat{Q}_{\alpha(K)}(f(x, Y^{(1)}), \dots, f(x, Y^{(K)})) \leq 0$$
   Aqui, $\hat{Q}_{\alpha(K)}$ é o quantil empírico em um nível de confiança específico $\alpha(K)$. Os autores demonstram que esta reformulação é uma instanciação de SAA, permitindo que a CPP herde garantias a priori da literatura de SAA para classes específicas de problemas (ex: restrições separáveis).

2. Etapa de Calibração (Garantias A Posteriori):
   Para fornecer garantias de viabilidade a posteriori rigorosas sem depender de suposições estruturais como convexidade, a CPP utiliza um segundo conjunto de dados de calibração independente $\{Y^{(K+1)}, \dots, Y^{(K+L)}\}$.

   • Garantias Marginais: Utilizando o Lema do Quantil da CP, a CPP calcula um quantil $C_m$ sobre os dados de calibração. O Teorema 3.4 estabelece que a solução $x^*(K)$ satisfaz $P(f(x^*(K), Y) \leq C_m) \geq 1-\delta$ em relação à medida do produto dos dados.
   • Garantias Condicionais: Ao empregar um nível de confiança mais rigoroso durante o cálculo do quantil (Lema do Quantil Condicional), a CPP fornece garantias que se mantêm com alta confiança ($1-\beta$) condicionadas ao conjunto de dados de calibração.
   • Deslocamento de Quantil (Quantile Shift): Para lidar com casos onde o limite $C$ calculado é positivo, os autores propõem um método de "deslocamento de quantil" (Teorema 3.6). Este calcula uma probabilidade de falha ajustada $\delta^*$ baseada no número de restrições satisfeitas no conjunto de calibração, garantindo que $P(f(x^*(K), Y) \leq 0) \geq 1-\delta^*$ com alta confiança.

Principais Contribuições

• Novo Framework: A introdução da CPP como uma abordagem baseada em amostragem que requer limitações de suposições estruturais no problema de CCO.
• Garantias Estatísticas: A provisão de garantias de viabilidade tanto condicionais quanto marginais a posteriori. Diferente da SA padrão, estas garantias não dependem da dimensão da variável de decisão $n$, reduzindo o conservadorismo para problemas de alta dimensão.
• Modularidade e Versatilidade: O framework é projetado para incorporar facilmente várias variantes de Predição Conforme. Os autores demonstram isso estendendo a CPP para:
  • CPP Robusta (RCPP): Lida com mudanças de distribuição (ex: lacunas sim-to-real) usando predição conforme robusta e conjuntos de ambiguidade.
  • CPP de Mondrian (MCPP): Aborda restrições de chance condicionadas à classe (MCCO), garantindo que as garantias de segurança se mantenham para subgrupos específicos da distribuição da variável aleatória.
• Conexão com a Teoria Existente: O artigo estabelece que a CPP herda garantias a priori da SAA e que suas garantias condicionais a posteriori reduzem-se assintoticamente aos limites de Chernoff.

Resultados e Estudos de Caso
Os autores validam a CPP através de estudos de caso numéricos envolvendo problemas convexos e não convexos, bem como uma tarefa de controle ótimo estocástico.

• Otimização Convexa e Não Convexa: Em experimentos comparando a CPP contra a Abordagem de Cenários (SA) para problemas não convexos, a CPP demonstrou um desempenho competitivo. Notavelmente, enquanto os métodos de SA não convexos (ex: [18, 26]) exigem etapas computacionalmente caras para encontrar subconjuntos de suporte irredutíveis para garantias a posteriori (levando cerca de 10 segundos no estudo), o cálculo do deslocamento de quantil da CPP é significativamente mais rápido (tempo linear).
• Cobertura Empírica: Os experimentos confirmaram que a cobertura empírica das soluções converge para os limites teóricos ($1-\delta$ ou $1-\delta^*$). Os histogramas dos limites calculados centrados próximo a zero indicam que a reformulação de quantil aproxima efetivamente a restrição de chance original.
• Extensões Robusta e Mondrian: Em um problema de controle ótimo estocástico (navegação de robôs), a RCPP lidou com sucesso com uma mudança de distribuição (simulando uma mudança na variância do ruído), alcançando uma cobertura empírica superior (0.96) em comparação com a linha de base da CPP padrão (0.80). Da mesma forma, a Mondrian CPP conseguiu manter as garantias de cobertura para grupos específicos de magnitude de perturbação onde a CPP padrão falhou.

Significância e Alegações
O artigo afirma que a CPP oferece um framework computacionalmente eficiente e extensível para problemas de CCO onde suposições padrão (convexidade, distribuições conhecidas) não estão disponíveis ou são difíceis de verificar. Sua principal significância reside no fornecimento de certificados de viabilidade independentes da dimensão. Diferente da Abordagem de Cenários, onde as garantias tornam-se mais frouxas à medida que o número de variáveis de decisão aumenta, as garantias da CPP permanecem robustas independentemente da dimensionalidade, desde que um segundo conjunto de dados de calibração esteja disponível. Os autores enfatizam que esta abordagem preenche a lacuna entre o rigor teórico da predição conforme e as necessidades práticas de controle e planejamento sob incerteza, oferecendo uma alternativa prática a métodos que dependem de análises estruturais complexas ou que resultam em soluções excessivamente conservadoras.