Ottimizzazione robusta - assunzioni
Ragazzi, ho bisogno del vostro aiuto per capire le dimostrazioni da E.1 a E.4 che ci sono a pag. 3 del seguente paper:
So che da regolamento bisognerebbe inserire un "tentativo di soluzione" ma non saprei proprio cosa scrivere dato che non ho capito nulla di quello che c'è scritto. Magari potrei abbozzare un principio di ragionamento con qualche suggerimento, ma per il momento non saprei davvero da dove cominciare.
Spero possiate darmi una mano.
So che da regolamento bisognerebbe inserire un "tentativo di soluzione" ma non saprei proprio cosa scrivere dato che non ho capito nulla di quello che c'è scritto. Magari potrei abbozzare un principio di ragionamento con qualche suggerimento, ma per il momento non saprei davvero da dove cominciare.
Spero possiate darmi una mano.
Risposte
In particolare mi sto concentrando sulla dimostrazione E.3, dove viene spiegato che l'insieme di incertezza $U$ si può sempre sostituire con il suo inviluppo convesso, rendendo così un problema apparentemente non convesso in un problema convesso che ammette per definizione un insieme numerabile di soluzioni ammissibili.
Il concetto in sé sembra abbastanza chiaro: come dice l'autore, siccome l'inviluppo convesso di un insieme è il più piccolo convesso che include l'insieme, allora testare l'ammissibilità di una soluzione su $U$ equivale a prendere l'estremo superiore di $U$ e a valutare l'obiettivo su tale soluzione, il cui valore coinciderà giocoforza con il valore dell'obiettivo calcolato sul suo inviluppo.
Tuttavia sono le premesse a tale ragionamento che non mi sono chiare. Ok che $U$ è un insieme infinito perché infinite sono le $u \in U$ possibili realizzazioni, ma questo non significa che non sia convesso. Infatti per infinite possibili realizzazioni equivalgono infiniti semipiani, quindi ci troveremmo di fronte ad un iperpoliedro ad $n$ dimensioni con $2^n$ soluzioni ammissibili, non ad un insieme non convesso che non ammette regione ammissibile. Al massimo potremmo parlare di non trattabilità del problema perchè iterare su $2^n$ soluzioni è computazionalmente impossibile, ma non di "non convessità". Quindi non vedo il senso di andare a sostituire $U$ con il suo inviluppo convesso.
Cosa mi sfugge?
Il concetto in sé sembra abbastanza chiaro: come dice l'autore, siccome l'inviluppo convesso di un insieme è il più piccolo convesso che include l'insieme, allora testare l'ammissibilità di una soluzione su $U$ equivale a prendere l'estremo superiore di $U$ e a valutare l'obiettivo su tale soluzione, il cui valore coinciderà giocoforza con il valore dell'obiettivo calcolato sul suo inviluppo.
Tuttavia sono le premesse a tale ragionamento che non mi sono chiare. Ok che $U$ è un insieme infinito perché infinite sono le $u \in U$ possibili realizzazioni, ma questo non significa che non sia convesso. Infatti per infinite possibili realizzazioni equivalgono infiniti semipiani, quindi ci troveremmo di fronte ad un iperpoliedro ad $n$ dimensioni con $2^n$ soluzioni ammissibili, non ad un insieme non convesso che non ammette regione ammissibile. Al massimo potremmo parlare di non trattabilità del problema perchè iterare su $2^n$ soluzioni è computazionalmente impossibile, ma non di "non convessità". Quindi non vedo il senso di andare a sostituire $U$ con il suo inviluppo convesso.
Cosa mi sfugge?
Non ho provato a risolverli, ma E.1 e E.3 fanno riferimento ad un manuale. Quindi ti invito a guardarlo.
[edit] pensavo il riferimento fosse ad un articolo
[edit] pensavo il riferimento fosse ad un articolo
Per manuale intendi il riferimento a Ben-Tal 2009? Online ho trovato questo
e devo dire che mi è stato d'aiuto per le dimostrazioni da E.1 ad E.3. Diciamo che su queste ci sono. Resta la dimostrazione E.4, e non riesco a venirne a capo (benché meno con il link di cui sopra) prima di tutto perché non capisco il significato di constraint-wise: se almeno ne capissi la traduzione sarebbe (probabilmente) più facile.
Io ho un sistema ${ ( x_1+d_1<=0 ),( x_2+d_2<=0 ):}$ e un insieme di incertezza $U={d \in \mathbb(R)^2 : d_1 >=0, d_2 >=0, d_1 + d_2 <=1}$. E ovviamente, per $U$ così definito, si ha che $d_1,d_2 \in [0,1]$.
Bene: che ca
o significa ora " It is easy to see that robustness of the i-th constraint with respect to $U$ is equivalent to robustness with respect to $U_i$, i.e., the uncertainty in the problem data can be modelled constraint-wise."?
e devo dire che mi è stato d'aiuto per le dimostrazioni da E.1 ad E.3. Diciamo che su queste ci sono. Resta la dimostrazione E.4, e non riesco a venirne a capo (benché meno con il link di cui sopra) prima di tutto perché non capisco il significato di constraint-wise: se almeno ne capissi la traduzione sarebbe (probabilmente) più facile.
Io ho un sistema ${ ( x_1+d_1<=0 ),( x_2+d_2<=0 ):}$ e un insieme di incertezza $U={d \in \mathbb(R)^2 : d_1 >=0, d_2 >=0, d_1 + d_2 <=1}$. E ovviamente, per $U$ così definito, si ha che $d_1,d_2 \in [0,1]$.
Bene: che ca
o significa ora " It is easy to see that robustness of the i-th constraint with respect to $U$ is equivalent to robustness with respect to $U_i$, i.e., the uncertainty in the problem data can be modelled constraint-wise."?
Una mia personale traduzione è "l'incertezza nei dati del problema può essere modellata tendo conto del vincolo, in funzione dei vincoli, riguardante il vincolo, dipendente dal vincolo" ... IMHO
Cordialmente, Alex
EDIT: "In modern English the suffix -wise is attached to nouns to form a sentence adverb meaning ‘concerning or with respect to’, as in confidence-wise, tax-wise, price-wise, time-wise, news-wise, and culture-wise. The suffix is very productive and widely used in modern English but most of the words so formed are considered inelegant or not good English style"
Cordialmente, Alex
EDIT: "In modern English the suffix -wise is attached to nouns to form a sentence adverb meaning ‘concerning or with respect to’, as in confidence-wise, tax-wise, price-wise, time-wise, news-wise, and culture-wise. The suffix is very productive and widely used in modern English but most of the words so formed are considered inelegant or not good English style"
Ciao Alex, anzitutto grazie mille per la tua risposta.
In secondo luogo beh, se così è, non capisco il senso di tutto ciò. Voglio dire, tutto l'esempio per dire che un insieme di incertezza si può modellare in funzione dei vincoli del problema?
In secondo luogo beh, se così è, non capisco il senso di tutto ciò. Voglio dire, tutto l'esempio per dire che un insieme di incertezza si può modellare in funzione dei vincoli del problema?
Forse ho trovato la risposta ma vorrei conferma, se possibile, del ragionamento.
Secondo me l'obiettivo della dimostrazione E.4 è far vedere che l'incertezza è sempre modellabile mediante insiemi chiusi e limitati, come appunto avviene nell'esempio per $U_i=[0,1]$.
Io so che nell'ipotesi in cui le possibili realizzazioni di $A$ risultino descritte dall’insieme di incertezza $U$, e posti certi (per le dimostrazioni E.1 ed E.2) sia $c \in \mathbb(R)^n$ che $b in \mathbb(R)^m$, la controparte robusta di un problema di PL nominale sotto incertezza del tipo $min_x {c^T x∶Ax≤b}_((c,A,b)∈U)$ ha forma
dove $\zeta-= \zeta(\omega) \in U$ è la singola realizzazione mentre $A(\zeta)∈\mathbb(R)^(m xx n)$ è la matrice dei coefficienti incerti del sistema di vincoli, che gli autori in
assumono affine in $\zeta$.
Bene: io so che una funzione $f:I->\mathbb(R)$ è affine, cioè di forma lineare più una costante, solo se $I$ è chiuso e limitato. Allora, se per la E.4 si può modellare $U_A$ come un insieme chiuso e limitato, si può estrarre dalla matrice $A:U_A->\mathbb(R)^(m xx n) $ un singolo vincolo con lato sinistro di forma affine, che gli autori lo indicano con
Che ne pensate?
Secondo me l'obiettivo della dimostrazione E.4 è far vedere che l'incertezza è sempre modellabile mediante insiemi chiusi e limitati, come appunto avviene nell'esempio per $U_i=[0,1]$.
Io so che nell'ipotesi in cui le possibili realizzazioni di $A$ risultino descritte dall’insieme di incertezza $U$, e posti certi (per le dimostrazioni E.1 ed E.2) sia $c \in \mathbb(R)^n$ che $b in \mathbb(R)^m$, la controparte robusta di un problema di PL nominale sotto incertezza del tipo $min_x {c^T x∶Ax≤b}_((c,A,b)∈U)$ ha forma
$min_x{c^Tx:A(\zeta)x<=b,\forall zeta \in U}$
dove $\zeta-= \zeta(\omega) \in U$ è la singola realizzazione mentre $A(\zeta)∈\mathbb(R)^(m xx n)$ è la matrice dei coefficienti incerti del sistema di vincoli, che gli autori in
assumono affine in $\zeta$.
Bene: io so che una funzione $f:I->\mathbb(R)$ è affine, cioè di forma lineare più una costante, solo se $I$ è chiuso e limitato. Allora, se per la E.4 si può modellare $U_A$ come un insieme chiuso e limitato, si può estrarre dalla matrice $A:U_A->\mathbb(R)^(m xx n) $ un singolo vincolo con lato sinistro di forma affine, che gli autori lo indicano con
$(a+P\zeta)^Tx<=b, \forall \zeta \in U$
Che ne pensate?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo