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]}

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 , ^[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.

Ejemplo 1

Considere el siguiente problema de programación lineal

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

donde es un subconjunto dado de . ${\displaystyle 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 \forall (c,d)\in P}$ ${\displaystyle (x,y)}$ ${\displaystyle cx+dy\leq 10}$ ${\displaystyle (c,d)\in P}$ ${\displaystyle (x,y)}$ ${\displaystyle (c,d)\in P}$ ${\displaystyle cx+dy}$ ${\displaystyle (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 . ${\displaystyle P}$ ${\displaystyle (c,d)\in 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. ${\displaystyle P}$

Clasificación

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 .

Robustez local

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}})}$ ${\displaystyle \rho }$ ${\displaystyle {\hat {u}}}$ ${\displaystyle S(x)}$ ${\displaystyle u}$ ${\displaystyle 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: ${\displaystyle x}$ ${\displaystyle {\hat {u}}}$ ${\displaystyle x}$

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

Robustez global

Consideremos el simple y abstracto problema de optimización robusta

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

donde denota el conjunto de todos los valores posibles de bajo consideración. ${\displaystyle U}$ ${\displaystyle 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,\forall u\in U}$ ${\displaystyle 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\in X}$ ${\displaystyle x\in X}$ ${\displaystyle x\in X}$ ${\displaystyle f(x)}$ ${\displaystyle X}$ ${\displaystyle x'\in X}$ ${\displaystyle f(x')}$

Ejemplo 2

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\in X}$ ${\displaystyle u}$ ${\displaystyle U}$ ${\displaystyle x\in X}$ ${\displaystyle g(x,u)\leq b,\forall u\in U}$

${\displaystyle \rho (x):=\max _{Y\subseteq U}\ \{size(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 size(Y)}$ ${\displaystyle Y}$ ${\displaystyle U}$ ${\displaystyle size(Y)}$ ${\displaystyle Y}$

En otras palabras, la robustez de una decisión es el tamaño del subconjunto más grande de 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. ${\displaystyle U}$ ${\displaystyle g(x,u)\leq b}$ ${\displaystyle u}$

Esto produce el siguiente problema de optimización robusto:

${\displaystyle \max _{x\in X,Y\subseteq U}\ \{size(Y):g(x,u)\leq b,\forall u\in 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.

Ejemplo 3

Consideremos el problema de optimización robusta

${\displaystyle z(U):=\max _{x\in X}\ \{f(x):g(x,u)\leq b,\forall u\in 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. ${\displaystyle g}$ ${\displaystyle X\times U}$ ${\displaystyle g(x,u)\leq b,\forall u\in 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}}}$ ${\displaystyle U}$ ${\displaystyle 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}}}$ ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle u}$ ${\displaystyle 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}$ ${\displaystyle u}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle u}$ ${\displaystyle {\mathcal {N}}}$

${\displaystyle g(x,u)\leq b+\beta \cdot dist(u,{\mathcal {N}})\ ,\ \forall u\in 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}})}$ ${\displaystyle 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}})\ ,\ \forall u\in U\}}$

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

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

y

${\displaystyle dist(u,{\mathcal {N}})=0,\forall u\in {\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}$ ${\displaystyle u}$ ${\displaystyle {\mathcal {N}}}$

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

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

Modelos de optimización robusta no probabilística

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)\}}$

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. 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.

Contraparte robusta

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]}

Véase también

• Radio de estabilidad
• Minimáximo
• Estimador minimax
• Minimax arrepentido
• 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

Referencias

1. Riaz, Muhammad; Ahmad, Sadiq; Hussain, Irshad; Naeem, Muhammad; Mihet-Popa, Lucian (2022). "Técnicas de optimización probabilística en sistemas de energía inteligentes". Energías . 15 (3): 825. doi : 10.3390/en15030825 . hdl : 11250/2988376 .
2. https://people.eecs.berkeley.edu/~elghaoui/Teaching/EE227A/lecture24.pdf ^{[ URL básica PDF ]}
3. Bertsimas, Dimitris; Sim, Melvyn (2004). "El precio de la robustez". Investigación de operaciones . 52 (1): 35–53. doi :10.1287/opre.1030.0065. hdl : 2268/253225 . S2CID  8946639.
4. Giraldo, Juan S.; Castrillon, Jhon A.; Lopez, Juan Camilo; Rider, Marcos J.; Castro, Carlos A. (julio de 2019). "Gestión energética de microrredes mediante programación convexa robusta". IEEE Transactions on Smart Grid . 10 (4): 4520–4530. doi :10.1109/TSG.2018.2863049. ISSN  1949-3053. S2CID  115674048.
5. Shabanzadeh M; Sheikh-El-Eslami, MK; Haghifam, P; MR (octubre de 2015). "El diseño de una herramienta de cobertura de riesgos para plantas de energía virtuales a través de un enfoque de optimización robusto". Applied Energy . 155 : 766–777. Bibcode :2015ApEn..155..766S. doi :10.1016/j.apenergy.2015.06.059.
6. Shabanzadeh M; Fattahi, M (julio de 2015). "Programación del mantenimiento de la generación mediante optimización robusta". 23.ª Conferencia iraní sobre ingeniería eléctrica de 2015. págs. 1504-1509. doi :10.1109/IranianCEE.2015.7146458. ISBN 978-1-4799-1972-7.S2CID8774918  .​
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". IEEE Transactions on Automatic Control . 35 (3): 356–361. doi :10.1109/9.50357.
8. Optimización robusta de la cartera
9. Md. Asadujjaman y Kais Zaman, "Optimización robusta de carteras en condiciones de incertidumbre de datos", 15ª Conferencia Estadística Nacional, diciembre de 2014, Dhaka, Bangladesh.
10. 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.
11. Strano, M (2006). "Optimización bajo incertidumbre de procesos de conformado de chapa metálica mediante el método de elementos finitos". Actas de la Institución de Ingenieros Mecánicos, Parte B: Revista de Ingeniería de Manufactura . 220 (8): 1305–1315. doi :10.1243/09544054JEM480. S2CID  108843522.
12. Bernardo, Fernando P.; Saraiva, Pedro M. (1998). "Marco de optimización robusto para el diseño de parámetros y tolerancias de procesos". AIChE Journal . 44 (9): 2007–2017. Bibcode :1998AIChE..44.2007B. doi :10.1002/aic.690440908. hdl : 10316/8195 .
13. 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. Bibcode :2005PMB....50.5463C. doi :10.1088/0031-9155/50/23/003. PMID  16306645. S2CID  15713904.
14. Verdu, S.; Poor, HV (1984). "Sobre la robustez Minimax: un enfoque general y aplicaciones". IEEE Transactions on Information Theory . 30 (2): 328–340. CiteSeerX 10.1.1.132.837 . doi :10.1109/tit.1984.1056876. 
15. Kassam, SA; Poor, HV (1985). "Técnicas robustas para el procesamiento de señales: un estudio". Actas del IEEE . 73 (3): 433–481. doi :10.1109/proc.1985.13167. hdl : 2142/74118 . S2CID  30443041.
16. M. Danish Nisar. "Robustez Minimax en el procesamiento de señales para comunicaciones", Shaker Verlag, ISBN 978-3-8440-0332-1 , agosto de 2011. 
17. Ben-Tal A., El Ghaoui, L. y Nemirovski, A. (2009). Optimización robusta. Princeton Series in Applied Mathematics, Princeton University Press, 9-16.
18. Leyffer S. , Menickelly M., Munson T., Vanaret C. y Wild S. M (2020). Un estudio de optimización robusta no lineal. INFOR: Sistemas de información e investigación operativa, Taylor & Francis.

Lectura adicional

• 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 . pp. 1504–1509. doi :10.1109/IranianCEE.2015.7146458. ISBN . 978-1-4799-1972-7.S2CID8774918  .​

Enlaces externos

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