Problema di ottimizzazione continua

(1)

Problema di ottimizzazione continua

min

x∈S

f(x)

con regione ammissibile S ⊆ Rⁿ contenente un’infinità non numerabile di punti.

(2)

Problema di ottimizzazione continua

min

x∈S

f(x)

con regione ammissibile S ⊆ Rⁿ contenente un’infinità non numerabile di punti.

Va sottolineato che il fatto di restringere l’attenzione a soli problemi di minimo non è una restrizione reale in quanto l’uguaglianza

max

x∈S

f(x) = − min

x∈S −f(x)

(3)

Ottimizzazione vincolata e non

Se S = Rⁿ, si parla di problemi di ottimizzazione non vincolata.

(4)

Ottimizzazione vincolata e non

Se S è definita attraverso equazioni e/o disequazioni, cioè:

S = {x ∈ Rⁿ : g_i(x) ≤ 0, i ∈ I¹, g_i(x) = 0, i ∈ I²}.

si parla di problemi di ottimizzazione vincolata.

(5)

Ottimizzazione vincolata e non

Se S è definita attraverso equazioni e/o disequazioni, cioè:

S = {x ∈ Rⁿ : g_i(x) ≤ 0, i ∈ I¹, g_i(x) = 0, i ∈ I²}.

si parla di problemi di ottimizzazione vincolata.

Si osservi che quest’ultima classe di problemi comprende come sottocaso i problemi di PL dove la funzione f e le funzioni g_i sono funzioni lineari.

(6)

Domanda

Esiste sempre una soluzione del problema?

(7)

Domanda

Nei problemi di ottimizzazione combinatoria con regione ammissibile formata da un numero finito di punti la risposta era sempre affermativa. Ma qui la risposta può essere

negativa.

(8)

Domanda

Nei problemi di ottimizzazione combinatoria con regione ammissibile formata da un numero finito di punti la risposta era sempre affermativa. Ma qui la risposta può essere

negativa.

Esempio di non esistenza della soluzione già noto: il caso di illimitatezza nella PL.

(9)

Esempi

f(x) = x³ Il minimo di questa funzione su S = R non esiste in quanto la funzione può essere fatta

decrementare a piacere spostandosi verso _−∞.

(10)

Esempi

f(x) = e⁻^x In questo caso la funzione non può essere decrementata a piacere su S = R (essa non scende

mai sotto il valore 0) ma nessun punto in R ha un valore non superiore rispetto a tutti gli altri.

(11)

Esempi

f(x) = e⁻^x In questo caso la funzione non può essere decrementata a piacere su S = R (essa non scende

mai sotto il valore 0) ma nessun punto in R ha un valore non superiore rispetto a tutti gli altri.

Per l’ottimizzazione vincolata ricordiamo che se f è

continua e S è un insieme compatto (chiuso e limitato), allora il teorema di Weierstrass ci garantisce l’esistenza di una soluzione ottima.

(12)

Ottimi globali e locali

Ottimo globale: punto x^∗ ∈ S tale che

f(x^∗) ≤ f(x) ∀ x ∈ S.

Può essere estremamente difficile da determinare.

(13)

Ottimi globali e locali

Ottimo globale: punto x^∗ ∈ S tale che

f(x^∗) ≤ f(x) ∀ x ∈ S.

Può essere estremamente difficile da determinare.

Tipicamente più semplice determinare un ottimo locale.

Definizione Un punto x^′ si definisce ottimo locale della funzione f se esiste un ε > 0 e un intorno di x^′

N(x^′, ε) = {y ∈ Rⁿ : ky − x^′k ≤ ε},

(14)

Nota bene

Ogni ottimo globale (se esiste) è anche un ottimo locale mentre non è vero il viceversa.

(15)

Nota bene

In alcuni casi esistono ottimi locali ma non ottimi globali. Ad esempio la funzione f(x) = x³ − 3x ha un ottimo locale

x^′ = 1 ma non ha ottimi globali.

(16)

Nota bene

In alcuni casi esistono ottimi locali ma non ottimi globali. Ad esempio la funzione f(x) = x³ − 3x ha un ottimo locale

x^′ = 1 ma non ha ottimi globali.

Ci sono però anche casi più semplici in cui tutti gli ottimi locali sono anche ottimi globali.

(17)

Funzione convessa

Una funzione f si dice convessa su un insieme convesso S se _{∀ x}¹, x2 ∈ S e ∀ λ ∈ (0, 1):

f(λx¹ + (1 − λ)x²) ≤ λf(x¹) + (1 − λ)f(x²).

Si dice strettamente convessa se _{∀ x}¹, x² ∈ S e ∀ λ ∈ (0, 1): f(λx¹ + (1 − λ)x²) < λf (x¹) + (1 − λ)f(x²).

(18)

Teorema

Se f è una funzione convessa e S è un insieme convesso, allora ogni ottimo locale x^′ di f su S (se ne esistono) è

anche un ottimo globale. Se f è strettamente convessa può esistere un solo ottimo globale.

(19)

Dimostrazione

Ragioniamo per assurdo e supponiamo che l’ottimo locale x^′ non sia un ottimo globale.

(20)

Dimostrazione

Quindi esiste y ∈ S tale che f(y) < f (x^′).

(21)

Dimostrazione

Quindi esiste y ∈ S tale che f(y) < f (x^′). Dato il segmento

λx^′ + (1 − λ)y λ ∈ [0, 1].

esso è interamente contenuto in S per la convessità di S. Inoltre la convessità di f implica che ∀ λ ∈ (0, 1):

f(λx^′ + (1 − λ)y) ≤ λf (x^′) + (1 − λ)f (y) < λf (x^′) + (1 − λ)f (x^′) = f (x^′).

(22)

Continua

Quindi: ogni punto sul segmento ha valore della funzione strettamente minore di f(x^′).

(23)

Continua

Quindi: ogni punto sul segmento ha valore della funzione strettamente minore di f(x^′).

Dal momento che per ogni ε > 0 l’intorno N(x^′, ε) di x^′ contiene almeno un punto del segmento diverso da x^′, questo contraddice il fatto che x^′ sia un ottimo locale.

(24)

Continua

Se f è strettamente convessa per assurdo siano x^∗₁, x^∗₂ ∈ S due ottimi globali distinti con, ovviamente, f(x^∗₁) = f (x^∗₂).

(25)

Continua

Se f è strettamente convessa per assurdo siano x^∗₁, x^∗₂ ∈ S due ottimi globali distinti con, ovviamente, f(x^∗₁) = f (x^∗₂). Allora, in base alla definizione di funzione strettamente convessa si ha che ∀ λ ∈ (0, 1):

f(λx^∗₁ + (1 − λ)x^∗₂) < λf (x^∗₁) + (1 − λ)f (x^∗₂) = λf (x^∗₁) + (1 − λ)f (x^∗₁) = f (x^∗₁).

(26)

Continua

Se f è strettamente convessa per assurdo siano x^∗₁, x^∗₂ ∈ S due ottimi globali distinti con, ovviamente, f(x^∗₁) = f (x^∗₂). Allora, in base alla definizione di funzione strettamente convessa si ha che ∀ λ ∈ (0, 1):

f(λx^∗₁ + (1 − λ)x^∗₂) < λf (x^∗₁) + (1 − λ)f (x^∗₂) = λf (x^∗₁) + (1 − λ)f (x^∗₁) = f (x^∗₁).

Quindi tutti i punti del segmento diversi da x^∗₁ e x^∗₂ (tutti appartenenti a S per la convessità di S) hanno valore della funzione minore di f(x^∗₁) e f(x^∗₂) il che contraddice il fatto che ^x^∗₁ e ^x^∗₂ siano ottimi globali.

(27)

Funzioni quadratiche

Sono funzioni di n variabili in cui compaiono termini al massimo di secondo grado:

f(x¹, . . . , x_n) = 1 2

n

X

i=1 n

X

j=1

a_ijx_ix_j +

n

X

i=1

b_ix_i

(28)

Funzioni quadratiche

Sono funzioni di n variabili in cui compaiono termini al massimo di secondo grado:

f(x¹, . . . , x_n) = 1 2

n

X

i=1 n

X

j=1

a_ijx_ix_j +

n

X

i=1

b_ix_i

Possiamo anche rappresentarla in forma matriciale, con l’introduzione di una matrice simmetrica ^A di ordine n × n con entrate a_ij, di un vettore b con le n componenti b_i e con il vettore x delle n variabili:

(29)

Esempio

f(x¹, x²) = 2x²1 + 3x²2 + 2x¹x² + 5x¹ + 3x²

(30)

Esempio

f(x¹, x²) = 2x²1 + 3x²2 + 2x¹x² + 5x¹ + 3x² Matrice A:

"

4 2 2 6

#

(31)

Esempio

f(x¹, x²) = 2x²1 + 3x²2 + 2x¹x² + 5x¹ + 3x² Matrice A:

"

4 2 2 6

#

Vettore ^b:

"

5 3

#

(32)

Convessità

La sola analisi della matrice ^A ci consente di individuare quali tra le funzioni quadratiche sono convesse e

strettamente convesse.

(33)

Positività

Una matrice simmetrica A si dice semidefinita positiva se

∀ x ∈ Rⁿ : xAx ≥ 0.

(34)

Positività

∀ x ∈ Rⁿ : xAx ≥ 0.

Equivalentemente, A è semidefinita positiva se tutti i suoi autovalori sono non negativi.

(35)

Positività

∀ x ∈ Rⁿ : xAx ≥ 0.

Una matrice simmetrica ^A si dice definita positiva se

∀ x ∈ Rⁿ \ {0} : xAx > 0.

(36)

Positività

∀ x ∈ Rⁿ : xAx ≥ 0.

Una matrice simmetrica ^A si dice definita positiva se

∀ x ∈ Rⁿ \ {0} : xAx > 0.

Equivalentemente, ^A è definita positiva se tutti i suoi

(37)

Calcolo degli autovalori

Data una matrice ^A, i suoi autovalori sono le radici della seguente equazione:

det(A − λI) = 0 dove ^I è la matrice identica.

(38)

Esempio

A − λI =

"

4 − λ 2 2 6 − λ

#

(39)

Esempio

A − λI =

"

4 − λ 2 2 6 − λ

#

det(A − λI) = (4 − λ) × (6 − λ) − 2 × 2 = λ² − 10λ + 20

(40)

Esempio

A − λI =

"

4 − λ 2 2 6 − λ

#

det(A − λI) = (4 − λ) × (6 − λ) − 2 × 2 = λ² − 10λ + 20 Autovalori di ^A:

λ¹ = 5 + √

25 − 20 = 5 + √ 5 λ2 = 5 − √

25 − 20 = 5 − √ 5

(41)

Osservazioni

Osservazione 1 Se A è definita positiva, è anche invertibile e la sua inversa ^A⁻¹ è anch’essa definita positiva.

(42)

Osservazioni

Osservazione 1 Se A è definita positiva, è anche invertibile e la sua inversa ^A⁻¹ è anch’essa definita positiva.

Osservazione 2 Data la funzione quadratica f(x) = 1

2xAx + bx,

essa è convessa se e solo se A è semidefinita positiva. È strettamente convessa se e solo se A è definita positiva.

(43)

Ottimizzazione non vincolata

Restringeremo ora l’attenzione ai problemi di ottimizzazione non vincolata e più precisamente ai soli casi in cui la

funzione f è differenziabile in modo continuo almeno fino al secondo ordine, ovvero la funzione ammette derivate sia prime che seconde continue.

(44)

Condizioni di ottimalità locale

Condizioni necessarie: sono condizioni che devono essere soddisfatte da tutti gli ottimi locali ma che possono essere soddisfatte anche da altri punti.

(45)

Condizioni di ottimalità locale

Condizioni necessarie: sono condizioni che devono essere soddisfatte da tutti gli ottimi locali ma che possono essere soddisfatte anche da altri punti.

Condizioni sufficienti: sono condizioni che, se soddisfatte da un punto, garantiscono che questo sia un ottimo locale ma non sono necessariamente soddisfatte da tutti gli ottimi

locali.

(46)

Espansione in forma di Taylor

Sotto opportune condizioni di differenziabilità della funzione f (differenziabile in modo continuo almeno fino al secondo ordine) si ha che in un intorno di un punto x^′ la funzione f(x) è pari a:

f(x) = f (x^′)+g(x^′)(x−x^′)+1

2(x−x^′)H(x^′)(x−x^′)+o(kx−x^′k²), dove ...

(47)

...

g(x^′) è il gradiente della funzione f in x^′, ovvero un vettore in Rⁿ la cui j-esima componente è:

∂f (x)

∂x_j

x=x^′

.

(48)

...

g(x^′) è il gradiente della funzione f in x^′, ovvero un vettore in Rⁿ la cui j-esima componente è:

∂f (x)

∂x_j

x=x^′

.

H(x^′) è l’hessiano di f in ^x^′, ovvero una matrice in R^n×n che in corrispondenza della riga i e della colonna j ha la derivata seconda:

∂²f(x)

.

(49)

o(kx − x^′k²) è una quantità che al tendere di ^x a ^x^′ è piccola rispetto a _{kx − x}^′_k² (più precisamente converge a 0 più rapidamente di _{kx − x}^′_k² al tendere di x a x^′).

(50)

Esempio

f(x¹, x²) = e^x¹ + x¹x²₂

(51)

Esempio

f(x¹, x²) = e^x¹ + x¹x²₂

g(x¹, x2) =

"

e^x¹ + x²2

2x¹x²

#

(52)

Esempio

f(x¹, x²) = e^x¹ + x¹x²₂

g(x¹, x2) =

"

e^x¹ + x²2

2x¹x²

#

H(x¹, x²) =

"

e^x¹ 2x² 2x² 2x¹

#

(53)

Esempio- continua

Espansione in forma di Taylor nel punto 0 = (0, 0): f(x) = f (0) + g(0)(x − 0) + 1

2(x − 0)H(0)(x − 0) +o(k(x − 0)k²) cioè:

(54)

Esempio- continua

Espansione in forma di Taylor nel punto 0 = (0, 0): f(x) = f (0) + g(0)(x − 0) + 1

2(x − 0)H(0)(x − 0) +o(k(x − 0)k²) cioè:

f(x¹, x²) = 1 + x¹ + 1

2x²₁ + o(x²1 + x²2)

(55)

Teorema

Condizione necessaria perchè un punto x^′ sia un ottimo locale di f è che

g(x^′) = 0.

(56)

Dimostrazione

Per assurdo sia g(x^′) 6= 0 e si considerino i punti x = x^′ − λg(x^′) λ > 0.

(57)

Dimostrazione

Sostituendo nell’espansione di Taylor si ottiene:

f(x) = f (x^′) − λkg(x^′)k² + 1

2λ²[g(x^′)H(x^′)g(x^′)] + o(λ²).

(58)

Dimostrazione

f(x) = f (x^′) − λkg(x^′)k² + 1

2λ²[g(x^′)H(x^′)g(x^′)] + o(λ²).

Se g(x^′) 6= 0, allora _kg(x^′_)k² _{6= 0} e per λ > 0 e

sufficientemente piccolo si ha che il termine dominante, tra quelli in cui compare λ, nell’espressione sopra è _−λkg(x^′_)k²,

(59)

Dimostrazione

f(x) = f (x^′) − λkg(x^′)k² + 1

2λ²[g(x^′)H(x^′)g(x^′)] + o(λ²).

Se g(x^′) 6= 0, allora _kg(x^′_)k² _{6= 0} e per λ > 0 e

sufficientemente piccolo si ha che il termine dominante, tra quelli in cui compare λ, nell’espressione sopra è _−λkg(x^′_)k², cioè per ogni λ > 0 sufficientemente piccolo si ha:

(60)

Condizione necessaria ma ...

... non sufficiente, cioè esistono punti che soddisfano la condizione ma non sono ottimi locali.

(61)

Condizione necessaria ma ...

Esempio: se si considera f(x) = x³ si ha g(x) = 3x² e g(0) = 0 ma x^′ = 0 non è un ottimo locale.

(62)

Condizione necessaria ma ...

Esempio: se si considera f(x) = x³ si ha g(x) = 3x² e g(0) = 0 ma x^′ = 0 non è un ottimo locale.

Punti ^x^′ per i quali g(x^′) = 0 vengono detti punti stazionari. Il teorema appena visto ci dice che se un punto è un ottimo locale, allora è anche un punto stazionario, mentre

l’esempio successivo mostra che non è vero il viceversa, cioè un punto può essere un punto stazionario senza

(63)

Condizione necessaria più forte

g(x^′) = 0.

(64)

Condizione necessaria più forte

g(x^′) = 0.

H(x^′) sia semidefinita positiva.

(65)

Dimostrazione

Abbiamo già dimostrato che deve essere g(x^′) = 0.

(66)

Dimostrazione

Per assurdo sia H(x^′) non semidefinita positiva, cioè esiste d ∈ Rⁿ tale che

dH(x^′)d < 0.

(67)

Dimostrazione

dH(x^′)d < 0.

Si considerino ora i punti

x = x^′ + λd λ > 0.

(68)

Dimostrazione

dH(x^′)d < 0.

Si considerino ora i punti

x = x^′ + λd λ > 0.

Sostituendo nell’espansione di Taylor e ricordando che g(x^′) = 0 si ottiene:

(69)

Continua

Poiché dH(x^′)d < 0, per ogni λ > 0 sufficientemente piccolo si avrà

f(x) ≈ f(x^′) + 1

2λ²[dH(x^′)d] < f (x^′),

il che contraddice il fatto che x^′ sia un ottimo locale.

(70)

Ancora ...

... condizione necessaria ma non sufficiente, cioè esistono punti che soddisfano la condizione ma non sono ottimi

locali.

(71)

Ancora ...

... condizione necessaria ma non sufficiente, cioè esistono punti che soddisfano la condizione ma non sono ottimi

locali.

Esempio: se si considera di nuovo f(x) = x³ si ha

g(x) = 3x², H(x) = 6x e g(0) = 0, H(0) = 0 ma x^′ = 0 non è un ottimo locale.

(72)

Condizione sufficiente

Condizione sufficiente perchè un punto x^′ sia un ottimo locale di f è che

g(x^′) = 0.

(73)

Condizione sufficiente

Condizione sufficiente perchè un punto x^′ sia un ottimo locale di f è che

g(x^′) = 0.

H(x^′) sia definita positiva.

(74)

Sufficiente ma ...

... non necessaria, cioè esistono ottimi locali che non la soddisfano.

(75)

Sufficiente ma ...

... non necessaria, cioè esistono ottimi locali che non la soddisfano.

Esempio: se si considera f(x) = x⁴ si ha

g(x) = 4x³, H(x) = 12x² e g(0) = 0, H(0) = 0, quindi H(0) è semidefinita positiva ma non definita positiva, pur essendo x^′ = 0 un ottimo locale.

(76)

Un esempio in cui funziona

Data

f(x¹, x2) = x²1 + x²2

si ha che

(77)

Un esempio in cui funziona

Data

f(x¹, x2) = x²1 + x²2

si ha che

g(x¹, x²) = 2x¹ 2x²

!

H(x¹, x²) = 2 0 0 2

! .

(78)

Un esempio in cui funziona

Data

f(x¹, x2) = x²1 + x²2

si ha che

g(x¹, x²) = 2x¹ 2x²

!

H(x¹, x²) = 2 0 0 2

! .

Si nota che per il punto (x¹, x²) = (0, 0) si ha che

g(0, 0) = (0, 0) mentre l’hessiano è indipendente da (x¹, x²) ed è sempre definito positivo (essendo una matrice

(79)

Un esempio in cui funziona

Data

f(x¹, x2) = x²1 + x²2

si ha che

g(x¹, x²) = 2x¹ 2x²

!

H(x¹, x²) = 2 0 0 2

! .

Si nota che per il punto (x¹, x²) = (0, 0) si ha che

g(0, 0) = (0, 0) mentre l’hessiano è indipendente da (x¹, x²) ed è sempre definito positivo (essendo una matrice

diagonale i suoi due autovalori coincidono con gli elementi lungo la diagonale e sono entrambi uguali a 2, quindi

(80)

Un caso più semplice: problema convesso

Se f è una funzione convessa, condizione necessaria e

sufficiente perché il punto x^′ sia un ottimo locale è che esso sia un punto stazionario, cioè g(x^′) = 0.

(81)

Funzioni quadratiche

Nel caso di funzioni quadratiche f(x) = bx + 1

2xAx,

si può dimostrare che esse possono avere almeno un ottimo locale (e globale) se e solo se sono convesse (e quindi, equivalentemente, se A è semidefinita positiva).

(82)

Funzioni quadratiche

Nel caso di funzioni quadratiche f(x) = bx + 1

2xAx,

si può dimostrare che esse possono avere almeno un ottimo locale (e globale) se e solo se sono convesse (e quindi, equivalentemente, se A è semidefinita positiva).

Inoltre, hanno un unico ottimo locale (e globale) se e solo se sono strettamente convesse (e quindi,

(83)

Soluzione ottima

Data una funzione quadratica strettamente convessa il suo unico ottimo locale (e globale) è il punto

x^′ = −A⁻¹b.

(84)

Soluzione ottima

x^′ = −A⁻¹b.

Dimostrazione Nel caso convesso gli ottimi locali coincidono con i punti stazionari. Il gradiente di f è il seguente:

g(x) = b + Ax

e quindi se vogliamo trovare l’ottimo locale basta azzerare il gradiente, cioè

(85)

Soluzione ottima

x^′ = −A⁻¹b.

g(x) = b + Ax

e quindi se vogliamo trovare l’ottimo locale basta azzerare il gradiente, cioè l’ottimo locale è la soluzione del seguente sistema:

(86)

Soluzione ottima

x^′ = −A⁻¹b.

g(x) = b + Ax

e quindi se vogliamo trovare l’ottimo locale basta azzerare il gradiente, cioè l’ottimo locale è la soluzione del seguente

(87)

Esempio

Per la funzione quadratica strettamente convessa f(x¹, x²) = 2x²1 + 3x²2 + 2x¹x² + 5x¹ + 3x²

l’ottimo globale si calcola risolvendo il seguente sistema, ottenuto ponendo a 0 tutte le componenti del gradiente:

( 4x¹ + 2x² + 5 = 0 6x² + 2x¹ + 3 = 0 con soluzione:

x^∗₁ = −6

x^∗₂ = − 1