Condiciones de Karush-Kuhn-Tucker

En optimización matemática , las condiciones de Karush–Kuhn–Tucker ( KKT ) , también conocidas como condiciones de Kuhn-Tucker , son pruebas de primera derivada (a veces llamadas condiciones necesarias de primer orden ) para que una solución en programación no lineal sea óptima , siempre que se cumplan algunas condiciones de regularidad.

Al permitir restricciones de desigualdad, el enfoque KKT para la programación no lineal generaliza el método de multiplicadores de Lagrange , que solo permite restricciones de igualdad. De manera similar al enfoque de Lagrange, el problema de maximización (minimización) restringida se reescribe como una función de Lagrange cuyo punto óptimo es un máximo o mínimo global sobre el dominio de las variables de elección y un mínimo (máximo) global sobre los multiplicadores. El teorema de Karush-Kuhn-Tucker a veces se conoce como el teorema del punto de silla. ^[1]

Las condiciones KKT recibieron originalmente su nombre en honor a Harold W. Kuhn y Albert W. Tucker , quienes publicaron las condiciones por primera vez en 1951. ^[2] Estudiosos posteriores descubrieron que las condiciones necesarias para este problema habían sido enunciadas por William Karush en su tesis de maestría en 1939. ^{[3] [4]}

Consideremos el siguiente problema de optimización no lineal en forma estándar :

minimizar${\displaystyle f(\mathbf {x} )}$

sujeto a

${\displaystyle g_{i}(\mathbf {x} )\leq 0,}$

${\displaystyle h_{j}(\mathbf {x} )=0.}$

donde es la variable de optimización elegida de un subconjunto convexo de , es la función objetivo o de utilidad , son las funciones de restricción de desigualdad y son las funciones de restricción de igualdad . Los números de desigualdades e igualdades se denotan por y respectivamente. Correspondiente al problema de optimización restringida se puede formar la función lagrangiana${\displaystyle \mathbf {x} \en \mathbf {X} }$${\displaystyle \mathbb {R} ^{n}}$${\estilo de visualización f}$${\displaystyle g_{i}\ (i=1,\ldots ,m)}$${\displaystyle h_{j}\ (j=1,\ldots ,\ell )}$${\estilo de visualización m}$${\displaystyle \ell}$

$${\displaystyle {\mathcal {L}}(\mathbf {x} ,\mathbf {\mu } ,\mathbf {\lambda } )=f(\mathbf {x} )+\mathbf {\mu } ^{\top }\mathbf {g} (\mathbf {x} )+\mathbf {\lambda } ^{\top }\mathbf {h} (\mathbf {x} )=L(\mathbf {x} ,\mathbf {\alpha } )=f(\mathbf {x} )+\mathbf {\alpha } ^{\top }{\begin{pmatrix}\mathbf {g} (\mathbf {x} )\\\mathbf {h} (\mathbf {x} )\end{pmatrix}}}$$

dónde

$${\displaystyle \mathbf {g} \left(\mathbf {x} \right)={\begin{bmatrix}g_{1}\left(\mathbf {x} \right)\\\vpuntos \\g_{i}\left(\mathbf {x} \right)\\\vpuntos \\g_{m}\left(\mathbf {x} \right)\end{bmatrix}},\quad \mathbf {h} \left(\mathbf {x} \right)={\begin{bmatrix}h_{1}\left(\mathbf {x} \right)\\\vpuntos \\h_{j}\left(\mathbf {x} \right)\\\vpuntos \\h_{\ell }\left(\mathbf {x} \right)\end{bmatrix}},\quad \mathbf {\mu } ={\begin{bmatrix}\mu _{1}\\\vdots \\\mu _{i}\\\vdots \\\mu _{m}\\\end{bmatrix}},\quad \mathbf {\lambda } ={\begin{bmatrix}\lambda _{1}\\\vdots \\\lambda _{j}\\\vdots \\\lambda _{\ell }\ end{bmatrix}}\quad {\text{y}}\quad \mathbf {\alpha } ={\begin{bmatrix}\mu \\\lambda \end{bmatrix}}.}$$El teorema de Karush-Kuhn-Tucker establece lo siguiente:

Dado que la idea de este enfoque es encontrar un hiperplano de apoyo en el conjunto factible , la prueba del teorema de Karush-Kuhn-Tucker hace uso del teorema de separación de hiperplanos . ^[6]${\displaystyle \mathbf {\Gamma } =\left\{\mathbf {x} \in \mathbf {X} :g_{i}(\mathbf {x} )\leq 0,i=1,\ldots ,m\right\}}$

El sistema de ecuaciones e inecuaciones correspondiente a las condiciones KKT no suele resolverse directamente, excepto en los pocos casos especiales en los que se puede derivar analíticamente una solución en forma cerrada . En general, muchos algoritmos de optimización pueden interpretarse como métodos para resolver numéricamente el sistema de ecuaciones e inecuaciones KKT. ^[7]

Supóngase que la función objetivo y las funciones de restricción y tienen subderivadas en un punto . Si es un óptimo local y el problema de optimización satisface algunas condiciones de regularidad (ver más abajo), entonces existen constantes y , llamadas multiplicadores KKT, tales que se cumplen los siguientes cuatro grupos de condiciones: ^[8]${\displaystyle f\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} }$${\displaystyle g_{i}\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} }$${\displaystyle h_{j}\colon \mathbb {R} ^{n}\rightarrow \mathbb {R} }$${\displaystyle x^{*}\in \mathbb {R} ^{n}}$${\displaystyle x^{*}}$${\displaystyle \mu _{i}\ (i=1,\ldots ,m)}$${\displaystyle \lambda _{j}\ (j=1,\ldots ,\ell )}$

Estacionariedad

Para minimizar :${\displaystyle f(x)}$${\displaystyle \partial f(x^{*})+\sum _{j=1}^{\ell }\lambda _{j}\partial h_{j}(x^{*})+\sum _{i=1}^{m}\mu _{i}\partial g_{i}(x^{*})\ni \mathbf {0} }$

Para maximizar :${\displaystyle f(x)}$${\displaystyle -\partial f(x^{*})+\sum _{j=1}^{\ell }\lambda _{j}\partial h_{j}(x^{*})+\sum _{i=1}^{m}\mu _{i}\partial g_{i}(x^{*})\ni \mathbf {0} }$

Viabilidad primaria

${\displaystyle h_{j}(x^{*})=0,{\text{ for }}j=1,\ldots ,\ell \,\!}$

${\displaystyle g_{i}(x^{*})\leq 0,{\text{ for }}i=1,\ldots ,m}$

Doble viabilidad

${\displaystyle \mu _{i}\geq 0,{\text{ for }}i=1,\ldots ,m}$

Holgura complementaria

${\displaystyle \sum _{i=1}^{m}\mu _{i}g_{i}(x^{*})=0.}$

La última condición a veces se escribe en la forma equivalente:${\displaystyle \mu _{i}g_{i}(x^{*})=0,{\text{ for }}i=1,\ldots ,m.}$

En el caso particular , es decir, cuando no hay restricciones de desigualdad, las condiciones KKT se convierten en condiciones de Lagrange y los multiplicadores KKT se denominan multiplicadores de Lagrange .${\displaystyle m=0}$

El problema primal puede interpretarse como mover una partícula en el espacio de y someterla a tres tipos de campos de fuerza:${\displaystyle x}$

• ${\displaystyle f}$es un campo potencial que la partícula está minimizando. La fuerza generada por es .${\displaystyle f}$${\displaystyle -\partial f}$
• ${\displaystyle g_{i}}$son superficies de restricción unilaterales. Se permite que la partícula se mueva dentro de , pero siempre que toca , es empujada hacia adentro.${\displaystyle g_{i}\leq 0}$${\displaystyle g_{i}=0}$
• ${\displaystyle h_{j}}$Son superficies de restricción de dos lados. La partícula solo puede moverse sobre la superficie .${\displaystyle h_{j}}$

La estacionariedad primordial establece que la "fuerza" de está exactamente equilibrada por una suma lineal de fuerzas y .${\displaystyle \partial f(x^{*})}$${\displaystyle \partial h_{j}(x^{*})}$${\displaystyle \partial g_{i}(x^{*})}$

La viabilidad dual establece además que todas las fuerzas deben ser unilaterales, apuntando hacia adentro del conjunto factible para .${\displaystyle \partial g_{i}(x^{*})}$${\displaystyle x}$

La holgura complementaria establece que si , entonces la fuerza que proviene de debe ser cero, es decir , dado que la partícula no está en el límite, la fuerza de restricción unilateral no puede activarse.${\displaystyle g_{i}(x^{*})<0}$${\displaystyle \partial g_{i}(x^{*})}$${\displaystyle \mu _{i}(x^{*})=0}$

Las condiciones necesarias se pueden escribir con matrices jacobianas de las funciones de restricción. Sea θ y θ definidas como . Sea θ y θ . Entonces las condiciones necesarias se pueden escribir como:${\displaystyle \mathbf {g} (x):\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m}}$${\displaystyle \mathbf {g} (x)=\left(g_{1}(x),\ldots ,g_{m}(x)\right)^{\top }}$${\displaystyle \mathbf {h} (x):\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{\ell }}$${\displaystyle \mathbf {h} (x)=\left(h_{1}(x),\ldots ,h_{\ell }(x)\right)^{\top }}$${\displaystyle {\boldsymbol {\mu }}=\left(\mu _{1},\ldots ,\mu _{m}\right)^{\top }}$${\displaystyle {\boldsymbol {\lambda }}=\left(\lambda _{1},\ldots ,\lambda _{\ell }\right)^{\top }}$

Estacionariedad

Para maximizar :${\displaystyle f(x)}$${\displaystyle \partial f(x^{*})-D\mathbf {g} (x^{*})^{\top }{\boldsymbol {\mu }}-D\mathbf {h} (x^{*})^{\top }{\boldsymbol {\lambda }}=\mathbf {0} }$

Para minimizar :${\displaystyle f(x)}$${\displaystyle \partial f(x^{*})+D\mathbf {g} (x^{*})^{\top }{\boldsymbol {\mu }}+D\mathbf {h} (x^{*})^{\top }{\boldsymbol {\lambda }}=\mathbf {0} }$

Viabilidad primaria

${\displaystyle \mathbf {g} (x^{*})\leq \mathbf {0} }$

${\displaystyle \mathbf {h} (x^{*})=\mathbf {0} }$

Doble viabilidad

${\displaystyle {\boldsymbol {\mu }}\geq \mathbf {0} }$

Holgura complementaria

${\displaystyle {\boldsymbol {\mu }}^{\top }\mathbf {g} (x^{*})=0.}$

Se puede preguntar si un punto minimizador del problema de optimización original, restringido (suponiendo que exista uno) tiene que satisfacer las condiciones KKT anteriores. Esto es similar a preguntar bajo qué condiciones el minimizador de una función en un problema sin restricciones tiene que satisfacer la condición . Para el caso restringido, la situación es más complicada, y se pueden establecer una variedad de condiciones de "regularidad" (cada vez más complicadas) bajo las cuales un minimizador restringido también satisface las condiciones KKT. A continuación se presentan algunos ejemplos comunes de condiciones que garantizan esto, siendo el LICQ el más utilizado:${\displaystyle x^{*}}$${\displaystyle x^{*}}$${\displaystyle f(x)}$${\displaystyle \nabla f(x^{*})=0}$

Restricción	Acrónimo	Declaración
Calificación de restricción de linealidad	LCQ	Si y son funciones afines , entonces no se necesita ninguna otra condición.${\displaystyle g_{i}}$${\displaystyle h_{j}}$
Calificación de restricción de independencia lineal	LICQ	Los gradientes de las restricciones de desigualdad activa y los gradientes de las restricciones de igualdad son linealmente independientes en .${\displaystyle x^{*}}$
Calificación de restricción de Mangasarian-Fromovitz	MFCQ	Los gradientes de las restricciones de igualdad son linealmente independientes en y existe un vector tal que para todas las restricciones de desigualdad activas y para todas las restricciones de igualdad. [10]${\displaystyle x^{*}}$${\displaystyle d\in \mathbb {R} ^{n}}$${\displaystyle \nabla g_{i}(x^{*})^{\top }d<0}$${\displaystyle \nabla h_{j}(x^{*})^{\top }d=0}$
Calificación de restricción de rango constante	CRCQ	Para cada subconjunto de los gradientes de las restricciones de desigualdad activas y los gradientes de las restricciones de igualdad, el rango en las proximidades de es constante.${\displaystyle x^{*}}$
Calificación de restricción de dependencia lineal positiva constante	CPLD	Para cada subconjunto de gradientes de restricciones de desigualdad activas y gradientes de restricciones de igualdad, si el subconjunto de vectores es linealmente dependiente en con escalares no negativos asociados con las restricciones de desigualdad, entonces permanece linealmente dependiente en un entorno de .${\displaystyle x^{*}}$${\displaystyle x^{*}}$
Calificación de restricción de cuasicondición normal	QNCQ	Si los gradientes de las restricciones de desigualdad activas y los gradientes de las restricciones de igualdad son linealmente dependientes en con multiplicadores asociados para igualdades y para desigualdades, entonces no existe ninguna secuencia tal que y${\displaystyle x^{*}}$${\displaystyle \lambda _{j}}$${\displaystyle \mu _{i}\geq 0}$${\displaystyle x_{k}\to x^{*}}$${\displaystyle \lambda _{j}\neq 0\Rightarrow \lambda _{j}h_{j}(x_{k})>0}$${\displaystyle \mu _{i}\neq 0\Rightarrow \mu _{i}g_{i}(x_{k})>0.}$
La condición de Slater	CAROLINA DEL SUR	Para un problema convexo (es decir, suponiendo minimización, son convexos y son afines), existe un punto tal que y${\displaystyle f,g_{i}}$${\displaystyle h_{j}}$${\displaystyle x}$${\displaystyle h_{j}(x)=0}$${\displaystyle g_{i}(x)<0.}$

Las implicaciones estrictas se pueden demostrar

LICQ ⇒ MFCQ ⇒ CPLD ⇒ QNCQ

y

LICQ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ

En la práctica, se prefieren calificaciones de restricciones más débiles porque se aplican a una selección más amplia de problemas.

En algunos casos, las condiciones necesarias también son suficientes para la optimalidad. En general, las condiciones necesarias no son suficientes para la optimalidad y se requiere información adicional, como las Condiciones Suficientes de Segundo Orden (SOSC). Para funciones suaves, las SOSC involucran las derivadas segundas, lo que explica su nombre.

Las condiciones necesarias son suficientes para la optimalidad si la función objetivo de un problema de maximización es una función cóncava diferenciable , las restricciones de desigualdad son funciones convexas diferenciables , las restricciones de igualdad son funciones afines y se cumple la condición de Slater . ^[11] De manera similar, si la función objetivo de un problema de minimización es una función convexa diferenciable , las condiciones necesarias también son suficientes para la optimalidad.${\displaystyle f}$${\displaystyle g_{j}}$${\displaystyle h_{i}}$${\displaystyle f}$

Martin demostró en 1985 que la clase más amplia de funciones en las que las condiciones KKT garantizan la optimalidad global son las denominadas funciones invex de tipo 1. [ 12 ^{] [13]}

Para problemas de optimización suave y no lineal , se da una condición suficiente de segundo orden como sigue.

La solución encontrada en la sección anterior es un mínimo local restringido si para el Lagrangiano,${\displaystyle x^{*},\lambda ^{*},\mu ^{*}}$

${\displaystyle L(x,\lambda ,\mu )=f(x)+\sum _{i=1}^{m}\mu _{i}g_{i}(x)+\sum _{j=1}^{\ell }\lambda _{j}h_{j}(x)}$

entonces,

${\displaystyle s^{T}\nabla _{xx}^{2}L(x^{*},\lambda ^{*},\mu ^{*})s\geq 0}$

donde es un vector que satisface lo siguiente,${\displaystyle s\neq 0}$

${\displaystyle \left[\nabla _{x}g_{i}(x^{*}),\nabla _{x}h_{j}(x^{*})\right]^{T}s=0_{\mathbb {R} ^{2}}}$

donde solo se aplican las restricciones de desigualdad activas correspondientes a complementariedad estricta (es decir, donde ). La solución es un mínimo local restringido estricto en el caso de que la desigualdad también sea estricta.${\displaystyle g_{i}(x)}$${\displaystyle \mu _{i}>0}$

Si , se debe utilizar la expansión de Taylor de tercer orden del lagrangiano para verificar si es un mínimo local. La minimización de es un buen contraejemplo, véase también la superficie de Peano .${\displaystyle s^{T}\nabla _{xx}^{2}L(x^{*},\lambda ^{*},\mu ^{*})s=0}$${\displaystyle x^{*}}$${\displaystyle f(x_{1},x_{2})=(x_{2}-x_{1}^{2})(x_{2}-3x_{1}^{2})}$

En economía matemática, el enfoque KKT se utiliza a menudo en modelos teóricos para obtener resultados cualitativos. Por ejemplo, ^[14] considere una empresa que maximiza sus ingresos por ventas sujeta a una restricción de beneficio mínimo. Si se considera que es la cantidad de producción producida (a elegir), los ingresos por ventas con una primera derivada positiva y con un valor cero con una producción cero, los costes de producción con una primera derivada positiva y con un valor no negativo con una producción cero, y el nivel mínimo aceptable positivo de beneficio , entonces el problema tiene sentido si la función de ingresos se estabiliza de modo que, en última instancia, es menos empinada que la función de costes. El problema expresado en la forma de minimización dada anteriormente es${\displaystyle Q}$${\displaystyle R(Q)}$${\displaystyle C(Q)}$${\displaystyle G_{\min }}$

Minimizar${\displaystyle -R(Q)}$

sujeto a

${\displaystyle G_{\min }\leq R(Q)-C(Q)}$

${\displaystyle Q\geq 0,}$

y las condiciones del KKT son

${\displaystyle {\begin{aligned}&\left({\frac {{\text{d}}R}{{\text{d}}Q}}\right)(1+\mu )-\mu \left({\frac {{\text{d}}C}{{\text{d}}Q}}\right)\leq 0,\\[5pt]&Q\geq 0,\\[5pt]&Q\left[\left({\frac {{\text{d}}R}{{\text{d}}Q}}\right)(1+\mu )-\mu \left({\frac {{\text{d}}C}{{\text{d}}Q}}\right)\right]=0,\\[5pt]&R(Q)-C(Q)-G_{\min }\geq 0,\\[5pt]&\mu \geq 0,\\[5pt]&\mu [R(Q)-C(Q)-G_{\min }]=0.\end{aligned}}}$

Dado que violaría la restricción de ganancia mínima, tenemos y, por lo tanto, la tercera condición implica que la primera condición se cumple con igualdad. Resolviendo esa igualdad obtenemos${\displaystyle Q=0}$${\displaystyle Q>0}$

${\displaystyle {\frac {{\text{d}}R}{{\text{d}}Q}}={\frac {\mu }{1+\mu }}\left({\frac {{\text{d}}C}{{\text{d}}Q}}\right).}$

Debido a que se dio que y son estrictamente positivos, esta desigualdad junto con la condición de no negatividad en garantiza que es positiva y, por lo tanto, la empresa que maximiza los ingresos opera en un nivel de producción en el que el ingreso marginal es menor que el costo marginal , un resultado que es de interés porque contrasta con el comportamiento de una empresa que maximiza las ganancias , que opera en un nivel en el que son iguales.${\displaystyle {\text{d}}R/{\text{d}}Q}$${\displaystyle {\text{d}}C/{\text{d}}Q}$${\displaystyle \mu }$${\displaystyle \mu }$ ${\displaystyle {\text{d}}R/{\text{d}}Q}$ ${\displaystyle {\text{d}}C/{\text{d}}Q}$

Si reconsideramos el problema de optimización como un problema de maximización con restricciones de desigualdad constantes:

${\displaystyle {\text{Maximize }}\;f(x)}$

${\displaystyle {\text{subject to }}\ }$

${\displaystyle g_{i}(x)\leq a_{i},h_{j}(x)=0.}$

La función de valor se define como

${\displaystyle V(a_{1},\ldots ,a_{n})=\sup \limits _{x}f(x)}$

${\displaystyle {\text{subject to }}\ }$

${\displaystyle g_{i}(x)\leq a_{i},h_{j}(x)=0}$

${\displaystyle j\in \{1,\ldots ,\ell \},i\in \{1,\ldots ,m\},}$

Entonces el dominio de es${\displaystyle V}$${\displaystyle \{a\in \mathbb {R} ^{m}\mid {\text{for some }}x\in X,g_{i}(x)\leq a_{i},i\in \{1,\ldots ,m\}\}.}$

Dada esta definición, cada coeficiente es la tasa a la que la función de valor aumenta a medida que aumenta . Por lo tanto, si cada uno se interpreta como una restricción de recursos, los coeficientes indican cuánto aumentará el valor óptimo de nuestra función al aumentar un recurso . Esta interpretación es especialmente importante en economía y se utiliza, por ejemplo, en problemas de maximización de la utilidad .${\displaystyle \mu _{i}}$${\displaystyle a_{i}}$${\displaystyle a_{i}}$${\displaystyle f}$

Con un multiplicador adicional , que puede ser cero (siempre que ), frente a las condiciones de estacionariedad KKT se convierten en${\displaystyle \mu _{0}\geq 0}$${\displaystyle (\mu _{0},\mu ,\lambda )\neq 0}$${\displaystyle \nabla f(x^{*})}$

${\displaystyle {\begin{aligned}&\mu _{0}\,\nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}\,\nabla g_{i}(x^{*})+\sum _{j=1}^{\ell }\lambda _{j}\,\nabla h_{j}(x^{*})=0,\\[4pt]&\mu _{j}g_{i}(x^{*})=0,\quad i=1,\dots ,m,\end{aligned}}}$

que se denominan condiciones de Fritz John . Estas condiciones de optimalidad se cumplen sin restricciones y son equivalentes a la condición de optimalidad KKT o (no-MFCQ) .

Las condiciones KKT pertenecen a una clase más amplia de condiciones necesarias de primer orden (FONC), que permiten funciones no suaves utilizando subderivadas .

• El lema de Farkas
• Multiplicador de Lagrange
• El método Big M , para problemas lineales, que extiende el algoritmo simplex a problemas que contienen restricciones de "mayor que".
• Método del punto interior: un método para resolver las condiciones KKT.
• Variable de holgura
• La condición de Slater

• Andreani, R.; Martínez, JM; Schuverdt, ML (2005). "Sobre la relación entre la condición de dependencia lineal positiva constante y la calificación de restricción de cuasinormalidad". Journal of Optimization Theory and Applications . 125 (2): 473–485. doi :10.1007/s10957-004-1861-9. S2CID  122212394.
• Avriel, Mordecai (2003). Programación no lineal: análisis y métodos . Dover. ISBN 0-486-43227-0.
• Boltyanski, V.; Martini, H.; Soltan, V. (1998). "El teorema de Kuhn-Tucker". Métodos geométricos y problemas de optimización . Nueva York: Springer. págs. 78–92. ISBN 0-7923-5454-0.
• Boyd, S.; Vandenberghe, L. (2004). "Condiciones de optimalidad" (PDF) . Optimización convexa . Cambridge University Press. págs. 241–249. ISBN 0-521-83378-7.
• Kemp, Murray C.; Kimura, Yoshio (1978). Introducción a la economía matemática. Nueva York: Springer. pp. 38–73. ISBN 0-387-90304-6.
• Rau, Nicholas (1981). "Multiplicadores de Lagrange". Matrices y programación matemática . Londres: Macmillan. pp. 156–174. ISBN. 0-333-27768-6.
• Nocedal, J.; Wright, SJ (2006). Optimización numérica . Nueva York: Springer. ISBN 978-0-387-30303-1.
• Sundaram, Rangarajan K. (1996). "Restricciones de desigualdad y el teorema de Kuhn y Tucker". Un primer curso de teoría de optimización . Nueva York: Cambridge University Press. págs. 145–171. ISBN 0-521-49770-1.

• Condiciones de Karush-Kuhn-Tucker con derivación y ejemplos
• Ejemplos y tutoriales sobre las condiciones KKT