Condiciones kkt

Solo disponible en BuenasTareas
  • Páginas : 12 (2832 palabras )
  • Descarga(s) : 0
  • Publicado : 29 de agosto de 2012
Leer documento completo
Vista previa del texto
condiones KKTCondiciones de Karush-Kuhn-Tucker
Departamento de Matem´ticas, CSI/ITESM a 21 de abril de 2010


Historia

Las condiciones necesarias que deben satisfacer los optimos de problemas de optimizaci´n no lineal con ´ o restricciones de desigualdad fueron publicadas por primera vez (1939) en la tesis de Maestr´ de William ıa Karush (1917-1997) (en aqu´l entonces estudiante dematem´ticas de la Universidad de Chicago) (W. Karush e a (1939): Minima of Functions of Several Variables with Inequalities as Side Constraints. M.Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois.), aunque fueron renombradas tras un art´ ıculo en una conferencia de Harold W. Kuhn y Albert W. Tucker en 1951. (H. W. Kuhn, Tucker, A. W.: Nonlinear programming (Proceedings of 2ndBerkeley Symposium, University of California Press, 1951, Berkeley.) Las condiciones de Karush-Kuhn-Tucker (KKT) son una generalizaci´n del m´todo de los multiplicadores de o e Lagrange para restricciones de desigualdad.

16.2.

Formulaci´n o

Considere el problema de optimizaci´n o Min f (x1 , x2 , . . . , xn ) sujeto a g1 (x1 , x2 , . . . , xn ) ≤ 0 g2 (x1 , x2 , . . . , xn ) ≤ 0 . . . gm(x1 , x2 , . . . , xn ) ≤ 0 El m´todo de soluci´n procede de la siguiente manera. Cambiemos cada restricci´n de desigualdad gi ≤ 0 a e o o una restricci´n de igualdad introduciendo una variable si de la siguiente manera: o g i ≤ 0 → g i + s2 = 0 i (1)

De acuerdo a la t´cnica de los multiplicadores de Lagrange se construye la funci´n: e o
m

F (x, λ, s) = f (x) +
i=1

λi · (gi + s2 ) i(2)

Los puntos que minimizan a f sujeta a las restricciones gi ≤ 0 (1 ≤ i ≤ m) est´n dentro de los puntos cr´ a ıticos de F : Que hacen cero las parciales con respecto a las variables xj (j = 1, . . . , n): ∂f ∂F = + ∂xj ∂xj
m

λi
i=1

∂gi =0 ∂xj

Que hacen cero las parciales con respecto a las variables λi (i = 1, . . . , m): ∂F = g i + s2 = 0 ↔ g i ≤ 0 i ∂λi Que hacen cero lasparciales con respecto a las variables si (i = 1, . . . , m): ∂F = 2 λi s i = 0 ↔ λi s i = 0 ↔ λi g i = 0 ∂si Lo anterior se resume en el siguiente teorema que indica las condiciones que deben satisfacer los puntos que minimizan la funci´n sujeta a las restricciones. o Teorema Suponga una formulaci´n para el problema anterior de minimizaci´n. Si x0 = (a1 , a2 , . . . , an ) es un o o o ´ptimo, entoncesdeben existir n´meros reales llamados multiplicadores λ1 , λ2 ,. . . ,λm no negativos u tales que (a1 , a2 , . . . , an , λ1 , . . . , λm ) es un punto cr´ ıtico para F . Es decir que se cumple: + ∂f (xo ) ∂xj Bloque I + = 0 j = 1, 2 . . . , n Bloque II: Condici´n de Holgura Complementaria o λi gi (xo ) = 0 i = 1, 2, . . . , m Bloque III gi ≤ 0 i = 1, 2, . . . , m
∂gi (xo ) m i=1 λi ∂xj

(3)Observe que los valores de si se obtienen de la relaci´n gi + s2 = 0 y de que gi ≤ 0. o i Si ahora el problema es de maximizaci´n: o Max f (x1 , x2 , . . . , xn ) sujeto a g1 (x1 , x2 , . . . , xn ) ≤ 0 g2 (x1 , x2 , . . . , xn ) ≤ 0 . . . gm (x1 , x2 , . . . , xn ) ≤ 0 (4)

2

Para su soluci´n lo cambiamos a un problema de minimizaci´n para −f (x). En este caso la funci´n F queda o o o en laforma:
m

F (x, λ, s) = −f (x) +
i=1

λi · (gi + s2 ) i

De tal forma que las condiciones que deben satisfacer los optimos ahora quedan de acuerdo al siguiente ´ teorema. Teorema Suponga una formulaci´n para el problema anterior en el caso de maximizaci´n. Si x0 = (a1 , a2 , . . . , an ) o o es un ´ptimo, entonces deben existir n´meros reales llamados multiplicadores λ1 , λ2 ,. . . ,λm nonegativos o u tales que (a1 , a2 , . . . , an , λ1 , . . . , λm ) es un punto cr´ ıtico para F . Es decir, que se cumple: − ∂f (xo ) + ∂xj
∂gi (xo ) m i=1 λi ∂xj

Bloque I = 0

j = 1, 2 . . . , n (5)

Bloque II λi gi (xo ) = 0 i = 1, 2, . . . , m Bloque III gi ≤ 0 i = 1, 2, . . . , m

16.3.

Uso de las Condiciones KKT

La forma de operar las condiciones de KKT ser´ la siguiente:...
tracking img