1 PROGRAMACIÓN NO LINEAL - 3CARLOS JAVIER URIBE -UNIVERSIDAD DE LA COSTA

2 MULTIPLICADORES LAGRANGELa técnica de los multiplicadores de Lagrange permite solucionar NLPs con restricciones en forma de igualdad:

3 MULTIPLICADORES LAGRANGELa función de Lagrange (lagrangeano) asociada con un NLP con restricciones de igualdad es: donde 𝜆 𝑖 es el multiplicador de Lagrange de la restricción 𝑖.

4 MULTIPLICADORES LAGRANGEUna solución 𝑥 ∗ , 𝜆 ∗ es un punto estacionario de la función lagrangeana si satisface: 𝛻𝐿 𝑥 ∗ , 𝜆 ∗ =0

5 MULTIPLICADORES LAGRANGESi 𝑥 ∗ , 𝜆 ∗ es un punto estacionario de la función Lagrangeana 𝐿 𝑥,𝜆 y 𝑥 ∗ es un óptimo no restringido de 𝐿 𝑥, 𝜆 ∗ , entonces 𝑥 ∗ es un óptimo del correspondiente NLP con restricciones de igualdad.

6 MULTIPLICADORES LAGRANGELa aproximación Lagrangiana para resolver NLP con restricciones de igualdad es: Forme la función lagrangeana asociada al NLP con restricciones de igualdad Resuelva el sistema de ecuaciones 𝛻L x ∗ , λ ∗ =0 para encontrar los puntos estacionarios Establezca que la parte de x ∗ del punto estacionario es un punto óptimo del Lagrangeano y por lo tanto también óptimo del modelo original

7 MULTIPLICADORES LAGRANGELos valores óptimos de los multiplicadores de Lagrange, 𝑣 ∗ , asociados con la restricción 𝑔 𝑖 𝑥 = 𝑏 𝑖 se pueden interpretar como las tasas de cambio en el valor óptimo por unidad de incremento en el lado derecho 𝑏 𝑖 .

8 MULTIPLICADORES LAGRANGEEl método tiene serias limitaciones: Las ecuaciones para determinar los puntos estacionarios solo se pueden resolver si son lineales o funciones no lineales simples. En otros casos, resolver esas ecuaciones puede ser más difícil que buscar directamente una solución óptima en el problema inicial. Si un modelo tiene muchas restricciones de desigualdad, puede ser una tarea combinatoria compleja determinar cuáles están activas en la solución óptima.

9 CONDICIONES KKT Las condiciones de Karush-Kuhn-Tucker (KKT), permiten resolver NLP diferenciables. Esto es, de la forma: donde 𝑓 y cada 𝑔 𝑖 son funciones diferenciables.

10 CONDICIONES KKT Son 4 las condiciones de KKT para las variables óptimas del primal y el dual. Condición de factibilidad: En el óptimo se deben satisfacer las restricciones. Condición del gradiente: En el óptimo no existe una dirección factible de movimiento que potencialmente pueda mejorar la función objetivo. Holgura complementaria. Restricción de signos de las variables duales.

11 CONDICIONES KKT Se satisfacen las restricciones del modelo primal:

12 CONDICIONES KKT Se satisface la ecuación de gradiente 𝛻 𝑔 𝑖 𝑥 𝜆 𝑖 =𝛻𝑓(𝑥) o de forma equivalente: 𝛻𝑓 𝑥 ∗ − 𝛻 𝑔 𝑖 𝑥 ∗ 𝜆 𝑖 ∗ =0

13 CONDICIONES KKT Las restricciones de desigualdad deben estar activas en un óptimo local o la variable de Lagrange correspondiente debe ser igual a cero. Es decir, 𝜆 𝑖 𝑔 𝑖 𝑥 − 𝑏 𝑖 =0, para todas las desigualdades.

14 CONDICIONES KKT Los multiplicadores de Lagrange 𝜆 𝑖 en la restricción 𝑖 deben satisfacer las restricciones de signo: Objetivo i es ≤ i es  i es = Minimizar 𝜆 𝑖 ≤0 𝜆 𝑖 ≥0 No restringida Maximizar

15 CONDICIONES KKT Cualquier 𝑥 para el cual existe un correspondiente 𝜆 que satisface las anteriores condiciones se denomina un punto KKT. Si 𝑥 es un punto KKT de un programa convexo, entonces 𝑥 es un óptimo global.

16 CONDICIONES KKT Un óptimo local de un NLP diferenciable debe ser un punto KKT si todas las restricciones son lineales o si los gradientes de todas las restricciones activas en el óptimo local son linealmente independientes.

17 CASOS ESPECIALES DE NLPProgramas convexos Programas separables Programas cuadráticos Programas geométricos

18 REFERENCIAS Bazaraa, M., et al (2006). Nonlinear Programming Theory and Algorithms. Wiley. Hedengren, J.D. (2016) Karush-Kuhn-Tucker (KKT) Conditions. Recuperado de: Rardin, R. (1998). Optimization in Operations Research. Prentice-Hall. Winston, W. (2004). Operations Research: Algorithms and Applications. Thomson.