Ottimizzazione vincolata: dimostrare convessità o concavità della funzione obiettivo
Buongiorno a tutti,
svolgendo degli esercizi di ottimizzazione vincolata (seguo un corso di matematica per il business) mi sono imbattuta in un esercizio dove la nostra funzione obiettivo in due variabili è data da una retta e i vincoli compongono una regione ammissibile non convessa. L'esercizio richiede se la funzione obiettivo è convessa o concava, ma non riesco a capire come dimostrarlo. Il metodo di dimostrazione mediante matrice hessiana non è utilizzabile in quanto la matrice in questione è composta da quattro zeri.
Nello specifico i dati del problema sono i seguenti:
Objective function : $ f(x_1 , x_2 ) = x_1 + 3x_2 $
Constraints :
$ (x_1 - 1 ) ^ 2 + x_2^2 - 5 <=0 $
$ -x_1 - x_2^2 <= 0 $
Il secondo modo che conosco è legato al fatto che comunque la regione ammissibile sia convessa, ma nel nostro caso questo non è verificato. Come posso fare?
Grazie mille a chiunque saprà aiutarmi!
svolgendo degli esercizi di ottimizzazione vincolata (seguo un corso di matematica per il business) mi sono imbattuta in un esercizio dove la nostra funzione obiettivo in due variabili è data da una retta e i vincoli compongono una regione ammissibile non convessa. L'esercizio richiede se la funzione obiettivo è convessa o concava, ma non riesco a capire come dimostrarlo. Il metodo di dimostrazione mediante matrice hessiana non è utilizzabile in quanto la matrice in questione è composta da quattro zeri.
Nello specifico i dati del problema sono i seguenti:
Objective function : $ f(x_1 , x_2 ) = x_1 + 3x_2 $
Constraints :
$ (x_1 - 1 ) ^ 2 + x_2^2 - 5 <=0 $
$ -x_1 - x_2^2 <= 0 $
Il secondo modo che conosco è legato al fatto che comunque la regione ammissibile sia convessa, ma nel nostro caso questo non è verificato. Come posso fare?
Grazie mille a chiunque saprà aiutarmi!
Risposte
Per prima cosa è utile riconoscere le funzioni.
Cambio i nomi alle variabili per comodità in $x_1=x$ e $x_2=y$
$f(x,y)=z=x+3y$ è un piano inclinato di $RR^3$ che passa per l'origine. E' una funzione convessa o concava?
Il dominio è composto dai vincoli:
$(x-1)^2+y^2<=5$ che non è altro che l'area della circonferenza sul piano XY di centro $(1,0)$ e raggio $sqrt(5)$
Mentre $x>=-y^2$ e il bordo + la parte esterna di una parabola che passa per l'origine.
Mettendo insieme i due vincoli, la zona blu è quella che ti interessa. E' convessa o concava?
Ora immagina di tirare la zona blu, verso l'alto e il basso, come se estraessi un cilindro. Il solido andrà ad intersecare il piano: che tipo regione creerà sul piano, concava o convessa?
P.S. Il disegno è da intendersi come "libera rappresentazione"
Cambio i nomi alle variabili per comodità in $x_1=x$ e $x_2=y$
$f(x,y)=z=x+3y$ è un piano inclinato di $RR^3$ che passa per l'origine. E' una funzione convessa o concava?
Il dominio è composto dai vincoli:
$(x-1)^2+y^2<=5$ che non è altro che l'area della circonferenza sul piano XY di centro $(1,0)$ e raggio $sqrt(5)$
Mentre $x>=-y^2$ e il bordo + la parte esterna di una parabola che passa per l'origine.
Mettendo insieme i due vincoli, la zona blu è quella che ti interessa. E' convessa o concava?
Ora immagina di tirare la zona blu, verso l'alto e il basso, come se estraessi un cilindro. Il solido andrà ad intersecare il piano: che tipo regione creerà sul piano, concava o convessa?
P.S. Il disegno è da intendersi come "libera rappresentazione"
Direi che crea una regione concava!
@NoemiRonco
Pertanto puoi provare che non è convessa con un controesempio (scegliendo due punti ad hoc).
Inoltre, penso che tu abbia capito che l'intersezione fra vincolo e funzione obiettivo, essendo sostanzialmente una proiezione su un piano, avrà il/i suoi massimo/i e minimo/i lungo il bordo. Perchè?
Fai qualche conto adesso, a partire dai punti di intersezione fra parabola e circonferenza.
Pertanto puoi provare che non è convessa con un controesempio (scegliendo due punti ad hoc).
Inoltre, penso che tu abbia capito che l'intersezione fra vincolo e funzione obiettivo, essendo sostanzialmente una proiezione su un piano, avrà il/i suoi massimo/i e minimo/i lungo il bordo. Perchè?
Fai qualche conto adesso, a partire dai punti di intersezione fra parabola e circonferenza.
La rappresentazione, per quanto libera, dovrebbe essere quanto meno aderente alla realtà... E non mi pare che in questo caso lo sia.
Infatti, la parabola di equazione $x = -y^2$ è simmetrica rispetto ad un diametro della circonferenza $(x - 1)^2 + y^2 = 5$, quindi la regione ammissibile individuata dai vincoli è simmetrica rispetto a tale diametro; in particolare, il diametro è quello che giace lungo l'asse $x$ e la regione ammissibile è la parte del cerchio $(x - 1)^2 + y^2 <= 5$ (in blu) che cade nella regione esterna alla parabola, i.e. nell'insieme individuato da $x >= -y^2$ (in rosso).
In altre parole, la regione ammissibile è quella interna al contorno (verde) disegnato in figura nel piano $Ox_1x_2$:
[asvg]xmin=-4; xmax=4; ymin=-4;ymax=4;
axes("","");
stroke="green"; strokewidth=2;
arc([-1,-1],[1+2.23607,0],2.23607); arc([1+2.23607,0],[-1,1],2.23607); plot("sqrt(-x)",-1,0); plot("-sqrt(-x)",-1,0);[/asvg]
Un metodo per risolvere il problema è quello di tracciare sul piano $Ox_1x_2$ le curve di livello della funzione obiettivo, i.e. la famiglia di curve di equazione $mathcal(F)_k: x_1 + 3x_2 = k$ (con $k in RR$ parametro), e determinare i valori di $k$ massimo e minimo affinché tale famiglia ad un parametro abbia intersezione non vuota con la regione ammissibile: tali valori $k_max$ e $k_min$ sono il massimo ed il minimo della funzione obiettivo (perché? e perché sono sicurissimo che esistano?).
Infatti, la parabola di equazione $x = -y^2$ è simmetrica rispetto ad un diametro della circonferenza $(x - 1)^2 + y^2 = 5$, quindi la regione ammissibile individuata dai vincoli è simmetrica rispetto a tale diametro; in particolare, il diametro è quello che giace lungo l'asse $x$ e la regione ammissibile è la parte del cerchio $(x - 1)^2 + y^2 <= 5$ (in blu) che cade nella regione esterna alla parabola, i.e. nell'insieme individuato da $x >= -y^2$ (in rosso).
In altre parole, la regione ammissibile è quella interna al contorno (verde) disegnato in figura nel piano $Ox_1x_2$:
[asvg]xmin=-4; xmax=4; ymin=-4;ymax=4;
axes("","");
stroke="green"; strokewidth=2;
arc([-1,-1],[1+2.23607,0],2.23607); arc([1+2.23607,0],[-1,1],2.23607); plot("sqrt(-x)",-1,0); plot("-sqrt(-x)",-1,0);[/asvg]
Un metodo per risolvere il problema è quello di tracciare sul piano $Ox_1x_2$ le curve di livello della funzione obiettivo, i.e. la famiglia di curve di equazione $mathcal(F)_k: x_1 + 3x_2 = k$ (con $k in RR$ parametro), e determinare i valori di $k$ massimo e minimo affinché tale famiglia ad un parametro abbia intersezione non vuota con la regione ammissibile: tali valori $k_max$ e $k_min$ sono il massimo ed il minimo della funzione obiettivo (perché? e perché sono sicurissimo che esistano?).
@Gugo
Alla faccia di lasciare ragionare la gente...
P.S. Il disegno era volutamente senza coordinate e NON la soluzione
Alla faccia di lasciare ragionare la gente...
P.S. Il disegno era volutamente senza coordinate e NON la soluzione
"Bokonon":
P.S. Il disegno era volutamente senza coordinate e NON la soluzione
Il disegno era fatto male, coordinate o meno.
Per come la vedo io, se un disegno deve essere utile a qualcosa, che sia fatto bene; altrimenti, meglio non farlo e ragionare coi numeri.
P.S.: Il disegno col fascio di rette era un regalo a dissonance che è tornato moderatore; il post è un regalo per me, che non posto da mesi e credo tornerò nell'oblio.
Buona permanenza a tutti.
P.P.S.:
"Bokonon":
@Gugo
Alla faccia di lasciare ragionare la gente...
La questione non riguardava la soluzione del problema, quindi averla fornita non altera la discussione in modo sostanziale.
"Bokonon":
@NoemiRonco
Pertanto puoi provare che non è convessa con un controesempio (scegliendo due punti ad hoc).
Inoltre, penso che tu abbia capito che l'intersezione fra vincolo e funzione obiettivo, essendo sostanzialmente una proiezione su un piano, avrà il/i suoi massimo/i e minimo/i lungo il bordo. Perchè?
Fai qualche conto adesso, a partire dai punti di intersezione fra parabola e circonferenza.
Allora, il massimo o il minimo è lungo i bordi perchè corrisponderà all'intersezione tra appunto la regione ammissibile composta dai vincoli e la funzione obiettivo dove quest'ultima assume il valore di K maggiore , poi dipende dalla forma funzionale ecc per definire se sono di massimo o di minimo, corretto?
Poi aldilà della rappresentazione geometrica per cui ringrazio @gugo82, e di fatto è identica alla mia, la mia domanda era più incentrata sul come dimostrare in maniera rigorosa la concavità O convessità della funzione obiettivo. Della concavità della regione ammissibile ora mi è più chiaro(avevo necessità di ragionarci meglio e mi siete stati d'aiuto), ne deduco però quindi che la funzione obiettivo non è né concava ne convessa....giusto?
Ovvero, in maniera più "sistematica", la non convessità della regione ammissibile implica che la funzione obiettivo non sia ne concava ne convessa??
Grazie mille a tutti
@NoemiRonco
Vorrei riassumere il ragionamento.
Invece di partire a spron battuto con i calcoli, è cosa utile e giusta ragionare sul problema.
In questo caso abbiamo una funzione obiettivo che è un piano. Senza manco scrivere la definizione di convessità (che invece deve esserti chiara e devi conoscerla), mi chiedo "se prendo due punti qualsiasi del piano e li congiungo con un segmento, tutti i punti del segmento appartengono ancora al piano?"
La risposta è chiaramente positiva: il piano è una figura convessa e puoi dimostrarlo usando la definizione.
Poi guardo i due vincoli e mi chiedo "potranno non intersecarsi?". Se così fosse i vincoli formerebbero una regione aperta e pertanto non esisterà una soluzione di massimo o minimo. Prima ancora di fare alcun calcolo, so già che i due vincoli formeranno una regione chiusa e posso darmene una rappresentazione qualitativa (il disegno che ho proposto) basato sul riconoscimento delle funzioni che formano i due vincoli.
Quindi so già che il vincolo proposto è una regione concava e pure come dimostrarlo perchè se considero i punti di intersezione fra la parabola e la circonferenza e li congiungo, tutti i punti del segmento ottenuto (eccetto gli estremi) non appartengono alla regione stessa. E mi basta un controesempio per dimostrarne la concavità.
Inoltre, proiettando la regione sul piano, e congiungendo sempre i due punti ottenuti, potrò dimostrare che anch'essa è concava.
Infine, poichè il piano è inclinato e si può immaginare come un insieme di rette parallele, posso prenderne una che intersechi la regione del vincolo e dedurre che i due punti di intersezione, proiettati sulla funzione obiettivo, avranno "altezze" $z_0$ e $z_1$ diverse. Inoltre tutti i punti che stanno sul segmento avranno altezze comprese fra $z_0$ e $z_1$, ergo so già le soluzioni minime e massime saranno sulla proiezione del bordo del vincolo.
Tutto questo, prima ancora di aver buttato giù il minimo calcolo: ed ho già una strategia chiara su come procedere.
Vorrei riassumere il ragionamento.
Invece di partire a spron battuto con i calcoli, è cosa utile e giusta ragionare sul problema.
In questo caso abbiamo una funzione obiettivo che è un piano. Senza manco scrivere la definizione di convessità (che invece deve esserti chiara e devi conoscerla), mi chiedo "se prendo due punti qualsiasi del piano e li congiungo con un segmento, tutti i punti del segmento appartengono ancora al piano?"
La risposta è chiaramente positiva: il piano è una figura convessa e puoi dimostrarlo usando la definizione.
Poi guardo i due vincoli e mi chiedo "potranno non intersecarsi?". Se così fosse i vincoli formerebbero una regione aperta e pertanto non esisterà una soluzione di massimo o minimo. Prima ancora di fare alcun calcolo, so già che i due vincoli formeranno una regione chiusa e posso darmene una rappresentazione qualitativa (il disegno che ho proposto) basato sul riconoscimento delle funzioni che formano i due vincoli.
Quindi so già che il vincolo proposto è una regione concava e pure come dimostrarlo perchè se considero i punti di intersezione fra la parabola e la circonferenza e li congiungo, tutti i punti del segmento ottenuto (eccetto gli estremi) non appartengono alla regione stessa. E mi basta un controesempio per dimostrarne la concavità.
Inoltre, proiettando la regione sul piano, e congiungendo sempre i due punti ottenuti, potrò dimostrare che anch'essa è concava.
Infine, poichè il piano è inclinato e si può immaginare come un insieme di rette parallele, posso prenderne una che intersechi la regione del vincolo e dedurre che i due punti di intersezione, proiettati sulla funzione obiettivo, avranno "altezze" $z_0$ e $z_1$ diverse. Inoltre tutti i punti che stanno sul segmento avranno altezze comprese fra $z_0$ e $z_1$, ergo so già le soluzioni minime e massime saranno sulla proiezione del bordo del vincolo.
Tutto questo, prima ancora di aver buttato giù il minimo calcolo: ed ho già una strategia chiara su come procedere.
@ NoemiRonco: Le funzioni lineari sono le uniche ad essere contemporaneamente concave e convesse... Dunque il tuo problema, in questo caso, non è che abbia molto senso.
Per il resto, la convessità di funzioni numeriche di una o più variabili è uno di quegli argomenti canonici per ogni corso di Analisi II: esistono teoremi appositi (test della derivata seconda, test dell'hessiano, etc...) che ti dicono cosa fare. Ti occorre ripeterli, se non li ricordi.
@ Bokonon:
Dai, non scherziamo... Passi pure il disegno fatto maluccio, ma una cosa del genere no, eh.
Per il resto, la convessità di funzioni numeriche di una o più variabili è uno di quegli argomenti canonici per ogni corso di Analisi II: esistono teoremi appositi (test della derivata seconda, test dell'hessiano, etc...) che ti dicono cosa fare. Ti occorre ripeterli, se non li ricordi.
@ Bokonon:
"Bokonon":
[...] abbiamo una funzione obiettivo che è un piano [...]
Dai, non scherziamo... Passi pure il disegno fatto maluccio, ma una cosa del genere no, eh.
@gugo
Non hai letto il testo del problema...
Non hai letto il testo del problema...
"Bokonon":
@gugo
Non hai letto il testo del problema...
L'ho letto, ma ciò non scusa tue imprecisioni.
@gugo
Ok, Objective function : $ f(x_1 , x_2 ) = x_1 + 3x_2 $ è un piano "impreciso" e il disegno "rappresentativo" doveva essere la soluzione.
Giuro che non riesco ad entrare nella tua testa
Ok, Objective function : $ f(x_1 , x_2 ) = x_1 + 3x_2 $ è un piano "impreciso" e il disegno "rappresentativo" doveva essere la soluzione.
Giuro che non riesco ad entrare nella tua testa
"Bokonon":
@gugo
Ok, Objective function : $ f(x_1 , x_2 ) = x_1 + 3x_2 $ è un piano "impreciso" e il disegno "rappresentativo" doveva essere la soluzione.
Giuro che non riesco ad entrare nella tua testa
Non si tratta di entrare nella mia testa; si tratta di saper leggere l'italiano.
"gugo82":
Non si tratta di entrare nella mia testa; si tratta di saper leggere l'italiano.
Oh, lo conosco poco. Ne approfitto per farmi spiegare questo passaggio:
"NoemiRonco":
la nostra funzione obiettivo in due variabili è data da una retta
Sei meno flessibile della signorina Rottenmeier
"Bokonon":
[quote="gugo82"]
Non si tratta di entrare nella mia testa; si tratta di saper leggere l'italiano.
Oh, lo conosco poco. Ne approfitto per farmi spiegare questo passaggio:
"NoemiRonco":[/quote]
la nostra funzione obiettivo in due variabili è data da una retta
Appunto... Avendo rilevato un errore del genere, avresti potuto chiedere lumi ad OP, invece che aggiungere la tua confusione alla sua (ed invece che chiedere a me l'esegesi di altri).
Quanto al resto, mi pare abbastanza evidente che gli errori di chi posta per le prime volte sono più tollerabili di chi posta da anni, o no?
"gugo82":
Quanto al resto, mi pare abbastanza evidente che gli errori di chi posta per le prime volte sono più tollerabili di chi posta da anni, o no?
Ma certo...io ci passo sopra e provo a relazionarmi comunque. Sono diventato assai flessibile (forse troppo) con l'età ma capisco il tuo punto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo