Optimization methods 2022-2023
Indice
- Introduzione
- Definizioni fondamentali
- Algoritmi di ottimizzazione non vincolata
- Analisi dei punti di accumulazione
- Analisi della convergenza asintotica verso la stazionarietà
- Analisi della velocità di convergenza
- Classificazione degli algoritmi di ottimizzazione
- Metodi di tipo Line Search
- Ricerca di linea esatta
- Ricerca di linea inesatta
- Metodo del gradiente
- Complessità degli algoritmi di ottimizzazione
- Metodo del gradiente con passo costante
- Metodo del gradiente accelerato
- Metodo Heavy Ball
- Metodo del gradiente accelerato di Nesterov
- Metodi delle direzioni coniugate
- Metodo di Wolfe
- Metodo di Newton
- Metodo Quasi-Newton
- Metodi Trust-Region
- Metodi Derivative-Free
- Approssimazione alle differenze finite
- Metodi Direct Search
- Algoritmi di ottimizzazione vincolata
- Problemi con insieme ammissibile convesso
- Problemi con vincoli poliedrali
- Problemi con vincoli di box
- Problemi con vincoli di simplesso
- Proiezione su un insieme convesso
- Algoritmi Line Search per problemi vincolati
- Metodo del gradiente proiettato
- Metodo di Frank-Wolfe
- Ottimizzazione con vincoli analitici
- Condizioni di ottimalità di Fritz-John
- Condizioni di ottimalità di Karush-Kuhn-Tucker
- Problema duale di Wolfe
- Metodi di decomposizione
- Metodi sequenziali
- Metodi paralleli
- Metodi con blocchi sovrapposti
- Problemi con insieme ammissibile convesso
- Problemi di ottimizzazione nel machine learning
- Regressione lineare
- Regressione lineare non regolarizzata
- Regressione logistica
- Regressione lineare
- Support Vector Machines
- Metodi di decomposizione per SVM
- Sequential Minimal Optimization
- Algoritmi per SVM lineari
- Metodi di decomposizione per SVM
- Metodi stocastici per problemi di somme finite
- Metodo del Gradiente Stocastico
- Ottimizzazione per Deep Networks
- Miglioramenti ad SGD
- Calcolo del gradiente e Backpropagation
Introduzione
L'ottimizzazione (o programmazione matematica) ha per oggetto lo studio di problemi di decisione, in cui si richiede di determinare i punti di minimo o di massimo di una funzione a valori reali in un insieme prefissato. L'ottimizzazione matematica definisce un modello matematico sulla base di un modello reale, che viene risolto attraverso un algoritmo numerico.
Un problema di ottimizzazione assume una forma del seguente tipo:
min (x) max (x)f fx∈S x∈S
dove x è detta variabile di decisione, S è un insieme ammissibile definito da vincoli ed f è una funzione obiettivo che vogliamo ottimizzare (cioè minimizzare o massimizzare).
N.B: un problema di minimizzazione può essere sempre ricondotto ad un problema di massimizzazione (e viceversa), poiché -fmin (x) = max (x).
Esempio (problema della selezione del portafoglio ottimale secondo Markowitz): Questo problema rappresenta un classico problema di ottimizzazione applicato all’ambito della finanza.
Supponiamo di poter investire su n possibili titoli di borsa, detti asset. Indichiamo con xi la frazione del budget totale disponibile che intendiamo investire sull’asset i-esimo, ovvero la quantità di budget che si vuole investire sull’asset i-esimo, e quindi rappresentano le variabili di decisione. Allora i vincoli saranno:
- xi ≥ 0 ∀i (poiché l’investimento è positivo)
- Σi=1n xi = 1 (poiché investiamo tutto il budget disponibile)
N.B: il vincolo può essere riscritto anche come Σi=1n xi = 1 = 1, e dove T rappresenta un vettore unitario.
Chiamiamo ui il ritorno atteso dall’asset i-esimo (ovvero il valore che otterremmo se investissimo sull’asset i-esimo), e σij la covarianza tra l’asset i-esimo e l’asset j-esimo (se i = j allora σij rappresenta la varianza dell’asset i-esimo e indica quanto l’investimento si sposta dal valore atteso).
N.B: se la covarianza è alta allora significa che l’asset i-esimo e l’asset j-esimo sono fortemente correlati, quindi l’investimento sull’asset j-esimo dipende molto dall’investimento sull’asset i-esimo (cioè se l’asset i-esimo sta andando male, allora con buona probabilità sta andando male anche l’asset j-esimo).
Possiamo quindi scrivere la funzione obiettivo nel seguente modo:
f(x) = xTΣx - μTx
dove xTΣx rappresenta il rischio ed μTx rappresenta il ricavo atteso da tutti gli investimenti (ovvero il ritorno totale).
Allora, il problema di ottimizzazione del portafoglio diventa:
min xTΣx - μTx
s.t. Σi=1n xi = 1
xi ≥ 0
I problemi di ottimizzazione si possono classificare in vario modo, a seconda dello spazio delle variabili, della struttura dell’insieme ammissibile e delle ipotesi sulla funzione obiettivo:
Problemi di ottimizzazione continua:
- Problemi in cui le variabili assumono valori reali, ovvero x ∈ ℝn (il precedente esempio del portafoglio è un tipico problema di ottimizzazione continua). Questi problemi possono essere ulteriormente classificati in:
- Problemi di ottimizzazione lineare: problemi in cui la funzione obiettivo è un prodotto scalare (cioè f(x) = cTx) ed i vincoli sono lineari (cioè Ax ≤ Rb).
- Problemi di ottimizzazione non lineare: possono essere a loro volta classificati in base alla struttura dell’insieme ammissibile e alle ipotesi sulla funzione obiettivo. In particolare distinguiamo:
- Problemi di ottimizzazione differenziabile: problemi in cui è possibile calcolare il gradiente rispetto alla funzione obiettivo (∇f).
- Problemi di ottimizzazione non differenziabile: problemi in cui non è possibile calcolare il gradiente rispetto alla funzione obiettivo (∇f).
Problemi di ottimizzazione vincolata: problemi in cui l’insieme ammissibile appartiene ad un sottoinsieme di ℝn.
Problemi di ottimizzazione non vincolata: problemi in cui l’insieme ammissibile coincide con ℝn (cioè S = ℝn).
Problemi di ottimizzazione intera: problemi in cui le variabili sono intere, ovvero x ∈ ℤn. Un caso particolare di questa categoria è il problema di ottimizzazione binaria, con x ∈ {0, 1}n.
Problemi di ottimizzazione mista-intera: problemi in cui alcune variabili x sono continue, ovvero ℝn, ed altre variabili sono intere, ovvero ℤn.
Esempio (problema di ottimizzazione non lineare): Supponiamo di avere un sistema fisico in cui, dato un input X, otteniamo un output Y. Vogliamo definire un modello matematico (con opportuni parametri) del sistema fisico, per ottenere una stima dell’output Ŷ a partire dallo stesso input X.
A tale scopo è necessario effettuare delle misurazioni sul sistema fisico per ottenere un dataset di osservazioni (xi, yi). Quindi possiamo creare una funzione di errore f(x, u) che mostri quanto l’output ottenuto è distante dall’output atteso Ŷ. L’obiettivo è quello di minimizzare tale errore, cercando i migliori parametri per il modello matematico:
min Σi=1n f(x, u)
Possiamo scegliere differenti funzioni di errore, a seconda delle quali si ottengono differenti problemi di ottimizzazione:
Errore quadratico (least square): e(Ŷ, y) = (Ŷ - y)2
In questo caso il problema di ottimizzazione diventa:
min ||f(x, u) - y||2
Errore assoluto (absolute): e(Ŷ, y) = |Ŷ - y|
In questo caso il problema di ottimizzazione diventa:
min ||f(x, u) - y||1
Esempio (classificazione supervisionata): Vogliamo trovare una relazione sconosciuta f(x) tra gli input x e gli output y. In particolare, vogliamo trovare una funzione f̃(x) che approssima la funzione incognita f(x), la quale genera gli output y a partire dagli input x (ovvero f̃(x) ≈ f(x) ∀x).
N.B: se gli output sono valori reali (ovvero y ∈ ℝ) allora si tratta di un problema di regressione. Invece, se gli output sono valori interi binari (ovvero y ∈ {0, 1}) allora si tratta di un problema di classificazione binaria.
Il problema principale è che la funzione f non è nota. Quindi dobbiamo decidere la classe di funzioni da cui scegliere f̃, detta spazio delle ipotesi H (ad esempio rette, parabole, reti neurali, ecc...). Una volta scelto lo spazio delle ipotesi, f̃ dipenderà dai parametri (detti pesi). Quindi otteniamo una funzione f̃(·; w) ∈ H.
I pesi w vengono scelti attraverso una misura di errore l(f̃(x; w), y), detta loss. In particolare, tali pesi saranno scelti in modo tale da minimizzare la funzione di rischio:
min Ep(x,y)[l(f̃(x; w), y)]
Tuttavia, la distribuzione dei dati p(x, y) è sconosciuta. Nell’apprendimento supervisionato possiamo approssimare tale distribuzione effettuando N misurazioni, da cui otteniamo il dataset D (con |D| = N), e minimizzando la somma degli errori che si commettono su tali misurazioni:
min 1/N Σi=1N l(f̃(xi; w), yi)
dove L(w) prende il nome di Empirical Risk.
Tale Empirical Risk può essere minimizzato. Questa minimizzazione garantisce di avere una buona approssimazione per i dati osservati, ma non garantisce una buona approssimazione per i dati non presenti nel dataset (quindi non osservati). Per questo motivo si aggiunge un parametro di regolarizzazione:
min L(w) + λΩ(w)
dove λ rappresenta un iperparametro ed Ω(w) è detto regolarizzatore (rappresenta una funzione di penalizzazione sui pesi del modello). Generalmente i regolarizzatori utilizzati sono la norma euclidea o la norma uno.
Definizioni fondamentali
Definizione. Una norma è una funzione tale che:
- k · k : ℝn → ℝ ed k x k ≥ 0 se e solo se x = 0 (semidefinita positiva).
- k αx k = |α| k x k ∀x ∈ ℝn ∀α ∈ ℝ (omogenea).
- k x + y k ≤ k x k + k y k ∀x, y ∈ ℝn (disuguaglianza triangolare).
Elenchiamo alcune norme importanti:
- Norma Euclidea (radice quadrata della somma dei quadrati di tutte le componenti): ||x|| = sqrt(Σ xi2)
- Norma 1 (somma dei valori assoluti di tutte le componenti): ||x||1 = Σ |xi|
- Norma infinito (massimo valore dei valori assoluti di tutte le componenti): ||x||∞ = max |xi|
Definizione. Consideriamo il seguente problema di ottimizzazione: (i) min f(x) x∈S
Un punto x* si dice punto di minimo globale per il problema (i) se:
x* ∈ S e f(x*) ≤ f(x) ∀x ∈ S
In questo caso si dice che il valore f(x*) è il minimo globale per il problema (i).
N.B: una soluzione del problema (i), se esiste, viene indicata con la notazione x* ∈ arg minx∈S f(x) (dove arg min rappresenta l’insieme dei punti di S in corrispondenza dei quali la funzione f assume il valore minimo su S).
Osserviamo i casi di non esistenza di una soluzione ottimale:
- S = ∅ (se non abbiamo soluzioni ammissibili, allora non possiamo avere neanche soluzioni ottimali). Ad esempio, se l’insieme ammissibile è definito dai vincoli x ≥ 3, x ≤ 2, allora il problema non ammette soluzioni.
- f è una funzione illimitata inferiormente sull’insieme ammissibile S (in questo caso non troveremo mai un punto di minimo globale).
- Altri casi non banali:
Definizione. Un insieme S si dice aperto se per ogni x ∈ S esiste un ε > 0 tale che B(x, ε) ⊂ S, dove B(x, ε) = {x ∈ ℝn | ||x - x|| ≤ ε}.
Ovvero S si dice aperto se esiste una sfera aperta di centro x e raggio ε > 0 contenuta interamente in S.
Definizione. Un insieme S si dice chiuso se il suo complementare ℝn \ S è un insieme aperto.
Definizione. Un insieme S si dice limitato se esiste un M > 0 tale che ||x|| ≤ M per ogni x ∈ S.
Definizione. Un insieme S si dice compatto se soddisfa le seguenti proprietà:
- Per ogni successione {xk} esiste un insieme K tale che {xk} ⊂ S e limk→∞ xk = x k ∈ K.
- Per ogni successione {xk} tale che {xk} ⊂ S, allora limk→∞ xk = x x ∈ S.
Ovvero S si dice compatto se ogni successione di elementi di S ammette una sottosuccessione convergente ad un elemento di S.
Lemma. Sia S ⊂ ℝn (sottoinsieme dello spazio Euclideo). Allora:
- S è limitato se e solo se vale la proprietà (a).
- S è chiuso se e solo se vale la proprietà (b).
- S è compatto se e solo se è chiuso e limitato.
Teorema (Weierstrass). Sia f : S ⊂ ℝn → ℝ una funzione continua e sia S un insieme compatto. Allora f ammette un punto di minimo globale in S.
Dim: Sia Y = {y ∈ ℝ | ∃x ∈ S : f(x) = y} = f(S) (cioè Y è l’immagine di S attraverso f). In particolare osserviamo che Y è un sottoinsieme di ℝ, ovvero Y ⊂ ℝ. Perciò, come tutti i sottoinsiemi di ℝ anche Y avrà un estremo inferiore L = inf f(S).
Allora esiste una sequenza {yk} tale che limk→∞ yk = L.
Definiamo una sequenza {xk} tale che f(xk) = yk ∀k. Allora:
- Dalla limitatezza di S abbiamo che esiste K tale che {xk} ⊂ S e limk→∞ xk = x k ∈ K.
- Dalla chiusura di S sappiamo che x ∈ S.
- Dalla continuità di f sappiamo che limk→∞ f(xk) = f(x) k ∈ K.
In particolare tale limite sarà uguale a L, ovvero:
f(x) = limk→∞ f(xk) = L ⇒ f(x) = L per qualche x ∈ S.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
-
![Appunti Optimization and data science for management (primo parziale, parte 2)]()
Appunti Optimization and data science for management (primo parziale, parte 2)
-
![Appunti riassuntivi di Optimization and innovation of production processes]()
Appunti riassuntivi di Optimization and innovation of production processes
-
![Appunti Optimization and data science for management (primo parziale, parte 1)]()
Appunti Optimization and data science for management (primo parziale, parte 1)
-
![Appunti Optimization and innovation processes in italiano (parte 6)]()
Appunti Optimization and innovation processes in italiano (parte 6)
Recensioni
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
