Kuhn-Tucker
Buongiorno ragazzi 
Mi sto da poco cimentando con i problemi di ottimizzazione con vincoli rilassati ma in ogni esercizio che ho provato a risolvere finisco sempre col bloccarmi al momento di risolvere il sistema.
Vi propongo questo esercizio:
Data $ f(x,y)=(x^2-y^2)/(x^2+y^2+1) $, trovare massimi e minimi nel triangolo $ T={(x,y)in RR^2|3x+2y<=7} $.
Inizio con l'ottimizzazione libera.
Calcolate le derivate parziali e poste a sistema ottengo come unico punto stazionario $ P_1=(0,0) $ il quale, tramite Hessiano, mi restituisce un sella. Fin qua non dovrebbero esserci errori.
Proseguo con l'ottimizzazione vincolata.
La condizione di vincolo qualificato $ R([ ( 3 ),( 2 ) ])=1 $ è sempre verificata. Imposto poi la lagrangiana $ L(\cdot )=(x^2-y^2)/(x^2+y^2+1)+\lambda_1(3x+2y-7)+\lambda_2(-x)+\lambda_3(-y) $ , e ottengo così il sistema
A questo punto non ho ben chiaro come procedere. Ho iniziato col considerare la terza, quarta e quinta equazione, che per $\lambda_1=\lambda_2=\lambda_3=0$ mi riportano al sistema di ottimizzazione libera, ovvero $(x,y)=(0,0)$. Dovrebbe essere una soluzione accettabile perchè la condizione di vincolo qualificato è verificata $ AA bar(x) $ . Poi, siccome le costanti lambda devono essere tutte $>=0$, da quanto ho capito non dovrei far altro che mantenere uguali una o più costanti e imporre la positività dei restanti (ad es. verificare cosa succede per $\lambda_1=\lambda_2=0, \lambda_3>0$). Ecco, se così fosse, come lo risolvo? Potreste mostrarmi i passaggi?
Mi sto da poco cimentando con i problemi di ottimizzazione con vincoli rilassati ma in ogni esercizio che ho provato a risolvere finisco sempre col bloccarmi al momento di risolvere il sistema. Vi propongo questo esercizio:
Data $ f(x,y)=(x^2-y^2)/(x^2+y^2+1) $, trovare massimi e minimi nel triangolo $ T={(x,y)in RR^2|3x+2y<=7} $.
Inizio con l'ottimizzazione libera.
Calcolate le derivate parziali e poste a sistema ottengo come unico punto stazionario $ P_1=(0,0) $ il quale, tramite Hessiano, mi restituisce un sella. Fin qua non dovrebbero esserci errori.
Proseguo con l'ottimizzazione vincolata.
La condizione di vincolo qualificato $ R([ ( 3 ),( 2 ) ])=1 $ è sempre verificata. Imposto poi la lagrangiana $ L(\cdot )=(x^2-y^2)/(x^2+y^2+1)+\lambda_1(3x+2y-7)+\lambda_2(-x)+\lambda_3(-y) $ , e ottengo così il sistema
$ { ( (4xy^2+2x)/(x^2+y^2+1)^2-3\lambda_1-\lambda_2=0),( (-4x^2y-2y)/(x^2+y^2+1)^2-2\lambda_1-\lambda_3=0 ),( \lambda_1(3x+2y-7)=0 ),( \lambda_2(-x)=0 ),( \lambda_3(-y)=0 ):} $
A questo punto non ho ben chiaro come procedere. Ho iniziato col considerare la terza, quarta e quinta equazione, che per $\lambda_1=\lambda_2=\lambda_3=0$ mi riportano al sistema di ottimizzazione libera, ovvero $(x,y)=(0,0)$. Dovrebbe essere una soluzione accettabile perchè la condizione di vincolo qualificato è verificata $ AA bar(x) $ . Poi, siccome le costanti lambda devono essere tutte $>=0$, da quanto ho capito non dovrei far altro che mantenere uguali una o più costanti e imporre la positività dei restanti (ad es. verificare cosa succede per $\lambda_1=\lambda_2=0, \lambda_3>0$). Ecco, se così fosse, come lo risolvo? Potreste mostrarmi i passaggi?
Risposte
Nulla da fare ragazzi, è un giorno intero che mi sbatto a capire come procedere ma non ne cavo un ragno dal buco.
Ho provato a seguire le indicazioni qui di seguito…
…e ho provato ad applicarle al mio caso ma con scarsi risultati. Dato il vincolo $3x+2y<=7$ (e i due vincoli "impliciti" $x>=0$ e $y>=0$) la lagrangiana è $ L=(x^2-y^2)/(x^2+y^2+1)-\lambda_1(x)-\lambda_2(y)-\lambda_3(3x+2y-7) $ .
Inizio disattivando tutti i vincoli: mi trovo quindi in ottimizzazione libera. Ottengo il punto $(0,0)$ che però non credo sia accettabile dato che sia per $x>=0$ che per $y>=0$ risulta $0>0$, il che dovrebbe significare che i vincoli sono in realtà attivi.
Poi attivo il primo vincolo ($\lambda_2=\lambda_3=0$) e ottengo il sistema $ { ( (4xy^2+2x)/(x^2+y^2+1)^2-3\lambda_1=0 ),( (-4x^2y-2y)/(x^2+y^2+1)^2-2\lambda_1=0 ),( x=0 ):} $. Dato $x=0$ risulta $ -3\lambda_1=0rArr\lambda_1=0 $ e $ -(2y)/(y^2+1)^2=0rArry=0 $ , quindi ottengo il punto $(0,0,0)$. Sostituendolo nei vincoli inattivi si ha, per $y>=0rArr0>0$, quindi se vale quanto detto sopra anche in questo caso la soluzione va scartata.
Attivo il secondo vincolo ($\lambda_1=\lambda3=0$) e il sistema è $ { ( (4xy^2+2x)/(x^2+y^2+1)^2-\lambda_2=0 ),( (-4x^2y-2y)/(x^2+y^2+1)^2=0 ),( y=0 ):} $. Ora, dato $y=0$ il sistema è indeterminato quindi come procedo?
Ho provato a seguire le indicazioni qui di seguito…
"Vulplasir":
Eh qui hai vincoli introdotto da più condizioni...per usare lagrange devi considerare i vari vincoli ognuno per conto proprio e poi considerare le restrizioni introdotte dagli altri vincoli...un lavoraccio, in questi casi la generlizzazione al metodo di Lagrange è il metodo dei moltiplicatori di Kuhn-Tucker
1) Prendi il vincolo $x^3+y^3=1$, ci applichi lagrange, trovi i punti che lo soddisfano, e verifichi che tali punti soddisfino gli altri due vincoli x>=0 e y>=0
2) Prendi il vincolo x=0, ci applichi lagrange, trovi i punti che lo soddisfano e verifichi che tali punti soddisfino gli altri due vincoli y>=0 e x^3+y^3<=1
3) Prendi il vincolo y=0, ci applichi Lagrange, trovi i punti che lo soddisfano e verifichi che tali punti soddisfino gli altri due vincoli x>=0 e x^3+y^3<=1
…e ho provato ad applicarle al mio caso ma con scarsi risultati. Dato il vincolo $3x+2y<=7$ (e i due vincoli "impliciti" $x>=0$ e $y>=0$) la lagrangiana è $ L=(x^2-y^2)/(x^2+y^2+1)-\lambda_1(x)-\lambda_2(y)-\lambda_3(3x+2y-7) $ .
Inizio disattivando tutti i vincoli: mi trovo quindi in ottimizzazione libera. Ottengo il punto $(0,0)$ che però non credo sia accettabile dato che sia per $x>=0$ che per $y>=0$ risulta $0>0$, il che dovrebbe significare che i vincoli sono in realtà attivi.
Poi attivo il primo vincolo ($\lambda_2=\lambda_3=0$) e ottengo il sistema $ { ( (4xy^2+2x)/(x^2+y^2+1)^2-3\lambda_1=0 ),( (-4x^2y-2y)/(x^2+y^2+1)^2-2\lambda_1=0 ),( x=0 ):} $. Dato $x=0$ risulta $ -3\lambda_1=0rArr\lambda_1=0 $ e $ -(2y)/(y^2+1)^2=0rArry=0 $ , quindi ottengo il punto $(0,0,0)$. Sostituendolo nei vincoli inattivi si ha, per $y>=0rArr0>0$, quindi se vale quanto detto sopra anche in questo caso la soluzione va scartata.
Attivo il secondo vincolo ($\lambda_1=\lambda3=0$) e il sistema è $ { ( (4xy^2+2x)/(x^2+y^2+1)^2-\lambda_2=0 ),( (-4x^2y-2y)/(x^2+y^2+1)^2=0 ),( y=0 ):} $. Ora, dato $y=0$ il sistema è indeterminato quindi come procedo?
Ciao mobley,
Non è che ti stai complicando un po' la vita?
La funzione proposta $z = f(x, y) = (x^2-y^2)/(x^2+y^2+1) $ è una funzione pari definita sul dominio $D = \RR^2 $ e $f(0,0) = 0 $
Se il vincolo è effettivamente un triangolo come hai scritto allora non è quello che hai scritto, ma è il seguente:
$T = {(x,y) \in \RR^2 | x >= 0, y >= 0, 3x+2y <= 7} $
Dato che la funzione $z = f(x, y)$ non ha estremi relativi interni, i punti di massimo e minimo assoluto sono su $\del T $ (la frontiera di $T$), che è piuttosto semplice da esplicitare nel caso in esame e ci si ritrova a studiare funzioni di una sola variabile:
Sull'asse $y$ ($x = 0 $) si ha $f(0,y) = -y^2/(y^2 + 1) <= 0 \quad \AA y >= 0 $
Sull'asse $x$ ($y = 0 $) si ha $f(x, 0) = x^2/(x^2 + 1) >= 0 \quad \AA x >= 0 $
Sulla retta $3x+2y = 7 \implies 2y = -3x + 7 \implies y = -3/2 x + 7/2 $ si ha $f(x, -3/2 x + 7/2) $ che è una funzione della sola variabile $x $ non difficile da studiare.
I punti di estremo assoluto per la funzione proposta si trovano quindi considerando i massimi ed i minimi di semplici funzioni di una sola variabile...
Anzi, ti dirò di più: viste le particolari funzioni di una variabile ottenute, non serve neanche studiarle perché si avrà un massimo nel punto $M(7/3, 0) $ di intersezione della retta $ y = -3/2 x + 7/2 $ con l'asse $x$, ed un minimo nel punto $N(0, 7/2) $ di intersezione della retta $ y = -3/2 x + 7/2 $ con l'asse $y$.
Non è che ti stai complicando un po' la vita?
La funzione proposta $z = f(x, y) = (x^2-y^2)/(x^2+y^2+1) $ è una funzione pari definita sul dominio $D = \RR^2 $ e $f(0,0) = 0 $
Se il vincolo è effettivamente un triangolo come hai scritto allora non è quello che hai scritto, ma è il seguente:
$T = {(x,y) \in \RR^2 | x >= 0, y >= 0, 3x+2y <= 7} $
Dato che la funzione $z = f(x, y)$ non ha estremi relativi interni, i punti di massimo e minimo assoluto sono su $\del T $ (la frontiera di $T$), che è piuttosto semplice da esplicitare nel caso in esame e ci si ritrova a studiare funzioni di una sola variabile:
Sull'asse $y$ ($x = 0 $) si ha $f(0,y) = -y^2/(y^2 + 1) <= 0 \quad \AA y >= 0 $
Sull'asse $x$ ($y = 0 $) si ha $f(x, 0) = x^2/(x^2 + 1) >= 0 \quad \AA x >= 0 $
Sulla retta $3x+2y = 7 \implies 2y = -3x + 7 \implies y = -3/2 x + 7/2 $ si ha $f(x, -3/2 x + 7/2) $ che è una funzione della sola variabile $x $ non difficile da studiare.
I punti di estremo assoluto per la funzione proposta si trovano quindi considerando i massimi ed i minimi di semplici funzioni di una sola variabile...
Anzi, ti dirò di più: viste le particolari funzioni di una variabile ottenute, non serve neanche studiarle perché si avrà un massimo nel punto $M(7/3, 0) $ di intersezione della retta $ y = -3/2 x + 7/2 $ con l'asse $x$, ed un minimo nel punto $N(0, 7/2) $ di intersezione della retta $ y = -3/2 x + 7/2 $ con l'asse $y$.
Ciao pilloeffe, anzitutto grazie mille per la risposta.
Ti dico... Io sto provando a generalizzare il meccanismo di risoluzione, che sia valido in ogni circostanza, e in alcuni casi riesco a farlo. Come in questo caso, che ti invito a guardare:
Nel caso dell'esercizio in questione, invece, mi blocco arrivato al caso $\lambda_2>0$. Non so proprio come andare avanti…
Cosa ne pensi? Credo che il metodo di risoluzione sia corretto… Senza dubbio una faticaccia eh, ma altrimenti non sono riuscito a fare.
Ti dico... Io sto provando a generalizzare il meccanismo di risoluzione, che sia valido in ogni circostanza, e in alcuni casi riesco a farlo. Come in questo caso, che ti invito a guardare:
Nel caso dell'esercizio in questione, invece, mi blocco arrivato al caso $\lambda_2>0$. Non so proprio come andare avanti…
Cosa ne pensi? Credo che il metodo di risoluzione sia corretto… Senza dubbio una faticaccia eh, ma altrimenti non sono riuscito a fare.
"mobley":
Io sto provando a generalizzare il meccanismo di risoluzione, che sia valido in ogni circostanza.
Se tutti i problemi in matematica fossero risolubili con "meccanismi generali e sempre validi" allora non vedrei differenze fra laureati in matematica e calcolatrici umane. Tu vuoi a tutti i costi utilizzare un metodo che non si adatta al caso, per applicare il metodo dei moltiplicatori dovresti esprimere il bordo di $T$ come luogo degli zeri di una funzione $g(x,y)$.
L'insieme $T$ inoltre, come lo hai scritto te, non è un triangolo ma circa mezzo piano cartesiano.
Ritorno su questo post perchè, dopo lunga e attenta riflessione ( 
), e soprattutto dopo il prezioso aiuto che @pilloeffe mi ha dato, credo di aver capito come svolgere questo tipo di esercizi. Nell'ordine: calcolo le derivate parziali della funzione, imposto la lagrangiana, costruisco il sistema usando le condizioni di Kuhn-Tucker, e verifico di volta in volta ponendo $x=0$, $y=0$ e $g(bar(x))=0$ cosa accade al sistema iniziale, trovando così i punti stazionari. Una volta fatto questo calcolo le derivate parziali sia della funzione che del vincolo in modo tale da costruire l'Hessiano orlato e stabilire così se si tratta di massimo, minimo oppure se la condizione del II ordine è inconclusiva.
Detto questo però, tornando all'esercizio del post, non mi risulta una cosa. Svolgendolo ho ottenuto diversi punti stazionari: $(0,0,0)$ e $(0, 7/2, -56/2809)$ per $x=0$, $(0,0,0)$ e $(7/3,0,62/1682)$ per $y=0$ e $(7/3,0,0)$ per $3x+2y=7$. Ora, mentre $(0,0,0)$ e $(7/3,0,62/1682)$ rispettano tutte le condizioni di ottimalità di KKT, il punto che teoricamente dovrebbe essere di minimo (ossia $(0, 7/2, -56/2809)$) ha $\lambda<0$ (come si vede dalla foto), il che non soddisferebbe la condizione di non negatività del moltiplicatore.
Ho controllato e ricontrollato i calcoli, e credo siano giusti. Dove sto sbagliando?
), e soprattutto dopo il prezioso aiuto che @pilloeffe mi ha dato, credo di aver capito come svolgere questo tipo di esercizi. Nell'ordine: calcolo le derivate parziali della funzione, imposto la lagrangiana, costruisco il sistema usando le condizioni di Kuhn-Tucker, e verifico di volta in volta ponendo $x=0$, $y=0$ e $g(bar(x))=0$ cosa accade al sistema iniziale, trovando così i punti stazionari. Una volta fatto questo calcolo le derivate parziali sia della funzione che del vincolo in modo tale da costruire l'Hessiano orlato e stabilire così se si tratta di massimo, minimo oppure se la condizione del II ordine è inconclusiva. Detto questo però, tornando all'esercizio del post, non mi risulta una cosa. Svolgendolo ho ottenuto diversi punti stazionari: $(0,0,0)$ e $(0, 7/2, -56/2809)$ per $x=0$, $(0,0,0)$ e $(7/3,0,62/1682)$ per $y=0$ e $(7/3,0,0)$ per $3x+2y=7$. Ora, mentre $(0,0,0)$ e $(7/3,0,62/1682)$ rispettano tutte le condizioni di ottimalità di KKT, il punto che teoricamente dovrebbe essere di minimo (ossia $(0, 7/2, -56/2809)$) ha $\lambda<0$ (come si vede dalla foto), il che non soddisferebbe la condizione di non negatività del moltiplicatore.
Ho controllato e ricontrollato i calcoli, e credo siano giusti. Dove sto sbagliando?
Sto sbattendo la testa sull'inammissibilità del presunto minimo (di cui alla foto del post appena precedente), e non ne vengo a capo. Spero ancora in un aiuto onestamente 
Detto questo… Supponiamo che ora io abbia risolto il sistema con le condizioni di KKT (o tramite curve di livello) e mi trovi con una serie di punti possibili candidati ad essere massimi o minimi. Ebbene, in ogni esercizio che ho trovato online e in tutti quelli proposti dal mio libro si chiede SIN DA SUBITO di determinare il massimo e/o il minimo della funzione proposta (e sottoposta agli uno o più vincoli). Vale a dire: "Determinare $ max\\ min f(x) $ dati i vincoli…" . In questo modo è quindi sufficiente, una volta trovati i punti, calcolare la funzione in quei punti ed operare per confronto per individuare il massimo o il minimo richiesto. A conferma di ciò:
Tuttavia supponiamo che io NON abbia questa informazione iniziale. Devo quindi stabilire QUALI TRA QUEI PUNTI sono massimi e/o minimi. Vale a dire: "Trovare massimi e minimi di $f(x)$ dati i vincoli…" (con vincoli di disuguaglianza che richiedono evidentemente KKT). Come faccio? Costruisco l'Hessiano "normale"? Oppure l'Hessiano "orlato"? Ci sono altri modi?
Detto questo… Supponiamo che ora io abbia risolto il sistema con le condizioni di KKT (o tramite curve di livello) e mi trovi con una serie di punti possibili candidati ad essere massimi o minimi. Ebbene, in ogni esercizio che ho trovato online e in tutti quelli proposti dal mio libro si chiede SIN DA SUBITO di determinare il massimo e/o il minimo della funzione proposta (e sottoposta agli uno o più vincoli). Vale a dire: "Determinare $ max\\ min f(x) $ dati i vincoli…" . In questo modo è quindi sufficiente, una volta trovati i punti, calcolare la funzione in quei punti ed operare per confronto per individuare il massimo o il minimo richiesto. A conferma di ciò:
"TeM":
La determinazione dei punti critici risulta così conclusa e […] Non rimane che esplicitarli e valutarli in \(f\), quindi decretare minimi e massimi assoluti semplicemente per confronto.
Tuttavia supponiamo che io NON abbia questa informazione iniziale. Devo quindi stabilire QUALI TRA QUEI PUNTI sono massimi e/o minimi. Vale a dire: "Trovare massimi e minimi di $f(x)$ dati i vincoli…" (con vincoli di disuguaglianza che richiedono evidentemente KKT). Come faccio? Costruisco l'Hessiano "normale"? Oppure l'Hessiano "orlato"? Ci sono altri modi?
Ragazzi, è urgente, domani ho l'esame 
Trovati 'sti benedettissimi punti di possibile massimo o minimo, come stabilisco se effettivamente sono l'uno o l'altro? Non posso usare il metodo del confronto perché non viene detto dal testo se devo massimizzare o minimizzare!!!
Trovati 'sti benedettissimi punti di possibile massimo o minimo, come stabilisco se effettivamente sono l'uno o l'altro? Non posso usare il metodo del confronto perché non viene detto dal testo se devo massimizzare o minimizzare!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo