Saltar al contenido
Volver a los resultados

Optimización Robusta — Programación Matemática de Peor Caso

Propuesto por
Ben-Tal, El Ghaoui & Nemirovski (seminal book, 2009); Bertsimas & Sim (tractable polyhedral formulation, 2004)
Año
1970s theoretical roots; modern tractable form from late 1990s–2004
Tipo
Mathematical programming framework

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

La optimización robusta es un marco de programación matemática, formalizado por Ben-Tal y Nemirovski a finales de los años 90 y hecho ampliamente tratable por Bertsimas y Sim (2004), que encuentra decisiones garantizadas para funcionar de manera aceptable bajo cada escenario dentro de un conjunto de incertidumbre predefinido, en lugar de asumir que los valores de los parámetros se conocen exactamente.

En lugar de optimizar para un único resultado esperado, minimiza el objetivo de peor caso en todas las realizaciones plausibles de datos inciertos.

La intuición detrás del método

La optimización ordinaria confía en los números que se le dan. La optimización robusta pregunta: ¿qué pasa si esos números son incorrectos, dentro de un rango acotado? Encuentra la decisión que menos perjudica cuando la naturaleza elige la peor entrada posible dentro de ese rango. Piense en ello como el diseño de un puente para que resista no la carga promedio, sino la carga creíble más pesada, aceptando un modesto costo de rendimiento en el caso típico a cambio de una garantía en el caso malo.

Historia

Las raíces teóricas de la optimización robusta se remontan a Soyster (1971) y a la teoría de decisión minimax de Wald (1945). El campo recibió una base moderna y tratable por Arkadi Nemirovski y Aharon Ben-Tal en una serie de artículos a partir de 1997, culminando en su monografía de 2009 con El Ghaoui. Dimitris Bertsimas y Melvyn Sim (2004) introdujeron la formulación de presupuesto de incertidumbre (poliédrica) que preserva la linealidad del problema nominal e hizo que la programación lineal robusta fuera ampliamente accesible. Desde entonces, la optimización robusta se ha expandido para cubrir programas enteros, formulaciones de dos etapas y conjuntos de incertidumbre basados en datos derivados de observaciones históricas.

Cuándo usarlo

La optimización robusta es apropiada cuando la incertidumbre de los parámetros es acotada pero su distribución es desconocida o poco fiable, cuando se requieren garantías de peor caso (contextos críticos para la seguridad o regulatorios), y cuando se necesita una única decisión implementable en lugar de una distribución de políticas como en la programación estocástica. Funciona con variables de decisión continuas. No hay requisito de tamaño mínimo de muestra — el conjunto de incertidumbre se define analíticamente, no se estima a partir de datos. No es adecuada cuando la incertidumbre es ilimitada, cuando una distribución de probabilidad para los parámetros inciertos está disponible y es precisa (usar optimización estocástica en su lugar), o cuando menos de aproximadamente 1.000 evaluaciones de escenarios serían factibles para la validación basada en escenarios.

Limitaciones y consideraciones

  • La solución es necesariamente más conservadora que el óptimo nominal; el precio de la robustez puede ser significativo cuando el conjunto de incertidumbre es grande.
  • Definir un conjunto de incertidumbre realista requiere conocimiento del dominio; un conjunto mal elegido puede ser demasiado conservador o no cubrir las perturbaciones reales.
  • Para problemas no convexos o programas de enteros mixtos generales, las reformulaciones robustas pueden ser NP-difíciles y requieren algoritmos de descomposición especializados.
  • La optimización robusta no incorpora información de probabilidad; cuando una distribución fiable está disponible, la programación estocástica puede producir un rendimiento esperado mayor.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Proporciona garantías deterministas de peor caso sin requerir una distribución de probabilidad para parámetros inciertos.
  • Las reformulaciones para conjuntos de incertidumbre convexos son a menudo tan tratables como el problema nominal — sin explosión computacional adicional.
  • El nivel de conservadurismo es directamente controlable a través del tamaño y la forma del conjunto de incertidumbre, haciendo que la compensación robustez-rendimiento sea explícita y transparente.
  • Aplicable en diversos dominios — cadena de suministro, finanzas, diseño de ingeniería, sistemas de energía — dondequiera que exista incertidumbre paramétrica acotada.

Aplicaciones

  • Diseño de redes de cadena de suministro y logística bajo demanda y tiempos de entrega inciertos.
  • Optimización de carteras bajo incertidumbre en los rendimientos de los activos — la frontera robusta media-varianza.
  • Diseño de ingeniería (estructural, mecánica, aeroespacial) donde las tolerancias de fabricación introducen incertidumbre paramétrica.
  • Planificación de sistemas energéticos bajo generación renovable y precios de combustible inciertos.
  • Problemas de programación y enrutamiento donde los tiempos de procesamiento o de viaje se conocen de forma imprecisa.

Cómo funciona

Cómo funciona

1

El analista especifica un conjunto de incertidumbre — la región de perturbaciones plausibles alrededor de los valores nominales de los parámetros. Las formas comunes incluyen conjuntos de caja (cada parámetro varía independientemente dentro de un intervalo), elipsoidales (perturbaciones acotadas en norma euclidiana), poliédricos y con presupuesto restringido (Bertsimas-Sim). La elección codifica una suposición sobre cuán correlacionada y severa puede ser la incertidumbre, y controla directamente el conservadurismo de la solución resultante.

2

El problema de optimización se plantea en forma minimax: minimizar sobre las decisiones el costo máximo que la incertidumbre adversaria puede imponer. Formalmente, el objetivo se convierte en min_x max_{u in U} f(x, u) sujeto a restricciones que deben cumplirse para todo u en el conjunto de incertidumbre U. Esta maximización interna modela a la naturaleza eligiendo la peor realización de los parámetros inciertos.

3

Para conjuntos de incertidumbre convexos, el problema minimax es analíticamente equivalente a un programa convexo determinista — a menudo un programa de cono de segundo orden para conjuntos elipsoidales o un programa lineal para conjuntos poliédricos. Esta reformulación tratable es la clave de Ben-Tal y Nemirovski: las contrapartes robustas de muchos problemas clásicos no son más difíciles de resolver que el problema nominal. Para estructuras no convexas, la descomposición de Benders divide el problema en un subproblema maestro y adversario que se resuelven iterativamente.

4

El programa determinista reformulado se pasa a un solucionador convexo o de enteros mixtos estándar. Dado que la reformulación es típicamente un programa cónico o lineal, los solucionadores listos para usar lo manejan eficientemente. El solucionador devuelve un único vector de decisión — la solución óptima robusta — que es factible y casi óptima en todos los escenarios del conjunto de incertidumbre.

5

El analista examina el precio de la robustez: la brecha entre el valor objetivo óptimo nominal (sin incertidumbre) y el valor óptimo robusto. Un conjunto de incertidumbre ajustado produce una brecha pequeña pero garantías más débiles; un conjunto grande produce una fuerte protección de peor caso a un mayor costo de rendimiento en escenarios típicos. El análisis de sensibilidad sobre el tamaño del conjunto de incertidumbre guía la elección final del nivel de conservadurismo.

Errores comunes

  • Elegir un conjunto de incertidumbre demasiado grande produce soluciones tan conservadoras que son prácticamente inútiles — calibrar el tamaño del conjunto contra el conocimiento del dominio o los límites de variabilidad históricos.
  • Confundir optimización robusta con optimización estocástica: si una distribución de probabilidad para los parámetros inciertos está bien establecida y es confiable, la programación estocástica es probablemente más apropiada.
  • Aplicar optimización robusta cuando la incertidumbre es verdaderamente ilimitada invalida la garantía de peor caso — la optimización robusta asume perturbaciones acotadas.
  • No examinar el precio de la robustez después de resolver: una gran brecha entre los objetivos nominal y robusto indica que el conjunto de incertidumbre puede ser irrealistamente amplio y debe revisarse.

Preguntas frecuentes

¿Cómo se diferencia la optimización robusta de la programación estocástica?

La optimización robusta busca una única decisión que sea factible y casi óptima para cada escenario en un conjunto de incertidumbre acotado, sin asumir ninguna distribución de probabilidad sobre esos escenarios. La programación estocástica utiliza una distribución de probabilidad conocida (o estimada) para optimizar el rendimiento esperado, produciendo típicamente una política o acciones de recurso en lugar de una solución fija. Elija optimización robusta cuando las garantías de peor caso importan y no hay una distribución fiable disponible; elija programación estocástica cuando se conoce una buena distribución y el rendimiento promedio es el criterio principal.

¿Cuál es el precio de la robustez?

El precio de la robustez es el aumento en el valor del objetivo (para un problema de minimización) en comparación con la solución óptima nominal obtenida sin tener en cuenta la incertidumbre. Bertsimas y Sim (2004) demostraron que para su formulación de presupuesto de incertidumbre, este precio crece solo como la raíz cuadrada del número de parámetros inciertos, haciéndolo modesto en la práctica. Examinar esta brecha después de resolver es esencial: si es muy grande, el conjunto de incertidumbre es probablemente demasiado conservador.

¿Qué forma de conjunto de incertidumbre debo elegir?

Los conjuntos de caja son los más simples y conservadores — cada parámetro varía independientemente. Los conjuntos elipsoidales (Ben-Tal y Nemirovski) modelan perturbaciones correlacionadas acotadas en norma euclidiana y conducen a programas de cono de segundo orden. Los conjuntos poliédricos / con presupuesto restringido (Bertsimas y Sim) controlan el número de parámetros que pueden desviarse simultáneamente, preservando la linealidad y reduciendo el conservadurismo. Elija según el conocimiento del dominio sobre cómo co-ocurren las perturbaciones y qué clase de solucionador está disponible.

¿Puede la optimización robusta manejar variables de decisión enteras?

Sí, pero la programación entera y de enteros mixtos robusta es sustancialmente más difícil. Las contrapartes robustas de los programas lineales de enteros mixtos son a menudo NP-difíciles en el peor caso. La descomposición de Benders y los algoritmos de generación de columnas y restricciones son enfoques estándar, pero el tamaño del problema y la complejidad del conjunto de incertidumbre deben mantenerse manejables.

Métodos relacionados

Fuentes

  1. Ben-Tal, A., El Ghaoui, L. & Nemirovski, A. (2009). Robust Optimization. Princeton University Press.

    ISBN: 9780691143682
    Copiado.
  2. Bertsimas, D. & Sim, M. (2004). The Price of Robustness. Operations Research, 52(1), 35-53.

    Abrir referencia DOI
    Copiado.