Optimización robusta

La optimización robusta es un campo de la teoría de optimización matemática que se ocupa de problemas de optimización en los que se busca una cierta medida de robustez frente a la incertidumbre que puede representarse como variabilidad determinista en el valor de los parámetros del problema en sí y/o su solución. Está relacionada con los métodos de optimización probabilística, como la optimización con restricciones de azar, pero a menudo se distingue de ellos. ^{[1] [2]}

Los orígenes de la optimización robusta se remontan al establecimiento de la teoría de la decisión moderna en la década de 1950 y al uso del análisis del peor de los casos y del modelo maximin de Wald como herramienta para el tratamiento de la incertidumbre severa. Se convirtió en una disciplina propia en la década de 1970 con desarrollos paralelos en varios campos científicos y tecnológicos. A lo largo de los años, se ha aplicado en estadística , pero también en investigación de operaciones , ^[3] ingeniería eléctrica , ^{[4] [5] [6]} teoría de control , ^[7] finanzas , ^[8] gestión de cartera ^[9] logística , ^[10] ingeniería de fabricación , ^[11] ingeniería química , ^[12] medicina , ^[13] y ciencias de la computación . En problemas de ingeniería , estas formulaciones a menudo toman el nombre de "Optimización de diseño robusto", RDO u "Optimización de diseño basada en confiabilidad", RBDO.

Considere el siguiente problema de programación lineal

${\displaystyle \max _{x,y}\ \{3x+2y\}\ \ \mathrm {sujeto\ a} \ \ x,y\geq 0;cx+dy\leq 10,\forall (c,d)\in P}$

donde es un subconjunto dado de . ${\estilo de visualización P}$${\displaystyle \mathbb {R} ^{2}}$

Lo que hace que este sea un problema de "optimización robusta" es la cláusula de las restricciones. Su implicación es que para que un par sea admisible, la restricción debe ser satisfecha por el peor perteneciente a , es decir, el par que maximiza el valor de para el valor dado de . ${\displaystyle \paratodos (c,d)\en P}$${\estilo de visualización (x,y)}$${\displaystyle cx+dy\leq 10}$ ${\displaystyle (c,d)\en P}$${\estilo de visualización (x,y)}$${\displaystyle (c,d)\en P}$${\displaystyle cx+dy}$${\estilo de visualización (x,y)}$

Si el espacio de parámetros es finito (compuesto por un número finito de elementos), entonces este problema de optimización robusta en sí mismo es un problema de programación lineal : para cada uno hay una restricción lineal . ${\estilo de visualización P}$${\displaystyle (c,d)\en P}$${\displaystyle cx+dy\leq 10}$

Si no es un conjunto finito, entonces este problema es un problema de programación lineal semi-infinita , es decir, un problema de programación lineal con un número finito de (2) variables de decisión y un número infinito de restricciones. ${\estilo de visualización P}$

Existen varios criterios de clasificación para los problemas/modelos de optimización robusta. En particular, se puede distinguir entre problemas que abordan modelos locales y globales de robustez, y entre modelos de robustez probabilísticos y no probabilísticos . La optimización robusta moderna aborda principalmente modelos de robustez no probabilísticos que están orientados al peor de los casos y, como tales, suelen implementar los modelos maximin de Wald .

Existen casos en los que se busca robustez frente a pequeñas perturbaciones en un valor nominal de un parámetro. Un modelo muy popular de robustez local es el modelo de radio de estabilidad :

${\displaystyle {\hat {\rho }}(x,{\hat {u}}):=\max _{\rho \geq 0}\ \{\rho :u\in S(x),\forall u\in B(\rho ,{\hat {u}})\}}$

donde denota el valor nominal del parámetro, denota una bola de radio centrada en y denota el conjunto de valores de que satisfacen las condiciones de estabilidad/rendimiento dadas asociadas con la decisión . ${\displaystyle {\hat {u}}}$${\displaystyle B(\rho ,{\hat {u}})}$${\estilo de visualización \rho}$${\displaystyle {\hat {u}}}$${\estilo de visualización S(x)}$${\estilo de visualización u}$${\estilo de visualización x}$

En palabras, la robustez (radio de estabilidad) de la decisión es el radio de la bola más grande centrada en todos cuyos elementos satisfacen los requisitos de estabilidad impuestos en . La imagen es la siguiente: ${\estilo de visualización x}$${\displaystyle {\hat {u}}}$${\estilo de visualización x}$

donde el rectángulo representa el conjunto de todos los valores asociados con la decisión . ${\displaystyle U(x)}$${\estilo de visualización u}$${\estilo de visualización x}$

Consideremos el simple y abstracto problema de optimización robusta

${\displaystyle \max _{x\en X}\ \{f(x):g(x,u)\leq b,\forall u\en U\}}$

donde denota el conjunto de todos los valores posibles de bajo consideración. ${\estilo de visualización U}$${\estilo de visualización u}$

Este es un problema de optimización robusta global en el sentido de que la restricción de robustez representa todos los valores posibles de . ${\displaystyle g(x,u)\leq b,\para todo u\en U}$${\estilo de visualización u}$

La dificultad es que una restricción "global" de este tipo puede ser demasiado exigente en el sentido de que no existe una solución que la satisfaga. Pero incluso si existe una , la restricción puede ser demasiado "conservadora" en el sentido de que produce una solución que genera un resultado muy pequeño que no es representativo del desempeño de otras decisiones en . Por ejemplo, podría haber una solución que solo viole ligeramente la restricción de robustez pero que produzca un resultado muy grande . En tales casos, podría ser necesario relajar un poco la restricción de robustez y/o modificar el enunciado del problema. ${\displaystyle x\en X}$${\displaystyle x\en X}$${\displaystyle x\en X}$${\estilo de visualización f(x)}$${\estilo de visualización X}$${\displaystyle x'\en X}$${\estilo de visualización f(x')}$

Consideremos el caso en el que el objetivo es satisfacer una restricción . donde denota la variable de decisión y es un parámetro cuyo conjunto de valores posibles en . Si no existe tal que , entonces se sugiere la siguiente medida intuitiva de robustez: ${\displaystyle g(x,u)\leq b,}$${\displaystyle x\en X}$${\estilo de visualización u}$${\estilo de visualización U}$${\displaystyle x\en X}$${\displaystyle g(x,u)\leq b,\para todo u\en U}$

${\displaystyle \rho (x):=\max _{Y\subseteq U}\ \{tamaño(Y):g(x,u)\leq b,\forall u\in Y\}\ ,\ x\in X}$

donde denota una medida apropiada del "tamaño" del conjunto . Por ejemplo, si es un conjunto finito, entonces podría definirse como la cardinalidad del conjunto . ${\displaystyle tamaño(Y)}$${\estilo de visualización Y}$${\estilo de visualización U}$${\displaystyle tamaño(Y)}$${\estilo de visualización Y}$

En otras palabras, la robustez de una decisión es el tamaño del subconjunto más grande para el cual se satisface la restricción para cada uno de los elementos de este conjunto. Una decisión óptima es entonces una decisión cuya robustez es la más grande. ${\estilo de visualización U}$${\displaystyle g(x,u)\leq b}$${\estilo de visualización u}$

Esto produce el siguiente problema de optimización robusto:

${\displaystyle \max _{x\en X,Y\subseteq U}\ \{tamaño(Y):g(x,u)\leq b,\forall u\en Y\}}$

Esta noción intuitiva de robustez global no se utiliza a menudo en la práctica porque los problemas de optimización robusta que induce suelen ser (no siempre) muy difíciles de resolver.

Consideremos el problema de optimización robusta

${\displaystyle z(U):=\max _{x\en X}\ \{f(x):g(x,u)\leq b,\forall u\en U\}}$

donde es una función de valor real en , y supongamos que no hay una solución factible para este problema porque la restricción de robustez es demasiado exigente. ${\estilo de visualización g}$${\displaystyle X\veces U}$${\displaystyle g(x,u)\leq b,\para todo u\en U}$

Para superar esta dificultad, supongamos que un subconjunto relativamente pequeño de representa valores "normales" de y consideremos el siguiente problema de optimización robusta: ${\displaystyle {\mathcal {N}}}$${\estilo de visualización U}$${\estilo de visualización u}$

${\displaystyle z({\mathcal {N}}):=\max _{x\in X}\ \{f(x):g(x,u)\leq b,\forall u\in {\mathcal {N}}\}}$

Dado que es mucho más pequeño que , su solución óptima puede no funcionar bien en una gran porción de y, por lo tanto, puede no ser robusta frente a la variabilidad de más de . ${\displaystyle {\mathcal {N}}}$${\estilo de visualización U}$${\estilo de visualización U}$${\estilo de visualización u}$${\estilo de visualización U}$

Una forma de solucionar esta dificultad es relajar la restricción para los valores de fuera del conjunto de una manera controlada, de modo que se permitan violaciones mayores a medida que aumenta la distancia de desde . Por ejemplo, considere la restricción de robustez relajada ${\displaystyle g(x,u)\leq b}$${\estilo de visualización u}$${\displaystyle {\mathcal {N}}}$${\estilo de visualización u}$${\displaystyle {\mathcal {N}}}$

${\displaystyle g(x,u)\leq b+\beta \cdot dist(u,{\mathcal {N}})\ ,\ \para todo u\en U}$

donde es un parámetro de control y denota la distancia de desde . Por lo tanto, para la restricción de robustez relajada se reduce nuevamente a la restricción de robustez original. Esto produce el siguiente problema de optimización robusta (relajada): ${\displaystyle \beta \geq 0}$${\displaystyle dist(u,{\mathcal {N}})}$${\estilo de visualización u}$${\displaystyle {\mathcal {N}}}$${\displaystyle \beta = 0}$

${\displaystyle z({\mathcal {N}},U):=\max _{x\in X}\ \{f(x):g(x,u)\leq b+\beta \cdot dist(u,{\mathcal {N}})\ ,\ \para todo u\in U\}}$

La función se define de tal manera que ${\estilo de visualización dist}$

${\displaystyle dist(u,{\mathcal {N}})\geq 0,\forall u\in U}$

y

${\displaystyle dist(u,{\mathcal {N}})=0,\para todo u\en {\mathcal {N}}}$

y por lo tanto la solución óptima al problema relajado satisface la restricción original para todos los valores de en . También satisface la restricción relajada ${\displaystyle g(x,u)\leq b}$${\estilo de visualización u}$${\displaystyle {\mathcal {N}}}$

${\displaystyle g(x,u)\leq b+\beta \cdot dist(u,{\mathcal {N}})}$

afuera . ${\displaystyle {\mathcal {N}}}$

El paradigma dominante en esta área de optimización robusta es el modelo maximin de Wald , es decir

${\displaystyle \max _{x\in X}\min _{u\in U(x)}f(x,u)}$

donde representa al que toma la decisión, representa la naturaleza, es decir, la incertidumbre , representa el espacio de decisión y denota el conjunto de posibles valores de asociados con la decisión . Este es el formato clásico del modelo genérico y a menudo se lo denomina problema de optimización minimax o maximin . El modelo no probabilístico ( determinista ) ha sido y está siendo ampliamente utilizado para la optimización robusta, especialmente en el campo del procesamiento de señales. ^{[14] [15] [16]}${\displaystyle \max }$${\displaystyle \min }$${\displaystyle X}$${\displaystyle U(x)}$${\displaystyle u}$${\displaystyle x}$

La programación matemática (PM) equivalente del formato clásico anterior es

${\displaystyle \max _{x\in X,v\in \mathbb {R} }\ \{v:v\leq f(x,u),\forall u\in U(x)\}}$

Se pueden incorporar restricciones explícitamente en estos modelos. El formato clásico genérico restringido es

${\displaystyle \max _{x\in X}\min _{u\in U(x)}\ \{f(x,u):g(x,u)\leq b,\forall u\in U(x)\}}$

El formato MP restringido equivalente se define como:

${\displaystyle \max _{x\in X,v\in \mathbb {R} }\ \{v:v\leq f(x,u),g(x,u)\leq b,\forall u\in U(x)\}}$

Estos modelos cuantifican la incertidumbre en el valor "verdadero" del parámetro de interés mediante funciones de distribución de probabilidad. Tradicionalmente se han clasificado como modelos de programación estocástica y de optimización estocástica . Recientemente, la optimización probabilísticamente robusta ha ganado popularidad gracias a la introducción de teorías rigurosas como la optimización de escenarios capaces de cuantificar el nivel de robustez de las soluciones obtenidas por aleatorización. Estos métodos también son relevantes para los métodos de optimización basados ​​en datos.

El método de solución de muchos programas robustos implica la creación de un equivalente determinista, llamado contraparte robusta. La dificultad práctica de un programa robusto depende de si su contraparte robusta es computacionalmente manejable. ^{[17] [18]}

• Radio de estabilidad
• Minimáximo
• Estimador minimax
• Arrepentimiento de Minimax
• Estadísticas robustas
• Toma de decisiones robusta
• Programación estocástica
• Optimización estocástica
• Teoría de la decisión basada en la brecha de información
• Métodos de Taguchi

• HJ Greenberg. Glosario de programación matemática. World Wide Web, http://glossary.computing.society.informs.org/, 1996-2006. Editado por INFORMS Computing Society.
• Ben-Tal, A.; Nemirovski, A. (1998). "Optimización convexa robusta". Matemáticas de la investigación de operaciones . 23 (4): 769–805. CiteSeerX  10.1.1.135.798 . doi :10.1287/moor.23.4.769. S2CID  15905691.
• Ben-Tal, A.; Nemirovski, A. (1999). "Soluciones robustas para programas lineales inciertos". Operations Research Letters . 25 : 1–13. CiteSeerX  10.1.1.424.861 . doi :10.1016/s0167-6377(99)00016-4.
• Ben-Tal, A.; Arkadi Nemirovski, A. (2002). "Optimización robusta: metodología y aplicaciones". Programación matemática, serie B . 92 (3): 453–480. CiteSeerX  10.1.1.298.7965 . doi :10.1007/s101070100286. S2CID  1429482.
• Ben-Tal A., El Ghaoui, L. y Nemirovski, A. (2006). Programación matemática, Número especial sobre optimización robusta, volumen 107(1-2).
• Ben-Tal A., El Ghaoui, L. y Nemirovski, A. (2009). Optimización robusta. Princeton Series in Applied Mathematics, Princeton University Press.
• Bertsimas, D.; Sim, M. (2003). "Optimización discreta robusta y flujos de red". Programación matemática . 98 (1–3): 49–71. CiteSeerX  10.1.1.392.4470 . doi :10.1007/s10107-003-0396-4. S2CID  1279073.
• Bertsimas, D.; Sim, M. (2006). "Aproximaciones manejables a problemas de optimización cónica robusta Dimitris Bertsimas". Programación matemática . 107 (1): 5–36. CiteSeerX  10.1.1.207.8378 . doi :10.1007/s10107-005-0677-1. S2CID  900938.
• Chen, W.; Sim, M. (2009). "Optimización basada en objetivos". Investigación de operaciones . 57 (2): 342–357. doi :10.1287/opre.1080.0570.
• Chen, X.; Sim, M.; Sun, P.; Zhang, J. (2008). "Un enfoque de aproximación basado en decisiones lineales para la programación estocástica". Investigación de operaciones . 56 (2): 344–357. doi :10.1287/opre.1070.0457.
• Chen, X.; Sim, M.; Sun, P. (2007). "Una perspectiva de optimización robusta en la programación estocástica". Investigación de operaciones . 55 (6): 1058–1071. doi :10.1287/opre.1070.0441.
• Dembo, R (1991). "Optimización de escenarios". Anales de Investigación de Operaciones . 30 (1): 63–80. doi :10.1007/bf02204809. S2CID  44126126.
• Dodson, B., Hammett, P. y Klerx, R. (2014) Diseño probabilístico para optimización y robustez para ingenieros John Wiley & Sons, Inc. ISBN 978-1-118-79619-1 
• Gupta, SK; Rosenhead, J. (1968). "Robustez en decisiones de inversión secuenciales". Management Science . 15 (2): 18–29. doi :10.1287/mnsc.15.2.B18.
• Kouvelis P. y Yu G. (1997). Optimización discreta robusta y sus aplicaciones, Kluwer.
• Mutapcic, Almir; Boyd, Stephen (2009). "Métodos de conjuntos de corte para optimización convexa robusta con oráculos pesimistas". Métodos de optimización y software . 24 (3): 381–406. CiteSeerX  10.1.1.416.4912 . doi :10.1080/10556780802712889. S2CID  16443437.
• Mulvey, JM; Vanderbei, RJ; Zenios, SA (1995). "Optimización robusta de sistemas a gran escala". Investigación de operaciones . 43 (2): 264–281. doi :10.1287/opre.43.2.264.
• Nejadseyfi, O., Geijselaers HJM, van den Boogaard AH (2018). "Optimización robusta basada en la evaluación analítica de la propagación de la incertidumbre". Engineering Optimization 51 (9): 1581-1603. doi:10.1080/0305215X.2018.1536752.
• Rosenblat, MJ (1987). "Un enfoque robusto para el diseño de instalaciones". Revista Internacional de Investigación en Producción . 25 (4): 479–486. doi :10.1080/00207548708919855.
• Rosenhead, MJ; Elton, M; Gupta, SK (1972). "Robustez y optimalidad como criterios para decisiones estratégicas". Operational Research Quarterly . 23 (4): 413–430. doi :10.2307/3007957. JSTOR  3007957.
• Rustem B. y Howe M. (2002). Algoritmos para el diseño en el peor de los casos y aplicaciones para la gestión de riesgos, Princeton University Press.
• Sniedovich, M (2007). "El arte y la ciencia de modelar la toma de decisiones bajo incertidumbre severa". Toma de decisiones en manufactura y servicios . 1 (1–2): 111–136. doi : 10.7494/dmms.2007.1.2.111 .
• Sniedovich, M (2008). "El modelo Maximin de Wald: ¡un tesoro disfrazado!". Journal of Risk Finance . 9 (3): 287–291. doi :10.1108/15265940810875603.
• Sniedovich, M (2010). "Una perspectiva general de la teoría de decisiones sobre brechas de información". Journal of Risk Finance . 11 (3): 268–283. doi :10.1108/15265941011043648.
• Wald, A (1939). "Contribuciones a la teoría de la estimación estadística y la prueba de hipótesis". Anales de Matemáticas . 10 (4): 299–326. doi : 10.1214/aoms/1177732144 .
• Wald, A (1945). "Funciones de decisión estadística que minimizan el riesgo máximo". Anales de Matemáticas . 46 (2): 265–280. doi :10.2307/1969022. JSTOR  1969022.
• Wald, A. (1950). Funciones de decisión estadística, John Wiley, NY.
• Shabanzadeh, Morteza; Fattahi, Mohammad (2015). "Programación del mantenimiento de la generación mediante optimización robusta". 2015 23.ª Conferencia iraní sobre ingeniería eléctrica . págs. 1504–1509. doi :10.1109/IranianCEE.2015.7146458. ISBN . 978-1-4799-1972-7.S2CID8774918  .​

• ROMA: Optimización robusta simplificada
• Toma de decisiones sólida en condiciones de gran incertidumbre
• Robustimizer: software de optimización robusto