1 1er semestre 2013 Profesor: Pamela Álvarez M.Departamento de Ingeniería Industrial y de Sistemas Pontificia Universidad Católica de Chile Optimización ICS 1113 Parte IV: Programación No Lineal 1er semestre Profesor: Pamela Álvarez M.

2 Programación no LinealYa vimos: Nociones básicas de convexidad: Veremos: Condiciones necesarias y suficientes para un mínimo local o global. Métodos de búsqueda de soluciones óptimas (Gradiente, Newton) Optimización con restricciones de igualdad y desigualdad. ICS1113. Prof.: Pamela Álvarez M.

3 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Sea el problema: Donde: Dominio D: ¿Cuándo se dice que es un problema sin restricciones? ICS1113. Prof.: Pamela Álvarez M. 3

4 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Un punto extremo de una función definida sobre un dominio D puede ser local o global, estricto o no estricto. Definiciones que ya vimos: máximo global máximo global estricto máximo local máximo local estricto ICS1113. Prof.: Pamela Álvarez M. 4

5 Programación no LinealHay que recordar lo que vimos de convexidad ICS1113. Prof.: Pamela Álvarez M.

6 Programación no LinealProposiciones: Si P) es convexo, todo punto mínimo local del problema es también su óptimo global. Si f(x) es estrictamente convexa sobre D, entonces todo punto mínimo local de f(x) es también su único mínimo global. ICS1113. Prof.: Pamela Álvarez M.

7 Programación no LinealEn la práctica, ¿cómo saber si una función es convexa?: Sea f(x)=f(x1,x2,…,xn) continua y dos veces diferenciable. Su matriz Hessiana es: Veamos la siguiente figura: ICS1113. Prof.: Pamela Álvarez M.

8 Programación no LinealCaracterización de la matriz Hessiana: Si todos los determinantes de las matrices menores son estrictamente positivos, la matriz H se dirá definida positiva. Si todos los determinantes de las matrices menores son no negativos, la matriz H se dirá semidefinida positiva. Si todos los determinantes de las matrices menores impares son estrictamente negativos y los de las matrices menores pares estrictamente positivos, la matriz H se dirá definida negativa. ICS1113. Prof.: Pamela Álvarez M.

9 Programación no LinealSea f() dos veces diferenciable sobre D, con D  Rn y convexo. Entonces f() es convexa sobe D si y solo si D2f(x)=H es semidefinida positiva x D. ICS1113. Prof.: Pamela Álvarez M.

10 Programación no LinealOptimización Sin Restricciones: Sigamos utilizando el problema básico Definición: Si la función es diferenciable sobre Rn , un punto se dice ESTACIONARIO para f si: ICS1113. Prof.: Pamela Álvarez M.

11 Programación no LinealLas siguientes son las condiciones necesarias y suficientes para que una función f(x) tenga puntos extremos. Teorema 1 (Condición Necesaria): Sea una función diferenciable. Si el punto es mínimo local de f, entonces: Dem: Sea tal que no cumple la condición y sea Entonces se tiene que: Derivada direccional de f en la dirección d es negativa. Contradice el hecho que es mínimo local. ICS1113. Prof.: Pamela Álvarez M.

12 Programación no Lineal¿Es posible saber, analizando otras propiedades si el punto es un mínimo local de f? ICS1113. Prof.: Pamela Álvarez M.

13 Programación no LinealTeorema 2 (Condición Necesaria de 2º orden): Sea una función de clase C2. Sea el punto tal que Entonces si es semidefinida positiva, es mínimo local de f. Teorema 3 (Condición Suficiente): Sea una función de clase C2. Sea el punto tal que Entonces si es definida positiva, es mínimo local estricto de f. ICS1113. Prof.: Pamela Álvarez M.

14 Programación no LinealDem: La expresión de Taylor de f en torno a es: Como se tiene: Como es definida positiva se tiene: Y por lo tanto: En consecuencia, es mínimo local. ICS1113. Prof.: Pamela Álvarez M.

15 Programación no Lineal¿Cómo construir un algoritmo con esta información? ¿Qué hacer si estoy en un punto x0 cualquiera? Evaluar el punto Buscar un punto estacionario Determinar una dirección de descenso Moverse en dicha dirección Verificar criterio de parada Método iterativo dada la complejidad de determinar puntos estacionarios en forma analítica. ICS1113. Prof.: Pamela Álvarez M.

16 Programación no LinealDefinición: Sea una función diferenciable. En un punto , se llama dirección de descenso para f en a todo vector d  Rn tal que Una vez que tenemos la dirección de descenso, ¿cómo llego al siguiente punto? k  R, se denomina paso Se determina de modo tal que f(xk+1) < f(xk). ICS1113. Prof.: Pamela Álvarez M.

17 Programación no LinealLa estructura general de un método de descenso es: Inicialización, k=0: Seleccionar un punto de partida x0 Iteración k: Si entonces xk es un punto estacionario: finalizar Determinar una dirección de descenso dk para f en xk. Determinar un paso k > 0 tal que f(xk+1)= f(xk+ k dk )< f(xk). Definir xk+1= xk+k dk e incrementar el índice k. ICS1113. Prof.: Pamela Álvarez M.

18 Programación no LinealMétodo del Gradiente o Descenso más pronunciado Contribución del matemático francés Cauchy. Algoritmo: Sea x0  Rn un punto inicial, k = 0. Si f(xk) = 0, STOP, es un punto estacionario de f Determinar una dirección de descenso Moverse en esa dirección . Determinar el nuevo punto. Hacer k = k +1, ir a 2. ICS1113. Prof.: Pamela Álvarez M.

19 Programación no LinealMétodo del Gradiente o Descenso más pronunciado Para completar nuestro algoritmo tenemos que responder: Como ya señalamos debemos escoger alguna dirección d tal que: f(x0+  d )< f(x0) ¿Cómo escoger d y  de modo que f(x0+  d ) sea lo más pequeño posible? ICS1113. Prof.: Pamela Álvarez M.

20 Programación no LinealMétodo del Gradiente o Descenso más pronunciado Dirección d para el método del gradiente: ¿A qué corresponde f(x0) ? Dirección de máximo crecimiento de la función en el punto. Recordemos que nuestro problema es de minimización. Escoger la dirección de máximo decrecimiento, entonces: d=-f(xk) ICS1113. Prof.: Pamela Álvarez M.

21 Programación no LinealMétodo del Gradiente o Descenso más pronunciado Ahora cómo determina el paso . Determinar el mínimo relativo de f en esa dirección. Es decir, se debe encontrar el  que minimice f(xk+1) Problema unidimensional. Resolver: min{f(x+ d):  >0} ICS1113. Prof.: Pamela Álvarez M.

22 Programación no LinealMétodo del Gradiente o Descenso más pronunciado Nuestro algoritmo finalmente es: Sea x0  Rn un punto inicial, k = 0. Si f(xk) = 0, STOP, es un punto estacionario de f Sea la dirección de descenso d=-f(xk) Resolver min{f(x+ d):  >0} . Sea k su solución. Sea xk+1=xk+ k dk. Hacer k = k +1, ir a 2. ICS1113. Prof.: Pamela Álvarez M.

23 Programación no LinealMétodo del Gradiente o Descenso más pronunciado ¿Es realizable computacionalmente nuestro algoritmo? Criterios de parada: ICS1113. Prof.: Pamela Álvarez M.

24 Programación no LinealMétodo del Gradiente o Descenso más pronunciado ICS1113. Prof.: Pamela Álvarez M.

25 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Ejemplo: Dado el siguiente problema: Resuelva con el método del gradiente partiendo del punto (0,0). Resuelva con el método del gradiente partiendo del punto (1,1). Debe hacer por lo menos 2 iteraciones completas. ICS1113. Prof.: Pamela Álvarez M. 25 25

26 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Solución: ICS1113. Prof.: Pamela Álvarez M. 26 26

27 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Solución: ICS1113. Prof.: Pamela Álvarez M. 27 27

28 Programación no LinealMétodo del Gradiente o Descenso más pronunciado ¿Cómo es la convergencia del método? Podría ser extremadamente lenta, dependerá de la función objetivo. Curvas de nivel más elípticas Curvas de nivel circulares ICS1113. Prof.: Pamela Álvarez M.

29 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Convergencia del Método del gradiente: La convergencia del método del gradiente depende de un parámetro , que se calcula a partir de los valores propios de la matriz hessiana. Mientras el parámetro sea más cercano a 0, el método converge más rápido. ICS1113. Prof.: Pamela Álvarez M. 29 29

30 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Convergencia del Método del gradiente: Tiene relación con la excentricidad de las curvas de nivel. También podemos ver que si vamos a minimizar una función cuadrática simple de la forma: Con a y b>0 ¿Cómo será la convergencia para distintos valores de los parámetros? ICS1113. Prof.: Pamela Álvarez M. 30 30

31 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Método del Gradiente o Descenso más pronunciado Dijimos que la convergencia podía ser extremadamente lenta dependiendo de la función objetivo. ¿Se puede mejorar? Aquí tenemos el Método de Newton ICS1113. Prof.: Pamela Álvarez M. 31 31

32 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Método de Newton Se puede aproximar la función f entorno a xk, a través de una expansión de Taylor de 2º grado. ¿Por qué esta función es una buena aproximación para f ? ICS1113. Prof.: Pamela Álvarez M. 32 32

33 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Método de Newton Se minimiza la función q. Despejando obtenemos: ICS1113. Prof.: Pamela Álvarez M. 33 33

34 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Método de Newton Algoritmo: Sea x0  Rn un punto inicial, k = 0. Si f(xk) = 0, STOP, es un punto estacionario de f Sea dk = –[Hf(xk)]-1f(xk) Sea xk+1=xk+ k dk. Hacer k = k +1, ir a 2. ICS1113. Prof.: Pamela Álvarez M. 34 34

35 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Método de Newton Ejemplo: ICS1113. Prof.: Pamela Álvarez M. 35 35

36 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Método de Newton Este método iterativo típicamente se aproxima sucesivamente a un óptimo local. Sin embargo, es posible que tarde infinitas iteraciones en lograrlo. También puede que no converja. Criterios de parada: ICS1113. Prof.: Pamela Álvarez M. 36 36

37 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Método de Newton Es importante señalar que este método busca puntos extremos. Este método utiliza mayor información que el anterior optimizando polinomios de segundo orden tangentes a un punto. Hay que revisar el signo de la segunda derivada de la función en cada punto. Más complejo. Introducir modificaciones al método. ICS1113. Prof.: Pamela Álvarez M. 37 37

38 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Método de Newton El cálculo reiterativo de [Hf(xk)]-1 puede resultar muy costoso..... Idea básica de un método “Quasi-Newton”: Trabajar con una matriz que se “parezca” a [Hf(xk)]-1 Por ejemplo, comenzar con [Hf(xo)]-1 y actualizarla parcialmente en cada iteración.... Hay diversas formas de hacer eso, es un tema ampliamente abordado y los métodos implementados en el software moderno incorporan los últimos avances en este sentido... Las aproximaciones hacen perder algo de la convergencia cuadrática, pero la ganancia en eficiencia es enorme. ICS1113. Prof.: Pamela Álvarez M. 38 38

39 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Ya estudiamos cómo resolver problemas no lineales sin restricciones. Pero el mundo tiene restricciones ICS1113. Prof.: Pamela Álvarez M. 39

40 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal En la mayor parte de los problemas de toma de decisiones están presentes ligaduras entre las variables o limitaciones en las mismas: Unas debidas a las ecuaciones del modelo Otras al rango permisible de algunas variables Otras debidas a reglas de operación, existencias, etc. La presencia de restricciones limita el espacio de búsqueda pero, al mismo tiempo, dificulta el encontrar la solución óptima. No es útil considerar una política conducente a calcular el óptimo sin restricciones y luego tratar de aplicarla. ICS1113. Prof.: Pamela Álvarez M. 40 40

41 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Veamos un par de ejemplos: En la frontera En el interior ICS1113. Prof.: Pamela Álvarez M. 41 41

42 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Caso 1: Problema Unidimensional Caso 2: Problema con restricciones de igualdad Caso 3: Problemas con desigualdades ICS1113. Prof.: Pamela Álvarez M. 42 42

43 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal ¿Qué puede decir del punto (1,1) para el siguiente problema? ICS1113. Prof.: Pamela Álvarez M. 43

44 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Analice la convexidad de la siguiente función y qué ocurre con el punto (1,1): ICS1113. Prof.: Pamela Álvarez M. 44

45 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Clasifique según los valores de los parámetros a, b y c los puntos críticos de la siguiente función e indique si se trata de óptimos globales: ICS1113. Prof.: Pamela Álvarez M. 45

46 Programación no LinealVeamos un ejemplo: Considere el problema: Condiciones de primer orden: Condiciones de segundo orden: ICS1113. Prof.: Pamela Álvarez M.

47 ICS1113. Prof.: Pamela Álvarez M.Programación no Lineal Método de Newton Ejemplo: k xk f'(xk) f''(xk) 4 1 3.29 470.06 701.54 2 2.62 167.35 267.32 3 2.00 58.91 103.13 1.43 20.37 40.58 5 0.92 6.82 16.53 6 0.51 2.15 7.20 7 0.21 0.59 3.59 8 0.05 0.11 2.32 9 0.00 0.01 2.02 ICS1113. Prof.: Pamela Álvarez M. 47 47