Condiciones de Karush-Kuhn-Takker

En la teoría de la optimización , las condiciones de Karush-Kuhn-Tucker ( condiciones de Karush-Kuhn-Tucker , KKT) son condiciones necesarias para resolver un problema de programación no lineal . Para que la solución sea óptima, se deben cumplir algunas condiciones de regularidad. El método es una generalización del método del multiplicador de Lagrange . Por el contrario, las restricciones impuestas a las variables no son ecuaciones , sino desigualdades .

Historia

Kuhn y Tucker generalizaron el método del multiplicador de Lagrange (para usar en la construcción de criterios de optimalidad para problemas con restricciones de igualdad) al caso de un problema general de programación no lineal con restricciones de igualdad y desigualdad [1] .

Las condiciones necesarias para un mínimo local para problemas con restricciones se han estudiado durante mucho tiempo. Uno de los principales es la transferencia de restricciones a la función objetivo propuesta por Lagrange. Las condiciones de Kuhn-Tucker también se derivan de este principio [2] .

Planteamiento del problema

En el problema de optimización no lineal, se requiere encontrar el valor de la variable multidimensional , minimizando la función objetivo: $x=(x^{{(1)}},...,x^{{(n)}})$

\min \limits _{{x\in X}}f(x)

bajo condiciones en las que se imponen restricciones de tipo desigualdad sobre la variable: $X$

g_{i}(x)\leqslant 0,\;i=1\ldots m

y los componentes del vector no son negativos [3] . $X$

William Karush en su trabajo de tesis encontró las condiciones necesarias en el caso general, cuando las condiciones impuestas pueden contener tanto ecuaciones como desigualdades. Independientemente de él, Harold Kuhn y Albert Tucker llegaron a las mismas conclusiones .

Condiciones necesarias para el mínimo de una función

Si , bajo las restricciones impuestas, es una solución al problema, entonces existe un vector de multiplicadores de Lagrange tal que se cumplen las siguientes condiciones para la función de Lagrange : ${\ sombrero {x}} \ en \ arg \ min f$ $\lambda \in \mathbb{R} ^{m}$ $L(x)=f(x)+\sum_{{i=1}}^{m}\lambda_{i}g_{i}(x)$

estacionariedad : ; $\min _{x}L(x)=L({\sombrero {x)))$
falta de rigidez complementaria : ; $\lambda _{i}g_{i}({\hat {x)))=0,\;i=1\ldots m$
no negatividad : . $\lambda _{i}\geqslant 0,\;i=1\ldots m$

Condiciones suficientes para el mínimo de una función

Las condiciones necesarias enumeradas para la función mínima en el caso general no son suficientes. Siempre que las funciones y sean convexas, hay varias opciones para condiciones adicionales que hacen que las condiciones del teorema de Karush-Kuhn-Tucker sean suficientes: $F$ ${\displaystyle g_{1},\puntos,g_{m))$

Redacción simple

Si un punto admisible satisface las condiciones de estacionariedad, no rigidez complementaria y no negatividad, y también , entonces . ${\ sombrero {x}}$ $\lambda _{1}>0$ ${\ sombrero {x}} \ en \ arg \ min f$

Condiciones más débiles

Si para un punto admisible se cumplen las condiciones de estacionariedad, no rigidez complementaria y no negatividad, y también ( condición de Slater ), entonces . ${\ sombrero {x}}$ $\exists {\tilde {x}}:g_{i}({\tilde {x}})<0,\;i=1\ldots m$ ${\ sombrero {x}} \ en \ arg \ min f$

Notas

↑ Condiciones de Kuhn-Tucker . Consultado el 7 de febrero de 2011. Archivado desde el original el 24 de enero de 2011. (indefinido)
↑ Zhiliniskas A., Shaltyanis V. Búsqueda del óptimo: la computadora amplía las posibilidades. — M.: Nauka, 1989, pág. 76, ISBN 5-02-006737-7
↑ Fundamentos matemáticos de la cibernética, 1980 , p. 253.

Véase también

La investigación de operaciones

Literatura

J. Hadley. Programación no lineal y dinámica. - M. : Mir, 1967. - 506 p.
Korshunov Yu. M. Fundamentos matemáticos de la cibernética. - M. : Energía, 1980. - 424 p.