KUHN TUCKER
Sean:
- la función objetivo f : ℝ n → ℝ , x = ( xi )i =1,...,n = ( x1 ,..., xn ) ∈ ℝ n
-
Las restricciones g k : ℝ n → ℝ, k = 1,..., m
Supondremos que tanto la función objetivo f comolas restricciones g k son
diferenciables. Vamos a considerar el siguiente problema de optimización:
Max f ( x)
s.a. g 1 ( x ) ≤ 0
⋮
g
m
( x) ≤ 0
x1 ≥ 0,..., xn ≥ 0
Construimos la siguiente funciónLagrangiana
m
L ( x, λ ) = f ( x) − ∑ λk g k ( x)
k =1
Donde λ = ( λ1 ,..., λm ) ∈ ℝ
m
Definición: Diremos que x verifica KT si existe un λ tal que:
∂L
∂L
- KT1: ∀i = 1,..., n :
≤ 0, xi ≥ 0, xi
=0∂xi
∂xi
-
∂L
= 0 . Solución positiva
si xi > 0 ⇒
∂xi
k
k
KT2: ∀k = 1,..., m : λk ≥ 0, g ( x) ≤ 0, λk g ( x) = 0
( si λ
k
> 0 ⇒ g k = 0. Restricción saturada )
Tenemos los siguientesresultados:
T.1 (Condiciones necesarias) Si x es solución óptima entonces x verifica KT.
T.2 (Condiciones necesarias y suficientes) Si f es una función cuasicóncava
( ⇔ {x ∈ ℝ : f ( x ) ≥ k} es convexo∀k ) y ∀k = 1,..., m las funciones g son convexas
(⇒ {x ∈ ℝ : g ( x ) ≤ 0} es convexo ) , entonces x es un óptimo si y sólo si verifica KT.
n
n
k
k
Ejemplo gráfico
Dos variables x = ( x1 , x2 )y una restricción g
Supondremos que se dan las condiciones necesarias y suficientes para aplicar
el T.2. Supondremos también que f es una función estrictamente creciente,
∂f
por lo tanto
> 0, i = 1, 2. Denotamos por:
∂xi
∂L ∂L
∂f ∂f
∂g ∂g
∇L =
,
,
,
, ∇f =
, ∇g =
∂x1 ∂x2
∂x1 ∂x2
∂x1 ∂x2
L ( x, λ ) = f ( x ) − λ g ( x )
Haremos el análisis para el caso desoluciones positivas: x > 0 .
Como ∇f ( x) > 0, ∀x , no pueden existir máximos incondicionados: ∇f ( x) = 0 . Esto
impide que λ = 0 , ya que si no, tendríamos L( x, λ ) = f ( x) y por KT1, ∇L = ∇f = 0
encontradicción con ∇f > 0 . Entonces, como λ > 0 , por KT2 se tiene que
g ( x) = 0 (se agota la restricción)
Como x > 0 , por KT1, tenemos ∇L = ∇f − λ∇g = 0 ⇔ ∇f = λ∇g
x2
g ( x) = 0
f ( x)
∇L = 0...
Regístrate para leer el documento completo.