Condizioni sufficienti di ottimalità di Karush-Kuhn

La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Condizioni sufficienti di ottimalità di
Karush-Kuhn-Tucker.
Lezioni del 25 e 30 novembre 2015
Matematica generale. Corso A
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Possiamo scrivere le condizioni di Karush-Kuhn-Tucker tramite la
funzione Lagrangiana.
Consideriamo il problema
max / min f (x, y )
(P) :
gi (x, y ) ≤ 0 i = 1, ..., m
f : R2 → R e gi : R2 → R, i = 1, ..., m funzioni di classe C 1 .
(x 0 , y 0 ) ammissibile per P
I0 l’insieme dei vincoli aderentia (x 0 , y 0 ),
I0 = {i ∈ {1, ..., m} : gi x 0 , y 0 = 0}.
Denotiamo con k la cardinalità dell’insieme I0 .
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Si consideri la funzione Lagrangiana L : R2 × Rk → R
X
L(x, y , λ) = f (x, y ) −
λi gi (x, y )
i∈I0
Se
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Si consideri la funzione Lagrangiana L : R2 × Rk → R
X
L(x, y , λ) = f (x, y ) −
λi gi (x, y )
i∈I0
Se
1
i vettori ∇gi (x 0 , y 0 ), i ∈ I0 sono linearmente indipendenti
2
(x 0 , y 0 ) è punto di massimo (di minimo) relativo per (P),
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Si consideri la funzione Lagrangiana L : R2 × Rk → R
X
L(x, y , λ) = f (x, y ) −
λi gi (x, y )
i∈I0
Se
1
i vettori ∇gi (x 0 , y 0 ), i ∈ I0 sono linearmente indipendenti
2
(x 0 , y 0 ) è punto di massimo (di minimo) relativo per (P),
allora
esiste λ0 = (λ0i )i∈I0 , con λ0i ≥ 0, i ∈ I0 (λ0i ≤ 0, i ∈ I0 ) tale che
(x 0 , y 0 , λ0 ) è punto critico per L, ovvero
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Si consideri la funzione Lagrangiana L : R2 × Rk → R
X
L(x, y , λ) = f (x, y ) −
λi gi (x, y )
i∈I0
Se
1
i vettori ∇gi (x 0 , y 0 ), i ∈ I0 sono linearmente indipendenti
2
(x 0 , y 0 ) è punto di massimo (di minimo) relativo per (P),
allora
esiste λ0 = (λ0i )i∈I0 , con λ0i ≥ 0, i ∈ I0 (λ0i ≤ 0, i ∈ I0 ) tale che
(x 0 , y 0 , λ0 ) è punto critico per L, ovvero
∂L 0 0 0 ∂L 0 0 0 ∂L 0 0 0 x ,y ,λ = 0
x ,y ,λ = 0
x , y , λ = 0 i ∈ I0
∂x
∂y
∂λi
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esempio
Si consideri il problema

max / min f (x, y ) = log(x) + log(y )



x ≥1
(P) :
y ≥1



3x + 2y ≤ 60
a) Determinare i punti di massimo e minimo assoluto per il
problema P.
b) Relativamente al punto di massimo trovato in a), verificare che
esiste un opportuno λ ≥ 0 per il quale (10, 15, λ) è un punto
critico per la funzione lagrangiana associata.
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esempio (...segue)
a) Si lascia lo svolgimento di questo punto agli studenti. (10,15) è
p.to di max assoluto e (1, 1) è p.to di min. assoluto.
b) Il punto (10, 15) è aderente al vincolo 3x + 2y ≤ 60. La
funzione Lagrangiana è
L(x, y , λ) = log(x) + log(y ) − λ(3x + 2y − 60)
le cui derivate parziali sono
∂L
(x, y , λ) =
∂x
∂L
(x, y , λ) =
∂y
1
− 3λ
x
1
− 2λ
y
∂L
(x, y , λ) = −3x − 2y + 60
∂λ
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esempio (...segue)
Dobbiamo stabilire se esiste λ tale che (10, 15, λ) è un punto
critico per L, ovvero soluzione del sistema
 1
 x − 3λ = 0
1
− 2λ = 0
 y
−3x − 2y + 60 = 0
1
Il sistema ha soluzione per (10, 15, 30
) che risulta quindi essere un
punto critico della Lagrangiana.
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Dalle lezioni precedenti.
Caratterizzazione del I ordine delle funzioni concave e convesse
Sia f : A → R, A ⊆ R2 insieme aperto e convesso, f di classe C 1 .
i) f è convessa se e solo se vale la seguente condizione
0
0 0
0 0 T x −x
f (x, y ) ≥ f (x , y )+∇f (x , y )
, ∀(x, y ), ∀(x 0 , y 0 ) ∈ A.
y − y0
ii) f è concava se e solo se vale la seguente condizione
0
0 0
0 0 T x −x
f (x, y ) ≤ f (x , y )+∇f (x , y )
, ∀(x, y ), ∀(x 0 , y 0 ) ∈ A.
y − y0
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Teorema (Convessità e punti critici)
Sia f : A → R, A ⊆ R2 , A aperto e convesso, f di classe C 1 .
i) Se f è convessa e (x 0 , y 0 ) ∈ A è punto critico per f , allora
(x 0 , y 0 ) è punto di minimo assoluto per f su A
ii) Se f è concava e (x 0 , y 0 ) ∈ A è punto critico per f , allora
(x 0 , y 0 ) è punto di massimo assoluto per f su A.
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Teorema
Sia f : A → R, A ⊆ R2 , A aperto, f di classe C 1 . Sia X un
sottoinsieme convesso di A.
i) Se f è convessa, allora l’insieme dei punti di minimi è convesso.
ii) Se f è concava, allora l’insieme dei punti di massimo è
convesso.
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Teorema
Sia f : A → R, A ⊆ R2 , A aperto, f di classe C 1 . Sia X un
sottoinsieme convesso di A.
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Teorema
Sia f : A → R, A ⊆ R2 , A aperto, f di classe C 1 . Sia X un
sottoinsieme convesso di A.
i) Se f è convessa su X e (x 0 , y 0 ) ∈ X è punto di minimo relativo
per f su X , allora (x 0 , y 0 ) è punto di minimo assoluto di f su X .
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Teorema
Sia f : A → R, A ⊆ R2 , A aperto, f di classe C 1 . Sia X un
sottoinsieme convesso di A.
i) Se f è convessa su X e (x 0 , y 0 ) ∈ X è punto di minimo relativo
per f su X , allora (x 0 , y 0 ) è punto di minimo assoluto di f su X .
ii) Se f è concava su X e (x 0 , y 0 ) ∈ X è punto di massimo relativo
per f su X , allora (x 0 , y 0 ) è punto di massimo assoluto di f su X .
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Dimostrazione.
i) Se (x 0 , y 0 ) è punto interno di X , allora per la condizione
necessaria di ottimalità del I ordine ∇f (x 0 , y 0 ) = 0 e la tesi segue
dalla i) del Teorema “Convessità e punti critici” .
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Dimostrazione.
i) Se (x 0 , y 0 ) è punto interno di X , allora per la condizione
necessaria di ottimalità del I ordine ∇f (x 0 , y 0 ) = 0 e la tesi segue
dalla i) del Teorema “Convessità e punti critici” .
Se (x 0 , y 0 ) è punto di frontiera per X , supponiamo per assurdo
che non sia di minimo assoluto ovvero che esista un punto (x ∗ , y ∗ )
tale che f (x ∗ , y ∗ ) < f (x 0 , y 0 ).
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Dimostrazione.
i) Se (x 0 , y 0 ) è punto interno di X , allora per la condizione
necessaria di ottimalità del I ordine ∇f (x 0 , y 0 ) = 0 e la tesi segue
dalla i) del Teorema “Convessità e punti critici” .
Se (x 0 , y 0 ) è punto di frontiera per X , supponiamo per assurdo
che non sia di minimo assoluto ovvero che esista un punto (x ∗ , y ∗ )
tale che f (x ∗ , y ∗ ) < f (x 0 , y 0 ).
Poiché X è convesso, i punti del segmento di estremi
0 ) appartengono ad X e quindi la direzione
(x ∗ , y∗ ), (x 0 , y
∗
0
x −x
d=
è una direzione ammissibile uscente da (x 0 , y 0 ).
y∗ − y0
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Dimostrazione.
i) Se (x 0 , y 0 ) è punto interno di X , allora per la condizione
necessaria di ottimalità del I ordine ∇f (x 0 , y 0 ) = 0 e la tesi segue
dalla i) del Teorema “Convessità e punti critici” .
Se (x 0 , y 0 ) è punto di frontiera per X , supponiamo per assurdo
che non sia di minimo assoluto ovvero che esista un punto (x ∗ , y ∗ )
tale che f (x ∗ , y ∗ ) < f (x 0 , y 0 ).
Poiché X è convesso, i punti del segmento di estremi
0 ) appartengono ad X e quindi la direzione
(x ∗ , y∗ ), (x 0 , y
∗
0
x −x
d=
è una direzione ammissibile uscente da (x 0 , y 0 ).
y∗ − y0
Inoltre, in virtù della caratterizzazione del I ordine delle funzioni
∗ −x 0 convesse si ha: f (x ∗ , y ∗ ) ≥ f (x 0 , y 0 ) + ∇f (x 0 , y 0 )T yx ∗ −y
0
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Dimostrazione.
o equivalentemente
∗
∗
0
0
0
0 T
f (x , y ) − f (x , y ) ≥ ∇f (x , y )
Lezioni del 25 e 30 novembre 2015
x∗ − x0
.
y∗ − y0
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Dimostrazione.
o equivalentemente
∗
∗
0
0
0
0 T
f (x , y ) − f (x , y ) ≥ ∇f (x , y )
x∗ − x0
.
y∗ − y0
Essendo f (x ∗ , y ∗ ) < f (x 0 , y 0 ) si ha f (x ∗ , y ∗ ) − f (x 0 , y 0 ) < 0 da
∗
0
0 0 T
cui ∇f (x 0 , y 0 )T yx ∗ −x
−y 0 = ∇f (x , y ) d < 0.
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Dimostrazione.
o equivalentemente
∗
∗
0
0
0
0 T
f (x , y ) − f (x , y ) ≥ ∇f (x , y )
x∗ − x0
.
y∗ − y0
Essendo f (x ∗ , y ∗ ) < f (x 0 , y 0 ) si ha f (x ∗ , y ∗ ) − f (x 0 , y 0 ) < 0 da
∗
0
0 0 T
cui ∇f (x 0 , y 0 )T yx ∗ −x
Di conseguenza, la
0 = ∇f (x , y ) d < 0.
−y
∗
0
x −x
direzione d =
è una direzione ammissibile di decrescita
y∗ − y0
locale, in contraddizione con il fatto che (x 0 , y 0 ) è punto di
minimo locale.
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Funzioni convesse e concave. Richiami.
Convessità e punti critici
Dimostrazione.
o equivalentemente
∗
∗
0
0
0
0 T
f (x , y ) − f (x , y ) ≥ ∇f (x , y )
x∗ − x0
.
y∗ − y0
Essendo f (x ∗ , y ∗ ) < f (x 0 , y 0 ) si ha f (x ∗ , y ∗ ) − f (x 0 , y 0 ) < 0 da
∗
0
0 0 T
cui ∇f (x 0 , y 0 )T yx ∗ −x
Di conseguenza, la
0 = ∇f (x , y ) d < 0.
−y
∗
0
x −x
direzione d =
è una direzione ammissibile di decrescita
y∗ − y0
locale, in contraddizione con il fatto che (x 0 , y 0 ) è punto di
minimo locale.
ii) Analoga alla i).
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Sia dato il problema
(P) :
max / min f (x, y )
gi (x, y ) ≤ 0 i = 1, ..., m
f : R2 → R, f di classe C 1 .
gi : R2 → R, gi di classe C 1 . i = 1, ...m.
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Sia dato il problema
(P) :
max / min f (x, y )
gi (x, y ) ≤ 0 i = 1, ..., m
f : R2 → R, f di classe C 1 .
gi : R2 → R, gi di classe C 1 . i = 1, ...m.
Osservazione
In generale le condizioni di Karush Kuhn Tucker (KKT) sono
necessarie e non sufficienti!!!!,
ovvero
esistono punti che verificano tali condizioni, ma non sono né di
massimo né di minimo per il problema (P)
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Sia dato il problema
(P) :
max / min f (x, y )
gi (x, y ) ≤ 0 i = 1, ..., m
f : R2 → R, f di classe C 1 .
gi : R2 → R, gi di classe C 1 . i = 1, ...m.
Osservazione
In generale le condizioni di Karush Kuhn Tucker (KKT) sono
necessarie e non sufficienti!!!!,
ovvero
esistono punti che verificano tali condizioni, ma non sono né di
massimo né di minimo per il problema (P)
Tuttavia, sotto determinate ipotesi tali condizioni sono sufficienti.
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Teorema (Sufficienza delle condizioni di Karush-Kuhn-Tucker)
Dato il problema
(P) :
min /max f (x, y )
gi (x, y ) ≤ 0 i = 1, ..., m
Se
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Teorema (Sufficienza delle condizioni di Karush-Kuhn-Tucker)
Dato il problema
(P) :
min /max f (x, y )
gi (x, y ) ≤ 0 i = 1, ..., m
Se
le funzioni vincolari gi , (i = 1, ...m) sono convesse;
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Teorema (Sufficienza delle condizioni di Karush-Kuhn-Tucker)
Dato il problema
(P) :
min /max f (x, y )
gi (x, y ) ≤ 0 i = 1, ..., m
Se
le funzioni vincolari gi , (i = 1, ...m) sono convesse;
la funzione obiettivo f è convessa (concava);
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Teorema (Sufficienza delle condizioni di Karush-Kuhn-Tucker)
Dato il problema
(P) :
min /max f (x, y )
gi (x, y ) ≤ 0 i = 1, ..., m
Se
le funzioni vincolari gi , (i = 1, ...m) sono convesse;
la funzione obiettivo f è convessa (concava);
un punto (x 0 , y 0 ) verifica le condizioni di
Karush-Kuhn-Tucker, come candidato minimo (massimo)
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Teorema (Sufficienza delle condizioni di Karush-Kuhn-Tucker)
Dato il problema
(P) :
min /max f (x, y )
gi (x, y ) ≤ 0 i = 1, ..., m
Se
le funzioni vincolari gi , (i = 1, ...m) sono convesse;
la funzione obiettivo f è convessa (concava);
un punto (x 0 , y 0 ) verifica le condizioni di
Karush-Kuhn-Tucker, come candidato minimo (massimo)
allora
(x 0 , y 0 ) è punto di minimo assoluto (massimo assoluto) per il
problema (P).
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Esercizio 4. del 17 febbraio 2015
2
Sia data la funzione f (x, y ) = (x−2)
3−y + 1.
a) Determinare le regioni di piano in cui la funzione f è convessa.
b) Determinare i punti di massimo e di minimo assoluto della
funzione f sulla regione convessa e illimitata
S1 = {(x, y ) ∈ R2 : y ≤ 2, x ≥ 0}.
c) Determinare i punti di massimo e di minimo assoluto della
funzione f sulla regione convessa e illimitata
S2 = {(x, y ) ∈ R2 : y ≥ 0, y ≤ 2, x ≥ 5}.
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
a) ∇f (x, y ) =
2(x−2)
3−y
(x−2)
(3−y )2
Esercizio tratto dai compiti di esame
!
;
H(x, y ) =
2
3−y
2(x−2)
(3−y )2
2(x−2)
(3−y )2
2(x−2)2
(3−y )3
!
H(x, y ) è semidefinita positiva se e solo se
2
1
≥0
3−y
2(x − 2)2
2
≥0
(3 − y )3
3 | H(x, y ) |≥ 0
La prima condizione è soddisfatta per y < 3, la seconda e la terza
per y 6= 3. Di conseguenza f é convessa per y < 3.
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
b)
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
b)
Poiché lim f (x, 0) = +∞, la funzione f non ammette
x→+∞
massimo assoluto
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
b)
Poiché lim f (x, 0) = +∞, la funzione f non ammette
x→+∞
massimo assoluto
f ha una retta di punti critici x = 2
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
b)
Poiché lim f (x, 0) = +∞, la funzione f non ammette
x→+∞
massimo assoluto
f ha una retta di punti critici x = 2
I punti x = 2, y ≤ 2 appartengono alla regione S1
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
b)
Poiché lim f (x, 0) = +∞, la funzione f non ammette
x→+∞
massimo assoluto
f ha una retta di punti critici x = 2
I punti x = 2, y ≤ 2 appartengono alla regione S1
Poiché f è convessa su S1 , i punti x = 2, y ≤ 2 sono punti di
minimo assoluto
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
c)
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
c)
Poiché lim f (x, 0) = +∞, la funzione f non ammette
x→+∞
massimo assoluto
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
c)
Poiché lim f (x, 0) = +∞, la funzione f non ammette
x→+∞
massimo assoluto
f è convessa su S2
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
c)
Poiché lim f (x, 0) = +∞, la funzione f non ammette
x→+∞
massimo assoluto
f è convessa su S2
non esistono punti critici di f sulla regione S2
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
c)
Poiché lim f (x, 0) = +∞, la funzione f non ammette
x→+∞
massimo assoluto
f è convessa su S2
non esistono punti critici di f sulla regione S2
le funzioni vincolari sono convesse
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
c)
Poiché lim f (x, 0) = +∞, la funzione f non ammette
x→+∞
massimo assoluto
f è convessa su S2
non esistono punti critici di f sulla regione S2
le funzioni vincolari sono convesse
in base al Teorema della sufficienza delle condizioni di KKT, i
punti che verificano tali condizioni come minimi, sono punti di
minimo assoluto
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Ricerca dei punti che verificano le condizioni di KKT come
minimi
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Ricerca dei punti che verificano le condizioni di KKT come
minimi
Non esistono punti che soddisfano le condizioni di KKT
aderenti al vincolo y = 0 (la verifica di questa affermazione è
lasciata agli studenti)
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Ricerca dei punti che verificano le condizioni di KKT come
minimi
Non esistono punti che soddisfano le condizioni di KKT
aderenti al vincolo y = 0 (la verifica di questa affermazione è
lasciata agli studenti)
Non esistono punti che soddisfano le condizioni di KKT
aderenti al vincolo y = 2 (la verifica di questa affermazione è
lasciata agli studenti)
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Ricerca dei punti che verificano le condizioni di KKT come
minimi
Non esistono punti che soddisfano le condizioni di KKT
aderenti al vincolo y = 0 (la verifica di questa affermazione è
lasciata agli studenti)
Non esistono punti che soddisfano le condizioni di KKT
aderenti al vincolo y = 2 (la verifica di questa affermazione è
lasciata agli studenti)
Non esistono punti che verificano le condizioni di KKT
aderenti al vincolo x = 5 (la verifica di questa affermazione è
lasciata agli studenti)
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Ricerca dei punti che verificano le condizioni di KKT come
minimi
Non esistono punti che soddisfano le condizioni di KKT
aderenti al vincolo y = 0 (la verifica di questa affermazione è
lasciata agli studenti)
Non esistono punti che soddisfano le condizioni di KKT
aderenti al vincolo y = 2 (la verifica di questa affermazione è
lasciata agli studenti)
Non esistono punti che verificano le condizioni di KKT
aderenti al vincolo x = 5 (la verifica di questa affermazione è
lasciata agli studenti)
Il vertice (5, 2) non soddisfa le condizioni di KKT (la verifica
di questa affermazione è lasciata agli studenti)
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Ricerca dei punti che verificano le condizioni di KKT come
minimi
Non esistono punti che soddisfano le condizioni di KKT
aderenti al vincolo y = 0 (la verifica di questa affermazione è
lasciata agli studenti)
Non esistono punti che soddisfano le condizioni di KKT
aderenti al vincolo y = 2 (la verifica di questa affermazione è
lasciata agli studenti)
Non esistono punti che verificano le condizioni di KKT
aderenti al vincolo x = 5 (la verifica di questa affermazione è
lasciata agli studenti)
Il vertice (5, 2) non soddisfa le condizioni di KKT (la verifica
di questa affermazione è lasciata agli studenti)
Il vertice (5, 0) soddisfa le condizioni di KKT come minimo (la
verifica di questa affermazione è lasciata agli studenti)
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Esercizio tratto dai compiti di esame
Ricerca dei punti che verificano le condizioni di KKT come
minimi
Non esistono punti che soddisfano le condizioni di KKT
aderenti al vincolo y = 0 (la verifica di questa affermazione è
lasciata agli studenti)
Non esistono punti che soddisfano le condizioni di KKT
aderenti al vincolo y = 2 (la verifica di questa affermazione è
lasciata agli studenti)
Non esistono punti che verificano le condizioni di KKT
aderenti al vincolo x = 5 (la verifica di questa affermazione è
lasciata agli studenti)
Il vertice (5, 2) non soddisfa le condizioni di KKT (la verifica
di questa affermazione è lasciata agli studenti)
Il vertice (5, 0) soddisfa le condizioni di KKT come minimo (la
verifica di questa affermazione è lasciata agli studenti)
(5, 0) è il punto di minimo assoluto
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Le proprietà della regione ammissibile sono determinanti
ATTENZIONE !!!!!!
La metodologia usata per la ricerca dei punti di ottimo è
fortemente legata alle proprietà della regione ammissibile
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Le proprietà della regione ammissibile sono determinanti
ATTENZIONE !!!!!!
La metodologia usata per la ricerca dei punti di ottimo è
fortemente legata alle proprietà della regione ammissibile
Discriminante è sapere se la regione ammissibile è compatta
oppure no
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Le proprietà della regione ammissibile sono determinanti
Regione ammissibile compatta
Vale il Teorema di Weierstrass
Ricerca dei punti di ottimo tramite
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Le proprietà della regione ammissibile sono determinanti
Regione ammissibile compatta
Vale il Teorema di Weierstrass
Ricerca dei punti di ottimo tramite
1
Curve di livello
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Le proprietà della regione ammissibile sono determinanti
Regione ammissibile compatta
Vale il Teorema di Weierstrass
Ricerca dei punti di ottimo tramite
1
2
Curve di livello
Metodo di KKT
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Le proprietà della regione ammissibile sono determinanti
Regione ammissibile compatta
Vale il Teorema di Weierstrass
Ricerca dei punti di ottimo tramite
1
2
Curve di livello
Metodo di KKT
1
Ricerca dei candidati massimi
e minimi tra:
- punti critici interni
- punti di frontiera che
verificano le condizioni di
KKT
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Le proprietà della regione ammissibile sono determinanti
Regione ammissibile compatta
Vale il Teorema di Weierstrass
Ricerca dei punti di ottimo tramite
1
2
Curve di livello
Metodo di KKT
1
2
Ricerca dei candidati massimi
e minimi tra:
- punti critici interni
- punti di frontiera che
verificano le condizioni di
KKT
Confronta tra i valori assunti
dalla funzione nei punti
candidati
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Le proprietà della regione ammissibile sono determinanti
Regione ammissibile compatta
Vale il Teorema di Weierstrass
Ricerca dei punti di ottimo tramite
1
2
Curve di livello
Metodo di KKT
1
2
3
Ricerca dei candidati massimi
e minimi tra:
- punti critici interni
- punti di frontiera che
verificano le condizioni di
KKT
Confronta tra i valori assunti
dalla funzione nei punti
candidati
Convessitá / concavitá
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Regione ammissibile compatta
Vale il Teorema di Weierstrass
Ricerca dei punti di ottimo tramite
1
2
Regione ammissibile chiusa, illimitata
e convessa
Non vale il T. di Weierstrass
Ricerca dei punti di ottimo tramite
Curve di livello
Metodo di KKT
1
2
3
Le proprietà della regione ammissibile sono determinanti
Ricerca dei candidati massimi
e minimi tra:
- punti critici interni
- punti di frontiera che
verificano le condizioni di
KKT
Confronta tra i valori assunti
dalla funzione nei punti
candidati
Convessitá / concavitá
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Regione ammissibile compatta
Vale il Teorema di Weierstrass
Ricerca dei punti di ottimo tramite
1
2
Curve di livello
Metodo di KKT
1
2
3
Le proprietà della regione ammissibile sono determinanti
Regione ammissibile chiusa, illimitata
e convessa
Non vale il T. di Weierstrass
Ricerca dei punti di ottimo tramite
1
Curve di livello
Ricerca dei candidati massimi
e minimi tra:
- punti critici interni
- punti di frontiera che
verificano le condizioni di
KKT
Confronta tra i valori assunti
dalla funzione nei punti
candidati
Convessitá / concavitá
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Regione ammissibile compatta
Vale il Teorema di Weierstrass
Ricerca dei punti di ottimo tramite
1
2
Curve di livello
Metodo di KKT
1
2
3
Le proprietà della regione ammissibile sono determinanti
Regione ammissibile chiusa, illimitata
e convessa
Non vale il T. di Weierstrass
Ricerca dei punti di ottimo tramite
1
2
Curve di livello
Proprietà funzioni convesse
Ricerca dei candidati massimi
e minimi tra:
- punti critici interni
- punti di frontiera che
verificano le condizioni di
KKT
Confronta tra i valori assunti
dalla funzione nei punti
candidati
Convessitá / concavitá
Lezioni del 25 e 30 novembre 2015
Sufficienza di Karush-Kuhn-Tucker
La funzione Lagrangiana
Convessità nei problemi di ottimo vincolato
Condizioni sufficienti di Karush-Kuhn-Tucker
Problemi di Ottimo vincolato. Schema Riassuntivo
Regione ammissibile compatta
Vale il Teorema di Weierstrass
Ricerca dei punti di ottimo tramite
1
2
Curve di livello
Metodo di KKT
1
2
3
Ricerca dei candidati massimi
e minimi tra:
- punti critici interni
- punti di frontiera che
verificano le condizioni di
KKT
Confronta tra i valori assunti
dalla funzione nei punti
candidati
Convessitá / concavitá
Lezioni del 25 e 30 novembre 2015
Le proprietà della regione ammissibile sono determinanti
Regione ammissibile chiusa, illimitata
e convessa
Non vale il T. di Weierstrass
Ricerca dei punti di ottimo tramite
1
2
Curve di livello
Proprietà funzioni convesse
1
2
3
Verifica la convessità
(concavità) della funzione
obiettivo
Ricerca punti di minimo
(massimo) tra i critici interni
alla regione. Se non ci sono si
passa al punto 3.
Si applica il teorema sulla
Sufficienza delle condizioni di
KKT
Sufficienza di Karush-Kuhn-Tucker