Introduzione

Modulo di Ottimizzazione

Stefano GualandiUniversità di Pavia, Dipartimento di Matematica

email: stefano.gualandi@unipv.ittwitter: @famo2spaghi, @famo2contiblog: http://stegua.github.com

Introduzione

Introduzione

Ottimizzazione senza vincoliIn questa parte del corso tratteremo problemi di ottimizzazionesenza vincoli:

min{f (x) : x ∈ Rn} (1)

in cui la funzione obiettivo è del tipo f : Rn → R.

Minimo globaleIdealmente, i metodi che presenteremo hanno lo scopo diindividuare un vettore x∗ ∈ Rn tale che:

f (x∗) ≤ f (x), ∀x ∈ Rn. (2)

AttenzioneEsistono tuttavia una seria di difficoltà che rendono tale ricercaspesso troppo ambiziosa.

Introduzione

Introduzione

Ottimizzazione senza vincoliIn questa parte del corso tratteremo problemi di ottimizzazionesenza vincoli:

min{f (x) : x ∈ Rn} (1)

in cui la funzione obiettivo è del tipo f : Rn → R.

Minimo globaleIdealmente, i metodi che presenteremo hanno lo scopo diindividuare un vettore x∗ ∈ Rn tale che:

f (x∗) ≤ f (x), ∀x ∈ Rn. (2)

AttenzioneEsistono tuttavia una seria di difficoltà che rendono tale ricercaspesso troppo ambiziosa.

Introduzione

Introduzione

Ottimizzazione senza vincoliIn questa parte del corso tratteremo problemi di ottimizzazionesenza vincoli:

min{f (x) : x ∈ Rn} (1)

in cui la funzione obiettivo è del tipo f : Rn → R.

Minimo globaleIdealmente, i metodi che presenteremo hanno lo scopo diindividuare un vettore x∗ ∈ Rn tale che:

f (x∗) ≤ f (x), ∀x ∈ Rn. (2)

AttenzioneEsistono tuttavia una seria di difficoltà che rendono tale ricercaspesso troppo ambiziosa.

Introduzione

Introduzione

Esempio 1Si trovi il minimo della funzione:

f (x) = x3

Esempio 2Si trovi il minimo della funzione:

f (x) = e−x

Esempio 3Si trovi il minimo della funzione:

f (x) = x2 cos(x)

Introduzione

Introduzione

Esempio 1Si trovi il minimo della funzione:

f (x) = x3

Esempio 2Si trovi il minimo della funzione:

f (x) = e−x

Esempio 3Si trovi il minimo della funzione:

f (x) = x2 cos(x)

Introduzione

Introduzione

Esempio 1Si trovi il minimo della funzione:

f (x) = x3

Esempio 2Si trovi il minimo della funzione:

f (x) = e−x

Esempio 3Si trovi il minimo della funzione:

f (x) = x2 cos(x)

Introduzione

Introduzione

Esempio 1Si trovi il minimo della funzione:

f (x) = x3

Esempio 2Si trovi il minimo della funzione:

f (x) = e−x

Esempio 3Si trovi il minimo della funzione:

f (x) = x2 cos(x)

Introduzione

Introduzione

Esempio 1Si trovi il minimo della funzione:

f (x) = x3

Esempio 2Si trovi il minimo della funzione:

f (x) = e−x

Esempio 3Si trovi il minimo della funzione:

f (x) = x2 cos(x)

Introduzione

Introduzione

Esempio 1Si trovi il minimo della funzione:

f (x) = x3

Esempio 2Si trovi il minimo della funzione:

f (x) = e−x

Esempio 3Si trovi il minimo della funzione:

f (x) = x2 cos(x)

Introduzione

Minimo relativo o localeNell’ultimo esempio, si può solo arrivare a individuare un x∗ cheminimizza f (x) localmente, ma non globalmente; ciò significa chela (2) non vale per tutti gli x ∈ Rn, ma solo in un opportunointorno di x∗.

Definition 1 (Minimo relativo)x∗ ∈ Rn è un punto di minimo relativo di f (x) se esiste unintorno di x∗ di raggio ρ > 0, indicato con B(x∗; ρ), tale che:

f (x∗) ≤ f (x), ∀x ∈ B(x∗; ρ) ⊂ Rn (3)

Definition 2 (Minimo globale)x∗ ∈ Rn è un punto di minimo globale di f (x) se:

f (x∗) ≤ f (x), ∀x ∈ Rn (4)

Introduzione

Minimo relativo o localeNell’ultimo esempio, si può solo arrivare a individuare un x∗ cheminimizza f (x) localmente, ma non globalmente; ciò significa chela (2) non vale per tutti gli x ∈ Rn, ma solo in un opportunointorno di x∗.

Definition 1 (Minimo relativo)x∗ ∈ Rn è un punto di minimo relativo di f (x) se esiste unintorno di x∗ di raggio ρ > 0, indicato con B(x∗; ρ), tale che:

f (x∗) ≤ f (x), ∀x ∈ B(x∗; ρ) ⊂ Rn (3)

Definition 2 (Minimo globale)x∗ ∈ Rn è un punto di minimo globale di f (x) se:

f (x∗) ≤ f (x), ∀x ∈ Rn (4)

Introduzione

Minimo relativo o localeNell’ultimo esempio, si può solo arrivare a individuare un x∗ cheminimizza f (x) localmente, ma non globalmente; ciò significa chela (2) non vale per tutti gli x ∈ Rn, ma solo in un opportunointorno di x∗.

Definition 1 (Minimo relativo)x∗ ∈ Rn è un punto di minimo relativo di f (x) se esiste unintorno di x∗ di raggio ρ > 0, indicato con B(x∗; ρ), tale che:

f (x∗) ≤ f (x), ∀x ∈ B(x∗; ρ) ⊂ Rn (3)

Definition 2 (Minimo globale)x∗ ∈ Rn è un punto di minimo globale di f (x) se:

f (x∗) ≤ f (x), ∀x ∈ Rn (4)

Introduzione

Esempio 1

Si consideri la funzione f : R2 → R, definita da:

f (x , y) = (x2 + 3 y2)e1−x2−y2

Osservare la sua rappresentazione grafica e le sue curve di livello(demo Matlab).

Definition 3 (Grafico di f (x))Il grafico di una funzione z = f (x , y) è la superficie S formata datutti i punti (x , y , f (x , y)).

Introduzione

Esempio 1

Si consideri la funzione f : R2 → R, definita da:

f (x , y) = (x2 + 3 y2)e1−x2−y2

Osservare la sua rappresentazione grafica e le sue curve di livello(demo Matlab).

Definition 3 (Grafico di f (x))Il grafico di una funzione z = f (x , y) è la superficie S formata datutti i punti (x , y , f (x , y)).

Introduzione

Demo web

DEMO WEB:http://www.benfrederickson.com/numerical-optimization/

Introduzione

Notazione

In questi lucidi e nelle dispense, i vettori sono da intendersicome vettori colonna

Il vettore x∗ denota una soluzione ottima del problema (1)

x o xk indicano un vettore di Rn

{xk}k≥0 è una sequenza di vettori (possibili soluzioni)generate sino al passo k

La componente di indice i di un vettore x viene indicata con(x)i e del vettore xk con (xk)i

Introduzione

Notazione

In questi lucidi e nelle dispense, i vettori sono da intendersicome vettori colonna

Il vettore x∗ denota una soluzione ottima del problema (1)

x o xk indicano un vettore di Rn

{xk}k≥0 è una sequenza di vettori (possibili soluzioni)generate sino al passo k

La componente di indice i di un vettore x viene indicata con(x)i e del vettore xk con (xk)i

Introduzione

Notazione

In questi lucidi e nelle dispense, i vettori sono da intendersicome vettori colonna

Il vettore x∗ denota una soluzione ottima del problema (1)

x o xk indicano un vettore di Rn

{xk}k≥0 è una sequenza di vettori (possibili soluzioni)generate sino al passo k

La componente di indice i di un vettore x viene indicata con(x)i e del vettore xk con (xk)i

Introduzione

Notazione

In questi lucidi e nelle dispense, i vettori sono da intendersicome vettori colonna

Il vettore x∗ denota una soluzione ottima del problema (1)

x o xk indicano un vettore di Rn

{xk}k≥0 è una sequenza di vettori (possibili soluzioni)generate sino al passo k

La componente di indice i di un vettore x viene indicata con(x)i e del vettore xk con (xk)i

Introduzione

Notazione

In questi lucidi e nelle dispense, i vettori sono da intendersicome vettori colonna

Il vettore x∗ denota una soluzione ottima del problema (1)

x o xk indicano un vettore di Rn

{xk}k≥0 è una sequenza di vettori (possibili soluzioni)generate sino al passo k

La componente di indice i di un vettore x viene indicata con(x)i e del vettore xk con (xk)i