Condiciones de Karush-Kuhn-Tucker

Condiciones de Karush-Kuhn-Tucker

En matemáticas, Las condiciones de Karush-Kuhn-Tucker (también conocidas como las condiciones KKT o Kuhn-Tucker) son condiciones necesarias y suficientes para que la solución de una programación no lineal séa óptima. Es una generalización del método de los Multiplicadores de Lagrange

consideremos el problema siguiente de optimización no lineal:

\, \mbox{minimizar } f(x)
\mbox{sujeto a } g_i(x) \le 0, h_j(x) = 0

donde f(x) es la función a ser minimizada, g_i (x)\ (i = 1, \ldots,m) son las restricciones de desigualdad y h_j (x)\ (j = 1,\ldots,l) son las restricciones de igualdad, y m y l son el número de restricciones de desigualdad e igualdad, respectivamente.

Las condiciones necesarias para problemas con restricciones de desigualdad fueron publicadas por primera vez en la Tesis doctoral de W. Karush,[1] aunque fueron renombradas tras un artículo en una conferencia de Harold W. Kuhn y Albert W. Tucker.[2]

Contenido

Condiciones necesarias

Supongamos que la función objetivo, por ejemplo, a minimizar, es f : \mathbb{R}^n \rightarrow \mathbb{R} y las funciones de restricción son g_i : \,\!\mathbb{R}^n \rightarrow \mathbb{R} y h_j : \,\!\mathbb{R}^n \rightarrow \mathbb{R}. Además, supongamos que son continuamente diferenciables en el punto x * . Si x * es un mínimo local, entonces existe constantes \lambda \ge 0, \mu_i \ge 0\ (i = 1,\ldots,m) y \nu_j\ (j = 1,...,l) tales que

\lambda + \sum_{i=1}^m \mu_i + \sum_{j=1}^l |\nu_j| > 0,
\lambda\nabla f(x^*) + \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \nu_j \nabla h_j(x^*) = 0,
\mu_i g_i (x^*) = 0\; \mbox{para todo}\; i = 1,\ldots,m.

Condiciones de regularidad (o cualificación de las restricciones)

En la condición necesaria anterior, el multiplicador dual λ puede ser igual a cero. Este caso se denomina degenerado o anormal. La condición necesaria no tiene en cuenta las propiedades de la función sino la geometría de las restricciones.

Existen una serie de condiciones de regularidad que aseguran que la solución no es degenerada (es decir \lambda \ne 0). Estas incluyen:

  • Cualificación de la restricción de independencia lineal (CRIL): los gradientes de las restricciones activas de desigualdad y los gradientes de las restricciones de igualdad son linealmente independientes en x * .
  • Cualificación de la restricción de Mangasarian-Fromowitz (CRMF): los gradientes de las restricciones activas de desigualdad y los gradientes de las restricciones de igualdad son linealmente independientes positivos en x * .
  • Cualificación de la restricción de rango constante (CRRC): para cada subconjunto de las restricciones activas de desigualdad y los gradientes de las restricciones de igualdad, el rango en el entorno de x * es constante.
  • Cualificación de la restricción de dependencia lineal constante positiva (DLCP): para cada subconjunto de restricciones activas de desigualdad y de gradientes de las restricciones de igualdad, si es linealmente dependiente positivo en x * entonces es linealmente dependiente positivo en el entorno de x * . (\{v_1,\ldots,v_n\} es linealmente dependiente positivo si existe a_1>=0,\ldots,a_n>=0 distintos de cero tal que a_1v_1+\ldots+a_nv_n=0)
  • Condición de Slater: para un problema únicamente con restricciones de desigualdad, existe un punto x tal que gi(x) < 0 para todo i = 1,\ldots,m

Puede verse que CRIL=>CRMF=>DLCP, CRIL=>CRRC=>DLCP, aunque CRMF no es equivalente a CRRC. En la práctica, se prefiere cualificación de restricciones más débiles ya que proporcionan condiciones de optimalidad más fuertes.

Condiciones suficientes

Séa la función objetivo f: \mathbb{R}^n \rightarrow \mathbb{R} y las funciones de restricción g_i : \mathbb{R}^n \rightarrow \mathbb{R} sean funciones convexas y h_j : \mathbb{R}^n \rightarrow \mathbb{R} sean las mínimo global.

Referencias

  1. ↑ Minima of Functions of Several Variables with Inequalities as Side Constraints. M.Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois. 1939. . disponible en http://wwwlib.umi.com/dxweb/details?doc_no=7371591 (con cargo)
  2. ↑ H. W. Kuhn,Tucker, A. W., Proceedings of 2nd Berkeley Symposium, Nonlinear programming, University of California Press, 1951, Berkeley

El paper de A. Kuhn y W. Tucker está disponible en: http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?handle=euclid.bsmsp/1200500249&view=body&content-type=pdf_1

Véase también

  • Alejandro Jofré, Patricio Felmer, Paul Bosch, Matías Bulnes, Arturo Prat, Luis Rademacher, José Zamora, y Mauricio Vargas. "Cálculo en Varias Variables - Apunte Completo" (2011). Disponible en: http://works.bepress.com/mvargas/1
  • Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
  • R. Andreani, J. M. Martínez, M. L. Schuverdt, On the relation between constant positive linear dependence condition and quasinormality constraint qualification. Journal of optimization theory and applications, vol. 125, no2, pp. 473-485 (2005).

Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Albert W. Tucker — Nacimiento 28 de noviembre de 1905 Ontario, Canadá Fallecimiento 25 de enero, 1995 Highstown, N.J., Estados Unidos Residencia …   Wikipedia Español

  • Microeconomía — El modelo de oferta y demanda describe como varían los precios según el balance entre disponibilidad del producto a diferentes precios (oferta) y los deseos de aquellos con poder adquisitivo según el precio (demanda). La gráfica muestra un… …   Wikipedia Español

  • Multiplicadores de Lagrange — En los problemas de optimización, el método de los multiplicadores de Lagrange, llamados así en honor a Joseph Louis Lagrange, es un procedimiento para encontrar los máximos y mínimos de funciones de varias variables sujetas a restricciones. Este …   Wikipedia Español

  • Programación no lineal — Saltar a navegación, búsqueda En matemáticas, Programación no lineal (PNL) es el proceso de resolución de un sistema de igualdades y desigualdades sujetas a un conjunto de restricciones sobre un conjunto de variables reales desconocidas, con un… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”