Massimi e minimi vincolati con vincoli di disuguaglianza Indice 1

UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
1
Massimi e minimi vincolati con vincoli di disuguaglianza
Indice
1 Definizione del problema di massimo. La forma standard
1
2 Caso con un solo vincolo
2.1 Il metodo delle curve di livello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Condizione necessaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2
2
3 Caso generale
5
4 Il problema con vincoli di non negatività
4.1 Le condizioni di Kuhn–Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Problemi “misti” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
9
12
5 Problemi di minimo
15
In questa dispensa consideriamo un problema di ottimizzazione con vincoli di disuguaglianza.
1
Definizione del problema di massimo. La forma standard
La formulazione generale per un problema di massimo è la seguente.1
Siano f, g1 , . . . , gm funzioni definite nell’aperto A ⊂ Rn , tutte di classe C 1 nell’insieme A.
Il problema
max f (x1 , . . . , xn )
con vincoli
gi (x1 , . . . , xn ) ≤ bi , i = 1, 2, . . . , m
consiste nel trovare i punti di massimo (locale o globale) della funzione f sul sottoinsieme di A che è soluzione del
sistema di condizioni espresse dai vincoli, cioè dalle m disequazioni gi (x1 , . . . , xn ) ≤ bi .
Il problema come sempre si può anche esprimere in forma vettoriale: se indichiamo con g la funzione a valori
vettoriali che ha per componenti le funzioni di vincolo (g è funzione di A in Rm ), con b il vettore dei termini noti bi
(b ∈ Rm ) e con x il vettore (x1 , . . . , xn ), possiamo scrivere il problema nella forma compatta
max f (x)
con vincoli g(x) ≤ b.
La forma scritta qui sopra è la cosiddetta forma standard per un problema di massimo.2
La funzione f si chiama sempre funzione obiettivo e la funzione g si chiama ancora funzione di vincolo. L’insieme
n
o
X = x ∈ A : gi (x1 , . . . , xn ) ≤ bi , per i = 1, . . . m
si chiama sempre regione ammissibile e i suoi punti punti ammissibili.
Le definizioni di punto di massimo vincolato (locale o globale) sono analoghe a quelle viste in precedenza.
Osservazione A differenza di quello che a volte si può fare con i vincoli di uguaglianza, e intendo esplicitare una
variabile dal vincolo, questa tecnica non può essere utilizzata con i vincoli in forma di disuguaglianza, proprio perché la
disequazione non consente di ricavare i valori di una variabile in funzione delle altre (si consideri che, mentre y = 1 + x
mi fornisce una legge che, dato x permette di trovare con certezza y, una y ≤ 1+x non mi permette di fare altrettanto).
1 Per
i problemi con vincoli di disuguaglianza le condizioni di ottimalità (anche quelle necessarie) non sono le stesse tra problemi di
massimo e problemi di minimo. Si preferisce quindi di solito svolgere la trattazione con riferimento ai problemi di un tipo e poi imparare
a trasformare i problemi dell’altro tipo riconducendosi sempre ai primi. Svolgerò la trattazione con riferimento ai problemi di massimo.
2 La forma standard per un problema di massimo prevede quindi dei vincoli di disuguaglianza espressi con il minore o uguale. È
importante fissare questo per le condizioni di ottimalità, che altrimenti verrebbero scritte in altro modo.
2
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
2
Caso con un solo vincolo
In questa sezione consideriamo anzitutto, come fatto prima, un problema con un solo vincolo. Va detto subito che
il metodo grafico delle curve di livello continua ad essere valido e anzi può portare facilmente, senza troppi calcoli,
a farsi un’idea di come stanno le cose (ovviamente a patto di saper tracciare senza troppa fatica le curve di livello).
Anche qui vediamo un semplice esempio di applicazione di questo metodo.
2.1
Il metodo delle curve di livello
y
Supponiamo di avere il problema
max f (x, y) = y − (x − 1)2
con vincolo x2 + y ≤ 1.
∇f (x)=∇g(x)
x
La regione ammissibile è indicata in grigio in figura. Si tratta della parte di piano
1
2
che sta al di sotto della parabola di equazione y = 1 − x . Sono indicate anche
alcune curve di livello della funzione obiettivo f e sono anche queste delle parabole
1
x
(di equazione y = (x− 1)2 + k). Il livello della funzione f aumenta quando la parabola
si sposta verso l’alto. La curva di livello massimo che tocca la regione ammissibile è
quella indicata dal tratto continuo. Il punto di massimo vincolato (globale) è quello
indicato con x.
Per trovare il punto x si procede come fatto in precedenza, imponendo che l’intersezione tra il vincolo e la curva
di livello di f sia unica.
2
x +y =1
y = 1 − x2
cioè
2
y − (x − 1) = k
1 − x2 − (x − 1)2 = k.
b
La seconda equazione (nella sola x) diventa
2x2 − 2x + k = 0. Il discriminante è ∆ = 1 − 2k
e questo si annulla per k = 12 , da cui l’equazione diventa 2x2 − 2x + 21 = 0, cioè 4x2 − 4x + 1 = 0, cioè (2x − 1)2 = 0,
che ha per soluzione x = 12 . Dalla prima equazione del sistema si trova infine y = 43 . Si ha quindi che il punto di
massimo (globale) vincolato è ( 21 , 34 ).
Osservazione Calcoliamo i gradienti di f e di g nel punto trovato. Si ha
∇f (x, y) = − 2(x − 1), 1 e ∇g(x, y) = 2x, 1
e quindi
∇f ( 21 , 34 ) = 1, 1 e
∇g( 21 , 34 ) = 1, 1 .
Si può notare che nel punto di massimo vincolato i due gradienti sono proporzionali (ma non è una novità) e il
coefficiente di proporzionalità è positivo (qui è 1, ma questo è soltanto un caso). Si potrebbe credere che anche la
positività del coefficiente sia un caso, ma non è cosı̀. Infatti:
• se il vincolo è g(x, y) ≤ b, allora il gradiente di g è rivolto verso l’esterno della regione individuata dal vincolo
(si ricordi che il gradiente indica sempre la direzione di massimo aumento dei valori della funzione);
• se il problema è di massimo e cerchiamo quindi di aumentare il valore di f , allora anche il gradiente di f è
rivolto verso l’esterno della regione ammissibile.3 Quindi i due gradienti sono rivolti dalla stessa parte e quindi
il coefficiente (il moltiplicatore) deve essere non negativo (nel nostro esempio è strettamente positivo).
Osservazione Anticipo un’osservazione che permette di comprendere poi più facilmente la condizione generale di
ottimalità che formalizziamo presto. Nell’esempio considerato il punto di massimo è sul bordo della regione ammissibile
(il bordo, o frontiera, della regione è dato dai punti che soddisfano il vincolo con l’uguaglianza, cioè che sono soluzione
della g(x, y) = b). Apparentemente il punto di massimo deve necessariamente stare sempre sul bordo,4 ma non è
proprio cosı̀. Il punto di massimo può essere interno ma in questo caso il gradiente di f deve essere nullo (e cioè,
possiamo dire, il moltiplicatore deve essere nullo).
3 Se
fosse rivolto verso l’interno il valore di f potrebbe aumentare ancora, sempre restando nella regione ammissibile.
potrebbe dire infatti che partendo da un punto interno alla regione il valore di f possa sempre aumentare. Infatti è vero, a meno
che il gradiente di f non sia nullo.
4 Si
3
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
2.2
Condizione necessaria
Esprimendo in generale quanto abbiamo osservato sull’esempio della sezione precedente basandoci su considerazioni
geometriche, possiamo dire che per il problema
max f (x)
(x ∈ Rn ),
con vincolo g(x) ≤ b
assumendo che x sia un punto di massimo vincolato, avremo che
• se g(x) = b, allora esiste un λ ≥ 0 tale che ∇f (x) = λ∇g(x);
• se g(x) < b, allora ∇f (x) = 0 e cioè λ = 0 (dato che il vincolo è regolare).
Queste condizioni si possono ancora esprimere attraverso condizioni sulla funzione Lagrangiana del problema, che
continua ad essere
L(x, λ) = f (x) − λ(g(x) − b).
Infatti basta osservare che
• la condizione ∇f (x) = λ∇g(x) si può scrivere ∇x L(x, λ) = 0
• il rispetto dei vincoli (g(x) ≤ b) si può scrivere L′λ (x, λ) ≥ 0 infatti L′λ = −g(x) + b
• la condizione che impone λ = 0 quando il vincolo è verificato con la disuguaglianza stretta si può scrivere
λL′λ (x, λ) = 0 (infatti vuol dire λ(−g(x) + b) = 0 e quindi se non è zero il termine tra parentesi deve essere zero
il moltiplicatore).
Ecco allora le condizioni necessarie per un punto di massimo vincolato.
Teorema Siano f, g : A → R due funzioni di classe C 1 nell’aperto A ⊂ Rn . Dato il problema
max f (x)
con vincolo g(x) ≤ b,
definiamo la funzione Lagrangiana L(x, λ) = f (x) − λ g(x) − b .
Sia x un punto di massimo locale vincolato di f e, se g(x) = b, sia ∇g(x) 6= 0. Allora esiste un λ ∈ R tale che
valgano contemporaneamente le seguenti condizioni:
(i) ∇x L(x, λ) = 0
(ii) ∇λ L(x, λ) ≥ 0
∧
λ∇λ L(x, λ) = 0
5
(iii) λ ≥ 0.
Osservazione Si tratta a tutti gli effetti operativi di un sistema di condizioni. Le condizioni (i) sono in realtà n
condizioni di uguaglianza (una per ogni variabile); la (ii) contiene una condizione di disuguaglianza e una di uguaglianza
e la (iii) è un’altra condizione.
Mettendo a confronto queste con le condizioni di ottimalità per problemi con vincoli di uguaglianza (∇L(x, λ) =
0), possiamo notare anzitutto l’importante novità sul segno del moltiplicatore e poi che il gradiente parziale della
Lagrangiana rispetto alle x resta uguale a zero, mentre rispetto a λ diventa ≥ 0 e si aggiunge la condizione λ∇λ = 0.
Tale condizione, che ritroveremo in varie forme anche nel seguito, prende il nome di condizione di complementarità.
Quindi il gradiente di L rispetto al moltiplicatore diventa ≥ 0 con abbinata la condizione di complementarità.
Osservazione Si intuisce che la condizione sul gradiente di g è la condizione di regolarità del vincolo, del tutto
analoga a quella per i problemi con vincolo di equazione. Si noti però che nell’enunciato la regolarità viene richiesta
solo se g(x) = b. In effetti, se abbiamo g(x) < b il gradiente di f deve essere nullo e quindi può essere nullo anche il
gradiente di g.
Osservazione Dall’enunciato della condizione di ottimalità e dalle osservazioni che precedono l’enunciato stesso si
rileva che nei problemi con vincoli di disuguaglianza è importante la distinzione nei due casi di vincolo soddisfatto con
l’uguaglianza (g(x) = b) o vincolo soddisfatto con la disuguaglianza stretta (g(x) < b). Per questo motivo alle due
situazioni si dà un nome: si dice che nel primo caso il vincolo è attivo (altri dicono saturato, altri ancora stringente)
e nel secondo è non attivo (o non saturato o non stringente). Vedremo tra breve che nei casi generali con più vincoli
5 Il simbolo “∧” che uso qui e userò nel seguito significa “e”: le due condizioni devono essere vere entrambe. Le potrei anche scrivere su
righe diverse, ma non lo faccio per evitare che il sistema diventi troppo lungo e per abbinare le due condizioni.
4
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
le condizioni di regolarità riguardano soltanto i vincoli attivi, confermando la giusta sensazione che a questo punto si
ha che i vincoli non attivi non hanno alcuna rilevanza.
Esempio Riconsideriamo il problema risolto poco fa con le curve di livello, cioè
max f (x, y) = y − (x − 1)2
con vincolo x2 + y ≤ 1.
La funzione Lagrangiana è
L(x, y, λ) = y − (x − 1)2 − λ(x2 + y − 1).
Le condizioni di ottimalità sono:6

−2(x − 1) − 2λx = 0



1−λ=0
 x2 + y ≤ 1 ∧ λ(x2 + y − 1) = 0


λ≥0
cioè

 λ=1
x2 + y = 1

−2x + 2 − 2x = 0
cioè

 λ=1
x = 21

y = 34 .
Si trova quindi il punto ( 12 , 34 ) con moltiplicatore λ = 1 (che, si ricorderà, è il coefficiente di proporzionalità tra i due
gradienti).
Esempio
max f (x, y) = 2x + y
con vincolo xy ≥ 1.
Il problema non è in forma standard e quindi occorre prima scriverlo come
max f (x, y) = 2x + y
con vincolo
− xy ≤ −1.
La funzione Lagrangiana è
L(x, y, λ) = 2x + y − λ(−xy + 1).
Le condizioni di ottimalità sono:

2 + λy = 0



1 + λx = 0

xy ≥ 1 ∧


λ ≥ 0.
λ(xy − 1) = 0
Si può procedere considerando i due casi possibili: λ = 0 oppure λ > 0.
Se λ = 0 si vede subito (prima equazione) che non ci sono soluzioni. Se λ > 0 abbiamo

 2 + λy = 0
1 + λx = 0

xy = 1
cioè
y

2
 y = −λ
x = − λ1

xy = 1.
√
Sostituendo le prime due nella terza si ottiene λ22 = 1, da cui λ = ± 2. Soltanto il
√
valore positivo è accettabile e quindi si ha λ = 2, da cui poi si ricavano x = − √12 e
√
√
y = − 2. Pertanto l’unico punto che soddisfa le condizioni necessarie è (− √12 , − 2)
√
con moltiplicatore λ = 2. La figura illustra la situazione e conferma che abbiamo
trovato l’unico punto di massimo (locale)
vincolato. Si noti che non abbiamo trovato
√
come soluzione anche il punto ( √12 , 2), che infatti è un punto di minimo vincolato.
min
b
b
x
max
∇f
Esempio
max f (x, y) = xy
con vincolo y 2 − x ≤ 0.
La funzione Lagrangiana è
L(x, y, λ) = xy − λ(y 2 − x).
6 Occorrerà poi risolvere tale sistema di condizioni, trovare cioè tutte le terne (x, y, λ) che soddisfano le condizioni contemporaneamente.
Ricordo che queste soluzioni forniscono soltanto punti che sono candidati ad essere di massimo vincolato, dato che le condizioni sono
necessarie. Chiaramente, in mancanza di condizioni sufficienti, per arrivare a dire se il punto è effettivamente di massimo vincolato
occorrono o considerazioni geometriche (curve di livello) oppure considerazioni basate sulla variazione della funzione obiettivo in prossimità
del presunto punto di massimo. A volte succede che una conclusione definitiva si può trarre anche senza considerazioni geometriche. Ad
esempio, se la regione ammissibile è un insieme chiuso e limitato, la continuità di f permette di dire (teorema di Weierstrass) che c’è almeno
un punto di massimo vincolato. Ora, se le condizioni di ottimalità forniscono una sola soluzione, essa è certamente il punto di massimo
globale vincolato. Più avanti c’è un esempio in cui succede questo.
5
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
Le condizioni di ottimalità sono:

y+λ=0



x − 2λy = 0

y2 − x ≤ 0 ∧


λ ≥ 0.
λ(y 2 − x) = 0
Consideriamo i due casi possibili: λ = 0 oppure λ > 0. Se λ = 0 si trova subito la
soluzione nulla, cioè (0, 0) con λ = 0.
Se invece λ > 0 (allora il vincolo deve essere attivo) le condizioni diventano

 y+λ=0
x − 2λy = 0
 2
y −x=0
cioè

 y = −λ
x = 2λy
 2
y −x=0
cioè ancora

 y = −λ
x = −2λ2
 2
y − x = 0.
y
b
x
Sostituendo le prime due nella terza si ha l’equazione λ2 + 2λ2 = 0, cioè 3λ2 = 0, che
è evidentemente impossibile dato che λ > 0. Quindi il caso λ > 0 non fornisce altre
soluzioni. Nella figura a fianco possiamo vedere la situazione.
L’esempio è interessante in quanto il punto trovato, soluzione delle condizioni necessarie di ottimalità, non è in
realtà punto di massimo vincolato. Lo si capisce facilmente considerando che la funzione obiettivo f (x, y) = xy cambia
segno in un intorno dell’origine.7 Questo è una conferma che le condizioni sono in effetti necessarie ma non sufficienti
per dire che un punto è di massimo vincolato.
Esempio
con vincolo x2 + y 2 + z 2 ≤ 14.
√
Il vincolo definisce una sfera di centro l’origine e raggio 14. Le superfici di livello di f sono piani e quindi si intuisce
che il punto di massimo sulla sfera è su un punto di tangenza di tali piani con la sfera.
La funzione Lagrangiana è
L(x, y, λ) = x + 2y + 3z − λ(x2 + y 2 + z 2 − 14).
max f (x, y) = x + 2y + 3z
Le condizioni di ottimalità sono:


1 − 2λx = 0




 2 − 2λy = 0
3 − 2λx = 0



x2 + y 2 + z 2 ≤ 14



λ ≥ 0.
∧
λ(x2 + y 2 + z 2 − 14) = 0
Distinguiamo come sempre i due casi possibili: λ = 0 oppure λ > 0. Se λ = 0 si trova subito che non c’è soluzione. Se
invece λ > 0 (il vincolo è allora attivo) le condizioni diventano


1
1 − 2λx = 0
x = 2λ






1
2 − 2λy = 0
y=λ
cioè
3


3
−
2λx
=
0
z = 2λ


 2

x2 + y 2 + z 2 = 14.
x + y 2 + z 2 = 14
Sostituendo le prime tre nella quarta si ha l’equazione 4λ1 2 + λ12 + 4λ9 2 = 14, cioè 4λ1 2 = 1, che fornisce l’unica soluzione
positiva λ = 12 . Si trova in corrispondenza l’unica soluzione (1, 2, 3). Qui possiamo dire che, per il teorema di
Weierstrass, è il punto di massimo (globale) vincolato. Si noti che non troviamo il punto di minimo globale vincolato
(che certamente esiste): le condizioni imposte sono in effetti quelle per un punto di massimo.
3
Caso generale
Consideriamo ora un problema di massimo vincolato con vincoli di disuguaglianza nella forma generale, con la presenza
quindi di più vincoli. Sia come sempre A un insieme aperto in Rn .
Teorema Siano f : A → R e g : A → Rm funzioni di classe C 1 nell’aperto A. Dato il problema
max f (x) con vincoli g(x) ≤ b,
7 Essa
è positiva nei punti della regione ammissibile che stanno nel primo quadrante e negativa nei punti del secondo quadrante.
6
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
e definita la funzione Lagrangiana L(x, λ) = f (x) − λ · g(x) − b , dove λ ∈ Rm , se x è punto di massimo locale
vincolato di f e se i gradienti dei vincoli attivi in x sono linearmente indipendenti, allora esiste un λ ∈ Rm tale che
valgano contemporaneamente le seguenti condizioni:
(i) ∇x L(x, λ) = 0
(ii) ∇λ L(x, λ) ≥ 0
∧
λ · ∇λ L(x, λ) = 0
(iii) λ ≥ 0.
Osservazioni Come nel caso del problema con equazioni, quando sono presenti più vincoli vi sono sempre tanti
moltiplicatori quanti sono i vincoli (λ è un vettore). Le condizioni (i) sono in realtà n condizioni di uguaglianza (una
per ogni variabile). Le condizioni (ii) comprendono m condizioni di disuguaglianza e una di uguaglianza (prodotto
interno di due vettori uguale a zero); segnalo però che da un punto di vista operativo conviene di solito scrivere questa,
anziché come un’unica equazione con m moltiplicatori, come m equazioni di complementarità, una per ogni vincolo
(quindi ogni disequazione di vincolo va abbinata alla sua condizione di complementarità).
Osservazioni Per quanto riguarda la condizione di regolarità dei vincoli è da notare, come già segnalato in precedenza, che sono soltanto i vincoli attivi in x ad essere importanti da questo punto di vista. La condizione di indipendenza
dei gradienti dei vincoli attivi può essere formulata anche dicendo che, detta Jg(x) la matrice Jacobiana dei vincoli
e detta Jga (x) la sottomatrice formata con le sole, diciamo k, righe dei “gradienti attivi”, tale sottomatrice Jga (x)
abbia rango k.
Vediamo ora qualche esempio.
Esempio
max f (x, y) = x − y
con vincoli
x+y ≤ 1
y ≥ 0.
con vincoli
x+y ≤ 1
−y ≤ 0.
Scriviamo anzitutto il problema in forma standard:
max f (x, y) = x − y
È bene esaminare sempre la regolarità dei vincoli. La matrice Jacobiana dei vincoli è
1 1
.
Jg =
0 −1
Qui occorre riflettere un po’. Se esaminassimo la regolarità dei vincoli dopo aver studiato le condizioni di ottimalità
rischieremmo di perdere qualche soluzione. Infatti sono le condizioni di regolarità che garantiscono che nei punti di
massimo le condizioni siano verificate. Quindi occorre studiare la regolarità prima di trovare i punti, senza cioè sapere
in quali punti siamo interessati alla regolarità dei vincoli. Ricordando che regolarità vuol dire che i gradienti dei vincoli
attivi sono indipendenti, nel nostro attuale esempio questo significa che se è attivo il primo vincolo il primo gradiente
deve essere non nullo, se è attivo il secondo vincolo il secondo gradiente deve essere non nullo e se sono attivi entrambi
i vincoli i due gradienti devono essere indipendenti. Qui è immediato, dato che basta osservare che le due righe sono
sempre indipendenti. In altri casi può non essere banale la verifica della regolarità.
La funzione Lagrangiana è
y
L(x, y, λ) = x − y − λ1 (x + y − 1) − λ2 (−y).
Le condizioni di ottimalità sono:


1 − λ1 = 0




 −1 − λ1 + λ2 = 0
x + y ≤ 1 ∧ λ1 (x + y − 1) = 0



y
 ≥ 0 ∧ λ2 y = 0


λ1 , λ2 ≥ 0.
x
b
1
∇f
Si trova immediatamente dalle prime due equazioni λ1 = 1, λ2 = 2 e di conseguenza i vincoli sono entrambi attivi,
cioè y = 0 (dalla complementarità sul secondo vincolo) e quindi x = 1 dalla terza condizione. Si trova come unica
soluzione il punto (1, 0). Da uno studio grafico delle curve di livello si vede che è punto di massimo globale vincolato.
7
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
Esempio
max f (x, y) = y 2 − x
y≤x
x ≤ 1.
con vincoli
Scriviamo anzitutto il problema in forma standard:
max f (x, y) = y 2 − x
con vincoli
−x + y ≤ 0
x ≤ 1.
Esaminiamo la regolarità dei vincoli. La matrice Jacobiana dei vincoli è
−1 1
Jg =
1 0
e come prima basta osservare che le righe sono sempre indipendenti.
La funzione Lagrangiana è
L(x, y, λ) = y 2 − x − λ1 (−x + y) − λ2 (x − 1).
Le condizioni di ottimalità sono:


−1 + λ1 − λ2 = 0




 2y − λ1 = 0
y ≤ x ∧ λ1 (y − x) = 0



x ≤ 1 ∧ λ2 (x − 1) = 0



λ1 , λ2 ≥ 0.
Lo studente ha già visto negli esempi precedenti che non ci sono metodi generali per la risoluzione di questo tipo di
sistemi. Si tratta in genere di “percorrere tutte le strade possibili”. Qui possiamo procedere cosı̀:
• se λ1 = 0, dalla prima si troverebbe λ2 = −1, che non è accettabile. Quindi λ1 non può annullarsi. Quindi
(condizione di complementarità del primo vincolo) il primo vincolo deve essere attivo. Le condizioni possono
allora essere riscritte come

∇f

λ2 = λ1 − 1

y



 2y = λ1
y=x


 x ≤ 1 ∧ λ2 (x − 1) = 0


 λ > 0, λ ≥ 0.
1
2
b
• Se λ2 = 0 si ricava immediatamente λ1 = 1 e x = y = 21 , che è una soluzione.
1
x
• Se invece λ2 > 0 per la complementarità del secondo vincolo deve essere x = 1 e si
ricava immediatamente x = y = 1, λ1 = 2 e λ2 = 1, che è un’altra possibile soluzione.
Allora ci sono due punti candidati per un massimo vincolato: ( 12 , 12 ) e (1, 1), con i rispettivi moltiplicatori trovati
poco fa. Uno studio grafico con le curve di livello porta facilmente a dire che (1, 1) è in effetti di massimo (locale, non
globale) vincolato, mentre ( 12 , 21 ) non è né di massimo né di minimo vincolato.
Esempio
max f (x, y) = y − x con vincoli
x−y ≤ 1
x≥0
y ≤ 3.
Il problema scritto in forma standard è
max f (x, y) = y − x con vincoli
x−y ≤ 1
−x ≤ 0
y ≤ 3.
La matrice Jacobiana dei vincoli è

1
Jg =  −1
0

−1
0 
1
e i vincoli sono regolari.8
8
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
La Lagrangiana è
L(x, y, z, λ, µ) = y − x − λ1 (x − y − 1) − λ2 (−x) − λ3 (y − 3).
Le condizioni di ottimalità sono:

−1 − λ1 + λ2 = 0





1
+ λ1 − λ3 = 0



x − y ≤ 1 ∧ λ1 (x − y − 1) = 0

x ≥ 0 ∧ λ2 x = 0




y ≤ 3 ∧ λ3 (y − 3) = 0



λ1 , λ2 , λ3 ≥ 0.
Dalle prime due equazioni si vede subito che non può essere λ2 = 0 oppure λ3 = 0 (se
λ2 = 0 la prima è impossibile e se λ3 = 0 è impossibile la seconda). Allora il secondo
e il terzo vincolo devono essere attivi e cioè x = 0 e y = 3. Attenzione che, anche se
abbiamo trovato un punto, occorre sempre verificare che si ottenga una soluzione del
sistema. Con i valori trovati il primo vincolo non è attivo e quindi deve annullarsi
il primo moltiplicatore (λ1 = 0) e dalle prime due equazioni si trova λ2 = λ3 = 1.
Quindi c’è una soluzione alle condizioni di ottimalità, che individua il punto (0, 3).
Da un esame delle curve di livello si vede che è punto di massimo globale vincolato.
y
∇f
b
3
−1
4
x
Esempio
max f (x, y) = y
con vincoli
(x − 1)2 + (y − 1)2 ≤ 1
y − x ≤ 0.
Il problema è già in forma standard. La matrice Jacobiana dei vincoli è
2(x − 1) 2(y − 1)
Jg =
−1
1
e possiamo notare che in ogni caso c’è regolarità poiché nei punti in cui sono attivi entrambi i vincoli il determinante
della matrice non si annulla (lo si verifichi per esercizio).
La funzione Lagrangiana è
L(x, y, λ) = y − λ1 (x − 1)2 + (y − 1)2 − 1 − λ2 (y − x).
Le condizioni di ottimalità sono:


−2λ1 (x − 1) + λ2 = 0




 1 − 2λ1 (y − 1) − λ2 = 0
(x − 1)2 + (y − 1)2 ≤ 1 ∧



y ≤ x ∧ λ2 (y − x) = 0



λ1 , λ2 ≥ 0.
λ1 [(x − 1)2 + (y − 1)2 − 1] = 0
Per risolvere il sistema di condizioni possiamo procedere nel modo seguente:
• se λ1 = 0, allora dalla prima segue λ2 = 0 e la seconda è impossibile. Quindi non si hanno soluzioni se λ1 = 0 e
il primo vincolo deve essere attivo.
• Possiamo allora riscrivere le condizioni come


−2λ1 (x − 1) + λ2 = 0




 1 − 2λ1 (y − 1) − λ2 = 0
(x − 1)2 + (y − 1)2 = 1



y ≤ x ∧ λ2 (y − x) = 0



λ1 > 0, λ2 ≥ 0.
Ora ragioniamo sul secondo moltiplicatore. Se λ2 = 0 la prima diventa 2λ1 (x − 1) = 0, da cui deve essere x = 1
e dalla terza vi sono le possibilità y = 0 oppure y = 2. Nessuna delle due è accettabile in quanto y = 0 porta
8 È
importante osservare (vedi figura) che non ci sono punti ammissibili in cui tutti e tre i vincoli sono attivi. Per il resto è evidente
che nella Jacobiana i minori del secondo ordine sono diversi da zero e quindi in tutti i punti in cui due vincoli sono attivi i due gradienti
corrispondenti sono indipendenti.
9
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
(seconda condizione) ad un valore negativo di λ1 e y = 2 non soddisfa il secondo vincolo. Quindi anche il secondo
moltiplicatore deve essere positivo ed entrambi i vincoli allora sono attivi. Le condizioni diventano


 −2λ1 (x − 1) + λ2 = 0



y
∇f
 1 − 2λ1 (y − 1) − λ2 = 0
2
2
(x − 1) + (y − 1) = 1
√


1+1/ 2
 y=x



λ1 , λ2 > 0.
1
|
b
• Considerando il sistema dei due vincoli
(x − 1)2 + (y − 1)2 = 1
y=x
|
√
1 1+1/ 2
x
e sostituendo la seconda nella prima si ottiene
2(x − 1)2 = 1
cioè (x − 1)2 =
1
cioè x − 1 = ± √
2
1
2
1
cioè x = 1 ± √ .
2
Il valore x = 1 − √12 non è accettabile in quanto non rende possibile la prima equazione. Il valore x = 1 + √12
è accettabile (le prime due equazioni portano a valori positivi dei moltiplicatori). Il sistema delle condizioni
necessarie ha quindi l’unica soluzione 1 +
√1 , 1
2
+
√1
2
.
Uno studio grafico con le curve di livello porta a dire che si tratta del punto di massimo globale vincolato.
4
Il problema con vincoli di non negatività
Nei problemi di ottimizzazione di natura reale sono quasi sempre presenti dei vincoli, “speciali” per molti aspetti:
i cosiddetti vincoli di non negatività. Le variabili del problema devono cioè essere non negative.9 Quindi un caso
estremamente importante di un problema di programmazione è quello con vincoli di non negatività e si sono cercate
condizioni di ottimalità per questo particolare tipo di problemi.10
4.1
Le condizioni di Kuhn–Tucker
Le condizioni di ottimalità per un problema con vincoli di disequazione, tra i quali siano presenti i vincoli di non
negatività, sono note come le condizioni di Kuhn–Tucker e risalgono agli anni ’50.
Teorema Siano f : A → R e g : A → Rm funzioni di classe C 1 nell’aperto A. Dato il problema (con vincoli di non
negatività)
g(x) ≤ b
max f (x) con vincoli
x≥0
e definita la funzione Lagrangiana L(x, λ) = f (x) − λ · g(x) − b , dove λ ∈ Rm , se x è punto di massimo locale
vincolato di f e se i gradienti dei vincoli attivi in x sono linearmente indipendenti, allora esiste un λ ∈ Rm tale che
valgano contemporaneamente le seguenti condizioni:
(i) ∇x L(x, λ) ≤ 0
∧
x · ∇x L(x, λ) = 0
(ii) ∇λ L(x, λ) ≥ 0
∧
λ · ∇λ L(x, λ) = 0
(iii) x, λ ≥ 0.
Osservazione Anzitutto si osservi che, nonostante la presenza dei vincoli di non negatività, la funzione Lagrangiana
viene definita senza tener conto di tali vincoli (ed è quindi la stessa che avremmo se i vincoli di non negatività non ci
9 È ovvia la motivazione: nei problemi reali le variabili indicano quantità reali (quantità di una data risorsa, quantità di energia necessaria
per far funzionare le apparecchiature, quantità di denaro . . . ). Non avrebbe senso impostare un problema senza tener conto del fatto che
non sono certamente accettabili soluzioni che indicano quantità negative.
10 Va fatto notare però esplicitamente che il problema con vincoli di non negatività è un caso particolare di quello generale con vincoli di
disequazione e infatti siamo già in grado di risolvere un caso con vincoli di non negatività. Ad esempio se tra i vincoli ci sono anche x ≥ 0
e y ≥ 0, come già fatto in qualche esempio, possiamo scrivere tali vincoli in forma standard (−x ≤ 0 e −y ≤ 0) e impostare le condizioni
di ottimalità con questi vincoli.
10
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
fossero). La condizione di regolarità dei vincoli prevede che i gradienti dei vincoli attivi siano linearmente indipendenti
e occorre considerare sia i vincoli tradizionali sia quelli di non negatività.
Osservazione Per quanto riguarda le condizioni di KT, la novità rispetto a quelle senza vincoli di non negatività è
che la prima condizione (che era ∇x L(x, λ) = 0) diventa ora una condizione con disuguaglianza abbinata ad una nuova
condizione di complementarità, che può essere sostituita come l’altra da n condizioni del tipo xi L′i = 0, una per ogni
variabile. Le altre condizioni sono identiche alle precedenti, con l’ovvia condizione aggiuntiva della non negatività del
vettore x.
Osservazione Si potrebbe arrivare a giustificare le condizioni di KT o ricavandole dalle condizioni generali, dopo aver
scritto il problema in forma standard (vedi esempio più avanti) oppure anche riflettendo su alcuni aspetti geometrici,
ma tralascio la questione.
Vediamo qualche esempio di problema con vincoli di non negatività.
y
Esempio
max f (x, y) = x2 + y 2
con vincoli
x+y ≤1
x, y ≥ 0.
Si tratta di un problema in forma standard con vincoli di non negatività. Lo studio
grafico porta a dire facilmente che ci sono due punti di massimo (globale) vincolato:
(1, 0) oppure (0, 1). La matrice Jacobiana dei vincoli è11

1

Jg =
−1
0

1
0 
−1
e possiamo notare che in ogni caso c’è regolarità perché al
più sono attivi due vincoli su tre. Ad esempio in (0, 1) sono
attivi il vincolo obliquo e il primo vincolo di non negatività
e il primo minore della matrice è non nullo.
b
∇f
1
b
1
∇f
x
Possiamo scrivere la funzione Lagrangiana
L(x, y, λ) = x2 + y 2 − λ(x + y − 1).
Le condizioni di KT sono:

2x − λ ≤ 0 ∧ x(2x − λ) = 0


 2y − λ ≤ 0 ∧ y(2y − λ) = 0

x + y ≤ 1 ∧ λ(x + y − 1) = 0


x, y, λ ≥ 0.
Possiamo procedere come sempre distinguendo i casi possibili.
• Se λ = 0, le condizioni diventano

2x ≤ 0 ∧



2y ≤ 0 ∧

x+y ≤1


x, y ≥ 0
2x2 = 0
2y 2 = 0
e si ottiene la soluzione x = y = 0, con λ = 0.
• Se λ > 0 il vincolo è attivo e le condizioni diventano

2x − λ ≤ 0 ∧



2y − λ ≤ 0 ∧

x+y =1


x, y ≥ 0, λ > 0.
x(2x − λ) = 0
y(2y − λ) = 0
Ora, se x, y sono entrambi non nulli, dalla complementarità sulle variabili si trova che 2x = 2y = λ e da queste
si ottiene λ = 1 e x = y = 21 .
Se invece x = 0 si ottiene immediatamente y = 1 e λ = 2 e infine se y = 0, si ha x = 1 e ancora λ = 2.
11 Volendo
si potrebbe evitare di riscrivere i vincoli di non negatività in forma standard, dato che i gradienti di questi vincoli sono
comunque proporzionali ai vettori fondamentali.
11
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
In definitiva le possibili soluzioni delle condizioni di KT sono i punti (0, 0), ( 21 , 12 ), (1, 0) e (0, 1).
Tornando all’esame grafico si vede che i primi due punti non sono di massimo, gli altri due sı̀. Dalla figura è chiaro
che il punto ( 12 , 12 ), pur non essendo di massimo vincolato, soddisfa le condizioni necessarie in quanto in tale punto il
gradiente di f è proporzionale al gradiente del vincolo attivo, che è soltanto quello obliquo.
Esempio
max f (x, y) = y − 2x con vincoli
x2 + y 2 ≤ 1
x, y ≥ 0.
Si tratta di un problema in forma standard con vincoli di non negatività. Lo studio
grafico porta a dire facilmente si ha punto di massimo (globale) vincolato in (0, 1).
La matrice Jacobiana dei vincoli è
2x

Jg =
−1
0


2y
0 
−1
e possiamo notare che in ogni caso c’è regolarità perché al
più sono attivi due vincoli su tre. Ad esempio in (0, 1) sono
attivi il vincolo curvo e il primo vincolo di non negatività e
il primo minore della matrice è non nullo.
y
∇f
b
1
1
x
La funzione Lagrangiana è
L(x, y, λ) = y − 2x − λ(x2 + y 2 − 1).
Le condizioni di KT sono:

−2 − 2λx ≤ 0 ∧ x(−2 − 2λx) = 0



1 − 2λy ≤ 0 ∧ y(1 − 2λy) = 0
 x2 + y 2 ≤ 1 ∧ λ(x2 + y 2 − 1) = 0


x, y, λ ≥ 0.
Se λ = 0 la seconda condizione non può essere verificata. Quindi deve essere λ > 0 e il vincolo è attivo. Poi
consideriamo la prima condizione di complementarità sulla variabile x: certamente la quantità tra parentesi è negativa
e quindi deve essere x = 0. Dal fatto che il vincolo è attivo risulta y 2 = 1 e quindi y = 1 (la soluzione negativa non è
qui accettabile). Infine dalla condizione di complementarità sulla variabile y segue che 1 − 2λ = 0 e quindi λ = 12 .
Pertanto il sistema ha la sola soluzione (0, 1), che in effetti è punto di massimo globale vincolato.
Esempio
con vincoli
xy ≤ 1
x, y ≥ 0.
Si tratta di un problema in forma standard con vincoli di non negatività. Lo studio
grafico porta a dire che non ci sono punti di massimo vincolato.
La matrice Jacobiana dei vincoli è


y
x
e possiamo vedere che c’è regolarità in
Jg =  −1 0 
tutti i punti della regione ammissibile.
0 −1
y
∇f
1
|
max f (x, y) = x + y
b
|
1
x
La funzione Lagrangiana è
L(x, y, λ) = x + y − λ(xy − 1).
Le condizioni di KT sono:

1 − λy ≤ 0



1 − λx ≤ 0
 xy ≤ 1 ∧


x, y, λ ≥ 0.
∧ x(1 − λy) = 0
∧ y(1 − λx) = 0
λ(xy − 1) = 0
Se λ = 0 la prima condizione non può essere verificata. Quindi deve essere λ > 0 e il vincolo è attivo. Dato che né x
né y possono essere nulle, dalla complementarità sulle variabili segue che le condizioni si possono riscrivere come

λy = 1



λx = 1

xy = 1


x, y, λ > 0.
12
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
Ricavando x = y = λ1 e sostituendo nel vincolo si ottiene λ2 = 1 e quindi λ = 1, da cui anche x = y = 1.
Unica soluzione delle condizioni di KT è il punto (1, 1), che però non è punto di massimo vincolato. Nella figura
sopra si vede il motivo: in questo punto i gradienti di f e dell’unico vincolo attivo sono proporzionali.
Esempio
max f (x, y) = 3x + 2y + z
con vincoli
x + 2y + 3z ≤ 6
x, y, z ≥ 0.
Si tratta di un problema in forma standard con vincoli di non negatività e si vede subito che i vincoli sono regolari.
La funzione Lagrangiana è
L(x, y, λ) = 3x + 2y + z − λ(x + 2y + 3z − 6).
Le condizioni di KT sono:


3 − λ ≤ 0 ∧ x(3 − λ) = 0




2
 − 2λ ≤ 0 ∧ y(2 − 2λ) = 0
1 − 3λ ≤ 0 ∧ z(1 − 3λ) = 0



x
+ 2y + 3z ≤ 6 ∧ λ(x + 2y + 3z − 6) = 0



x, y, z, λ ≥ 0.
Dalla prima condizione (λ ≥ 3) segue che il vincolo è attivo. Sempre dalla prima segue che la seconda e la terza
disuguaglianza sono verificate in senso stretto (2 − 2λ < 0 e 1 − 3λ < 0) e che quindi (complementarità su y e z) deve
necessariamente essere y = z = 0. Essendo il vincolo attivo, sarà allora x = 6 e l’unica soluzione è il punto (6, 0, 0),
con moltiplicatore λ = 3.
Concludo questa sezione con un ultimo esempio, esempio che fu fornito dagli stessi Kuhn e Tucker e che prova che,
in mancanza di regolarità dei vincoli, le condizioni necessarie per un punto di massimo possono essere violate.
Esempio
max f (x, y) = x
con vincoli
(x − 1)3 + y ≤ 0
x, y ≥ 0.
Dalla figura qui a fianco si vede facilmente che (1, 0) è punto di massimo (globale)
vincolato. Se scriviamo la funzione Lagrangiana
L(x, y, λ) = x − λ (x − 1)3 + y
y
1
∇g1
e quindi le condizioni di KT sono
∇f
b
1

1 − 3λ(x − 1)2 ≤ 0 ∧ x(1 − 3λ(x − 1)2 ) = 0



−λ ≤ 0 ∧ yλ = 0
 (x − 1)3 + y ≤ 0 ∧ λ((x − 1)3 + y) = 0


x, y, λ ≥ 0.
x
∇g2
È immediato constatare che nel punto di massimo (1, 0) le condizioni non sono rispettate (la prima disuguaglianza
non è verificata). Il motivo sta nel fatto che i vincoli non sono regolari: infatti i vincoli attivi sono il vincolo “normale”
((x − 1)3 + y = 0) e uno dei due vincoli di non negatività (y = 0), i cui gradienti nel punto (1, 0) sono
∇g1 = (0, 1)
e
∇g3 = (0, −1),
che sono chiaramente dipendenti.
4.2
Problemi “misti”
Come ultimo argomento vediamo come si può affrontare un problema con vincoli di tipo misto, e la cosa può essere
intesa nel senso di vincoli equazioni/disequazioni o anche con vincoli di non negatività ma non su tutte le variabili.
Andando a riflettere su come sono cambiate le condizioni di ottimalità nei vari casi esaminati in precedenza non è
difficile intuire quali siano le condizioni da imporre in un problema misto.
Senza voler dare un enunciato generale, che sarebbe piuttosto pesante per la difficoltà di esprimere formalmente la
presenza di vari tipi di vincoli, vediamo come si opera con qualche semplice esempio.
Esempio (non negatività di alcune variabili)
13
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
Riconsideriamo l’esempio già visto in precedenza
max f (x, y) = x − y
con vincoli
x+y ≤ 1
y ≥ 0.
Prima lo avevamo risolto scrivendo il problema in forma standard e trattando il vincolo −y ≤ 0 come un qualsiasi
altro vincolo (quindi inserendolo nella Lagrangiana). Essendo però un vincolo di non negatività, lo possiamo anche
tralasciare nella Lagrangiana e tenere conto della sua presenza nelle condizioni di ottimalità. Scriviamo quindi la
funzione Lagrangiana
y
L(x, y, λ) = x − y − λ(x + y − 1)
e le condizioni “alla KT”

1−λ=0



−1 − λ ≤ 0 ∧ y(−1 − λ) = 0

x + y ≤ 1 ∧ λ(x + y − 1) = 0


y, λ ≥ 0.
x
b
1
∇f
A commento osservo:
• la prima condizione è di equazione dato che x non è vincolata in segno;
• la seconda invece è di disequazione (y è vincolata in segno) e viene affiancata da una condizione di complementarità sulla y;
• la terza condizione è una condizione classica di vincolo con disequazione (quindi affiancata da una complementarità su λ);
• la quarta è la non negatività della y e del moltiplicatore.
Risolviamo il sistema di condizioni. Dalla prima si ha λ = 1; dalla complementarità su y segue y = 0; dato che il
vincolo è attivo (complementarità sul vincolo poiché λ = 1) si ha infine x = 1. Unica soluzione è quindi il punto (1, 0)
con moltiplicatore λ = 1.
Esempio (vincoli equazione/disequazione)
max f (x, y) = x con vincoli
x2 + y 2 = 2
x + y ≤ 0.
I vincoli sono di tipo misto, essendoci un’equazione e una disequazione. La funzione Lagrangiana è quella che avremmo
con due equazioni (o due disequazioni):
y
√
2
2
Le condizioni di ottimalità sono:


 1 − 2λ1 x − λ2 = 0



 −2λ1 y − λ2 = 0
x2 + y 2 = 2


 x + y ≤ 0 ∧ λ2 (x + y) = 0



λ2 ≥ 0.
|
L(x, y, λ) = x − λ1 (x + y − 2) − λ2 (x + y).
1
1
√
− 2
|
|
−1
−1
|
2
b
√
2
x
∇f
A commento:
• le prime due condizioni sono di equazione dato che le variabili non sono vincolate in segno;
• la terza condizione è il rispetto del vincolo di equazione (e non c’è complementarità perché il vincolo è di
equazione);
• la quarta condizione è il rispetto del vincolo di disequazione, abbinato alla complementarità con il moltiplicatore
del secondo vincolo, cioè λ2 ;
14
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
• la quinta è la non negatività del moltiplicatore λ2 (il primo moltiplicatore è libero, dato che il primo vincolo è
di equazione).
Per risolvere il sistema di condizioni possiamo distinguere i due casi possibili su λ2 .
Se λ2 = 0 le condizioni diventano

1 − 2λ1 x = 0



−2λ1 y = 0

x2 + y 2 = 2


x + y ≤ 0.
Dalla seconda, λ1 = 0 non
√
à porta a soluzioni (la prima nonÏ verificata); allora deve essere y = 0, da cui (per la terza)
x2 = 2 e quindi x = ± 2. La soluzione positiva (x = 2) non è accettabile (la quarta è falsa): con x = − 2 si
ottiene invece una soluzione accettabile (e si trova λ1 = − 41 ). Quindi una soluzione del sistema di condizioni è il punto
√
(− 2, 0) con λ1 = − 41 e λ2 = 0.
Dobbiamo ora studiare il caso λ2 > 0, che permette di riscrivere le condizioni come


1 − 2λ1 x − λ2 = 0




 −2λ1 y − λ2 = 0
x2 + y 2 = 2



x+y =0



λ2 > 0.
Si noti che il vincolo di disequazione deve essere ora attivo. Si può ricavare quindi y = −x, da cui (per l’altro vincolo)
2x2 = 2, cioè x2 = 1, cioè x = ±1.
Con x = 1 allora y = −1 e rimane il sistema delle prime due equazioni
1
1
1 − 2λ1 x − λ2 = 0
che porta a λ1 = , λ2 = .
−2λ1 y − λ2 = 0
4
2
Quindi abbiamo il punto (1, −1) con λ1 = 14 e λ2 = 12 .
Con x = −1 allora y = 1 e il sistema delle prime due equazioni è ora
1
1
1 + 2λ1 x − λ2 = 0
che porta a λ1 = − , λ2 = .
−2λ1 y − λ2 = 0
4
2
Quindi abbiamo anche il punto (−1, 1) con λ1 = − 14 e λ2 = 12 .
Concludendo ci sono tre punti che soddisfano le condizioni di ottimalità. Con le curve di livello si trova che soltanto
il punto (1, −1) è di massimo (globale) vincolato.
y
2
Esempio (vincoli equazione/disequazione e un solo vincolo di non negatività)
max f (x, y) = 2x − y
con vincoli
x2 + y = 2
x+y ≥0
x ≥ 0.
2
|
max f (x, y) = 2x − y
con vincoli
x2 + y = 2
−x − y ≤ 0
x ≥ 0.
−2
|
Il problema non è in forma standard. Dobbiamo riscriverlo come
Ora possiamo scrivere la funzione Lagrangiana (senza considerare il vincolo di non negatività)
L(x, y, λ) = 2x − y − λ1 (x2 + y − 2) − λ2 (−x − y).
Le condizioni di ottimalità sono:


2 − 2λ1 x + λ2 ≤ 0 ∧ x(2 − 2λ1 x + λ2 ) = 0




 −1 − λ1 + λ2 = 0
x2 + y = 2


 x + y ≥ 0 ∧ λ2 (x + y) = 0



x, λ2 ≥ 0.
b
x
∇f
15
UNIVR – Facoltà di Economia – Corso di Matematica finanziaria 2008/09
A commento:
• la prima condizione è di disequazione dato che x è vincolata in segno (e a fianco c’è la complementarità su x);
• la seconda condizione è di equazione dato che y non è vincolata in segno;
• la terza condizione è il rispetto del vincolo di equazione;
• la quarta condizione è il rispetto del vincolo di disequazione, abbinato alla complementarità con il moltiplicatore
del secondo vincolo, cioè λ2 ;
• la quinta è la non negatività di x e del moltiplicatore λ2 (λ1 è libero poiché il vincolo corrispondente è di
equazione).
Per risolvere il sistema possiamo distinguere i due casi possibili su λ2 .
Se λ2 = 0 si ha subito dalla seconda λ1 = −1, per cui la complementarità su x diventa x(2 + 2x) = 0, che fornisce
x = 0 oppure x = −1. La seconda non è accettabile e nemmeno la prima dato che la prima disuguaglianza non è
verificata.
Allora deve essere λ2 > 0 e quindi il secondo vincolo è attivo. Riscriviamo le condizioni:


2 − 2λ1 x + λ2 ≤ 0 ∧ x(2 − 2λ1 x + λ2 ) = 0




 −1 − λ1 + λ2 = 0
x2 + y = 2



x+y =0


 x ≥ 0, λ > 0.
2
Dal secondo vincolo si ha y = −x e quindi il primo diventa x2 − x − 2 = 0, che ha per soluzioni x = 2 oppure x = −1.
La seconda non è accettabile. Con x = 2 si ha y = −2 e per la complementarità sulle x le prime due condizioni
diventano equazioni entrambe:

 2 − 2λ1 x + λ2 = 0
che porta a λ1 = 1, λ2 = 2.
−1 − λ1 + λ2 = 0

λ2 > 0
Quindi in conclusione abbiamo soltanto il punto (2, −2) con λ1 = 1 e λ2 = 2. Tale punto risulta in effetti di massimo
globale vincolato, come si vede facilmente con le curve di livello.
5
Problemi di minimo
Concludo rapidamente la dispensa dicendo che, se siamo in presenza di un problema
di minimo anziché di massimo, con qualunque tipo di vincoli, il modo più semplice
per risolverlo è ricondurlo ad un problema di massimo in forma standard, osservando
soltanto che in tutta generalità si ha
min f (x) = − max − f (x) ,
y
f
min f
max(−f )
con gli stessi vincoli (qualunque) per entrambi i problemi. Il punto di minimo della
prima coincide col punto di massimo della seconda.
Pertanto, ad esempio, il problema
min f (x, y) = x + y
con vincoli
x2 + y 2 ≥ 2
x+1≥0
y≥0
si può trasformare nel problema di massimo in forma standard
− max −f (x, y) = −x − y
con vincoli
che può essere affrontato con le condizioni di Kuhn–Tucker.12
12 Il
punto di minimo globale vincolato è x = (−1, 1) con valore ottimo f (x) = 0.
−x2 − y 2 ≤ −2
−x ≤ 1
−y ≤ 0,
x
x
−f