Conformal Predictive Programming for Chance Constrained Optimization

Resumen Técnico: Programación Predictiva Conforme para la Optimización con Restricciones de Probabilidad

Planteamiento del Problema
El artículo aborda problemas de Optimización con Restricciones de Probabilidad (CCO, por sus siglas en inglés), los cuales consisten en minimizar una función de costo $J(x)$ sujeta a restricciones que deben cumplirse con una alta probabilidad ($1-\delta$) sobre un vector aleatorio $Y$. Formalmente, el problema es:
$$\min_{x \in X} J(x) \quad \text{sujeto a} \quad P(f(x, Y) \leq 0) \geq 1 - \delta$$
donde $f$ es una función de Borel medible y $Y$ sigue una distribución desconocida $P_Y$. El desafío principal para resolver un CCO es que la distribución $P_Y$ es típicamente desconocida e, incluso si fuera conocida, evaluar la restricción de probabilidad requiere resolver integrales complejas y frecuentemente intratables. Los enfoques de muestreo existentes, como el Enfoque de Escenarios (SA) y la Aproximación de Promedio de Muestras (SAA), a menudo dependen de fuertes supuestos estructurales (por ejemplo, la convexidad de $J$, $f$ y $X$) para proporcionar garantías a priori. Cuando estos supuestos no se cumplen, o cuando las garantías a priori son demasiado conservadoras o computacionalmente costosas de calcular (por ejemplo, requiriendo la identificación de restricciones de soporte), los métodos existentes tienen dificultades para proporcionar garantías de factibilidad a posteriori fiables.

Metodología: Programación Predictiva Conforme (CPP)
Los autores proponen la Programación Predictiva Conforme (CPP), un marco que transforma el problema estocástico de CCO en un problema de optimización determinista utilizando la Predicción Conforme (CP). La CPP opera en dos fases distintas:

1. Paso de Optimización (Reformulación de Cuantil):
   En lugar de utilizar la restricción de probabilidad bruta, la CPP la reemplaza con una restricción de cuantil definida sobre un conjunto de datos de optimización $\{Y^{(1)}, \dots, Y^{(K)}\}$. El problema se reformula como:
   $$\min_{x \in X} J(x) \quad \text{sujeto a} \quad \hat{Q}_{\alpha(K)}(f(x, Y^{(1)}), \dots, f(x, Y^{(K)})) \leq 0$$
   Aquí, $\hat{Q}_{\alpha(K)}$ es el cuantil empírico en un nivel de confianza específico $\alpha(K)$. Los autores demuestran que esta reformulación es una instanciación de SAA, lo que permite que la CPP herede garantías a priori de la literatura de SAA para clases específicas de problemas (por ejemplo, restricciones separables).

2. Paso de Calibración (Garantías a Posteriori):
   Para proporcionar garantías de factibilidad a posteriori rigurosas sin depender de supuestos estructurales como la convexidad, la CPP utiliza un segundo conjunto de datos de calibración independiente $\{Y^{(K+1)}, \dots, Y^{(K+L)}\}$.

   • Garantías Marginales: Utilizando el Lema de Cuantil de la CP, la CPP calcula un cuantil $C_m$ sobre los datos de calibración. El Teorema 3.4 establece que la solución $x^*(K)$ satisface $P(f(x^*(K), Y) \leq C_m) \geq 1-\delta$ con respecto a la medida de producto de los datos.
   • Garantías Condicionales: Al emplear un nivel de confianza más ajustado durante el cálculo del cuantil (Lema de Cuantil Condicional), la CPP proporciona garantías que se mantienen con una alta confianza ($1-\beta$) condicionada al conjunto de datos de calibración.
   • Desplazamiento de Cuantil: Para abordar los casos donde el límite $C$ calculado es positivo, los autores proponen un método de "desplazamiento de cuantil" (Teorema 3.6). Este calcula una probabilidad de fallo ajustada $\delta^*$ basada en el número de restricciones satisfechas en el conjunto de calibración, asegurando que $P(f(x^*(K), Y) \leq 0) \geq 1-\delta^*$ con alta confianza.

Contribuciones Clave

• Nuevo Marco: La introducción de la CPP como un enfoque basado en muestreo que requiere supuestos estructurales limitados para los problemas de CCO.
• Garantías Estadísticas: La provisión de garantías de factibilidad tanto condicionales como marginales a posteriori. A diferencia del Enfoque de Escenarios (SA) estándar, estas garantías no dependen de la dimensión de la variable de decisión $n$, lo que reduce el conservadurismo para problemas de alta dimensionalidad.
• Modularidad y Versatilidad: El marco está diseñado para incorporar fácilmente diversas variantes de la Predicción Conforme. Los autores demuestran esto extendiendo la CPP a:
  • CPP Robusta (RCPP): Maneja cambios de distribución (por ejemplo, brechas sim-to-real) utilizando predicción conforme robusta y conjuntos de ambigüedad.
  • CPP de Mondrian (MCPP): Aborda restricciones de probabilidad condicionales por clase (MCCO), asegurando que las garantías de seguridad se mantengan para subgrupos específicos de la distribución de la variable aleatoria.
• Conexión con la Teoría Existente: El artículo establece que la CPP hereda garantías a priori de SAA y que sus garantías condicionales a posteriori reducen asintóticamente a los límites de Chernoff.

Resultados y Casos de Estudio
Los autores validan la CPP mediante estudios de casos numéricos que involucran problemas tanto convexos como no convexos, así como una tarea de control óptimo estocástico.

• Optimización Convexa y No Convexa: En experimentos comparando la CPP contra el Enfoque de Escenarios (SA) para problemas no convexos, la CPP demostró un desempeño competitivo. Notablemente, mientras que los métodos de SA no convexos (por ejemplo, [18, 26]) requieren pasos computacionalmente costosos para encontrar subconjuntos de soporte irreducibles para garantías a posteriori (tomando aproximadamente 10 segundos en el estudio), el cálculo del desplazamiento de cuantil de la CPP es significativamente más rápido (tiempo lineal).
• Cobertura Empírica: Los experimentos confirmaron que la cobertura empírica de las soluciones converge a los límites teóricos ($1-\delta$ o $1-\delta^*$). Los histogramas de los límites calculados centrados cerca de cero indican que la reformulación de cuantil aproxima eficazmente la restricción de probabilidad original.
• Extensiones Robusta y de Mondrian: En un problema de control óptimo estocástico (navegación robótica), la RCPP manejó con éxito un cambio de distribución (simulando un cambio en la varianza del ruido), logrando una cobertura empírica superior (0.96) en comparación con la línea base de la CPP estándar (0.80). Del mismo modo, la CPP de Mondrian mantuvo con éxito las garantías de cobertura para grupos específicos de magnitud de perturbación donde la CPP estándar falló.

Significado y Reivindicaciones
El artículo afirma que la CPP ofrece un marco computacionalmente eficiente y extensible para problemas de CCO donde los supuestos estándar (convexidad, distribuciones conocidas) no están disponibles o son difíciles de verificar. Su principal significancia radica en proporcionar certificados de factibilidad independientes de la dimensión. A diferencia del Enfoque de Escenarios, donde las garantías se vuelven más laxas a medida que aumenta el número de variables de decisión, las garantías de la CPP se mantienen robustas independientemente de la dimensionalidad, siempre que se disponga de un segundo conjunto de datos de calibración. Los autores enfatizan que este enfoque cierra la brecha entre el rigor teórico de la predicción conforme y las necesidades prácticas del control y la planificación bajo incertidumbre, ofreciendo una alternativa práctica a los métodos que dependen de análisis estructurales complejos o que producen soluciones excesivamente conservadoras.