L’ottimizzazione è onnipresente nei regni dell’informatica, della fisica, della matematica e dell’economia. È uno strumento essenziale per i professionisti dell’intelligenza artificiale e dell’apprendimento automatico (ML), applicabile in diversi domini tra cui il processo decisionale, la pianificazione del percorso e i parametri di apprendimento nei modelli ML, come le Support Vector Machines (SVM) e le reti neurali. La forma più generale di ottimizzazione consiste nel trovare un minimo/massimo di una funzione rispetto alle sue variabili indipendenti, che può essere ottenuto applicando i concetti di base del calcolo differenziale. Matematicamente, a queste estremità la pendenza (derivata prima) di una funzione è zero, denominata punti stazionari. Determinare se tale punto rappresenta un massimo o un minimo viene effettuato valutando la curvatura (derivata seconda).
Facendo un ulteriore passo avanti, possiamo aggiungere vincoli al problema di ottimizzazione che definiscono un dominio specifico nello spazio in cui la funzione deve essere ottimizzata. Di conseguenza, invece di determinare il massimo e il minimo di una funzione in tutto lo spazio reale (o complesso), l’ottimizzazione è ora confinata a questo dominio specifico. L’approccio convenzionale del calcolo dei punti stazionari non è più una soluzione, poiché questi punti potrebbero non rientrare nei limiti stabiliti dai vincoli. Nelle prossime sezioni analizzeremo le complessità dei problemi di ottimizzazione vincolata ed esploreremo le strategie per la loro risoluzione.
I problemi di ottimizzazione con vincoli di uguaglianza sono della forma
Dove f(x) è la funzione che cerchiamo di minimizzare e il vincolo g(x) = 0 definisce il dominio entro il quale deve essere effettuata la minimizzazione. In questi casi, il focus della minimizzazione è intrinsecamente confinato al dominio specifico definito dal vincolo. Tuttavia, come notato in precedenza, l’applicazione convenzionale del calcolo differenziale per determinare i punti stazionari non tiene conto del vincolo, rendendo necessario un approccio alternativo.
Funzione lagrangiana
Dato che si tratta di un problema di minimizzazione, un approccio per adattare il metodo convenzionale consiste nell’assegnare un valore infinito alla funzione al di fuori del dominio specificato. Per raggiungere questo obiettivo, introduciamo una nuova funzione f'(x) caratterizzato dalla seguente espressione:
Tale modifica elimina la possibilità che si verifichino dei minimi al di fuori del dominio, garantendo così che il punto ottimale si verifichi al suo interno. Di conseguenza, possiamo ora riformulare il problema di ottimizzazione vincolata in un problema di ottimizzazione non vincolata.
Tuttavia, c’è una sfida che deriva da questo approccio. Non è possibile utilizzare il calcolo differenziale per ottimizzare il problema di cui sopra, poiché la funzione f'(x) non è differenziabile a causa di una brusca discontinuità al confine del dominio. È qui che entra in gioco la Lagrangiana. Piuttosto che definire la funzione f'(x) come in (2), lo formuliamo come un problema di massimizzazione.
L’espressione sulla destra è chiamata the Funzione lagrangiana e la nuova variabile 𝞴 è la Moltiplicatore di Lagrange. È evidente da (4) che nelle regioni in cui {g(x)<0, g(x)>0}𝞴può assumere i valori {-∞, ∞} per massimizzare l’espressione a ∞.
Di conseguenza, l’ottimizzazione in (3) assume la forma seguente.
Vale la pena notare che il problema della non differenziabilità esiste ancora poiché la massimizzazione interna si traduce nella stessa funzione discontinua. Tuttavia, con la rappresentazione lagrangiana, possiamo utilizzare la disuguaglianza max-min per convertire il problema max-min nel problema min-max per superare questo problema.
Qui ottimizziamo prima rispetto alla variabile indipendente X e poi rispetto al moltiplicatore di Lagrange 𝞴.
Analizzeremo ora gli scenari in cui il vincolo non è un’equazione ma una disuguaglianza. Tali ottimizzazioni sono nella forma:
Possiamo risolvere questo problema utilizzando un approccio simile: definiamo f'(x) essere lo stesso di f(x) entro il dominio definito dai vincoli e infinito altrove:
E corrispondentemente, la funzione lagrangiana è definita come:
I moltiplicatori di Lagrange corrispondenti ai vincoli di disuguaglianza sono indicati con 𝝻. L’equazione (9) è diversa in quanto ha anche dei vincoli sui moltiplicatori di Lagrange, che non erano presenti nella (4). Ora il problema di ottimizzazione in (7) assume la forma
Applicando la disuguaglianza min-max,
Condizioni KKT (Karush-Kuhn-Tucker).
L’ottimizzazione in (10) è chiamata versione primale e (11) è la sua versione duale. Secondo la disuguaglianza min-max, la versione duale delimita inferiore la versione primale, suggerendo che le due versioni non sono necessariamente uguali. Tuttavia, ci sono condizioni in cui le versioni primale e duale sono uguali, il che è chiamato condizione di regolarità. Assumendo regolarità, per (X*, 𝝻*) per essere il punto di soluzione deve soddisfare quanto segue Condizioni KKT:
- Fattibilità primaria
Ne consegue dalla definizione del problema.
2. Doppia fattibilità
La doppia fattibilità segue dalla (9).
3. Stazionarietà
Questa è una proprietà interessante. Poiché 𝞴* è zero o positivo, la condizione di stazionarietà implica essenzialmente che nel punto ottimale i gradienti di f(x) E g(x) devono essere orientati in direzioni opposte. La logica alla base di ciò è la seguente: se i gradienti di f(x) E g(x) erano allineati nella stessa direzione in quel punto x = x*poi entrambi f(x) E g(x) diminuirebbero contemporaneamente in direzione opposta ai loro gradienti. Questo scenario lo consentirebbe f(x) continuare a diminuire oltre il valore f(x*) senza violare il vincolo, nel qual caso X* non si qualifica più come punto ottimale. Pertanto affinché un punto sia ottimo è necessario che valga la proprietà di stazionarietà.
4. Rilassamento complementare
Questa è un’altra proprietà interessante che segue direttamente dall’equazione (9). Quando il vincolo g(x*) < 0il moltiplicatore di Lagrange 𝝻* deve essere uguale a zero. Poiché il moltiplicatore di Lagrange indica anche quanto la nostra soluzione è sensibile al vincolo associato, un valore di 𝝻* = 0 significa che il vincolo associato non ha alcuna influenza sulla determinazione della soluzione. In altre parole, sia che si consideri la soluzione con o senza vincolo, il risultato rimane inalterato. Un esempio semplice è quando f(x) ha un minimo globale nel dominio dove g(x) ≤ 0. Per l’altro esempio, considera la minimizzazione della funzione f(x) soggetto a due vincoli: g¹(x) < 5 E g²(x) < -1. In questo caso, il moltiplicatore di Lagrange 𝝻²* corrispondente al vincolo g² è zero, come g¹ copre già le condizioni di g²rendering g² insignificante come vincolo.
Applicazione: Support Vector Machine (SVM)
Un esempio di ottimizzazione vincolata con vincoli di disuguaglianza nell’apprendimento automatico è la Support Vector Machine (SVM). Quando viene fornito un set di dati di punti dati {(x¹, y¹), (x², y²), …} con y ∈ {-1, 1} rappresentando le due classi, l’obiettivo è quello di individuare un classificatore che massimizzi il margine tra le classi. Nello specifico, formuliamo SVM come il seguente problema di minimizzazione:
Il termine ||w|| nell’equazione rappresenta l’inverso del margine. È evidente che esistono numerosi vincoli di disuguaglianza: infatti abbiamo un vincolo legato a ciascun punto dati. Tuttavia, in pratica, la soluzione è guidata solo da pochi punti dati che si trovano in prossimità del confine del classificatore; questi sono indicati come vettori di supporto. Come abbiamo discusso in lassità complementaresolo i moltiplicatori di Lagrange corrispondenti ai vincoli legati ai vettori di supporto possiedono valori diversi da zero. Per tutti gli altri punti dati, i vincoli associati portano valori del moltiplicatore di Lagrange pari a zero, rendendoli insignificanti nel determinare il confine del classificatore.
Conclusione
Abbiamo iniziato con una breve introduzione sul problema dell’ottimizzazione non vincolata e gradualmente espandendolo per incorporare i vincoli di uguaglianza e disuguaglianza. Inoltre, abbiamo discusso come la funzione lagrangiana risolve le sfide introdotte dai vincoli. Approfondendo l’ottimalità della Lagrangiana, abbiamo acquisito informazioni sulle condizioni KKT. Infine, abbiamo fornito una breve panoramica di come gli SVM vengono formulati come problemi di ottimizzazione vincolata e discusso brevemente le sue soluzioni.
Fonte: towardsdatascience.com
