Ottimizzazione robusta - Robust optimization

L'ottimizzazione robusta è un campo della teoria dell'ottimizzazione che si occupa di problemi di ottimizzazione in cui si ricerca una certa misura di robustezza rispetto all'incertezza che può essere rappresentata come variabilità deterministica nel valore dei parametri del problema stesso e/o della sua soluzione.

Storia

Le origini dell'ottimizzazione robusta risalgono all'istituzione della moderna teoria delle decisioni negli anni '50 e all'uso dell'analisi del caso peggiore e del modello maximin di Wald come strumento per il trattamento dell'incertezza grave. È diventata una disciplina a sé stante negli anni '70 con sviluppi paralleli in diversi campi scientifici e tecnologici. Nel corso degli anni, è stato applicato in statistica , ma anche in ricerca operativa , ingegneria elettrica , teoria del controllo , finanza , logistica di gestione del portafoglio , ingegneria manifatturiera , ingegneria chimica , medicina e informatica . Nei problemi di ingegneria , queste formulazioni prendono spesso il nome di "Robust Design Optimization", RDO o "Reliability Based Design Optimization", RBDO.

Esempio 1

Considera il seguente problema di programmazione lineare

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

dove è un dato sottoinsieme di . ${\displaystyle P}$${\displaystyle \mathbb {R} ^{2}}$

Ciò che rende questo problema di "ottimizzazione robusta" è la clausola nei vincoli. La sua implicazione è che affinché una coppia sia ammissibile, il vincolo deve essere soddisfatto dal peggio relativo a , ovvero la coppia che massimizza il valore di per il valore dato di . ${\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)}$

Se lo spazio dei parametri è finito (costituito da un numero finito di elementi), allora questo problema di ottimizzazione robusto è di per sé un problema di programmazione lineare : per ciascuno c'è un vincolo lineare . ${\displaystyle P}$${\displaystyle (c,d)\in P}$${\displaystyle cx+dy\leq 10}$

Se non è un insieme finito, allora questo problema è un problema di programmazione lineare semi-infinito , vale a dire un problema di programmazione lineare con un numero finito (2) di variabili decisionali e un numero infinito di vincoli. ${\displaystyle P}$

Classificazione

Esistono numerosi criteri di classificazione per problemi/modelli di ottimizzazione robusti. In particolare, si possono distinguere problemi che riguardano modelli di robustezza locali e globali ; e tra modelli probabilistici e non probabilistici di robustezza. L'ottimizzazione robusta moderna si occupa principalmente di modelli di robustezza non probabilistici che sono orientati al caso peggiore e come tali solitamente implementano i modelli maximin di Wald .

Robustezza locale

Ci sono casi in cui si cerca la robustezza contro piccole perturbazioni in un valore nominale di un parametro. Un modello molto popolare di robustezza locale è il modello del raggio di stabilità :

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

dove denota il valore nominale del parametro, denota una sfera di raggio centrata in e denota l'insieme dei valori che soddisfano determinate condizioni di stabilità/prestazioni associate alla decisione . ${\displaystyle {\hat {u}}}$${\displaystyle B(\rho ,{\hat {u}})}$${\displaystyle\rho}$${\displaystyle {\hat {u}}}$${\displaystyle S(x)}$${\displaystyle u}$${\displaystyle x}$

In parole povere, la robustezza (raggio di stabilità) di decisione è il raggio della sfera più grande centrata su tutti i cui elementi soddisfano i requisiti di stabilità imposti su . L'immagine è questa: ${\displaystyle x}$${\displaystyle {\hat {u}}}$${\displaystyle x}$

dove il rettangolo rappresenta l'insieme di tutti i valori associati a decision . ${\displaystyle U(x)}$${\displaystyle u}$${\displaystyle x}$

Robustezza globale

Considera il semplice problema di ottimizzazione robusta astratta

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

dove denota l'insieme di tutti i possibili valori in esame. ${\displaystyle U}$${\displaystyle u}$

Questo è un problema di ottimizzazione robusta globale, nel senso che il vincolo di robustezza rappresenta tutti i possibili valori di . ${\displaystyle g(x,u)\leq b,\forall u\in U}$${\displaystyle u}$

La difficoltà è che un tale vincolo "globale" può essere troppo impegnativo in quanto non esiste nessuno che soddisfi questo vincolo. Ma anche se esiste, il vincolo può essere troppo "conservativo" in quanto produce una soluzione che genera un profitto molto piccolo che non è rappresentativo delle prestazioni di altre decisioni in . Ad esempio, potrebbe esserci un che viola solo leggermente il vincolo di robustezza ma produce un profitto molto grande . In tali casi potrebbe essere necessario allentare un po' il vincolo di robustezza e/o modificare la formulazione 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')}$

Esempio 2

Consideriamo il caso in cui l'obiettivo è soddisfare un vincolo . dove denota la variabile di decisione ed è un parametro il cui insieme di possibili valori in . Se non esiste tale , allora la seguente misura intuitiva di robustezza si suggerisce: ${\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\ tra X}$

dove denota una misura appropriata della "dimensione" dell'insieme . Ad esempio, se è un insieme finito, allora potrebbe essere definito come la cardinalità di set . ${\dimensione displaystyle (Y)}$${\displaystyle Y}$${\displaystyle U}$${\dimensione displaystyle (Y)}$${\displaystyle Y}$

In parole povere, la robustezza della decisione è la dimensione del sottoinsieme più grande di cui il vincolo è soddisfatto per ciascuno in questo insieme. Una decisione ottimale è quindi una decisione la cui robustezza è la più grande. ${\displaystyle U}$${\displaystyle g(x,u)\leq b}$${\displaystyle u}$

Ciò produce il seguente problema di ottimizzazione robusta:

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

Questa nozione intuitiva di robustezza globale non è usata spesso nella pratica perché i problemi di ottimizzazione robusta che essa induce sono solitamente (non sempre) molto difficili da risolvere.

Esempio 3

Considera il problema di ottimizzazione robusta

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

dove è una funzione a valori reali su , e supponiamo che non ci sia una soluzione fattibile a questo problema perché il vincolo di robustezza è troppo impegnativo. ${\displaystyle g}$${\displaystyle X\times U}$${\displaystyle g(x,u)\leq b,\forall u\in U}$

Per superare questa difficoltà, sia un sottoinsieme relativamente piccolo di rappresentare valori "normali" e considerare il seguente problema di ottimizzazione 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}}\}}$

Poiché è molto più piccolo di , la sua soluzione ottimale potrebbe non funzionare bene su una grande porzione di e quindi potrebbe non essere robusta contro la variabilità di over . ${\displaystyle {\mathcal {N}}}$${\displaystyle U}$${\displaystyle U}$${\displaystyle u}$${\displaystyle U}$

Un modo per risolvere questa difficoltà consiste nell'allentare il vincolo per i valori al di fuori dell'insieme in modo controllato in modo che siano consentite violazioni maggiori all'aumentare della distanza da . Ad esempio, si consideri il vincolo di robustezza rilassato ${\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}$

dove è un parametro di controllo e indica la distanza di da . Pertanto, per il vincolo di robustezza rilassato si riduce al vincolo di robustezza originale. Ciò produce il seguente problema di ottimizzazione robusta (rilassata): ${\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 funzione è definita in modo tale che ${\displaystyle dist}$

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

e

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

e quindi la soluzione ottima del problema rilassato soddisfa il vincolo originario per tutti i valori di in . Soddisfa anche il vincolo rilassato ${\displaystyle g(x,u)\leq b}$${\displaystyle u}$${\displaystyle {\mathcal {N}}}$

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

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

Modelli di ottimizzazione robusti non probabilistici

Il paradigma dominante in quest'area di ottimizzazione robusta è il modello maximin di Wald , vale a dire

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

dove la rappresenta il decisore, la rappresenta la Natura, ovvero l' incertezza , rappresenta lo spazio decisionale e denota l'insieme dei possibili valori di associati alla decisione . Questo è il formato classico del modello generico ed è spesso indicato come problema di ottimizzazione minimax o maximin . Il modello non probabilistico ( deterministico ) è stato ed è ampiamente utilizzato per l'ottimizzazione robusta soprattutto nel campo dell'elaborazione del segnale. ${\displaystyle \max}$${\displaystyle\min}$${\displaystyle X}$${\displaystyle U(x)}$${\displaystyle u}$${\displaystyle x}$

La programmazione matematica equivalente (MP) del formato classico sopra è

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

I vincoli possono essere incorporati esplicitamente in questi modelli. Il formato classico vincolato generico è

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

Il formato MP vincolato equivalente è definito come:

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

Modelli di ottimizzazione probabilisticamente robusti

Questi modelli quantificano l'incertezza nel valore "vero" del parametro di interesse mediante funzioni di distribuzione di probabilità. Sono stati tradizionalmente classificati come programmazione stocastica e modelli di ottimizzazione stocastica . Recentemente, l'ottimizzazione probabilisticamente robusta ha guadagnato popolarità con l'introduzione di teorie rigorose come l' ottimizzazione degli scenari in grado di quantificare il livello di robustezza delle soluzioni ottenute per randomizzazione. Questi metodi sono rilevanti anche per i metodi di ottimizzazione basata sui dati.

Controparte robusta

Il metodo di soluzione per molti programmi robusti prevede la creazione di un equivalente deterministico, chiamato controparte robusta. La difficoltà pratica di un programma robusto dipende dal fatto che la sua controparte robusta sia trattabile computazionalmente.

Guarda anche

• Raggio di stabilità
• Minimax
• Stimatore Minimax
• Minimax rimpianto
• Statistiche robuste
• Processo decisionale robusto
• Programmazione stocastica
• Ottimizzazione stocastica
• Teoria della decisione del gap informativo
• metodi Taguchi

Riferimenti

Ulteriori letture

• HJ Greenberg. Glossario di programmazione matematica. World Wide Web, http://glossary.computing.society.informs.org/ , 1996-2006. A cura di INFORMS Computing Society.
• Ben Tal, A.; Nemirovski, A. (1998). "Ottimizzazione convessa robusta". Matematica della Ricerca Operativa . 23 (4): 769-805. CiteSeerX  10.1.1.135.798 . doi : 10.1287/moor.23.4.769 .
• Ben Tal, A.; Nemirovski, A. (1999). "Soluzioni robuste a programmi lineari incerti". Lettere di ricerca 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). "Ottimizzazione robusta: metodologia e applicazioni". Programmazione matematica, serie B . 92 (3): 453–480. CiteSeerX  10.1.1.298.7965 . doi : 10.1007/s101070100286 .
• Ben-Tal A., El Ghaoui, L. e Nemirovski, A. (2006). Programmazione matematica, numero speciale sull'ottimizzazione robusta, volume 107 (1-2).
• Ben-Tal A., El Ghaoui, L. e Nemirovski, A. (2009). Ottimizzazione robusta. Princeton Series in Matematica Applicata, Princeton University Press.
• Bertsimas, D.; Sim, M. (2003). "Ottimizzazione discreta e flussi di rete robusti". Programmazione matematica . 98 (1–3): 49–71. CiteSeerX  10.1.1.392.4470 . doi : 10.1007/s10107-003-0396-4 .
• Bertsimas, D.; Sim, M. (2006). "Approssimazioni trattabili a robusti problemi di ottimizzazione conica Dimitris Bertsimas". Programmazione matematica . 107 (1): 5-36. CiteSeerX  10.1.1.207.8378 . doi : 10.1007/s10107-005-0677-1 .
• Chen, W.; Sim, M. (2009). "Ottimizzazione guidata dagli obiettivi". Ricerca Operativa . 57 (2): 342-357. doi : 10.1287/opre.1080.0570 .
• Chen, X.; Sim, M.; Sole, P.; Zhang, J. (2008). "Un approccio di approssimazione basato sulla decisione lineare alla programmazione stocastica". Ricerca Operativa . 56 (2): 344-357. doi : 10.1287/opre.1070.0457 .
• Chen, X.; Sim, M.; Sole, P. (2007). "Una prospettiva di ottimizzazione robusta sulla programmazione stocastica". Ricerca Operativa . 55 (6): 1058–1071. doi : 10.1287/opre.1070.0441 .
• Dembo, R (1991). "Ottimizzazione dello scenario". Annali di Ricerca Operativa . 30 (1): 63-80. doi : 10.1007/bf02204809 .
• Dodson, B., Hammett, P. e Klerx, R. (2014) Progettazione probabilistica per l'ottimizzazione e la robustezza per gli ingegneri John Wiley & Sons, Inc. ISBN  978-1-118-79619-1
• Gupta, SK; Rosenhead, J. (1968). "Robustezza nelle decisioni di investimento sequenziali". Scienze della gestione . 15 (2): 18-29. doi : 10.1287/mnsc.15.2.B18 .
• Kouvelis P. e Yu G. (1997). Ottimizzazione discreta robusta e sue applicazioni, Kluwer.
• Mutapcic, Almir; Boyd, Stephen (2009). "Metodi di taglio-set per ottimizzazione convessa robusta con oracoli pessimizzanti". Metodi e software di ottimizzazione . 24 (3): 381–406. CiteSeerX  10.1.1.416.4912 . doi : 10.1080/10556780802712889 .
• Mulvey, JM; Vanderbei, RJ; Zenios, SA (1995). "Ottimizzazione robusta di sistemi su larga scala". Ricerca Operativa . 43 (2): 264–281. doi : 10.1287/opre.43.2.264 .
• Rosenblat, MJ (1987). "Un approccio solido alla progettazione delle strutture". Giornale internazionale di ricerca di produzione . 25 (4): 479-486. doi : 10.1080/00207548708919855 .
• Rosenhead, MJ; Elton, M; Gupta, SK (1972). "Robustezza e ottimalità come criteri per le decisioni strategiche". Trimestrale di ricerca operativa . 23 (4): 413–430. doi : 10.2307/3007957 . JSTOR  3007957 .
• Rustem B. e Howe M. (2002). Algoritmi per la progettazione del caso peggiore e applicazioni alla gestione del rischio, Princeton University Press.
• Sniedovich, M (2007). "L'arte e la scienza di modellare il processo decisionale in condizioni di grave incertezza" . Processo decisionale nel settore manifatturiero e dei servizi . 1 (1–2): 111-136. doi : 10.7494/dmms.2007.1.2.111 .
• Sniedovich, M (2008). "Modello Maximin di Wald: un tesoro travestito!". Giornale di finanza di rischio . 9 (3): 287–291. doi : 10.1108/15265940810875603 .
• Sniedovich, M (2010). "Una visione d'insieme della teoria delle decisioni sul gap informativo". Giornale di finanza di rischio . 11 (3): 268–283. doi : 10.1108/15265941011043648 .
• Wald, A (1939). "Contributi alla teoria della stima statistica e verifica delle ipotesi" . Gli Annali della Matematica . 10 (4): 299-326. doi : 10.1214/aoms/1177732144 .
• Wald, A (1945). "Funzioni di decisione statistica che minimizzano il rischio massimo". Gli Annali della Matematica . 46 (2): 265-280. doi : 10.2307/1969022 . JSTOR  1969022 .
• Wald, A. (1950). Funzioni di decisione statistica, John Wiley, NY.
• Shabanzadeh, Morteza; Fattahi, Mohammad (2015). "Pianificazione della manutenzione della generazione tramite una solida ottimizzazione". 2015 23° Conferenza iraniana sull'ingegneria elettrica . pp. 1504–1509. doi : 10.1109/IranianCEE.2015.7146458 . ISBN 978-1-4799-1972-7.

link esterno

• ROMA: ottimizzazione robusta resa semplice
• Processo decisionale solido in condizioni di grave incertezza