Condizioni di Karush-Kuhn-Tucker

In matematica, le condizioni di Karush–Kuhn–Tucker (anche conosciute come condizioni di Kuhn-Tucker o condizioni KKT) sono condizioni necessarie per la soluzione di un problema di programmazione non lineare in cui i vincoli soddisfino una delle condizioni di regolarità dette condizioni di qualificazione dei vincoli. Si tratta di una generalizzazione del metodo dei moltiplicatori di Lagrange, applicato a problemi in cui siano presenti anche vincoli di disuguaglianza. Tali considerazioni prendono il proprio nome da William Karush, Harold W. Kuhn, e Albert W. Tucker e sono derivate, come caso particolare in cui siano soddisfatte le condizioni di qualificazione dei vincoli, dalle condizioni di Fritz-John.

Considerato il seguente problema di ottimizzazione non lineare:

$\mathrm {min} \;f(x)$

$g_{i}(x)\leq 0$

$h_{j}(x)=0$

in cui $f(x)$ è la funzione da minimizzare (detta anche funzione obiettivo), $g_{i}(x)\ (i=1,\ldots ,m)$ sono i vincoli monolateri e $h_{j}(x)\ (j=1,\ldots ,l)$ sono i vincoli bilateri.

Le condizioni necessarie per questo generico problema di ottimizzazione vincolata furono inizialmente pubblicate, nella sua tesi di laurea magistrale, da William Karush, anche se furono conosciute solamente dopo l'articolo di Harold W. Kuhn e Albert W. Tucker..

Condizioni necessarie

Si suppone che $f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R}$ e che $g_{i}\colon \mathbb {R} ^{n}\rightarrow \mathbb {R}$ e $h_{j}\colon \mathbb {R} ^{n}\rightarrow \mathbb {R}$. Inoltre si suppone che esse siano funzioni continuamente differenziabili nell'intorno del punto $x^{*}$. Se $x^{*}$ è un punto di minimo locale che soddisfa le condizioni di regolarità dei vincoli, allora esistono dei moltiplicatori $\mu _{j},$ con $j=1,\ldots ,l,$ e $\lambda _{i},$ con $i=1,\ldots ,m,$ tali che:

1. $\nabla f(x^{*})+\sum _{i=1}^{m}\lambda _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\mu _{j}\nabla h_{j}(x^{*})=0;$
2. $\forall i\in \{1,\ldots ,m\}:g_{i}(x^{*})\leq 0;$
3. $\forall j\in \{1,\ldots ,l\}:h_{j}(x^{*})=0;$
4. $\forall i\in \{1,\ldots ,m\}:\lambda _{i}\geq 0;$
5. $\forall i\in \{1,\ldots ,m\}:\lambda _{i}g_{i}(x^{*})=0.$

La prima condizione è la condizione di annullamento del gradiente della funzione lagrangiana associata al problema, la seconda e la terza condizione sono i vincoli di ammissibilità del punto $x^{*}$, la quarta condizione è la condizione di non negatività del moltiplicatore associato ai vincoli di disuguaglianza, e infine l'ultima condizione viene detta condizione di complementarità o di "scarto complementare" in quanto il moltiplicatore di un vincolo inattivo deve essere nullo.

Le condizioni possono essere scritte anche come

1. $\nabla f(x^{*})+\lambda \cdot \nabla g(x^{*})+\mu \cdot \nabla h(x^{*})=0;$
2. $g(x^{*})\leq \mathbf {0} _{m};$
3. $h(x^{*})=\mathbf {0} _{l};$
4. $\lambda \geq \mathbf {0} _{m};$
5. $\lambda \cdot g(x^{*})=0.$

Qui $\cdot$ indica il prodotto scalare, $g$ e $h$ sono funzioni vettoriali a valori vettoriali, rispettivamente con componenti le funzioni dei vincoli $g_{i}$ e $h_{i}$, e $\lambda$ e $\mu$ sono i vettori dei moltiplicatori; inoltre $\mathbf {0} _{k}$ indica il vettore nullo con $k$ componenti e $v\leq u$ va inteso componente per componente, ossia $\forall i:v_{i}\leq u_{i}$.

Regolarità dei vincoli

Affinché le condizioni necessarie di KKT permettano di individuare dei punti di minimo locale, deve essere soddisfatta l'ipotesi di regolarità dei vincoli. In generale si può richiedere la regolarità dell'insieme ammissibile, ma in pratica è sufficiente che $x^{*}$ sia un punto di regolarità. Questa può essere dimostrata in più modi:

• Requisito di indipendenza lineare dei vincoli (LICQ): si richiede che il gradiente dei vincoli di disuguaglianza attivi (cioè stringenti) in $x^{*}$ (ossia il sottoinsieme dei vincoli di disuguaglianza che in $x^{*}$ sono verificati all'uguaglianza) e il gradiente dei vincoli di uguaglianza siano linearmente indipendenti in $x^{*}$.
• Requisito di Mangasarian-Fromowitz (MFCQ): la combinazione conica (combinazione lineare a coefficienti non negativi) del gradiente dei vincoli di disuguaglianza attivi in $x^{*}$ e del gradiente dei vincoli di uguaglianza non esiste.
• Requisito di rango costante (CRCQ): il rango della matrice costituita dai vincoli di disuguaglianza attivi e dai vincoli di uguaglianza ha rango costante, per ogni sottoinsieme di vincoli.
• Slater condition: se il problema è convesso, esiste un punto $x$ in cui sono soddisfatti i vincoli di uguaglianza e i vincoli di disuguaglianza attivi in $x^{*}$ sono strettamente minori di zero.
• Vincoli lineari: se $h$ e $g$ sono funzioni affini, allora la condizione di regolarità è sempre verificata in $x^{*}$.

Bibliografia

• R. Andreani, J. M. Martínez, M. L. Schuverdt, On the relation between constant positive linear dependence condition and quasinormality constraint qualification. Journal of Optimization Theory and Applications, vol. 125, no2, pp. 473-485 (2005).
• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• Jalaluddin Abdullah, Optimization by the Fixed-Point Method, Version 1.97. [1].
• J. Nocedal, S. J. Wright, Numerical Optimization. Springer Publishing. ISBN 978-0-387-30303-1.