Condicions de Karush-Kuhn-Tucker

De Viquipèdia
Dreceres ràpides: navegació, cerca

En programació no lineal les condicions de Karush-Kuhn-Tucker (també anomenades condicions de KKT, o condicions Kuhn-Tucker) són condicions que ha de complir un punt que sigui solució d'un problema de la forma:

 min \ f(x)
 g_i(x)\le 0 on i \in \{ 1,...,m\}
 h_j(x) = 0 on j \in \{ 1,...,l\}

On, si definim g(x)=(g_1(x),...,g_m(x)) i h(x)=(h_1(x),...,h_l(x)):

 f: \ \mathbb{R}^n \rightarrow \mathbb{R}
 g: \ \mathbb{R}^n \rightarrow \mathbb{R}^m
 h: \ \mathbb{R}^n \rightarrow \mathbb{R}^l

Es tracta d'una generalització del Mètode dels multiplicadors de Lagrange.

Condicions necessàries de 1r ordre[modifica | modifica el codi]

Es tracta d'aplicar les condicions necessàries de 1r ordre per tal que un punt sigui mínim d'una funció de classe C^1 a la funció Lagrangiana:

 L: \ \mathbb{R}^{n+m+l} \longrightarrow \mathbb{R}
 \ (x,\lambda,\mu) \mapsto f(x)+\lambda^{T} \cdot g(x) + \mu^{T} \cdot h(x)

Però per tal que els mínims d'aquesta funció coincideixi amb els de  f(x) cal que imposem un parell de condicions més (que "penalitzen" els punts on no es compleixen les restriccions). Les condicions necessàries de KKT de primer ordre ens diuen que:

Si  x^* és mínim relatiu de  f(x) on f \in C^1 , aleshores existeixen  \lambda \in \mathbb{R}^m i  \mu \in \mathbb{R}^l tals que:

1-

 \nabla f(x^*) +\lambda^{*^T} \cdot \nabla g(x^*) +\mu^{*^T} \nabla h(x^*) = 0

2-

 \lambda_i \cdot g_i(x^*) = 0

3-

 \lambda_i \ge 0

Condicions necessàries de 2n ordre[modifica | modifica el codi]

Condicions suficients[modifica | modifica el codi]

Si f és una funció convexa definida en un domini convex, aleshores les condicions de KKT són suficients.