Ccondiciones de optimalidad

8.2.2 Condiciones de Karush–Kuhn–Tucker
El resultado te´orico m´as importante en el campo de la programaci´on no lineal
es el que lleva a las llamadas condiciones de Karush, Kuhn, y Tucker. Estascondiciones deben ser satisfechas por la soluci´on ´optima de cualquier problema
lineal y la mayor´ıa de los problemas no lineales. Constituyen la base para eldesarrollo de muchos algoritmoscomputacionales y proporcionan un criterio de
parada para muchos otros, permitiendo establecer cuando ha sido alcanzado un
´optimo local restringido.
En los problemas diferenciables de optimizaci´on norestringida la condici´on
necesaria para que una soluci´on sea un m´ınimo local es que se anule el gradiente.
Por el contrario, esta propiedad no es cierta para problemas diferenciables
restringidos,como ilustra la figura 8.6 para el punto ￣x = a. Las condiciones
de Karush–Kuhn–Tucker generalizan la condici´on necesaria desarrollada para
problemas no restringidos a los problemas conrestricciones.
Definici´on 8.5 (condiciones de Karush–Kuhn–Tucker (CKKT)). El vector
￣x ∈ IRn satisface las CKKT para el PPNL (8.1)–(8.2) si existe un par de
vectores λ ∈ IR_ y μ ∈ IRm tales que
∇f(￣x) +
__k=1
λk∇hk(￣x) +
_m
j=1
μj∇gj(￣x) = 0 (8.3)
hk(￣x) = 0, k = 1, . . . , D (8.4)
gj(￣x) ≤ 0, j = 1, . . . , m (8.5)
μjgj(￣x) = 0, j = 1, . . . , m (8.6)
μj ≥ 0, j = 1, . . . , m (8.7)
Losvectores μ y λ se denominan multiplicadores de Kuhn–Tucker. La condici
´on (8.6) es conocida con el nombre condici´on de complementariedad, la condici
´on (8.7) requiere la no negatividad de losmultiplicadores, y es llamada condici
´on de factibilidad dual, y (8.4)–(8.5) se denominan condiciones de factibilidad
primal.
La g´enesis de estas condiciones de optimalidad de primer orden (CKKT)
puedeser motivada en el caso de dos variables independientes, como se muestra
en la figuras 8.7, 8.8, y 8.9.
Consid´erese el caso de una restricci´on de igualdad (v´ease la figura 8.7). Satisfacer
la...