Condizioni KKT — ingegnerismo.it

Le condizioni KKT (Karush-Kuhn-Tucker) sono condizioni di ottimalità per problemi di ottimizzazione non lineare con vincoli di uguaglianza e disuguaglianza. Generalizzano il metodo dei moltiplicatori di Lagrange al caso in cui alcuni vincoli possano essere attivi o inattivi.

Un problema standard è:

\min f(x) \quad \text{soggetto a}\quad g_i(x)\le0,\ h_j(x)=0

dove $x\in\mathbb{R}^n$ , $g_i$ sono vincoli di disuguaglianza e $h_j$ vincoli di uguaglianza.

Lagrangiana

La Lagrangiana è:

\mathcal L(x,\lambda,\mu) = f(x)+\sum_i\lambda_i g_i(x)+\sum_j\mu_jh_j(x)

dove $\lambda_i$ sono i moltiplicatori associati alle disuguaglianze e $\mu_j$ quelli associati alle uguaglianze.

Le condizioni

Le condizioni KKT sono:

Stazionarietà

\nabla_x\mathcal L(x^\ast,\lambda^\ast,\mu^\ast)=0

Ammissibilità primale

g_i(x^\ast)\le0, \qquad h_j(x^\ast)=0

Ammissibilità duale

\lambda_i^\ast\ge0

Complementarità

\lambda_i^\ast g_i(x^\ast)=0

La complementarità è la parte più caratteristica: un vincolo non attivo, cioè con $g_i(x^\ast)<0$ , ha moltiplicatore nullo; un vincolo con moltiplicatore positivo deve essere attivo, cioè $g_i(x^\ast)=0$ .

Interpretazione dei moltiplicatori

I moltiplicatori $\lambda_i$ misurano il costo marginale del vincolo. Se un vincolo è inattivo, allentarlo non cambia il valore ottimo al primo ordine e il moltiplicatore è nullo. Se è attivo, il moltiplicatore può indicare quanto migliorerebbe l’obiettivo rilassando leggermente il vincolo.

Questa interpretazione è centrale in programmazione lineare, ricerca operativa, economia, controllo ottimo e progettazione vincolata.

Necessità e sufficienza

Le KKT non sono automaticamente sufficienti in qualunque problema. In generale, sotto condizioni di regolarità, sono condizioni necessarie per un minimo locale. Per problemi convessi, invece, diventano anche sufficienti per l’ottimo globale se:

$f$ è convessa;
i vincoli $g_i$ sono convessi;
i vincoli $h_j$ sono affini;
vale una condizione di qualificazione dei vincoli, come Slater.

In problemi non convessi, un punto che soddisfa le KKT può essere un minimo locale, un massimo locale o un punto sella. Serve analisi aggiuntiva.

Vincoli attivi

Un vincolo $g_i(x)\le0$ è attivo in $x^\ast$ se:

g_i(x^\ast)=0

ed è inattivo se:

g_i(x^\ast)<0

Solo i vincoli attivi contribuiscono alla stazionarietà tramite moltiplicatori potenzialmente non nulli. Questo consente di interpretare il problema localmente come un problema con uguaglianze sui vincoli effettivamente “a contatto”.

Errori comuni

Gli errori più frequenti sono dimenticare il segno dei moltiplicatori, scrivere la Lagrangiana con una convenzione incoerente, applicare le KKT senza verificare regolarità e convessità, oppure trattare la complementarità come una semplice equazione algebrica ignorando il significato attivo/inattivo del vincolo.

Vedi anche: Ottimizzazione, Ottimizzazione non lineare, Moltiplicatori di Lagrange, Metodo del simplesso.