Ottimizzazione vincolata e le condizioni di KKT

Ottimizzazione vincolata e le condizioni di Kuratowski-Kruskal-Thaleski (KKT)

uno sguardo alla funzione Lagrangiana

L’ottimizzazione è ubiqua nei campi dell’informatica, della fisica, della matematica e dell’economia. Essa è uno strumento essenziale per i professionisti dell’IA e dell’apprendimento automatico (ML), applicabile in diversi ambiti tra cui la presa di decisioni, la pianificazione dei percorsi e l’apprendimento dei parametri nei modelli di 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, il che può essere ottenuto applicando i concetti base del calcolo differenziale. Matematicamente, in queste estremità la pendenza (prima derivata) di una funzione è zero, definita come punti stazionari. Determinare se tale punto rappresenta un massimo o un minimo viene fatto valutando la curvatura (seconda derivata).

Andando oltre, possiamo aggiungere vincoli al problema di ottimizzazione che definiscono un dominio specifico nello spazio in cui la funzione deve essere ottimizzata. Di conseguenza, anziché determinare il massimo e il minimo di una funzione in tutto lo spazio reale (o complesso), l’ottimizzazione è ora limitata a questo dominio specifico. L’approccio convenzionale di calcolare i punti stazionari non è più una soluzione, poiché questi punti possono cadere al di fuori del confine definito dai vincoli. Nelle prossime sezioni, analizzeremo le complicazioni dei problemi di ottimizzazione vincolata ed esploreremo strategie per la loro risoluzione.

Vincoli di Uguaglianza

I problemi di ottimizzazione con vincoli di uguaglianza hanno la forma

• È ora di cominciare a parlare dell’architettura rapida nei LLM?
• Incontra 3D-GPT Un framework di intelligenza artificiale per la modellazione 3D guidata da istruzioni che fa uso di grandi modelli di linguaggio (LLM).
• Semplice classificazione del testo utilizzando Fasttext

dove f(x) è la funzione che cerchiamo di minimizzare e il vincolo g(x) = 0 definisce il dominio all’interno del quale verrà eseguita la minimizzazione. In questi casi, l’attenzione alla minimizzazione è intrinsecamente limitata al dominio specifico definito dal vincolo. Tuttavia, come accennato 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 è assegnare un valore di infinito alla funzione al di fuori del dominio specificato. Per ottenere ciò, introduciamo una nuova funzione f'(x) caratterizzata dalla seguente espressione:

Tale modifica elimina la possibilità che i minimi si verifichino al di fuori del dominio, garantendo così che il punto ottimale si trovi al suo interno. Di conseguenza, possiamo ora riformulare l’ottimizzazione vincolata in un problema di ottimizzazione libera da vincoli.

Tuttavia, questo approccio presenta una sfida. Utilizzare il calcolo differenziale per ottimizzare il problema soprastante non è possibile, poiché la funzione f'(x) non è differenziabile a causa di una discontinuità improvvisa al confine del dominio. Qui entra in gioco la funzione Lagrangiana. Invece di definire la funzione f'(x) come in (2), la formuliamo come un problema di massimizzazione.

L’espressione nella parte destra è chiamata funzione Lagrangiana e la nuova variabile 𝞴 è il moltiplicatore di Lagrange. È evidente da (4) che nelle regioni dove {g(x) 0}, 𝞴 può assumere i valori {-∞, ∞} per massimizzare l’espressione a ∞.

Come risultato, l’ottimizzazione in (3) assume la seguente forma.

Vale la pena notare che il problema della non differenziabilità persiste poiché la massimizzazione interna porta alla stessa funzione discontinua. Tuttavia, con la rappresentazione del Lagrangiano, possiamo utilizzare la disuguaglianza max-min per convertire il problema di max-min in un problema di min-max per superare questo problema.

Qui, ottimizziamo prima rispetto alla variabile indipendente x e poi rispetto al moltiplicatore di Lagrange 𝞴.

Vincoli di disuguaglianza

Analizzeremo ora gli scenari in cui il vincolo non è un’equazione ma una disuguaglianza. Tali ottimizzazioni hanno la seguente forma:

Possiamo risolvere questo utilizzando un approccio simile: definiamo f'(x) come identico a f(x) all’interno del 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 perché ha anche dei vincoli sui moltiplicatori di Lagrange, che non erano presenti in (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 limita inferiormente la versione primale, suggerendo che le due versioni non siano necessariamente uguali. Tuttavia, ci sono condizioni in cui le versioni primale e duale sono uguali, che si chiamano condizione di regolarità. Supponendo la regolarità, per (x*, 𝝻*) essere il punto di soluzione deve soddisfare le seguenti condizioni KKT:

1. Primal Feasibility

Deriva dalla definizione del problema.

2. Dual Feasibility

La fattibilità duplice deriva dal (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 ragione di ciò è la seguente: se i gradienti di f(x) e g(x) fossero allineati nella stessa direzione nel punto x = x*, allora sia f(x) che g(x) diminuirebbero contemporaneamente in una direzione opposta ai loro gradienti. Questo scenario consentirebbe a f(x) di continuare a diminuire oltre il valore di f(x*) senza violare il vincolo, e in tal caso x* non sarebbe più considerato il punto ottimale. Pertanto, affinché un punto sia ottimale, deve essere verificata la proprietà di stazionarietà.

4. Complemetarity Slackness

Questa è un’altra proprietà interessante che deriva direttamente dall’equazione (9). Quando il vincolo g(x*) < 0 è soddisfatto, il moltiplicatore di Lagrange 𝝻* deve essere uguale a zero. Poiché il moltiplicatore di Lagrange indica anche quanto sensibile sia la nostra soluzione al vincolo associato, un valore di 𝝻* = 0 significa che il vincolo associato non influisce sulla determinazione della soluzione. In altre parole, che consideriamo la soluzione con o senza il vincolo, il risultato rimane inalterato. Un esempio molto semplice è quando f(x) ha un minimo globale nel dominio in cui g(x) ≤ 0. Per l’altro esempio, consideriamo la minimizzazione della funzione f(x) soggetta a due vincoli: g¹(x) < 5 e g²(x) < -1. In questo caso, il moltiplicatore di Lagrange 𝝻²* corrispondente al vincolo g² è zero, poiché g¹ già soddisfa le condizioni di g², rendendo 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 {(x¹, y¹), (x², y²), …} con y ∈ {-1, 1} che rappresenta le due classi, l’obiettivo è identificare un classificatore che massimizzi la distanza tra le classi. In particolare, formuliamo SVM come il seguente problema di minimizzazione:

Il termine ||w|| nell’equazione rappresenta l’inverso della distanza. È evidente che esistono numerosi vincoli di disuguaglianza: infatti, abbiamo un vincolo per ogni punto dati. Tuttavia, in pratica, la soluzione è guidata solo da alcuni punti dati che si trovano vicino al confine del classificatore; questi sono chiamati vettori di supporto. Come abbiamo discusso in complementary slackness, solo i moltiplicatori di Lagrange corrispondenti ai vincoli legati ai vettori di supporto hanno valori diversi da zero. Per tutti gli altri punti dati, i relativi vincoli hanno valori dei moltiplicatori di Lagrange pari a zero, rendendoli insignificanti nella determinazione del confine del classificatore.

Conclusioni

Abbiamo iniziato con una breve introduzione sul problema di ottimizzazione senza vincoli e lo abbiamo gradualmente ampliato per incorporare i vincoli di uguaglianza e disuguaglianza. Inoltre, abbiamo discusso come la funzione lagrangiana risolva le sfide introdotte dai vincoli. Approfondendo l’ottimalità del Lagrangiano, abbiamo acquisito conoscenze sulle condizioni KKT. Infine, abbiamo fornito una panoramica succinta su come le SVM siano formulate come problemi di ottimizzazione vincolata e abbiamo discusso brevemente sulle sue soluzioni.