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 los 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 denomina teorema del punto de silla.

Las condiciones KKT recibieron originalmente el nombre de Harold W. Kuhn y Albert W. Tucker, quienes publicaron las condiciones por primera vez en 1951. Los estudiosos posteriores descubrieron que las condiciones necesarias para este problema habían sido establecidas por William Karush en su obra maestra. s tesis en 1939.

Problema de optimización no lineal

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

minimizar ${\displaystyle f {x}$

sujeto a

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

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

Donde ${\displaystyle \mathbf {x} \in \mathbf {X}$ es la variable de optimización elegida de un subconjunto convexo de ${\displaystyle \mathbb {R} {} {}} {\fn}}$, ${\displaystyle f}$ es la función objetiva o de utilidad, ${\displaystyle g_{i}\i=1,\ldotsm)}$ son las funciones de limitación de la desigualdad y ${\displaystyle h_{j}\ (j=1,\ldots\ell)}$ son las funciones de limitación de la igualdad. El número de desigualdades e igualdades se denota por ${\displaystyle m}$ y ${\displaystyle \ell }$ respectivamente. Correspondiendo al problema de optimización limitada se puede formar la función lagrangia

$${\fnMicrosoft} {\fnMicrosoft}$$

dónde

$${\fnMicrosoft Sans Serif} ¿Por qué? ¿Por qué? \\mu _{m}\end{bmatrix}\quad \mathbf {\lambda } ={\begin{bmatrix}\lambda _{1}\\\\\\vdots \\lambda _{j}\\\\\\vdots \\lambda {\fnMicrosoft}\fnMicrosoft {\fnMicrosoft}\fnMicrosoft {\fnMicrosoft} } ={\begin{bmatrix}\mu\\lambda \end{bmatrix}}$$

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

El sistema de ecuaciones y desigualdades correspondientes a las condiciones KKT generalmente no se resuelve directamente, excepto en los pocos casos especiales en los que se puede derivar analíticamente una solución de forma cerrada. En general, muchos algoritmos de optimización pueden interpretarse como métodos para resolver numéricamente el sistema de ecuaciones y desigualdades KKT.

Condiciones necesarias

Supongamos que la función objetiva ${\displaystyle f\colon \mathbb {R} {R} {R} {R} {R} {R}} {R}} {R} {R}} {R}}}$ y las funciones de limitación ${\displaystyle g_{i}\colon \mathbb {R}\justarrow \mathbb {R}$ y ${\displaystyle h_{j}\colon \mathbb {R} {n}\rightarrow \mathbb {R}$ tienen subderivativos en un punto ${\displaystyle x^{*}\in \mathbb {R} {\fn}$. Si ${\displaystyle x^{*}$ es un óptimo local y el problema de optimización satisface algunas condiciones de regularidad (ver abajo), entonces existen constantes ${\displaystyle \mu _{i}\ (i=1,\ldotsm)}$ y ${\displaystyle \lambda _{j}\ (j=1,\ldots\ell)}$, llamados multiplicadores KKT, de tal manera que los siguientes cuatro grupos de condiciones sostienen:

Estabilidad

Para minimizar ${\displaystyle f(x)}$: ${\displaystyle \partial f(x^{*})+\sum _{j=1}}\lambda _{j}\partial h_{j}(x^{*})+\sum ¿Qué? ¿Por qué? {0}$

Para maximizar ${\displaystyle f(x)}$: ${\displaystyle -\partial f(x^{*})+\sum _{j=1}{\ell }\lambda _{j}\partial h_{j}(x^{*})+\sum ¿Qué? ¿Por qué? {0}$

Viabilidad primordial

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

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

Doble viabilidad

${\displaystyle \mu _{i}\gq 0,{\text{ for }i=1,\ldotsm}$

Slackness complementario

${\displaystyle \sum ¿Qué? ¿Por qué?$

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

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 llaman multiplicadores Lagrange.

Prueba

Interpretación: Condiciones KKT como fuerzas de restricción de equilibrio en el espacio de estados

El problema primario se puede interpretar como mover una partícula en el espacio de ${\displaystyle x}$, y sometiéndolo a tres tipos de campos de fuerza:

• ${\displaystyle f}$ es un campo potencial que la partícula está minimizando. La fuerza generada por ${\displaystyle f}$ es ${\displaystyle -\partial f}$.
• ${\displaystyle g_{i}$ son superficies limitadas unilaterales. Se permite que la partícula se mueva dentro ${\displaystyle g_{i}\leq 0}$, pero cuando toca ${\displaystyle G_{i}=0}$Es empujado hacia adentro.
• ${\displaystyle H_{j}$ son superficies de restricción de dos caras. Se permite que la partícula se mueva solamente en la superficie ${\displaystyle H_{j}$.

La estacionaridad primaria declara que la "fuerza" de ${\displaystyle \partial f(x^{*}}$ es exactamente equilibrado por una suma lineal de fuerzas ${\displaystyle \partial h_{j}(x^{*}}$ y ${\displaystyle \partial g_{i}(x^{*}}$.

La doble viabilidad afirma además que todo ${\displaystyle \partial g_{i}(x^{*}}$ las fuerzas deben ser unilaterales, señalando hacia dentro el conjunto factible ${\displaystyle x}$.

La doble slackness declara que si ${\displaystyle g_{i}(x^{*})traducido0}$, entonces el ${\displaystyle \partial g_{i}(x^{*}}$ la fuerza debe ser cero, ya que la partícula no está en el límite, la fuerza de restricción unilateral no puede activarse.

Representación matricial

Las condiciones necesarias se pueden escribir con matrices jacobinas de las funciones de restricción. Vamos. ${\displaystyle \mathbf {g} (x):\,\!\Mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m}$ se define como ${\displaystyle \mathbf {g} (x)=\left(g_{1}(x),\ldotsg_{m}(x)\right)^{\top }$ y dejar ${\displaystyle \mathbf {h} (x):\,\!\Mathbb {R} ^{n}\rightarrow \mathbb {R}$ se define como ${\displaystyle \mathbf {h} (x)=\left(h_{1}(x),\ldotsh_{\ell }(x)\right)^{\top }$. Vamos. ${\displaystyle {\boldsymbol {\mu} }=\left(\mu _{1},\ldots\mu _{m}\right)^{\top }$ y ${\displaystyle {\boldsymbol {\lambda }=\left(\lambda) _{1},\ldots\lambda ¿Por qué?$. Entonces las condiciones necesarias pueden ser escritas como:

Estabilidad

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

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

Viabilidad primordial

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

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

Doble viabilidad

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

Slackness complementario

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

Condiciones de regularidad (o calificaciones de restricción)

Uno puede preguntar si un punto de minimización ${\displaystyle x^{*}$ del problema original de optimización limitada (asumiendo que existe) tiene que satisfacer las condiciones de KKT anteriores. Esto es similar a preguntar en qué condiciones el minimizador ${\displaystyle x^{*}$ de una función ${\displaystyle f(x)}$ en un problema sin restricciones tiene que satisfacer la condición ${\displaystyle \nabla f(x^{*}=0}$. Para el caso limitado, la situación es más complicada, y se puede indicar una variedad de condiciones de "regularidad" cada vez más complicadas bajo las cuales un minimizador limitado también satisface las condiciones KKT. Algunos ejemplos comunes de condiciones que garantizan esto se tabulan en los siguientes, con el LICQ el más utilizado:

Constraint	Acrónimos	Estado
Obligación por limitaciones de la línea	LCQ	Si ${\displaystyle g_{i}$ y ${\displaystyle H_{j}$ son funciones afines, entonces no se necesita otra condición.
Limitación de la independencia lineal	LICQ	Los gradientes de las restricciones de desigualdad activas y los gradientes de las limitaciones de igualdad son linealmente independientes ${\displaystyle x^{*}$.
Obstáculos Mangasarian-Desdeovitz	MFCQ	Los gradientes de las limitaciones de igualdad son linealmente independientes en ${\displaystyle x^{*}$ y existe un vector ${\displaystyle d\in \mathbb {R} {\fn}$ tales que ${\displaystyle \nabla g_{i}(x^{*} {\top }d made0}$ para todas las restricciones de desigualdad activas ${\displaystyle \nabla h_{j}(x^{*}{\top }d=0}$ para todas las limitaciones de igualdad.
Posibilidades de restricción de rango constante	CRCQ	Para cada subconjunto de los gradientes de las restricciones de desigualdad activas y los gradientes de las limitaciones de igualdad, el rango en una vecindad ${\displaystyle x^{*}$ es constante.
Requisitos constantes de dependencia lineal	CPLD	Para cada subconjunto de gradientes de restricciones de desigualdad activas y de gradientes de restricciones de igualdad, si el subconjunto de vectores depende linealmente de ${\displaystyle x^{*}$ con escalares no negativos asociados a las limitaciones de desigualdad, entonces sigue dependiendo linealmente en un barrio ${\displaystyle x^{*}$.
Cuasi-normalidad	QNCQ	Si los gradientes de las restricciones de desigualdad activas y los gradientes de las limitaciones de igualdad dependen linealmente de ${\displaystyle x^{*}$ con multiplicadores asociados ${\displaystyle \lambda _{j}$ para la igualdad y ${\displaystyle \mu _{i}\gq 0}$ para las desigualdades, entonces no hay secuencia ${\displaystyle x_{k}\to x^{*}$ tales que ${\displaystyle \lambda _{j}\neq 0\Rightarrow \lambda ¿Qué?$ y ${\displaystyle \mu _{i}\neq 0\Rightarrow \mu _{i}g_{i}(x_{k})}0}$
La condición de Slater	SC	Para un problema convexo (es decir, suponiendo minimización, ${\displaystyle f,g_{i}$ son convex y ${\displaystyle H_{j}$ es afine), existe un punto ${\displaystyle x}$ tales que ${\displaystyle h_{j}(x)=0}$ y ${\displaystyle g_{i}(x) Seleccion0.}$

Se pueden mostrar las implicaciones estrictas

⇒ MFCQ ⇒ CPLD ⇒ QNCQ

y

⇒ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ

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

Condiciones suficientes

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

Las condiciones necesarias son suficientes para la optimización si la función objetiva ${\displaystyle f}$ de un problema de maximización es una función de concave diferenciable, las limitaciones de desigualdad ${\displaystyle g_{j}$ son funciones convexas diferenciables, las limitaciones de igualdad ${\displaystyle H_{i}$ son funciones de afinidad, y la condición de Slater tiene. Del mismo modo, si la función objetiva ${\displaystyle f}$ de un problema de minimización es una función convexa diferenciable, las condiciones necesarias también son suficientes para la óptimabilidad.

Martin demostró en 1985 que la clase más amplia de funciones en las que las condiciones KKT garantizan la optimización global son las llamadas funciones invex de Tipo 1.

Condiciones suficientes de segundo orden

Para problemas de optimización no lineales y fluidos, se proporciona una condición suficiente de segundo orden de la siguiente manera.

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

${\displaystyle L(x,\lambda\mu)=f(x)+\sum ¿Qué? _{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 ${\displaystyle s\neq 0}$ es un vector que satisface lo siguiente,

${\displaystyle \left[\nabla] ¿Por qué? _{x}h_{j}(x^{*) {T}s=0}$

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

Si ${\displaystyle s^{T}\nabla _{xx}{2}L(x^{*},\lambda ^{*},\mu ^{*})s=0}$, la tercera orden Taylor ampliación del Lagrangian debe ser utilizado para verificar si ${\displaystyle x^{*}$ es un mínimo local. La minimización de ${\displaystyle f(x_{1},x_{2}=(x_{2}-x_{1}^{2})(x_{2}-3x_{1}{2}}}}$ es un buen contra-ejemplo, ver también la superficie de Peano.

Economía

A menudo en la economía matemática el enfoque KKT se utiliza en modelos teóricos para obtener resultados cualitativos. Por ejemplo, considere una empresa que maximice sus ingresos de ventas sujetos a una limitación mínima de ganancia. Letting ${\displaystyle Q}$ ser la cantidad de producción (a elegir), ${\displaystyle R(Q)}$ ser ingresos de ventas con un primer derivado positivo y con un valor cero en la salida cero, ${\displaystyle C(Q)}$ ser costos de producción con un primer derivado positivo y con un valor no negativo a cero salida, y ${\displaystyle G_{\min}$ ser el nivel mínimo aceptable positivo de ganancia, entonces el problema es significativo si la función de ingresos se nivela así que eventualmente es menos empinado que la función de costo. El problema expresado en la forma de minimización previamente dada es

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

sujeto a

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

${\displaystyle Q\geq 0,}$

y las condiciones KKT son

${\fnMicrosoft Sans Serif}$

Desde ${\displaystyle Q=0}$ violaría la limitación mínima de ganancia, tenemos ${\displaystyle Q0}$ y por lo tanto la tercera condición implica que la primera condición tiene igualdad. Resolver que la igualdad da

${\displaystyle {\frac {\text{d}R}{\text{d}Q}={\frac}={\frac} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif} {\fnMicrosoft Sans Serif}} {\f}}}}}\derecho).$

Porque se le dio eso ${\displaystyle {\text{d}R/{d}Q}$ y ${\displaystyle {\text{d}C/{d}Q}$ son estrictamente positivas, esta desigualdad junto con la condición de no negativa ${\displaystyle \mu }$ garantías ${\displaystyle \mu }$ es positivo y por lo tanto la empresa que maximiza los ingresos opera a un nivel de producción en el que los ingresos marginales ${\displaystyle {\text{d}R/{d}Q}$ es menor que el costo marginal ${\displaystyle {\text{d}C/{d}Q}$ — un resultado que es de interés porque contrasta con el comportamiento de una empresa que maximiza el beneficio, que opera a un nivel en el que son iguales.

Función de valor

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

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

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

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

Generalizaciones

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

${\displaystyle {\begin{aligned} limite\mu _{0}\,\nabla f(x^{*})+\sum ¿Qué? ¿Qué? g_{i}(x^{*})+\sum _{j=1}{\ell }\lambda _{j}\,\nabla h_{j}(x^{*})=0,\[4pt] ventaja\mu _{j}g_}(x^{*})=0,\quad i=1,\dotsm} {\endal} {} {} {}}}}}=0}=0}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\f}\fn\f}\f}\f}\f}\fn\fnK\f}\f}\fn\fn\fnh\fnh\f}\fnK\fnK\fnh\f}\f}\fn$

que se llaman condiciones de Fritz John. Esta condición de optimización se cumple sin restricciones y es equivalente a la condición de optimización 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.