Optimización robusta

La optimización robusta es un campo de la teoría de la 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 una variabilidad determinista en el valor de los parámetros del problema en sí y/o su solución. Está relacionado con los métodos de optimización probabilística, como la optimización restringida por el azar, pero a menudo se distingue de ellos.

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] [4]} teoría del control , ^[5] finanzas , ^[6] gestión de carteras, ^[7] logística , ^[8] ingeniería manufacturera , ^[9] ingeniería química , ^[10] medicina , ^[11] e informática . En problemas de ingeniería , estas formulaciones suelen tomar 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

${\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 (consta de 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 semiinfinita , es decir, un problema de programación lineal con un número finito (2) de variables de decisión e infinitas restricciones. ${\displaystyle P}$

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 de robustez probabilísticos y no probabilísticos . 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 implementar los modelos maximin de Wald .

Robustez local

Hay 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 determinadas condiciones de estabilidad/rendimiento 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 decisión es el radio de la bola más grande centrada en todos cuyos elementos satisfacen los requisitos de estabilidad impuestos . La imagen es esta: ${\displaystyle x}$ ${\displaystyle {\hat {u}}}$ ${\displaystyle x}$

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

Robustez global

Considere el simple problema abstracto 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 tal restricción "global" puede ser demasiado exigente en el sentido de que no existe nada que la satisfaga. Pero incluso si tal existiera, la restricción puede ser demasiado "conservadora" en el sentido de que produce una solución que genera un beneficio muy pequeño que no es representativo del desempeño de otras decisiones en . Por ejemplo, podría haber una que viole sólo ligeramente la restricción de robustez pero produzca un beneficio muy grande . En tales casos, podría ser necesario relajar un poco la restricción de robustez y/o modificar el planteamiento 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

Considere 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 that , 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 palabras, la robustez de la decisión es el tamaño del subconjunto más grande de para el cual se satisface la restricción para cada uno de este conjunto. Una decisión óptima es entonces aquella cuya robustez es la mayor. ${\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 con frecuencia en la práctica porque los problemas de optimización robusta que induce suelen ser (no siempre) muy difíciles de resolver.

Ejemplo 3

Considere 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 hay una función con valor real en y suponemos 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, representemos un subconjunto relativamente pequeño de valores "normales" de y consideremos el siguiente problema de optimización robusto: ${\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 , es posible que su solución óptima no funcione bien en una gran parte de y, por lo tanto, puede no ser robusta frente a la variabilidad de over . ${\displaystyle {\mathcal {N}}}$ ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle u}$ ${\displaystyle U}$

Una forma de solucionar esta dificultad es relajar la restricción para valores de fuera del conjunto de manera controlada, de modo que se permitan violaciones mayores a medida que aumenta la distancia de . 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 . Por lo tanto, la restricción de robustez relajada se reduce a la restricción de robustez original. Esto produce el siguiente problema de optimización robusta (relajado): ${\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 in . 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 robustos no probabilísticos.

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 tomador de decisiones, 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 ) se ha utilizado y se utiliza ampliamente para una optimización sólida, especialmente en el campo del procesamiento de señales. ^{[12] [13] [14]} ${\displaystyle \max }$ ${\displaystyle \min }$ ${\displaystyle X}$ ${\displaystyle U(x)}$ ${\displaystyle u}$ ${\displaystyle x}$

La programación matemática (MP) 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)\}}$

Las restricciones se pueden incorporar explícitamente en estos modelos. El formato clásico restringido genérico 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 en 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 capaces de cuantificar el nivel de robustez de las soluciones obtenidas mediante 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. ^{[15] [16]}

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

1. Bertsimas, Dimitris; Sim, Melvyn (2004). "El precio de la robustez". La investigación de operaciones . 52 (1): 35–53. doi :10.1287/opre.1030.0065. hdl : 2268/253225 . S2CID  8946639.
2. Giraldo, Juan S.; Castrillón, Jhon A.; López, Juan Camilo; Jinete, Marcos J.; Castro, Carlos A. (julio 2019). "Gestión de energía de microrredes mediante programación convexa robusta". Transacciones IEEE en Smart Grid . 10 (4): 4520–4530. doi :10.1109/TSG.2018.2863049. ISSN  1949-3053. S2CID  115674048.
3. Shabanzadeh M; Sheikh-El-Eslami, diputado; Haghifam, P; SEÑOR (octubre de 2015). "El diseño de una herramienta de cobertura de riesgos para plantas de energía virtuales mediante un enfoque de optimización sólido". Energía Aplicada . 155 : 766–777. doi :10.1016/j.apenergy.2015.06.059.
4. Shabanzadeh M; Fattahi, M (julio de 2015). "Programación de mantenimiento de 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. S2CID  8774918.
5. Khargonekar, PP; Petersen, IR; Zhou, K. (1990). "Estabilización robusta de sistemas lineales inciertos: estabilizabilidad 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.
6. Sólida optimización de la cartera
7. Md. Asadujjaman y Kais Zaman, "Optimización robusta de la cartera en condiciones de incertidumbre de datos", 15ª Conferencia Estadística Nacional, diciembre de 2014, Dhaka, Bangladesh.
8. 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.
9. 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. S2CID  108843522.
10. Bernardo, Fernando P.; Saraiva, Pedro M. (1998). "Marco de optimización robusto para el diseño de tolerancias y parámetros de proceso". Revista AIChE . 44 (9): 2007-2017. doi :10.1002/aic.690440908. hdl : 10316/8195 .
11. Chu, Millie; Zinchenko, Yuriy; Henderson, Shane G; Sharpe, Michael B (2005). "Optimización sólida para la planificación del tratamiento de radioterapia de intensidad modulada en condiciones de incertidumbre". Física en Medicina y Biología . 50 (23): 5463–5477. Código bibliográfico : 2005PMB....50.5463C. doi :10.1088/0031-9155/50/23/003. PMID  16306645. S2CID  15713904.
12. Verdú, S.; Pobre, HV (1984). "Sobre la robustez 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. 
13. 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 . S2CID  30443041.
14. M. Nisar danés. "Robustez Minimax en el procesamiento de señales para comunicaciones", Shaker Verlag, ISBN 978-3-8440-0332-1 , agosto de 2011. 
15. Ben-Tal A., El Ghaoui, L. y Nemirovski, A. (2009). Optimización robusta. Serie Princeton en Matemáticas Aplicadas, Princeton University Press, 9-16.
16. Leyffer S. , Menickelly M., Munson T., Vanaret C. y Wild SM (2020). Un estudio sobre 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 la Sociedad de Computación INFORMA.
• 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 a 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 sólida: 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. Serie Princeton en Matemáticas Aplicadas, Princeton University Press.
• Bertsimas, D.; Sim, M. (2003). "Optimización robusta y discreta 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 impulsada por objetivos". La investigación de operaciones . 57 (2): 342–357. doi :10.1287/opre.1080.0570.
• Chen, X.; Sim, M.; Sol, P.; Zhang, J. (2008). "Un enfoque de aproximación basado en decisiones lineales para la programación estocástica". La investigación de operaciones . 56 (2): 344–357. doi :10.1287/opre.1070.0457.
• Chen, X.; Sim, M.; Sol, P. (2007). "Una perspectiva de optimización sólida de la programación estocástica". La 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". 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. S2CID  16443437.
• Mulvey, JM; Vanderbei, RJ; Zenios, SA (1995). "Optimización robusta de sistemas a gran escala". La 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 evaluación analítica de la propagación de la incertidumbre". Optimización de ingeniería 51 (9): 1581-1603. doi:10.1080/0305215X.2018.1536752.
• Rosenblat, MJ (1987). "Un enfoque sólido para el diseño de instalaciones". Revista Internacional de Investigación sobre 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 a la gestión de riesgos, Princeton University Press.
• Sniedovich, M (2007). "El arte y la ciencia de modelar la toma de decisiones en condiciones de grave incertidumbre". 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!". Revista de financiación de riesgos . 9 (3): 287–291. doi :10.1108/15265940810875603.
• Sniedovich, M (2010). "Una visión panorámica de la teoría de la decisión sobre la brecha de información". Revista de financiación 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 prueba 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 máximo riesgo". 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, Nueva York.
• Shabanzadeh, Morteza; Fattahi, Mohammad (2015). "Programación de mantenimiento de 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. S2CID  8774918.

enlaces externos

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