Esercizi di ottimizzazione vincolata

(1)

Esercizi di ottimizzazione vincolata

A. Agnetis, P. Detti

^∗

Esercizi svolti 1

Dato il seguente problema di ottimizzazione vincolata max x₁+ x₂

x₁ − 4x₂ ≥ −3

−x1+ x²₂ ≥ 0 x₁ ≥ 0

studiare l’esistenza di punti di massimo.

Soluzione. Studiamo il problema nella forma:

min −x₁− x₂

g₁(x) = 3 + x₁− 4x₂ ≥ 0 (1)

g₂(x) = −x₁+ x²₂ ≥ 0 (2)

g3(x) = x1 ≥ 0 (3)

La regione ammissibile del problema `e costituita dalla regione al di sotto della retta g₁ ed esterna alla parabola g₂ (Fig.1). Notare che tale regione `e illimitata e non convessa. Le condizioni di KKT sono quindi condizioni necessarie di minimo locale.

I gradienti dei vincoli, che serviranno per verificare la condizione di qualificazione dei vincoli attivi, sono:

∇g₁ =

1

−4

∇g₂ =

−1 2x₂

∇g₃ =

1 0

∗Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche - Universit`a di Siena

(2)

Figura 1: Regione ammissibile dell’esercizio 1.

La funzione Lagrangiana `e:

L(x, λ) = −x₁− x₂− λ₁(3 + x₁− 4x₂) − λ₂(−x₁+ x²₂) − x₁λ₃ Imponiamo le condizioni di KKT:

∂L

∂x1 = −1 − λ₁+ λ₂− λ₃ = 0

∂L

∂x2 = −1 + 4λ1− 2x2λ2 = 0 3 + x₁− 4x₂ ≥ 0

−x₁+ x²₂ ≥ 0

x1 ≥ 0

3λ₁+ x₁λ₁− 4x₂λ₁ = 0

−x₁λ₂+ x²₂λ₂ = 0

x1λ3 = 0

λ₁ ≥ 0

λ₂ ≥ 0

λ3 ≥ 0

Consideriamo i seguenti casi.

Caso 1

Nessun vincolo è attivo (λ₁ = λ₂ = λ₃ = 0). La regione ammissibile è un insieme aperto costituito dai punti del primo e del quarto quadrante al di sotto della retta ed esterni alla parabola. Poiché in questo caso nessun vincolo è attivo, la condizione di qualificazione è banalmente soddisfatta.

La prima condizione delle KKT diventa

∂L

∂x₁ = −1 = 0

(3)

ed il sistema quindi non ha soluzione.

Caso 2

Il solo vincolo attivo `e il vincolo (1) (λ₂ = λ₃ = 0). Poich´e ∇g₁ 6= 0, non ci sono punti che non soddisfano la condizione di qualificazione dei vincoli attivi.

La prima condizione diventa

∂L

∂x₁ = −1 − λ₁ = 0

ed il sistema anche in questo caso non ha soluzione (λ₁ < 0).

Caso 3

Il solo vincolo attivo `e il vincolo (2) (λ₁ = λ₃ = 0). Poich´e ∇g₂ 6= 0 anche in questo caso, non ci sono punti che non soddisfano la condizione di qualificazione dei vincoli attivi.

Si ha

∂L

∂x1 = −1 + λ₂ = 0

∂L

∂x2 = −1 − 2x2λ2 = 0

−x₁+ x²₂ = 0

dalle prime due condizioni si ottiene λ2 = 1 e x2 = −1/2, e dalla terza x1 = 1/4. Il punto ammissibile trovato `e quindi (1/4, −1/2), a cui corrisponde un valore della funzione obiettivo pari a 1/4.

Caso 4

Il solo vincolo attivo `e il vincolo (3) (λ₁ = λ₂ = 0). Poich´e ∇g₃ =

1 0

6= 0, non esistono punti che non soddisfano la condizione di qualificazione dei vincoli attivi.

La prima condizione delle KKT diventa

∂L

∂x₁ = −1 − λ₃ = 0

ed il sistema quindi non ha soluzione (λ₃ < 0).

Caso 5

Sono attivi i vincoli (1) e (2) (λ3 = 0). La regione in questo caso `e costituita dai punti A = (1, 1) e B = (9, 3). Controlliamo la condizione di qualificazione dei vincoli. I gradienti dei vincoli attivi nel punto A

∇g₁(A) =

1

−4

∇g₂(A) =

−1 2

sono linearmente indipendenti, e quindi vale la condizione di qualificazione dei vincoli attivi.

Le condizioni di KKT diventano:

∂L

∂x1 = −1 − λ₁+ λ₂ = 0

∂L

∂x2 = −1 + 4λ₁− 2λ₂ = 0

λ₁ ≥ 0

λ₂ ≥ 0

(4)

da cui λ₁ = 3/2 e λ₂ = 5/2. Il punto A `e un candidato di minimo locale. In tale punto la funzione obiettivo vale −2.

Consideriamo il punto B. I gradienti dei vincoli attivi

∇g₁(B) =

1

−4

∇g₂(B) =

−1 6

Dalle prime due condizioni di KKT calcolate in B si ottiene λ₂ < 0 e quindi il sistema non ammette soluzione.

Caso 6

Sono attivi i vincoli (1) e (3) (λ₂ = 0). La regione in questo caso `e costituita dal punto C = (0, 3/4). I gradienti dei vincoli attivi

∇g₁ =

1

−4

∇g₃ =

1 0

Le prime due condizioni diventano

∂L

∂x₁ = −1 − λ₁− λ₃ = 0∂L

∂x₂ = −1 + 4λ₁ = 0

da cui λ₁ = 1/4 e λ₃ = −5/4 < 0. Il sistema non ammette quindi soluzione.

Caso 7

Sono attivi i vincoli (2) e (3) (λ₁ = 0). La regione in questo caso `e costituita dal punto B = (0, 0). I gradienti dei vincoli attivi

∇g₂ =

−1 0

∇g₃ =

1 0

sono ovviamente linearmente dipendenti, e quindi la condizione di qualificazione dei vincoli attivi non `e soddisfatta. Nel punto (0, 0) non possiamo applicare le condizioni di KKT. Non si pu`o quindi escludere che il punto B sia un minimo locale.

Caso 8

Sono attivi tutti i vincoli. La regione ammissibile in questo caso `e vuota.

I punti candidati di minimo locale sono quindi (1/4, −1/2) e A = (1, 1), che soddisfano sia le condizioni di KKT sia la condizione di qualificazione, ed il punto (0, 0) che non soddisfa la condizione di qualificazione.

(5)

2

Dato l’insieme di punti descritto dalle seguenti disequazioni x₁− 2x₂ ≥ −1

−x₁+ x²₂ ≥ 0 x1 ≥ 0

verificare che il punto (1, 1) non soddisfa le condizioni di qualificazione.

Soluzione. Consideriamo le disequazioni nella forma:

g₁(x) = 1 + x₁− 2x₂ ≥ 0 g₂(x) = −x₁+ x²₂ ≥ 0 g₃(x) = x₁ ≥ 0

La regione ammissibile consiste nella regione del primo e quarto quadrante al di sotto della retta 1 + x₁− 2x₂ ed esterna alla parabola −x₁+ x²₂.

Nel punto A = (1, 1) sono attivi i vincoli g₁(x) e g₂(x). Controlliamo la condizione di

qualificazione dei vincoli. Si ha

∇g₁ =

1

−2

∇g₂ =

−1 2x₂

=

−1 2

(6)

I due vettori sono linearmente dipendenti e quindi la condizione di qualificazione dei vincoli non `e soddisfatta. Notare, infatti, che in A le due curve sono tangenti, e quindi i vettori gradiente relativi ai due vincoli sono paralleli.

3

Dato il seguente problema di ottimizzazione vincolata min x²₁+ 3x²₂

g₁(x) = x²₁+ x²₂ ≥ 1 g₂(x) = x²₂ ≥ 1/4

(4) studiare l’esistenza di punti di minimo.

min x²₁+ 3x²₂

g1(x) = x²₁+ x²₂− 1 ≥ 0 g₂(x) = 4x²₂− 1 ≥ 0

(5) La funzione Lagrangiana `e:

L(x, λ) = x²₁+ 3x²₂− λ₁(x₁²+ x²₂− 1) − λ₂(4x²₂− 1) Imponiamo le condizioni di KKT:

∂L

∂x1 = 2x₁− 2x₁λ₁ = 0

∂L

∂x2 = 6x₂− 2λ₁x₂− 8λ₂x₂ = 0 g₁(x) = x²₁+ x²₂− 1 ≥ 0 g₂(x) = 4x²₂− 1 ≥ 0 λ₁(x²₁+ x²₂− 1) = 0 λ₂(4x²₂− 1) = 0

λ₁ ≥ 0

λ₂ ≥ 0

La regione ammissibile del problema `e costituita dalla intersezione della regione esterna alla circonferenza g1 con i due semipiani x2 ≥ 1/2 e x2 ≤ −1/2. L’insieme ammissibile non `e convesso e quindi le condizioni di KKT sono condizioni necessarie di ottimo locale per i punti che soddisfano la condizione di qualificazione.

I gradienti dei vincoli, che serviranno per verificare la condizione di qualificazione, sono:

(7)

∇g1 =

2x₁ 2x₂

∇g2 =

0 2x₂

Caso 1

Nessun vincolo `e attivo (λ₁ = λ₂ = 0). Dalle prime due condizioni di KKT si ottiene il punto (0, 0) che non appartiene alla regione ammissibile.

Caso 2

E attivo il vincolo g` ₁(x) (λ₁ > 0 λ₂ = 0).

In questo caso, non ci sono punti ammissibili che non soddisfano la condizione di qualificazione dei vincoli attivi. Infatti, ∇g1 =

2x₁ 2x₂

si annulla solo nell’origine, non appartenente alla regione ammissibile.

Le prime due condizioni di KKT diventano:

∂L

∂x1 = 2x₁− 2x₁λ₁ = 0

∂L

∂x2 = 6x₂− 2λ₁x₂ = 0

Notare che nell’insieme ammissibile si ha sempre x2 6= 0. La seconda equazione pu`o essere quindi divisa per x₂ ottenendo λ₁ = 3.

Consideriamo i due sottocasi: x₁ = 0 e x₁ 6= 0.

Per x₁ = 0, dal primo vincolo si ottiene x₂ = 1 e x₂ = −1. I punti trovati sono quindi (0, 1), (0, −1). La funzione obiettivo in entrambi i punti assume valore 3.

Per x₁ 6= 0, dalle prime due condizioni di KKT si ottiene rispettivamente λ₁ = 1 e λ₁ = 3, e quindi il sistema non ammette soluzione.

Caso 3

E attivo il vincolo g` ₂(x) (λ₁ = 0 λ₂ > 0).

In questo caso, non ci sono punti ammissibili che non soddisfano la condizione di qualificazione dei vincoli attivi. Infatti, ∇g₂ =

0 8x₂

si annulla solo nei punti dell’asse delle

(8)

ascisse, che non appartengono alla regione ammissibile.

Imponendo le KKT, si ottengono i punti (0, 1/2), (0, −1/2) che non sono ammissibili.

Caso 4

Entrambi i vincoli sono attivi (λ₁ > 0 λ₂ > 0). La regione ammissibile `e costituita in questo caso dai quattro punti d’intersezione della circonferenza con le due rette x₂ = 1/2 e x₂ = −1/2: (

√ 3 2 ,¹₂), (

√ 3

2 , −¹₂), (−

√ 3

2 ,¹₂), (−

√ 3 2 , −¹₂).

E facile verificare che in tutti e quattro i punti la condizione di qualificazione `` e soddisfatta (∇g1 e ∇g2 sono linearmente indipendenti).

In tutti e quattro i punti, dalle prime due condizioni di KKT, si ottengono i moltiplicatori:

λ₁ = 1 e λ₂ = 1/2. Controlliamo la condizione di qualificazione dei vincoli attivi. Si ha la matrice

dg dx =

2x₁ 2x₂ 0 2x₂

che nei punti trovati ha sempre rango 2. In tutti i punti la funzione obiettivo vale sempre 3/2.

I punti candidati ad essere dei minimi locali sono quelli trovati nei Casi 2 e 4.

4

Si consideri il seguente problema di ottimizzazione vincolata:

min −x1− x²₂

2x²₁+ x²₂ ≤ 7 x²₁+ x²₂ ≥ 2

a) Vi sono punti in cui la condizione di qualificazione dei vincoli attivi non `e soddisfatta? Motivare la risposta.

b) Si individuino i punti che soddisfano le condizioni necessarie di ottimo del primo ordine (KKT). Siete in grado di indicare il punto di minimo globale?

Soluzione. Il problema pu`o essere formulato nel seguente modo:

min −x₁− x²₂

g₁(x) = −2x²₁− x²₂+ 7 ≥ 0 g₂(x) = x²₁+ x²₂− 2 ≥ 0

(9)

L’insieme ammissibile del problema è dato dall’intersezione della parte interna all’ellisse, corrispondente al primo vincolo, con quella interna alla circonferenza descritta dal secondo vincolo. Tale insieme non è convesso. Per quanto riguarda la condizione di qualificazione dei vincoli attivi, si noti che non esistono punti in cui entrambi vincoli sono attivi. I gradienti dei due vincoli, inoltre, si annullano solo nell’origine che non appartiene alla regione ammissibile. La condizione di qualificazione dei vincoli attivi è, quindi, sempre soddisfatta.

Troviamo i punti che soddisfano le condizioni di KKT. La funzione Lagrangiana `e:

L(x, λ) = −x₁− x²₂− λ₁(−2x²₁− x²₂+ 7) − λ₂(x²₁+ x²₂− 2) Imponiamo le condizioni di KKT:

∂L

∂x1 = −1 + 4x1λ1− 2x1λ2 = 0

∂L

∂x2 = −2x₂+ 2x₂λ₁− 2x₂λ₂ = 0 g₁(x) = −2x²₁− x²₂+ 7 ≥ 0 g₂(x) = x²₁+ x²₂− 2 ≥ 0 λ₁(−2x²₁− x²₂+ 7) = 0 λ₂(x²₁+ x²₂− 2) = 0

λ₁ ≥ 0

λ₂ ≥ 0

Consideriamo i seguenti quattro casi.

Caso 1

Entrambi i vincoli non sono attivi (λ₁ = λ₂ = 0) Dalla prima condizione si ottiene

−1 = 0

(10)

ed `e quindi impossibile.

Caso 2

Entrambi i vincoli sono attivi.

In questo caso non esistono punti ammissibili dato che ellisse e circonferenza non hanno punti in comune.

Caso 3

Il solo vincolo attivo `e g1(x) (λ2 = 0).

Notare che in questo caso, non ci sono punti ammissibili che non soddisfano la condizione di qualificazione dei vincoli attivi. Infatti, si ha ∇g₁ =

−4x₁

−2x2

che si annulla solo nell’origine, non appartenente alla regione ammissibile.

Applichiamo le condizioni KKT. Si ha il sistema:

−1 + 4x₁λ₁ = 0

−2x₂+ 2x₂λ₁ = 0

−2x²₁− x²₂+ 7 = 0

λ₁ ≥ 0

Dalla seconda equazione derivano i due seguenti sotto casi: i) x₂ = 0; ii) x₂ 6= 0.

i)

Dalla terza equazione, si ottengono i punti A(^q⁷₂, 0) e B(−^q⁷₂, 0), di cui solo A soddisfa la condizione di non negativit`a su λ₁.

ii)

Poich´e x₂ 6= 0 si pu`o dividere la seconda equazione per x₂ ottenendo λ₁ = 1. Dalla prima equazione si ottiene x₁ = ¹₄ e dalla terza x₂ = ±^q⁵⁵₈. I punti sono quindi C(¹₄,^q⁵⁵₈ ) e D(¹₄, −^q⁵⁵₈).

Caso 4

Il solo vincolo attivo `e g₂(x) (λ₁ = 0).

Anche in questo caso, non ci sono punti ammissibili che non soddisfano la condizione di qualificazione dei vincoli attivi. Infatti, ∇g₂ =

2x₁ 2x₂

che si annulla solo nell’origine, non appartenente alla regione ammissibile.

Si ha il sistema:

−1 − 2x₁λ₂ = 0

−2x₂− 2x₂λ₂ = 0 x²₁+ x²₂− 2 = 0

λ₂ ≥ 0

Possiamo considerare i due seguenti sotto casi: iii) x2 = 0; iv) x2 6= 0.

iii)

L’unico punto che soddisfa il sistema `e E(−√ 2, 0).

(11)

iv)

Dalla prima equazione si ha λ₂ = −1 che non soddisfa la quarta equazione.

Poich´e l’insieme ammissibile `e chiuso e limitato esiste almeno un minimo globale.

Tra quelli che soddisfano le condizioni necessarie di minimo, i punti che minimizzano la funzione obiettivo sono C e D.

5

Determinare il punto di intersezione dei piani 3x₁− 2x₂ + 4x₃ = 9 x₁+ 2x₂ = 3 pi`u vicino al punto di coordinate (3, −1, 2).

Soluzione. Il problema pu`o essere formulato come problema di ottimizzazione vincolata in cui l’obiettivo `e quello di minimizzare il quadrato della distanza tra il punto cercato e (3, −1, 2):

min(x1− 3)²+ (x2+ 1)² + (x3− 2)²

h₁(x) = 9 − 3x₁+ 2x₂− 4x₃ = 0 h₂(x) = 3 − x₁− 2x₂ = 0

Notare che la funzione obiettivo `e coerciva, convessa, con derivate parziali continue, e che i vincoli sono lineari. Le condizioni di Karush Kuhn Tucker (KKT) sono quindi condizioni necessarie e sufficienti di ottimo globale anche nei punti che non soddisfano la condizione di qualificazione (per la linearit`a dei vincoli).

Applichiamo le condizioni di KKT per determinare i punti che soddisfano le condizioni di ottimalit`a del primo ordine. La funzione Lagrangiana `e:

L(x, λ) = (x₁− 3)²+ (x₂+ 1)²+ (x₃− 2)²− λ₁(9 − 3x₁+ 2x₂− 4x₃) − λ₂(3 − x₁− 2x₂) I vincoli sono tutti di uguaglianza. Imponendo le condizioni di KKT si ottiene il seguente sistema di equazioni:

∂L

∂x1 = 2(x1− 3) + 3λ1+ λ2 = 0

∂L

∂x2 = 2(x₂ + 1) − 2λ₁+ 2λ₂ = 0

∂L

∂x3 = 2(x₃− 2) + 4λ₁ = 0 3x₁− 2x₂+ 4x₃ = 9

x₁ + 2x₂ = 3

(12)

Dall’ultima equazione si ottiene x₁ = 3 − 2x₂. La sostituzione di x₁ nella penultima equazione porta a x₃ = 2x₂. Il sistema, ridotto alle sole variabili x₂, λ₁ e λ₂, diventa:

4x₂− 3λ₁− λ₂ = 0

−2x₂+ 2λ₁− 2λ₂ = 2

−4x₂ − 4λ₁ = −4

da cui si ottiene λ₁ = ²₃, λ₂ = −²₃, x₂ = ¹₃, e

x₁ = 3 − 2x₂ = ⁷₃, x₃ = 2x₂ = ²₃. Il punto che soddisfa le condizioni del primo ordine `e ˆ

x = (⁷₃,¹₃,²₃). In tale punto la funzione obiettivo vale 4. Il punto ˆx `e quindi un punto di minimo globale.

6

Determinare il punto della regione definita dai vincoli x₁+ x₂ ≤ 2 x²₁ ≤ 4

pi`u vicino al punto di coordinate (2, 3).

Soluzione. Il problema pu`o essere formulato come problema di ottimizzazione vincolata nel modo seguente:

min(x1− 2)²+ (x2− 3)²

g₁(x) = 2 − x₁− x₂ ≥ 0 g₂(x) = 4 − x²₁ ≥ 0

La regione ammissibile `e quella compresa tra le due rette x₁ = 2, x₁ = −2, ed al di sotto della retta x₁+ x₂− 2 = 0.

Notare che la funzione obiettivo `e coerciva, convessa con derivate parziali continue, e che la regione ammissibile `e convessa. I vincoli hanno inoltre derivate parziali continue

(13)

ovunque. Le condizioni di KKT sono quindi condizioni necessarie e sufficienti di ottimo globale per i punti che soddisfano la condizione di qualificazione.

∇g₁ =

−1

∇g₂ =

−2x₁ 0

L(x, λ) = (x₁− 2)²+ (x₂− 3)²− λ₁(2 − x₁− x₂) − λ₂(4 − x²₁) Imponiamo le condizioni di KKT:

∂L

∂x1 = 2(x₁ − 2) + λ₁+ 2x₁λ₂ = 0

∂L

∂x2 = 2(x₂− 3) + λ₁ = 0 2 − x₁− x₂ ≥ 0

4 − x²₁ ≥ 0

2λ₁− x₁λ₁− x₂λ₁ = 0 4λ₂− x²₁λ₂ = 0

λ1 ≥ 0

λ₂ ≥ 0

Caso 1

Entrambi i vincoli sono attivi. L’insieme ammissibile `e costituito dai punti B = (2, 0) e A = (−2, 4). In entrambi i punti i gradienti dei due vincoli sono linearmente indipendenti e quindi la condizione di qualificazione `e soddisfatta.

Nel punto B il sistema diventa:

2(x₁ − 2) + λ₁+ 2x₁λ₂ = 0 2(x₂− 3) + λ₁ = 0

x₁ = 2

x₂ = 0

λ₁ ≥ 0

λ₂ ≥ 0

da cui

λ₁+ 4λ₂ = 0

−6 + λ₁ = 0

λ1 ≥ 0

λ₂ ≥ 0

che non ammette soluzione (λ₂ = −3/2 < 0).

Nel punto A il sistema diventa:

2(x₁ − 2) + λ₁+ 2x₁λ₂ = 0 2(x₂− 3) + λ₁ = 0

x₁ = −2

x₂ = 4

λ₁ ≥ 0

λ₂ ≥ 0

(14)

dalla seconda equazione si ottiene λ1 = −2 < 0

e quindi il sistema non ammette soluzione.

Caso 2

Consideriamo la regione in cui il solo vincolo g₁(x) ≥ 0 è attivo. Notare che in tale regione la condizione di qualificazione è sempre soddisfatta dato che ∇g1(x) è diverso dal vettore nullo.

Per λ₂ = 0 le condizioni di KKT diventano:

2(x1 − 2) + λ1 = 0 2(x₂ − 3) + λ₁ = 0 2 − x₁− x₂ = 0 4 − x²₁ > 0

λ₁ ≥ 0

eliminando λ₁ dalle prime due equazioni si ottiene:

x₁− x₂ = −1 x1+ x2 = 2

da cui x1 = 1/2 e x2 = 3/2. Sostituendo x1 nella prima equazione si ha λ1 = 3. Nel punto (1/2, 3/2) la funzione obiettivo vale 9/2.

Caso 3

Consideriamo la regione in cui il solo vincolo g₂(x) ≥ 0 è attivo. Tale regione è costituita dalle due semirette x₁ = −2 e x₁ = 2 aventi origine in A ed in B rispettivamente. Notare che A e B non appartengono a tale regione. Anche in questo caso, la condizione di qualificazione è sempre soddisfatta dato che ∇g₂(x) si annulla solo per x₁ = 0.

Dalle condizioni di KKT si ha il sistema:

2(x₁ − 2) + 2x₁λ₂ = 0 2(x₂− 3) = 0 2 − x1− x2 > 0 4 − x²₁ = 0

λ₂ ≥ 0

che non ha soluzione.

Caso 4

Nessun vincolo `e attivo (λ1 = λ2 = 0). Si ottiene il sistema:

x₁− 2 = 0 x₂− 3 = 0 2 − x₁− x₂ ≥ 0 4 − x²₁ ≥ 0

che non ha soluzione ammissibile.

L’unico punto che soddisfa le condizioni di ottimalità è il punto (1/2, 3/2) trovato nel Caso 2. L’ottimo globale è quindi (1/2, 3/2).

(15)

7

Dato il seguente problema di ottimizzazione vincolata max ln(x₁) + 2ln(x₂) + 3ln(x₃)

x₁+ x₂+ x₃ = 3000 x₁ ≥ 750 x₂ ≥ 1 x₃ ≥ 1 studiare l’esistenza di punti di massimo.

min −ln(x₁) − 2ln(x₂) − 3ln(x₃)

h₁(x) = 3000 − x₁− x₂− x₃ = 0 g₂(x) = x₁− 750 ≥ 0 g₃(x) = x₂− 1 ≥ 0 g₄(x) = x₃− 1 ≥ 0

Poiché la funzione obiettivo è convessa e continua nell’insieme ammissibile, e i vincoli sono lineari, le condizioni di Karush Kuhn Tucker (KKT) sono condizioni necessarie e sufficienti di ottimo globale anche nei punti che non soddisfano la condizione di qualificazione (per la linearità dei vincoli).

L(x, λ) = −ln(x₁) − 2ln(x₂) − 3ln(x₃) − λ₁(3000 − x₁− x₂− x₃) − λ₂(x₁− 750)+

−λ₃(x₂− 1) − λ₄(x₃− 1) Imponiamo le condizioni di KKT:

∂L

∂x₁ = −1

x₁ + λ1− λ2 = 0 (6)

∂L

∂x₂ = −2

x₂ + λ₁− λ₃ = 0 (7)

∂L

∂x₃ = −3

x₃ + λ₁− λ₄ = 0 (8)

3000 − x₁− x₂− x₃ = 0 (9)

x1− 750 ≥ 0 (10)

x₂ − 1 ≥ 0 (11)

x₃ − 1 ≥ 0 (12)

(16)

λ₂(x₁− 750) = 0 (13)

λ3(x2− 1) = 0 (14)

λ₄(x₃− 1) = 0 (15)

λ₂ ≥ 0 (16)

λ₃ ≥ 0 (17)

λ₄ ≥ 0 (18)

Caso 1

Il solo vincolo g2(x) ≥ 0 `e attivo, dunque λ3 = λ4 = 0 e x1 = 750. Dalle (7), (8) e (9) si ottiene:

3000 − 750 − 2 λ1

− 3 λ1

= 0 da cui

λ1 = 1 2250

mentre x₂ ed x₃ assumono i valori:

x₂ = 2

λ₁ = 900 x₃ = 3

λ₁ = 1350 Dalla prima equazione si pu`o ricavare λ₂

λ₂ = − 1

x₁ + λ₁ = − 1

750 + 1

450 = 2 2250 che `e positivo. Il punto trovato `e quindi:

x1 = 750 x2 = 900 x3 = 1350 Caso 2

Il solo vincolo g₂(x) ≥ 0 `e attivo, dunque λ₂ = λ₄ = 0 e x₂ = 1. Dalle (6), (8) e (9) si ottiene:

x₁ = 1

λ₁; x₃ = 3 λ₁

Per sostituzione, dal vincolo di uguaglianza si ottiene:

λ₁ = 4 2999

mentre dalla (7) si ricava λ3: λ₃ = 4

2999 − 2 < 0

(17)

e quindi il sistema non ha soluzione.

Caso 3

Il solo vincolo g₃(x) ≥ 0 `e attivo, dunque λ₂ = λ₃ = 0 e x₃ = 1. Dalle (7), (8) e (9) si ottiene:

x₁ = 2999/3 x₂ = 2/3(2999) x₃ = 1 λ₁ = 1

x₁ = 3

2999 λ₄ = λ₁− 3

e quindi il sistema non ha soluzione (λ₄ < 0).

Caso 4

Sono attivi i vincoli g₁(x) ≥ 0 e g₂(x) ≥ 0, dunque λ₄ = 0 e inoltre x₁ = 750 e x₂ = 1.

Da h(x) = 0 si ottiene inoltre x₃ = 2249. Dalle (6)–(8) si ha che

− 1

750 + λ1− λ2 = 0

−2 + λ₁− λ₃ = 0

− 3

2249 + λ₁ = 0

da cui λ₁ = ₂₂₄₉³ e di conseguenza λ₃ < 0.

Caso 5

Sono attivi i vincoli g1(x) ≥ 0 e g3(x) ≥ 0, dunque λ3 = 0 e inoltre x1 = 750 e x3 = 1.

Da h(x) = 0 si ottiene inoltre x2 = 2249. Dalle (6)–(8) si ha che

− 1

750 + λ₁− λ₂ = 0

− 2

2249 + λ₁ = 0

−3 + λ₁− λ₄ = 0 e dunque, come si vede, λ₄ < 0.

Caso 6

Sono attivi i vincoli g₂(x) ≥ 0 e g₃(x) ≥ 0, dunque λ₂ = 0 e inoltre x₂ = 1 e x₃ = 1. Da h(x) = 0 si ottiene inoltre x₁ = 2998. Dalle (6)–(8) si ha che

− 1

2998 + λ1 = 0

−2 + λ₁ − λ₃ = 0

−3 + λ₁ − λ₄ = 0

che ammette soluzione solo con λ₃ < 0 e λ₄ < 0.

Caso 7

(18)

Sono attivi tutti i vincoli (g₁(x) = 0, g₂(x) = 0 e g₃(x) = 0). L’insieme ammissibile `e vuoto.

Caso 8

Nessun vincolo `e attivo.

Dalle condizioni di KKT si ottiene il sistema:

−_x¹

1 + λ₁ = 0

−_x²

2 + λ₁ = 0

−_x³

3 + λ₁ = 0

3 − x1− x2− x3 = 0 che ammette la soluzione:

x₁ = 500 x₂ = 1000 x₃ = 1500 λ₁ = 1

500 λ₂ = 0 che non soddisfa il vincolo x₁ ≥ 750.

L’unico punto che soddisfa le condizioni di KKT `e il punto trovato nel Caso 1, ed `e quindi un ottimo globale.

8

Un agente di borsa ha a disposizione 1000 Euro da investire su due titoli finanziari. Siano x₁ ed x₂ le quantit`a investite sui due titoli rispettivamente. Dallo studio di dati storici, si stima che il guadagno medio atteso e la varianza dell’intero investimento, in funzione delle quantit`a investite, sono rispettivamente 0, 1x₁+ 0, 12x₂ e 0, 005x²₁− 0, 006x₁x₂+ 0, 008x²₂. Si richiede di massimizzare il guadagno atteso totale con il vincolo che la varianza non sia superiore a 625.

Soluzione. Il problema pu`o essere formulato nel seguente modo:

min −0, 1x₁ − 0, 12x₂

g1(x) = 625 − 0, 005x²₁+ 0, 006x1x2− 0, 008x²₂ ≥ 0 (19)

g₂(x) = 1000 − x₁− x₂ ≥ 0 (20)

Può essere dimostrato che l’insieme ammissibile del problema in esame è convesso (ossia che −g₁(x) è una funzione convessa). Le condizioni di KKT sono quindi condizioni necessarie e sufficienti di minimo globale nei punti che soddisfano la condizione di qualificazione.

∇g₁ =

−0, 01x₁+ 0, 006x₂ 0, 006x1− 0, 016x2

∇g₂ =

−1

(19)

L(x, λ) = −0, 1x1− 0, 12x2− λ1(625 − 0, 005x₁²+ 0, 006x1x2− 0, 008x²₂)−

−λ2(1000 − x1− x2)

Imponiamo le condizioni di KKT:

∂L

∂x1 = −0, 1 + 0, 01x₁λ₁− 0, 006x₂λ₁+ λ₂ = 0

∂L

∂x2 = −0, 12 + 0, 016x₂λ₁ − 0, 006x₁λ₁+ λ₂ = 0 g₁(x) = 625 − 0, 005x²₁+ 0, 006x₁x₂− 0, 008x²₂ ≥ 0 g₂(x) = 1000 − x₁− x₂ ≥ 0 625λ₂ − 0, 005x²₁λ₂+ 0, 006x₁x₂λ₂− 0, 008x²₂λ₂ = 0 1000λ₁− x₁λ₁− x₂λ₁ = 0

λ₁ ≥ 0

λ₂ ≥ 0

Consideriamo i seguenti quattro casi.

Caso 1

Entrambi i vincoli sono attivi.

Dal sistema

625 − 0, 005x²₁+ 0, 006x₁x₂− 0, 008x²₂ = 0

1000 − x₁− x₂ = 0

si ottiene l’equazione

0, 019x²₂− 16x₂+ 4375 = 0 che non ha soluzioni reali.

Caso 2

E attivo il solo vincolo g` ₁(x) (λ₂ = 0). Controlliamo la condizione di qualificazione, si ha:

∇g₁ =

−0, 01x₁+ 0, 006x₂ 0, 006x1− 0, 016x2

che si annulla solo nell’origine, non appartenente alla regione in esame (g₁(x) attivo). Non si hanno quindi punti che non soddisfano la condizione di qualificazione. Dalle KKT, si ottiene il seguente sistema di equazioni

∂L

∂x1 = −0, 1 + 0, 01x₁λ₁− 0, 006x₂λ₁ = 0

∂L

∂x2 = −0, 12 + 0, 016x₂λ₁− 0, 006x₁λ₁ = 0 g₁(x) = 625 − 0, 005x²₁+ 0, 006x₁x₂− 0, 008x²₂ = 0

Esplicitando le prime due equazioni rispetto a λ₁, ed uguagliando le due espressioni si ottiene

0, 1

0, 01x₁− 0, 006x₂ = 0, 12

0, 016x₂− 0, 006x₁

(20)

e quindi x₁ = 1, 29x₂. Sostituendo x₁ nella terza equazione si ottiene la soluzione x₂ = 269.9 e x₁ = 348.1.

Caso 3

E attivo il solo vincolo g` ₂(x) (λ₁ = 0). In questo caso ∇g₂(x) `e costante e la condizione di qualificazione `e banalmente soddisfatta. Le prime due condizioni KKT diventano

∂L

∂x1 = −0, 1 + λ₂ = 0

∂L

∂x2 = −0, 12 + λ₂ = 0 e quindi il sistema non ha soluzione.

Caso 4

Entrambi i vincoli non sono attivi (λ₁ = λ₂ = 0).

La prima condizione diventa

∂L

∂x1 = −0, 1 = 0

e quindi il sistema non ha soluzione.

Il minimo globale del problema `e quindi x₁ = 348.1 e x₂ = 269.9.

9

Dato il seguente problema di ottimizzazione min 2x³₁+ 3x2

s.t. x²₁+ x²₂ ≤ 1 2x²₁+ x₂− 1 ≥ 0

dire cosa succede nei punti A = (−1, 0), B = (1/√

2, 0), C = (0, 1).

La regione ammissibile `e quella disegnata in Figura 6.

Soluzione. Innanzitutto, riscriviamo il sistema nella forma canonica.

min 2x³₁+ 3x₂

s.t. −x²₁− x²₂+ 1 ≥ 0 2x²₁+ x₂− 1 ≥ 0 La funzione lagrangiana `e

L(x, λ) = 2x³₁+ 3x₂ − λ₁(−x²₁− x²₂+ 1) − λ₂(2x²₁+ x₂ − 1)

(21)

e le condizioni KKT impongono che in ogni punto di minimo che sia anche regolare, in cui cio`e sia soddisfatta la condizione di qualificazione dei vincoli attivi, si abbia:

∂L

∂x1 = 6x²₁+ 2λ₁x₁− 4λ₂x₁ = 0

∂L

∂x2 = 3 + 2λ₁x₂− λ₂ = 0 λ₁(−x²₁ − x²₂ + 1) = 0 λ₂(2x²₁+ x₂− 1) = 0

−x²₁− x²₂+ 1 ≥ 0 2x²₁+ x₂− 1 ≥ 0 λ₁ ≥ 0

λ2 ≥ 0

Consideriamo il punto A. Il solo vincolo attivo è il primo, il cui gradiente è non nullo in A, e dunque A è un punto di regolarità. Per la condizione di complementarietà, deve aversi λ₂ = 0, per cui la seconda condizione KKT diventa

3 = 0

Dunque, il punto A non è un punto di minimo. Consideriamo ora il punto B. Il solo vincolo attivo è il secondo, il cui gradiente è non nullo in B, e dunque, B è un punto di regolarità. Per la condizione di complementarietà, deve aversi λ₁ = 0, per cui si ha il sistema

3 − 2√

2λ₂ = 0 3 − λ₂ = 0

che non ha soluzione. Dunque, il punto B non `e un punto di minimo locale. Consid- eriamo ora il punto C. In C sono attivi entrambi i vincoli, e i loro gradienti ∇g₁(x) = [−2x₁, −2x₂]^T e ∇g₂(x) = [4x₁, 1]^T nel punto C diventano ∇g₁(C) = [0, −2]^T e ∇g₂(C) = [0, 1]^T, che sono tra loro linearmente dipendenti. Quindi, il punto non `e un punto di

(22)

regolarità, e come tale, non è tenuto a soddisfare le condizioni KKT. Si conclude allora che anche C può essere un punto di minimo locale.

10

Si risolva il seguente problema di ottimizzazione max x²₁+ 3x₂

s.t. x₂ ≤ x₁+ 1

x₁ ≥ 0

x₁ ≤ 3

Soluzione. Riscriviamo il sistema nella forma canonica.

min −x²₁− 3x₂

s.t. x₁− x₂+ 1 ≥ 0

x1 ≥ 0

−x₁+ 3 ≥ 0

La regione ammissibile `e riportata in Figura 7. Si noti che la regione ammissibile `e

convessa, i vincoli sono lineari, ma la funzione obiettivo `e concava. Poich´e i vincoli sono lineari le condizioni KKT sono necessarie di minimo locale anche nei punti che non soddisfano la condizione di qualificazione.

Imponendo ora le condizioni KKT, abbiamo

L(x, λ) = −x²₁− 3x₂− λ₁(x₁− x₂+ 1) − λ₂(x₁) − λ₃(−x₁+ 3)

(23)

e quindi abbiamo il sistema:

∂L

∂x1 = −2x1− λ1− λ2+ λ3 = 0

∂L

∂x2 = −3 + λ₁ = 0 λ₁(x₁− x₂+ 1) = 0 λ₂x₁ = 0

λ₃(−x₁ + 3) = 0 x₁− x₂+ 1 ≥ 0 x₁ ≥ 0

−x₁+ 3 ≥ 0 λ₁ ≥ 0 λ₂ ≥ 0

Appare evidente dalla seconda equazione che il solo valore λ₁ = 3 è possibile. Quindi, per la complementarietà, i soli punti che si trovano sulla retta x₁− x₂ + 1 = 0 possono soddisfare le condizioni KKT. Consideriamo allora, tra tutti i diversi casi, quelli in cui il primo vincolo è attivo:

Caso 1: solo il vincolo 1 attivo. In questo caso, si ha λ₂ = 0, λ₃ = 0, per cui il sistema diventa

−2x₁− 3 = 0 x₁− x₂+ 1 = 0

che ha come soluzione il punto A = (−³₂, −¹₂). Il punto A non appartiene alla regione ammissibile.

Caso 2: vincoli 1 e 2 attivi Abbiamo in questo caso, λ₃ = 0, per cui il sistema diventa:

−2x₁− 3 − λ₂ = 0 x₁− x₂+ 1 = 0 x₁ = 0

che ha come soluzione il punto B=(0, 1). Tuttavia, risolvendo il sistema, troviamo λ₂ =

−3. Dunque, il punto B non pu´o essere un punto di minimo.

Caso 3: vincoli 1 e 3 attivi Abbiamo in questo caso, λ₂ = 0, per cui il sistema diventa:

−2x₁− 3 + λ₃ = 0 λ₂x₁ = 0

x₁− x₂+ 1 = 0

−x₁+ 3 = 0

da cui otteniamo il punto C=(3, 4) per λ₃ = 9. Dunque, il punto C `e un possibile punto di minimo locale per la funzione.

(24)

11

Sia dato il seguente problema di ottimizzazione min x³₁− 2x²₁x₂+ x₂

s.t. x²₁+ x²₂ ≤ 1

Dire se nei punti A=(0, 0) e B=(1, 0) la direzione d = (−1, −1)^T `e una direzione di discesa ammissibile.

Soluzione. Riscriviamo il problema nella forma:

min x³₁− 2x²₁x₂+ x₂ s.t. 1 − x²₁− x²₂ ≥ 0

Perch´e d = (−1, −1)^T sia direzione di discesa, occorre che ∇f^Td < 0, cio`e (3x²₁ − 4x₁x₂, −2x²₁+ 1)^T(−1, −1) < 0

Nel punto A abbiamo

(0, 1)^T(−1, −1) = −1 < 0 e nel punto B abbiamo

(3, −1)^T(−1, −1) = −2 < 0

Verifichiamo ora l’ammissibilità della direzione d a partire dai punti A e B. In A il vincolo non è attivo e quindi ogni direzione è ammissibile. In B il vincolo è attivo. Quindi, perché d sia ammissibile si deve avere ∇g(B)^Td ≥ 0. Numericamente, troviamo

∇g(B)^Td = (−2, 0)^T(−1, −1) = 2 > 0

dunque nel punto B la direzione d risulta essere una direzione di discesa ammissibile.

12

min −x³₁− x₂

g₁(x) = x²₁ + x²₂ ≤ 4 g₂(x) = x²₁+ 4x²₂ ≥ 4 g₃(x) = x₁− x₂ ≤ 0

(25)

Quali di questi punti A = (−2, 0), B = (²₅√ 5,²₅√

5) e C = (0, 1) possono essere punti di minimo locale?

Soluzione. Nel punto A sono attivi i vincoli g₁ e g₂. Le condizioni di qualificazione dei vincoli attivi in A portano allo Jacobiano J (A) =

"

−4 0

#

. Le due righe sono linearmente dipendenti, quindi nel punto A le condizioni di qualificazione dei vincoli non sono rispettate e non si pu`o escludere che il punto sia di minimo. Nel punto B sono attivi i vincoli g2 e g3, quindi λ1 = 0. Le condizioni di qualificazione dei vincoli sono rispettate, infatti le colonne dello Jacobiano sono Linearmente Indipendenti J (B) =

" ₄

5

√5 ¹⁶₅ √ 5

1 −1

#

. Risolvendo le condizioni di KKT si ottiene λ2 = − ¹⁷

25

√

(5) (λ3 = ¹⁴⁷₁₂₅), quindi le condizioni di KKT non sono verificate. Il punto B si pu`o escludere che sia un punto di minimo. Nel punto C risulta attivo solo il vincolo g2, e le condizioni di qualificazione sono rispettate.

In C vale λ₁ = 0 e λ₃ = 0 le condizioni di KKT portano a λ₂ = −¹₈ e quindi non sono rispettate. Il punto C si pu`o escludere che sia un punto di minimo.

13

min x²₁+ 2x³₂

g₁(x) = x²₁+ x²₂ ≤ 1 g₂(x) = x₁+ x²₂ ≥ 1 g₃(x) = −x₁+ x²₂ ≤ 1

Quali di questi punti A = (1, 0), B = (0, 1), C = (−1, 0) possono essere punti di minimo locale?

Soluzione. Nel punto A sono attivi i vincoli g₁ e g₂. Le condizioni di qualificazione dei vincoli attivi in A portano allo Jacobiano J (A) =

"

2 1 0 0

#

. Le due colonne sono Linearmente Dipendenti, quindi nel punto A le condizioni di qualificazione dei vincoli non sono rispettate e non si può escludere che il punto sia di minimo. Nel punto B risultano attivi tutti e tre i vincoli, e quindi le condizioni di qualificazione dei vincoli non sono rispettate e non si può escludere che il punto sia di minimo. Il punto C è fuori dalla regione ammissibile (violato il vincolo g₂) e sicuramente non può essere punto di minimo.

(26)

14

Si consideri il problema min −x²₁+ x₂

g₁(x) = x₁+ x₂− 1 ≥ 0 g2(x) = 1 − x²₁− x²₂ ≥ 0

• Il punto di minimo di questo problema `e il punto A = [1 0]^T. Verificare che tale punto soddisfa le condizioni necessarie di ottimalit`a.

• Supponendo che il secondo vincolo subisca una piccolissima variazione, diventando 1 − x²₁ − x²₂ ≥ −||∇g₂(A)||

In che misura il valore ottimo della funzione obiettivo `e influenzato da ?

Soluzione. Nel punto A sono attivi i vincoli g1 e g2. Le condizioni di qualificazione dei vincoli attivi in A portano allo Jacobiano J (A) =

"

1 −2

1 0

#

. Le due colonne sono Linearmente Indipendenti, e le condizioni di qualificazione dei vincoli sono rispettate. Le condizioni di KKT calcolate in A portano a λ₁ = 1 e λ₂ = ³₂ e sono rispettate. Il punto A rispetta le condizioni necessarie di ottimalità. La sensibilità della funzione obiettivo alla variazione del vincolo g₂ di è pari a ^df_d = −||∇g₂(A)||λ₂ = −2³₂ = −3.

15

Indichiamo con P1 e P2 i seguenti problemi di ottimizzazione:

min 4x³₁+ x²₂+ 3

−2x²₁+ x₂− 3 = 0

min 4x³₁+ x²₂+ 3

−2x²₁+ x₂− 3 ≥ 0

Si considerino il punto x = [1 5]^T e la direzione d = [−1 − 3]^T. Per ciascuno dei due problemi P1 e P2, rispondere alle seguenti domande: Partendo dal punto x, la direzione d `e una direzione di discesa ammissibile?

(27)

Soluzione. La direzione d nel problema P1 `e direzione di discesa (∇f (x)^Td = −12−30 ≤ 0) ma non una direzione ammissibile (essendo il vincolo di uguaglianza una direzione ammissibile deve essere ortogonale al gradiente del vincolo nel punto). Infatti ∇g(x)^Td = 4−3 6= 0. La direzione d nel problema P2 `e direzione di discesa (∇f (x)^Td = −12−30 ≤ 0) e ammissibile (∇g(x)^Td = 4 − 3 ≥ 0).

Esercizi proposti 16

min x₁+ x²₂

g₁(x) = 4x²₁ − x₂+ 2 ≥ 0 g2(x) = −x1+ x²₂ ≥ 0 g₃(x) = −x₁x₂+ 1 ≥ 0 g₄(x) = x₁ ≥ 0 g₅(x) = −x₂+ 2 ≥ 0

• Si considerino i punti A = (0, 2), B = (1/2, 2) e C = (3/4, 4/3) e si discuta se ciascuno di essi pu`o essere un punto di minimo locale.

• Partendo dal punto D = (1, 1), la direzione d = [−1 1]^T `e una direzione di discesa?

E una direzione ammissibile?`

17

Indichiamo con P1 e P2 i seguenti problemi di ottimizzazione:

min x²₁+ x²₂− x₁x₂

x²₁+ x²₂ = 1

min x²₁+ x²₂− x₁x₂

x²₁+ x²₂ ≤ 1

Si considerino il punto x = [1 0]^T e la direzione d = [−1 − 1]^T. Per ciascuno dei due problemi P1 e P2, determinare se d `e una direzione di discesa ammissibile.

(28)

18

Si consideri il problema min x₁+ 3x₂

g₁(x) = x²₁+ x²₂ ≤ 2 g₂(x) = x₁+ x₂ ≥ 0

la cui soluzione ottima `e x^∗ = (1, −1). Supponiamo ora che il secondo vincolo subisca una piccolissima variazione, diventando

x₁+ x₂ ≥ −||∇g₂(x^∗)||

In che misura il valore ottimo della funzione obiettivo `e influenzato da , ossia quanto vale

df

d nell’intorno di x^∗?

19

min x²₁− 2x₁x₂+ 3x₂

−x²₁ − x²₂ ≥ −4

−x₁+ x₂ ≥ −2 x²₁ − x₂ ≥ 2

Si considerino i punti A = (0, 0), B = (0, −2), C = (2, 0), D = (√

3, 1) e si discuta se ciascuno di essi pu`o essere un punto di minimo locale.

Soluzione. Nel punto A nessun vincolo risulta attivo e le condizioni di KKT non sono rispettate. Nel punto B sono attivi tutti i vincoli e le condizioni di KKT sono rispettate. Nel punto C risultano attivi i primi due vincoli ma le condizioni di KKT non sono rispettate. Nel punto D risulta attivo il terzo vincolo e le condizioni di KKT non sono rispettate. Le condizioni di qualificazione dei vincoli sono rispettate in tutti i punti ad eccezione del punto B. Non si pu`o quindi escludere che il punto B sia un punto di minimo.

20

min x²₁− 2x²₂+ 3x₁+ 2x₂