La optimización robusta es un campo de la teoría de la optimización 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.
Historia
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 , [1] ingeniería eléctrica , [2] [3] teoría de control , [4] finanzas , [5] gestión de cartera [6] logística , [7] ingeniería de fabricación , [8] ingeniería química , [9] medicina , [10] e informática . En los problemas de ingeniería , estas formulaciones a menudo toman el nombre de "Optimización de diseño robusto", RDO o "Optimización de diseño basada en confiabilidad", RBDO.
Ejemplo 1
Considere el siguiente problema de programación lineal
dónde es un subconjunto dado de .
Lo que hace que esto sea un problema de 'optimización robusta' es la cláusula en las restricciones. Su implicación es que para un par para ser admisible, la restricción debe estar satisfecho con lo peor perteneciente a , a saber, el par que maximiza el valor de por el valor dado de .
Si el espacio de parámetros es finito (que consta de un número finito de elementos), entonces este robusto problema de optimización es en sí mismo un problema de programación lineal : para cada hay una restricción lineal .
Si no es un conjunto finito, entonces este problema es un problema de programación lineal semi-infinito , 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.
Clasificación
Hay una serie de criterios de clasificación para problemas / modelos de optimización robustos. En particular, se puede distinguir entre problemas relacionados con modelos de robustez locales y globales ; y entre modelos probabilísticos y no probabilísticos de robustez. La optimización robusta moderna se ocupa principalmente de modelos no probabilísticos de robustez que están orientados al peor de los casos y, como tales, suelen desplegar los modelos maximin de Wald .
Robustez local
Hay casos en los que se busca la 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 :
dónde denota el valor nominal del parámetro, denota una bola de radio centrado en y denota el conjunto de valores de que satisfacen determinadas condiciones de estabilidad / rendimiento asociadas con la decisión .
En palabras, la solidez (radio de estabilidad) de decisión es el radio de la bola más grande centrada en todos cuyos elementos satisfacen los requisitos de estabilidad impuestos a . La imagen es esta:
donde el rectángulo representa el conjunto de todos los valores asociado con la decisión .
Solidez global
Considere el simple problema abstracto de optimización robusta
dónde denota el conjunto de todos los valores posibles de bajo consideración.
Este es un problema de optimización robusto global en el sentido de que la restricción de robustezrepresenta todos los valores posibles de.
La dificultad es que tal restricción "global" puede ser demasiado exigente en el sentido de que no hay que satisface esta restricción. Pero incluso si tal existe, la restricción puede ser demasiado "conservadora" en el sentido de que produce una solución que genera una recompensa muy pequeña que no es representativo del desempeño de otras decisiones en . Por ejemplo, podría haber una que solo viola ligeramente la restricción de robustez, pero produce una recompensa muy grande . En tales casos, podría ser necesario relajar un poco la restricción de robustez y / o modificar el planteamiento del problema.
Ejemplo 2
Considere el caso en el que el objetivo es satisfacer una restricción. . dónde denota la variable de decisión y es un parámetro cuyo conjunto de valores posibles en . Si no hay tal que , entonces se sugiere la siguiente medida intuitiva de robustez:
dónde 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.
En palabras, la solidez de la decisión es el tamaño del subconjunto más grande de para lo cual la restricción está satisfecho por cada en este conjunto. Entonces, una decisión óptima es una decisión cuya solidez es la más grande.
Esto produce el siguiente problema de optimización robusto:
Esta noción intuitiva de robustez global no se usa a menudo en la práctica porque los problemas de optimización robustos que induce son usualmente (no siempre) muy difíciles de resolver.
Ejemplo 3
Considere el problema de la optimización robusta
dónde es una función de valor real en , y suponga que no hay una solución factible a este problema porque la restricción de robustez es demasiado exigente.
Para superar esta dificultad, dejemos ser un subconjunto relativamente pequeño de que representan valores "normales" de y considere el siguiente problema de optimización robusto:
Desde es mucho más pequeño que , su solución óptima puede no funcionar bien en una gran parte de y por lo tanto puede no ser robusto frente a la variabilidad de encima .
Una forma de solucionar esta dificultad es relajar la restricción para valores de fuera del set de manera controlada, de modo que se permitan infracciones mayores a medida que la distancia de de aumenta. Por ejemplo, considere la restricción de robustez relajada
dónde es un parámetro de control y denota la distancia de de . Por lo tanto, parala restricción de robustez relajada se reduce a la restricción de robustez original. Esto produce el siguiente problema de optimización robusto (relajado):
La función se define de tal manera que
y
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
fuera de .
Modelos de optimización robustos no probabilísticos
El paradigma dominante en esta área de optimización robusta es el modelo maximin de Wald , a saber
donde el representa al tomador de decisiones, el representa la naturaleza, es decir, la incertidumbre , representa el espacio de decisión y denota el conjunto de posibles valores de asociado con la decisión . Este es el formato clásico del modelo genérico y, a menudo, se denomina problema de optimización minimax o maximin . El modelo no probabilístico ( determinista ) se ha utilizado y se utiliza ampliamente para una optimización robusta, especialmente en el campo del procesamiento de señales. [11] [12] [13]
La programación matemática equivalente (MP) del formato clásico anterior es
Las restricciones se pueden incorporar explícitamente en estos modelos. El formato clásico genérico restringido es
El formato MP restringido equivalente se define como:
Modelos de optimización probabilísticamente robustos
Estos modelos cuantifican la incertidumbre en el valor "verdadero" del parámetro de interés mediante funciones de distribución de probabilidad. Se han clasificado tradicionalmente como programación estocástica y modelos de optimización estocástica . Recientemente, la optimización probabilísticamente robusta ha ganado popularidad mediante la introducción de teorías rigurosas como la optimización de escenarios capaz 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.
Contraparte robusta
El método de solución para 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 manejable computacionalmente. [14] [15]
Ver también
- Radio de estabilidad
- Minimax
- Estimador Minimax
- Arrepentimiento Minimax
- Estadísticas sólidas
- Toma de decisiones sólida
- Programación estocástica
- Optimización estocástica
- Teoría de la decisión de la brecha de información
- Métodos Taguchi
Referencias
- ^ Bertsimas, Dimitris; Sim, Melvyn (2004). "El precio de la robustez" . Investigación operativa . 52 (1): 35–53. doi : 10.1287 / opre.1030.0065 .
- ^ Shabanzadeh M; Sheikh-El-Eslami, MK; Haghifam, P; MR (octubre de 2015). "El diseño de una herramienta de cobertura de riesgos para centrales eléctricas virtuales mediante un enfoque de optimización robusto". Energía aplicada . 155 : 766–777. doi : 10.1016 / j.apenergy.2015.06.059 .
- ^ Shabanzadeh M; Fattahi, M (julio de 2015). Programación de mantenimiento de generación a través de una optimización robusta . 23ª Conferencia Iraní de Ingeniería Eléctrica (ICEE) . págs. 1504–1509. doi : 10.1109 / IranianCEE.2015.7146458 . ISBN 978-1-4799-1972-7.
- ^ Khargonekar, PP; Petersen, IR; Zhou, K. (1990). "Estabilización robusta de sistemas lineales inciertos: estabilización cuadrática y teoría de control / infinito H / sup". Transacciones IEEE sobre control automático . 35 (3): 356–361. doi : 10.1109 / 9.50357 .
- ^ Optimización robusta de la cartera
- ^ Md. Asadujjaman y Kais Zaman, "Optimización robusta de la cartera bajo incertidumbre de los datos" 15ª Conferencia estadística nacional, diciembre de 2014, Dhaka, Bangladesh.
- ^ Yu, Chian-Son; Li, Han-Lin (2000). "Un modelo de optimización robusto para problemas logísticos estocásticos". Revista Internacional de Economía de la Producción . 64 (1–3): 385–397. doi : 10.1016 / S0925-5273 (99) 00074-2 .
- ^ Strano, M (2006). "Optimización bajo incertidumbre de procesos de conformado de chapa por el método de elementos finitos". Actas de la Institución de Ingenieros Mecánicos, Parte B: Revista de fabricación de ingeniería . 220 (8): 1305-1315. doi : 10.1243 / 09544054JEM480 .
- ^ Bernardo, Fernando P .; Saraiva, Pedro M. (1998). "Marco de optimización robusto para parámetros de proceso y diseño de tolerancias". Revista AIChE . 44 (9): 2007-2017. doi : 10.1002 / aic.690440908 . hdl : 10316/8195 .
- ^ Chu, Millie; Zinchenko, Yuriy; Henderson, Shane G; Sharpe, Michael B (2005). "Optimización robusta para la planificación del tratamiento de radioterapia de intensidad modulada bajo incertidumbre". Física en Medicina y Biología . 50 (23): 5463–5477. doi : 10.1088 / 0031-9155 / 50/23/003 . PMID 16306645 .
- ^ Verdu, S .; Pobre, HV (1984). "Sobre la robustez de Minimax: un enfoque general y aplicaciones". Transacciones IEEE sobre teoría de la información . 30 (2): 328–340. CiteSeerX 10.1.1.132.837 . doi : 10.1109 / tit.1984.1056876 .
- ^ Kassam, SA; Pobre, HV (1985). "Técnicas robustas para el procesamiento de señales: una encuesta". Actas del IEEE . 73 (3): 433–481. doi : 10.1109 / proc.1985.13167 . hdl : 2142/74118 .
- ^ M. Danés Nisar. "Robustez de Minimax en el procesamiento de señales para comunicaciones" , Shaker Verlag, ISBN 978-3-8440-0332-1 , agosto de 2011.
- ^ Ben-Tal A., El Ghaoui, L. y Nemirovski, A. (2009). Optimización robusta. Serie de Princeton en Matemáticas Aplicadas, Princeton University Press, 9-16.
- ^ Leyffer S., Menickelly M., Munson T., Vanaret C. y Wild S. M (2020). Una encuesta de optimización robusta no lineal. INFOR: Sistemas de información e investigación operativa, Taylor \ & Francis.
Otras lecturas
- 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 operativa . 23 (4): 769–805. CiteSeerX 10.1.1.135.798 . doi : 10.1287 / moor.23.4.769 .
- Ben-Tal, A .; Nemirovski, A. (1999). "Soluciones robustas para programas lineales inciertos". Cartas de investigación operativa . 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 .
- 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. Serie de Princeton en Matemáticas Aplicadas, 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 .
- 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 .
- Chen, W .; Sim, M. (2009). "Optimización basada en objetivos". Investigación operativa . 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 a la programación estocástica". Investigación operativa . 56 (2): 344–357. doi : 10.1287 / opre.1070.0457 .
- Chen, X .; Sim, M .; Sol, P. (2007). "Una perspectiva de optimización robusta en la programación estocástica". Investigación operativa . 55 (6): 1058–1071. doi : 10.1287 / opre.1070.0441 .
- Dembo, R. (1991). "Optimización de escenarios". Anales de investigación operativa . 30 (1): 63–80. doi : 10.1007 / bf02204809 .
- 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". Ciencias de la gestión . 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 una optimización convexa robusta con oráculos pesimistas". Métodos y software de optimización . 24 (3): 381–406. CiteSeerX 10.1.1.416.4912 . doi : 10.1080 / 10556780802712889 .
- Mulvey, JM; Vanderbei, RJ; Zenios, SA (1995). "Optimización robusta de sistemas a gran escala". Investigación operativa . 43 (2): 264–281. doi : 10.1287 / opre.43.2.264 .
- Rosenblat, MJ (1987). "Un enfoque sólido 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 Optimidad como Criterios de Decisiones Estratégicas". Investigación operativa trimestral . 23 (4): 413–430. doi : 10.2307 / 3007957 . JSTOR 3007957 .
- Rustem B. y Howe M. (2002). Algoritmos para el diseño del 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 severa incertidumbre" . Toma de decisiones en manufactura y servicios . 1 (1-2): 111-136. doi : 10.7494 / dmms.2007.1.2.111 .
- Sniedovich, M (2008). "Modelo de Maximin de Wald: ¡un tesoro disfrazado!". Revista de Financiamiento de Riesgos . 9 (3): 287-291. doi : 10.1108 / 15265940810875603 .
- Sniedovich, M (2010). "Una vista de pájaro de la teoría de la decisión de brecha de información". Revista de Financiamiento de Riesgos . 11 (3): 268-283. doi : 10.1108 / 15265941011043648 .
- Wald, A (1939). "Contribuciones a la teoría de la estimación estadística y testeo de hipótesis" . Los anales de las 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". Los anales de las 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 de mantenimiento de generación mediante optimización robusta". 2015 23a Conferencia Iraní de Ingeniería Eléctrica . págs. 1504–1509. doi : 10.1109 / IranianCEE.2015.7146458 . ISBN 978-1-4799-1972-7.
enlaces externos
- ROMA: Optimización robusta simplificada
- Toma de decisiones sólida en condiciones de gran incertidumbre