OliForum Matematico

li vedo sparsi quà e là in alcune dimostrazioni... di che si tratta?

Si tratta di un metodo di risolvere problemi di massimo e minimo vincolato. Non fanno parte del bagaglio olimpico, dato che il metodo richiede un uso determinante delle derivate parziali (argomento che di solito si affronta durante il corso di Analisi II).

Come al solito, quando in un problema olimpico si usano strumenti avanzati (cosiddetti "cannoni"), il loro uso è lecito, ma fortemente deprecato: in una gara sensata ci sarà sempre anche la soluzione elementare senza i moltiplicatori.

Comunque, se proprio dovete strappare quel punticino che vi permette di arrivare in zona medaglie...

Supponi che ti chieda di trovare il massimo della funzione obiettivo
$ \max x^2 y $
con x e y soggetti al vincolo
$ x^2 + y^2 = 1 $

[l'esempio è scelto stupido apposta. Un buon concorrente olimpico dovrebbe sapere come risolvere questo problema con metodi... olimpici...]

Chiama $ f(x,y) $ la funzione obiettivo che vuoi massimizzare [minimizzare] e $ g(x,y) $ l'equazione del vincolo. [nota: i vincoli potrebbero essere più di uno...].

Nel mio esempio:

$ f(x,y) = x^2 y, \qquad g(x,y) = x^2 + y^2 - 1 $.

Il metodo funziona così: ti inventi una variabile extra per ogni vincolo (qui: un vincolo, una variabile, che chiamo, come è tradizione $ \lambda $). Le variabili extra sono i famosi moltiplicatori. Poi costruisci una funzione ausiliaria così:
funzione obiettivo + $ \lambda_1 \cdot $ vincolo1 + $ \lambda_2 \cdot $ vincolo2...

Nel mio esempio:

$ \Phi(x,y,\lambda) = x^2 y + \lambda \left( x^2 + y^2 - 1 \right) $

Sotto ipotesi buone (ad esempio, che il luogo di zeri dei vincoli non abbia singolarità o "spigoli", che le funzioni siano derivabili in un certo modo, e altre bazzecole che ti divertirai ad imparare ad Analisi II se mai avrai l'indubbia fortuna di doverlo fare), allora i candidati punti di massimo si trovano risolvendo un sistema ottenunto imponendo a 0 le derivate parziali della funzione ausiliaria. Tante equazioni quante sono le variabili della fz obiettivo + il numero dei vincoli [nell'esempio, 2 + 1].

Per chi non sapesse come si calcola una derivata parziale, è come una derivata semplice, calcolata rispetto ad una sola variabile "facendo finta" che tutte le altre variabili siano in realtà costanti. [ecco come buttare nel cesso anni di Calcolo Differenziale; evviva il rigore matematico!...]

$ \frac{\partial \Phi(x,y,\lambda)}{\partial x} = 2xy + 2 \lambda x = 0 $
$ \frac{\partial \Phi(x,y,\lambda)}{\partial y} = x^2 + 2 \lambda y = 0 $
$ \frac{\partial \Phi(x,y,\lambda)}{\partial \lambda} = x^2 + y^2 - 1 = 0 $

Notare che le derivate rispetto ai moltiplicatori ridanno sempre le equazioni dei vincoli, quindi posso risparmiarmi qualche derivata...

Ora viene il brutto del metodo: salvo casi particolarissimi e fortunati, quel che risulta è un sistemone non lineare, che va risolto affidandosi alla fortuna.

In questo caso, dato che mi son scelto l'esercizio facile, il sistema si risolve.

Dalla prima, $ x=0 $ oppure $ \lambda = -y $. La prima dà la soluzione $ x=0, y=\pm1 $ [notare che l'impostante è risolvere per x e y. Il valore finale di $ \lambda $ è invece irrilevante...]

La seconda dà $ x^2-2y^2=0 $, che si risolve in $ x^2=2/3, y^2=1/3 $.

Quindi ho sei soluzioni [occhio ai segni!!]. Calcolo la fz obiettivo:

$ x=0, y = \pm 1, \qquad f(x,y) = 0 $
$ x= \pm \sqrt \frac 2 3, y = \sqrt \frac 1 3, \qquad f(x,y) = \frac{2}{3\sqrt 3} $
$ x= \pm \sqrt \frac 2 3, y = -\sqrt \frac 1 3, \qquad f(x,y) = -\frac{2}{3\sqrt 3} $.

Le prime due, con x=0 sono un massimo e un minimo relativi (si vede, ad esempio, con i segni...). Le seconde due sono il massimo assoluto cercato; le ultime due sono il minimo assoluto. [le avevate viste tutti le simmetrie del problema, vero??: fz obiettivo pari rispetto alla x e dispari rispetto alla y...]

grazie 1000

In pratica questo metodo serve solo quando c'è un vincolo?

ma l'intero teorema non è di Lagrange-Kuhn-Tucker ???

Gauss_87 ha scritto:ma l'intero teorema non è di Lagrange-Kuhn-Tucker ???

Fermo restando che la cosa è ininfluente, chi sarebbero gli altri due? non li ho mai sentiti, e una rapida ricerca ha rivelato che nemmeno su wikipedia ci sono matematici con quei nomi.. tu come li conosci?

Chiedo venia per la mia ignoranza veramente disgustosa sulle disuguaglianze, ma... Come si risolve olimpicamente quella disuguaglianza?

GM - QM applicata alla terna $ (x/\sqrt2,x/\sqrt2,y) $.

Scusa la sintesi ma sono di fretta. Per molti dovrebbe bastare, ma se hai bisogno di delucidazioni, chiedi pure.

Ok grazie.. Non avevo pensato alla radice di due

pic88 ha scritto:

Gauss_87 ha scritto:ma l'intero teorema non è di Lagrange-Kuhn-Tucker ???

Fermo restando che la cosa è ininfluente, chi sarebbero gli altri due? non li ho mai sentiti, e una rapida ricerca ha rivelato che nemmeno su wikipedia ci sono matematici con quei nomi.. tu come li conosci?

in realtà ci sono anche i moltiplicatori di Kuhn-Tucker...

Più moltiplicatori per tutti!

EvaristeG ha scritto:Più moltiplicatori per tutti!

è una "presa in giro"

no, è una presa di corrente...

i massimi e i minimi vincolati hanno anche dimostrazioni geometriche carine... le sto vedendo a economia, in cui ci sono le curve di isoutilità e il vincolo del reddito.

Il problema si potrebbe risolvere in maniera elementare ad esempio così:

tracciamo le curve nel piano xy per cui x^2*y=c costante.

y=c/x^2 per cui sono delle curve abbastanza semplici da disegnare. Sono funzioni strettamente decrescenti o crescenti, e intuitivamente possono, a seconda del valore di c, intersecare la circonferenza unitaria in due coppie simmetriche di punti, essere tangenti in un punto solo oppure non intersecarla del tutto.

A seconda che c sia più o meno grande in valore assoluto queste curve saranno più o meno distanti dall'origine, quindi il valore estremo di c è quello per cui le curve sono tangenti alla circonferenza.

Possiamo imporre il tutto algebricamente:

y^2+c/y=1

ovviamente y=0 non è una soluzione del nostro problema per cui possiamo riscrivere l'equazione come:

y^3-y+c=0

Sfruttiamo le simmetrie e la tangenza:

se le curve interscenano la circonferenza, abbiamo due coppie di punti simmetrici rispetto all'asse y, per cui abbiamo solo due radici y=m e y=p nell'intervallo (-1,1).

(y-m)(y-p)(y-q)=0

Ora, se vogliamo che le curve siano tangenti, queste due radici devono essere coincidenti, per cui possiamo riscrivere l'equazione di terzo grado come:

(y-m)^2*(y-q)=0

y^3-(q+2m)*y^2+(2mq+m^2)*y-m^2*q=0

Eguagliando i coefficienti a quelli dell'equazione originale:

q+2m=0

2mq+m^2=-1

-m^2*q=c


rielaborando:

m=+-sqrt(1/3)

q=-2m

c=-2*m^3

Per cui vediamo che i 4 punti di tangenza sono dati da:

(x,y)=(+-sqrt(2/3),+-sqrt(1/3))

quello che ci interessa però sono i possibili valori di c:

c=+-2*(1/3)^(3/2)

Come vedete è un metodo che non usa minimamente il calcolo differenziale.

Ovviamente non è neanche minimamente originale, anzi ovvio per chi ha studiato grafici con curve di isolivello

pic88 ha scritto:

Gauss_87 ha scritto:ma l'intero teorema non è di Lagrange-Kuhn-Tucker ???

Fermo restando che la cosa è ininfluente, chi sarebbero gli altri due? non li ho mai sentiti, e una rapida ricerca ha rivelato che nemmeno su wikipedia ci sono matematici con quei nomi.. tu come li conosci?

In problemi di ottimizzazione legati ai moltiplicatori di Lagrange ho visto comparire su almeno un paio di libri le condizioni di Karush-Kuhn-Tucker (KKT). Quindi confermo che i signori Kuhn e Tucker esistono, sono matematici (o perlomeno ingeNIeri), e hanno ottenuto risultati collegati al teorema di Lagrange.

EDIT: aggiunto link di Wikipedia