Modelo de rostow

Pontificia Universidad Católica Escuela de Ingeniería Departamento de Ingeniería Industrial y de Sistemas

Clase 15 • Condiciones de Karush Kuhn Tucker
ICS 1102 • Optimizaci´n o Profesor : Claudio Seebach 25 de septiembre de 2006

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 105

Condiciones de Karush Kuhn Tucker

Proposici´n 9 Sup´ngase que f (x), gj (x) con j =1, ..., m, son funo o ciones diferenciables que satisfacen ciertas condiciones de regularidad. ¯ Entonces, x puede ser una soluci´n ´ptima para el problema de prograo o maci´n no-lineal, s´lo si existen m n´meros µ1, ..., µm que satisfagan o o u todas las condiciones necesarias siguientes:

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 106

Condiciones de Karush KuhnTucker

 m ∂gj (¯) x ∂L ∂f (¯) x  µj = + ≥ 0   ∂xi ∂xi ∂xi  j=1  m x x ∂gj (¯) ∂L ∂f (¯) ∀i = 1, .., n ¯ ¯ µj xi = xi + = 0   ∂xi ∂xi ∂xi j=1    ¯ xi ≥0  ∂L   x = gj (¯) − bj ≤ 0   ∂µj  ∂L ∀j = 1, .., m µj = µj gj (¯) − bj = 0  x  ∂µj    µj ≥ 0

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 107

Comentarios acerca de KKT
• Interpretaci´n de losmultiplicadores µj : o

– Indican cu´nto baja la funci´n objetivo si bj aumenta en una unidad. a o – Aumentar bj implica expandir el dominio, o sea expandir el espectro de posibilidades de donde escoger.
m

• Complementariedad de las holguras: f (¯) + x
j=1

µj gj = 0

µj (gj (¯) − bj ) = 0 x – En el ´ptimo el gradiente de la funci´n objetivo es una combinaci´n o o o lineal del gradiente delas restricciones activas

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 108

Comentarios acerca de KKT
• Las condiciones de optimalidad de Karush-Kuhn-Tucker son condiciones necesarias y s´lo garantizar´ optimalidad global si se cumplen adio ıan cionalmente otras condiciones de convexidad. Corolario 10 Sup´ngase que f (x) es una funci´n convexa y difero o enciable, yque g1(x), g2(x), ..., gm(x) tambi´n lo son en donde todas e estas funciones satisfacen las condiciones de regularidad. Entonces ¯ ¯ x = (¯1, ..., xn) es una soluci´n ´ptima si y s´lo si se satisfacen todas x o o o las condiciones del teorema. • El m´todo identifica puntos ´ptimos locales que cumplan condiciones e o de regularidad • Los gradientes de las restricciones activas en el punto deben serlinealmente independientes.

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 109

Condiciones de Regularidad del Dominio
• Ciertas condiciones garantizan regularidad en todo el dominio:

Proposici´n 11 (Slater) Las condiciones de regularidad de Slater eso tablecen que si hay un dominio D = {x : gj (x) ≤ 0} con gj (x) ¯ funciones convexas, y existe un punto x ∈ D tal quegj (¯) < 0 x ∀j = 1, . . . , m,entonces todo punto x ∈ D es regular.

Proposici´n 12 (Slater-Usawa) Las condiciones de regularidad de Slatero Usawa establecen que si hay un dominio D = {x : gj (x) ≤ 0} con gj (x) ¯ funciones convexas, y existe un punto x ∈ D tal que gj (¯) < 0 para x toda restricci´n no lineal, y gj (¯) ≤ 0 para toda restricci´n lineal, o x o entonces todo punto x ∈ D es regular.Corolario 13 En problemas lineales basta que haya un punto factible para decir que su dominio es regular.

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 110

Ejemplo

Ejemplo 16 Considere el siguiente problema: P ) max f (x1, x2) = ln(x1 + 1) + x2 s.a 2x1 + x2 ≤ 3 x 1 , x2 ≥ 0

Apuntes de Clases • Optimizaci´n • Claudio Seebach o

No Lineal • 111

Soluci´nEjemplo o

P ) max f (x1, x2) = ln(x1 + 1) + x2 s.a 2x1 + x2 ≤ 3 x 1 , x2 ≥ 0 El problema puede modificarse del siguiente modo: P ) min − ln(x1 + 1) − x2 → −f (x) es convexa s.a 2x1 + x2 ≤ 3 → g(x) es convexa x 1 , x2 ≥ 0 El problema presenta caracter´sticas que permiten garantizar que el ı m´todo de KKT identificar´ s´lo un punto y que ´ste ser´ el ´ptimo e a o e a o global. Adem´s, el dominio est´...