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 ciertas condiciones de regularidad .

Al permitir restricciones de desigualdad, el enfoque KKT para la programación no lineal generaliza el método de los multiplicadores de Lagrange , que solo permite restricciones de igualdad. De forma similar al enfoque de Lagrange, el problema de maximización (minimización) con restricciones 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 denomina teorema del punto de silla . ^{[ 1 ]}

Las condiciones KKT fueron nombradas originalmente en honor a Harold W. Kuhn y Albert W. Tucker , quienes las publicaron por primera vez en 1951. ^{[ 2 ]} Posteriormente, otros investigadores descubrieron que las condiciones necesarias para este problema habían sido enunciadas en una tesis de maestría inédita de William Karush 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.}$

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

$${\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)\\\vdots \\g_{i}\left(\mathbf {x} \right)\\\vdots \\g_{m}\left(\mathbf {x} \right)\end{bmatrix}},\quad \mathbf {h} \left(\mathbf {x} \right)={\begin{bmatrix}h_{1}\left(\mathbf {x} \right)\\\vdots \\h_{j}\left(\mathbf {x} \right)\\\vdots \\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{and}}\quad \mathbf {\alpha } ={\begin{bmatrix}\mu \\\lambda \end{bmatrix}}.}$$El teorema de Karush-Kuhn-Tucker establece entonces lo siguiente.

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

El sistema de ecuaciones e inecuaciones correspondiente a las condiciones de KKT generalmente no se resuelve directamente, excepto en los pocos casos especiales donde se puede obtener una solución analítica 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 de KKT. ^{[ 7 ]}

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

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}$

Viabilidad dual

${\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 de la forma equivalente:${\displaystyle \mu _{i}g_{i}(x^{*})=0,{\text{ for }}i=1,\ldots ,m.}$

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

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

Se pueden demostrar las estrictas implicaciones.

LICQ ⇒ MFCQ ⇒ CPLD ⇒ QNCQ

y

LICQ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ

En la práctica, se prefieren las restricciones menos estrictas, ya que se aplican a una gama 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 (CSSO). Para funciones suaves, las CSSO involucran las segundas derivadas, lo que explica su nombre.

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

Martin demostró en 1985 que la clase más amplia de funciones en las que las condiciones KKT garantizan la optimalidad global son las llamadas funciones invexas de Tipo 1. ^{[ 11 ] [ 12 ]}

A menudo, en economía matemática, el enfoque KKT se utiliza en modelos teóricos para obtener resultados cualitativos. Por ejemplo, ^{[ 13 ]} consideremos una empresa que maximiza sus ingresos por ventas sujeta a una restricción de beneficio mínimo. Sea${\displaystyle Q}$sea ​​la cantidad de producción producida (a elegir),${\displaystyle R(Q)}$sean los ingresos por ventas con una primera derivada positiva y con un valor cero en la producción cero,${\displaystyle C(Q)}$sean costos de producción con una primera derivada positiva y con un valor no negativo en producción cero, y${\displaystyle G_{\min }}$Sea el nivel mínimo aceptable de beneficio positivo , entonces el problema es significativo si la función de ingresos se estabiliza de modo que eventualmente sea menos pronunciada que la función de costos. El problema expresado en la forma de minimización dada anteriormente es

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

sujeto a

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

${\displaystyle Q\geq 0,}$

y las condiciones 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}}}$

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

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

Porque se dio que${\displaystyle {\text{d}}R/{\text{d}}Q}$y${\displaystyle {\text{d}}C/{\text{d}}Q}$son estrictamente positivas, esta desigualdad junto con la condición de no negatividad en${\displaystyle \mu }$garantiza que${\displaystyle \mu }$es positivo y, por lo tanto, la empresa que maximiza los ingresos opera a un nivel de producción en el que el ingreso marginal${\displaystyle {\text{d}}R/{\text{d}}Q}$es menor que el costo marginal${\displaystyle {\text{d}}C/{\text{d}}Q}$— un resultado que resulta interesante porque contrasta con el comportamiento de una empresa que maximiza sus beneficios , la cual opera a un nivel en el que son iguales.

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\},}$

por lo tanto el dominio de${\displaystyle V}$es${\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${\displaystyle \mu _{i}}$es la tasa a la que aumenta la función de valor a medida que${\displaystyle a_{i}}$aumenta. Por lo tanto, si cada${\displaystyle a_{i}}$Se interpreta como una restricción de recursos; los coeficientes indican cuánto aumentará un recurso el valor óptimo de nuestra función.${\displaystyle f}$Esta interpretación es especialmente importante en economía y se utiliza, por ejemplo, en problemas de maximización de la utilidad .

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

${\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 . Esta condición de optimalidad se cumple sin cualificaciones de restricciones y es equivalente a la condición de optimalidad KKT o (not-MFCQ) .

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

• El lema de Farkas
• multiplicador de Lagrange
• El método Big M , para problemas lineales, extiende el algoritmo simplex a problemas que contienen restricciones de "mayor que".
• Método de punto interior , un método para resolver las condiciones de 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 la 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. pp. 241–249 . ISBN  0-521-83378-7.
• Kemp, Murray C.; Kimura, Yoshio (1978). Introducción a la economía matemática . Nueva York: Springer. págs. 38–73 . ISBN  0-387-90304-6.
• Rau, Nicholas (1981). «Multiplicadores de Lagrange». Matrices y programación matemática . Londres: Macmillan. págs. 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 la optimización . Nueva York: Cambridge University Press. pp. 145–171 . ISBN  0-521-49770-1.

• Ejemplos y tutoriales sobre las condiciones KKT