Optimization under uncertainty: understanding orders and testing programs with specifications

1. El Problema

El problema central es encontrar todos los elementos de un conjunto finito en los que una función $f$ alcanza su mínimo (o máximo). Mientras que en la optimización clásica el codominio de $f$ está equipado con un orden total (permitiendo comparar cualquier par de valores), en escenarios reales (ciencia del clima, economía, ingeniería) esto no siempre es posible debido a dos tipos de incertidumbre:

1. Incertidumbre basada en valores (Value-based uncertainty): Ocurre cuando hay múltiples objetivos incompatibles (optimización multiobjetivo). No se puede reducir todo a un solo valor numérico sin perder información. El codominio es un vector con un orden parcial (no total), lo que genera un conjunto de soluciones óptimas (frente de Pareto) en lugar de un único mínimo.
2. Incertidumbre functorial (Functorial uncertainty): Ocurre cuando las consecuencias de una decisión no son conocidas con certeza, sino que se representan como distribuciones de probabilidad, intervalos o conjuntos de resultados posibles. Aquí, la función devuelve valores en un tipo $U\ B$ (donde $U$ es un "functor de incertidumbre") en lugar de un valor base $B$. Comparar estos valores requiere definir nuevas relaciones de orden.

El desafío es definir qué relaciones de orden son apropiadas en cada caso y cómo especificar y verificar algoritmos que manejen estas situaciones sin asumir implícitamente actitudes de riesgo (como la neutralidad al riesgo).

---

2. Metodología

Los autores utilizan la programación funcional (Haskell) para:

• Especificación Formal: Definir funciones genéricas min y argmin (y sus variantes para incertidumbre) mediante tipos y propiedades lógicas.
• Pruebas Basadas en Propiedades (Property-Based Testing): Utilizan la herramienta QuickCheck para generar casos de prueba aleatorios y verificar que las implementaciones cumplan con las especificaciones matemáticas (invariantes, condiciones de dominancia, etc.).
• Abstracción Functorial: Modelan la incertidumbre mediante funtores ($U$) como listas (List), distribuciones simples (SimpleProb), intervalos (I) o distribuciones de probabilidad (PDF).

El enfoque se centra en la claridad conceptual y la corrección formal, priorizando la especificación sobre la eficiencia computacional en las implementaciones de demostración.

---

3. Contribuciones Clave

A. Optimización Multiobjetivo (Incertidumbre de Valores)

• Definición del Frente de Pareto: Formalizan la noción de "óptimo de Pareto" para un conjunto de vectores bajo un orden parcial. Un elemento domina a otro si es mejor o igual en todas las dimensiones y estrictamente mejor en al menos una.
• Algoritmo bump: Presentan una función recursiva bump que construye el frente de Pareto incrementalmente.
  • Si un nuevo elemento es dominado por el frente existente, se descarta.
  • Si domina a elementos del frente, estos se eliminan.
  • Si es indiferente (no domina ni es dominado), se mantiene y se verifica contra el resto.
• Propiedades Verificadas: Demuestran que el algoritmo cumple con: ser un subconjunto del input, ser indiferente internamente y dominar al resto del conjunto. También discuten la falta de transitividad en la relación de "indiferencia", lo que requiere recursión en el algoritmo.

B. Optimización bajo Incertidumbre Functorial

• Generalización de min y argmin: Introducen minu y argminu, que toman una función de medida ($\mu$) como argumento adicional. Esta función mapea valores inciertos ($U\ B$) a un orden total ($C$) para permitir la comparación.
• Relación de Orden Estructural ($\prec_u$): Definen una relación de "estrictamente mejor universalmente": $ub_1 \prec_u ub_2$ si todos los valores posibles en $ub_1$ son estrictamente menores que todos los valores en $ub_2$.
• Condiciones de Monotonía (El Hallazgo Central):
  • Analizan qué propiedades debe tener la función de medida $\mu$ para garantizar que el algoritmo no devuelva soluciones que sean estructuralmente dominadas por otras opciones disponibles.
  • Condición M1 (Monotonía Puntual): Si los elementos aumentan, la medida no debe disminuir. Resultado: Insuficiente (ej. funciones constantes o longitud de lista la cumplen pero fallan en la optimización).
  • Condición M2 (Monotonía Estructural): Si $ub_1 \prec_u ub_2$, entonces $\mu(ub_1) < \mu(ub_2)$. Resultado: Necesaria y suficiente. Garantiza que si una opción es estrictamente mejor en todos sus escenarios posibles, la medida la reflejará como tal.
• Validación de Funtores: Demuestran mediante pruebas que medidas como la suma, el promedio, el mejor caso o el peor caso cumplen M2 para funtores como listas, intervalos y distribuciones simples, mientras que medidas como la "anchura" de un intervalo o funciones constantes fallan.

C. Integración de Incertidumbres

• Discuten cómo combinar incertidumbre de valores (multiobjetivo) y functorial (estocástica/epistémica) en problemas complejos como la política climática, donde se deben equilibrar costos y daños bajo incertidumbre.

---

4. Resultados

• Corrección Formal: Se han implementado y probado algoritmos genéricos que garantizan, bajo las condiciones de monotonía M2, que las soluciones encontradas no son estructuralmente dominadas.
• Identificación de Errores Comunes: Las pruebas automatizadas revelan que medidas intuitivas pero incorrectas (como minimizar la "anchura" de la incertidumbre o usar promedios en contextos de riesgo extremo) pueden llevar a seleccionar soluciones subóptimas o peligrosas.
• Aplicación a Benchmark: Se aplicaron los métodos a problemas estándar de optimización multiobjetivo (como el problema de ZDT o funciones de prueba con múltiples mínimos locales).
  • Se demostró que el muestreo aleatorio combinado con el algoritmo de Pareto puede aproximar el frente óptimo.
  • Se mostró que los algoritmos evolutivos pueden acelerar la búsqueda, pero la estructura lógica subyacente (la función bump) es la misma.
• Visualización de Riesgo: En el contexto climático, se ilustra cómo diferentes medidas (peor caso vs. valor esperado) generan frentes de Pareto con geometrías distintas, afectando la estabilidad de las decisiones políticas.

---

5. Significado e Impacto

• Pedagogía y Rigor: El trabajo proporciona un marco pedagógico para "entender los órdenes". Ayuda a los investigadores a distinguir cuándo un orden total es suficiente y cuándo se requiere un orden parcial o estructural.
• Validación de Software Científico: Ofrece una metodología para verificar la corrección de algoritmos de optimización bajo incertidumbre, crucial en campos donde los errores tienen altas consecuencias (política climática, ingeniería nuclear, economía).
• Transparencia en la Toma de Decisiones: Al hacer explícitas las funciones de medida y las condiciones de monotonía, permite a los responsables políticos y expertos de dominio entender cómo sus actitudes hacia el riesgo (aversión, neutralidad, propensión) influyen en los resultados óptimos.
• Fundamento para Verificación Formal: Las especificaciones presentadas son compatibles con sistemas de tipos dependientes (como Agda o Idris), abriendo la puerta a la verificación formal completa de estos componentes de software en el futuro.

En resumen, el artículo establece una base teórica y práctica sólida para la optimización bajo incertidumbre, utilizando la programación funcional para garantizar que los métodos utilizados sean matemáticamente consistentes y verificables, evitando las trampas de las heurísticas "caja negra".