1. 1. REPBLICA BOLIVARIANA DE VENEZUELA INSTITUTO UNIVERSITRIO POLITCNICO SANTIAGO MARIO INGENIERA DE SISTEMAS Profesor: Wilfreddy Inciarte Autores: Marienny Ysea Wilber Coello
2. 2. PROGRAMACIN NO LINEAL Es el proceso de resolucin de un sistema de igualdades y desigualdades sujetas a un conjunto de restricciones sobre un conjunto de variables reales desconocidas, con un funcin objetivo a maximizar (o minimizar), cuando alguna de las restricciones o la funcin objetivo no son lineales El problema de programacin no lineal puede enunciarse de una forma muy simple: Maximizar una funcin objetivo Minimizar una funcin objetivo
3. 3. ALGORITMOS DE OPTIMIZACIN SIN RESTRICCIONES Los mtodos para obtener la solucin de un PPNL se basan en obtener una sucesin de puntos tales que su lmite sea una solucin ptima del problema que se considera. Para asegurar la convergencia debe suponerse que el PPNL es un problema convexo diferenciable. Sin embargo, estos algoritmos se aplican an cuando no se satisfacen estas condiciones. El criterio de parada se basa en las CKKT. Cuando stas se satisfacen con una cierta tolerancia, se para el proceso iterativo y se toma como mnimo el punto correspondiente. Considere el problema: Minimizar ( )Z f x
4. 4. Los mtodos se dividen en dos categoras: 1. Los que usan informacin sobre las derivadas. Se basan en aplicar mtodos numricos para resolver las condiciones necesarias de KKT: donde x* es la solucin que se busca. 2. Los que slo usan evaluaciones de la funcin objetivo. Utilizan frmulas de interpolacin para estimar iterativamente el mnimo de un problema unidimensional. Si f es convexa, el problema de obtener un ptimo es equivalente al de resolver la anterior ecuacin. Pueden usarse mtodos de bsqueda de races para resolverlo.
5. 5. BSQUEDAS LINEALES CON DERIVADAS MTODO DE NEWTON Puesto que se tiene: Si se quiere que sea cero se obtiene: Considerando que obtenemos: Que utiliza las derivadas primera y segunda de f. ( 1) ( ) ( ) ( 1) ( ) ( ) ( ) '( )( )t t t t t g x g x g x x x ( ) ( 1) ( ) ( ) ( ) '( ) t t t t g x x x g x ( ) ( 1) ( ) ( ) ( ) '( ) t t t t g x x x g x
6. 6. MTODO QUASI-NEWTON O DE LA SECANTE Reemplazando en la expresin anterior por la aproximacin Se llega a : Con lo que: Que solo requiere derivadas primeras. ( ) ( 1) ( ) ( 1) ( ) ( )t t t t g x g x x x ( ) ( 1) ( ) ( ) ( 1) ( ) ( 1) ( ) ( ) ( ) ( ) t t t t t t t g x x x x x g x g x ( ) ( 1) ( ) ( ) ( 1) ( ) ( 1) '( ) ( ) '( ) '( ) t t t t t t t f x x x x x f x f x
7. 7. Ejemplo Mtodo de Newton/Mtodo quasi-Newton Minimizar Realizando el anlisis mediante el mtodo de Newton tenemos: Las derivadas primera y segunda son: y la sucesin asociada al mtodo de Newton resulta Ntese que si la sucesin converge al punto entonces, tomando lmites en ambos lados de la relacin se obtiene , y esta ecuacin tiene como su nica solucin . 4 ( ) ( 1)Z f x x 3 2 '( ) 4( 1) ''( ) 12( 1) f x x f x x ( ) ( ) 3 ( 1) ( ) ( ) ( ) 2 ( ) ( ) ( ) '( ) 4( 1) ( ) ''( ) 12( 1) 1 2 1 ( 1) 3 3 3 t t t t t t t t t f x x x x x t f x x x x x * 1x x 2 / 3 1/ 3x x
8. 8. Si realizamos el anlisis mediante el mtodo quasi-Newton obtenemos: El mtodo de Newton requiere slo un punto inicial, pero el quasi- Newton necesita dos puntos para comenzar. La siguiente tabla muestra las algunas iteraciones de ambos mtodos, cuando se utiliza como punto inicial x1 = 0, para el mtodo de Newton, y x1 = 0 y x2 = 1/3 para el quasi-Newton. ( ) ( 1) ( ) ( ) ( 1) ( ) ( 1) ( ) ( 1) ( ) ( ) 3 ( ) 3 ( 1) 3 ( ) ( 1) ( ) 3( 1) ( ) '( ) '( ) '( ) ( 1) ( 1) ( 1) 1 1 1 t t t t t t t t t t t t t t t t t t f x x x f x f x x x x x x x x x x x x x x
9. 9. Tabla 1. Resultados de los Mtodos de Newton y quasi- Newton.
10. 10. Bsquedas Lineales sin Derivadas Ajuste Cuadrtico Figura 1. Funcin objetivo a minimizar junto a una parbola interpolante.
11. 11. Bsquedas Lineales sin Derivadas Ajuste Cuadrtico El mtodo de ajuste cuadrtico usa una interpolacin parablica de f, basada en tres puntos. Supngase que se trata de minimizar una funcin convexa f(x), y que se tienen tres puntos a < b < c tales que Sin prdida de generalidad se puede suponer que una de las desigualdades es estricta. Seguidamente se ajusta una parbola pasando por los tres puntos (a, f(a)), (b, f(b)) y (c, f(c)). Su vrtice es: ( ) ( ) ( )f a f b f c 22 2 ( ) ( ) ( ) ( ) ( ) ( )1 2 ( ) ( ) ( ) ( ) ( ) ( ) b a f b f c b c f b f a v b b a f b f c b c f b f a
12. 12. Bsquedas Lineales sin Derivadas Ajuste Cuadrtico Si los tres puntos estn alineados, el denominador degenera a cero y la expresin anterior no es vlida. Sin embargo, esto no ocurre si se cumple al menos una de las condiciones: f(a)>f(b) y f(b)
13. 13. Figura 2. Ilustracin de los casos 1a y 1b de la bsqueda lineal mediante interpolacin cuadrtica
14. 14. Caso 2: v > b. Similarmente, , se elige , y si se elige . Caso 3: v = c. En este caso se recobran los tres puntos iniciales, y no se puede decidir cul es el nuevo intervalo reducido. Para evitar este problema, se reemplaza b por (a + b)/2 y se repite el proceso de nuevo, con la garanta de que la nueva situacin estar en los Casos 1 2. ( ) ( )f v f b { ', ', '} { , , }a b c a b v ( ) ( )f v f b { ', ', '} { , , }a b c b v c
15. 15. Optimizacin Multidimensional sin Restricciones Sea el problema Minimizar Donde y es diferenciable. Este problema se puede resolver por el mtodo de descenso, que genera un sucesin de puntos tales que: hasta que se satisface una condicin de parada. El mtodo consiste en iterar las etapas: Problema de generacin de una direccin de descenso: Dado x(t), el problema consiste en obtener una direccin d(t) tal que un ligero desplazamiento a partir de x(t) en tal direccin disminuya el valor de la funcin objetivo. d es una direccin descendente de f en x si existe un nmero positivo tal que: ( )Z f x n x : n f ( ) { }t x (1) (2) ( ) ( ) ( ) ... ( ) ...t f x f x f x
16. 16. Optimizacin Multidimensional sin Restricciones ( ) ( ) para todo (0, )f x d f x Problema de bsqueda lineal: Una vez obtenida la direccin descendente d(t) de f en el punto x(t), el problema consiste en decidir el tamao del desplazamiento, , tal que el nuevo punto tenga un valor asociado de la funcin objetivo menor que el del punto original x(t), es decir, elegir tal que para generar el nuevo punto . En muchos casos, el desplazamiento se calcula de forma que se minimice la funcin objetivo en esa direccin d(t). Lema 1 Sea diferenciable en . Sea d un vector de Si , entonces d es una direccin de descenso de f en x. 0ta ( ) ( ) ( ) ( ) ( )t t t tf x d f x ( ) ( )t t tx d ( 1) ( ) ( )t t t tx x d t : n f n x n ( ) 0T f x d
17. 17. Optimizacin Multidimensional sin Restricciones Figura 3. Ilustracin de las direcciones de descenso en R2.
18. 18. Los algoritmos que se basan en direcciones descendentes tienen la siguiente estructura: Algoritmo 1 (Direccin descendente) Etapa 1: (Valor inicial). Elegir un punto inicial , y hacer t = 1. Etapa 2: (Generacin de la direccin de bsqueda). Obtener una direccin descendente d(t). Etapa 3: (Comprobacin de la Optimalidad). Si d(t) = 0, entonces parar (x(t) es un punto KTT del problema). En otro caso, continuar. Etapa 4: (Bsqueda lineal). Encontrar el salto, ,que resuelve el problema unidimensional Minimizar sujeto a (1) n x ( ) ( ) ( )t t LSZ f x d 0
19. 19. Etapa 5: (Actualizar el punto). Hacer Etapa 6: (Criterio de parada). Si , entonces parar. En otro caso, hacer t = t + 1, e ir a la Etapa 2. Algoritmo 2 (Regla de Armijo) ( 1) ( ) ( )t t t tx x d ( 1) ( )t t x x Figura 4. Ilustracin grfica de la regla de Armijo
20. 20. Etapa 1: (Valor inicial). Elegir y . Valores tpicos son y . Se toma . Etapa 2: Si ir a la Etapa 3. En otro caso, ir a la Etapa 4. Etapa 3: Si parar, y hacer . En otro caso, hacer e ir a la Etapa 2. Etapa 4: Si parar. En otro caso, hacer e ir a la Etapa 3. 0, (0,1) 1 0.2 2 10 ( ) ( )g g ( ) ( )g g t ( / ) ( / )g g /
21. 21. DETERMINACIN DE LAS DIRECCIONES DE DESCENSO El criterio de parada suele ser , que se basa en la condicin necesaria de optimalidad y en la continuidad de Los mtodos ms importantes para seleccionar la direccin de descenso son: 1. Mtodo de la mxima pendiente. Este mtodo usa , como direccin de descenso en x(t). Si se cumple ( ) ( )t f x ( ) 0f x ( )f x ( ) ( ) ( )t t d f x ( ) ( ) 0t f x ( ) ( ) ( ) ( ) ( ) 2 ( ) ( ) ( ) ( ( ) ) 0t T t t T t t f x d f x f x f x 2. Mtodo de Newton. Este mtodo usa 12 ( ) ( ) ( ) ( ) ( )t t d t f x f x
22. 22. Si es definida positiva y su inversa tambin lo es, y entonces d(t) es descendente 2 ( ) ( )t f x ( ) ( ) 0t f x 1( ) ( ) ( ) 2 ( ) ( ) ( ) ( ) ( ) ( ) 0t T t t T t t f x d f x f x f x 3. Mtodos quasi-Newton. La direccin de bsqueda del mtodo de Newton resulta indefinida si la matriz hesiana es singular. Adems, el esfuerzo computacional puede resultar muy grande para problemas de dimensin modesta. Para resolver este problema se aproxima por una matriz definida positiva B(t),que se actualiza sucesivamente para que converja a la matriz hesiana en el punto solucin. La direccin de bsqueda se calcula as: 2 ( ) [ ( )]t f x 1( ) ( ) ( ) ( )t t d t B f x
23. 23. 4. Un Mtodo general. Los mtodos anteriores son casos particulares de considerar una transformacin del gradiente cambiado de signo mediante una matriz definida positiva A(t), es decir, para todo x0. Sea ,entonces 5. Mtodo del gradiente conjugado. Este mtodo utiliza ( ) 0T t x A x ( ) ( ) ( ) [ ( )]t t t d A f x ( ) ( ) ( ) ( ) ( ) ( ) ( ) [ ( ] 0t T t t T t t f x d f x A f x ( ) ( ) ( 1) (1) 1( ) ,con 0t t t td f x d d que es descendente, ya que, si ,se puede demostrar que: ( ) ( ) 0t f x 2( ) ( ) ( ) ( ) ( 1) 1( ) ( ) ( )t T t t t T t tf x d f x f x d
24. 24. Es un algoritmo para resolver numricamente los sistemas de ecuaciones lineales cuyas matrices son simtricas y definidas positivas. Es un mtodo iterativo, que se puede aplicar a los sistemas dispersos que son demasiado grandes para ser tratados por mtodos directos como la descomposicin de Cholesky. Tales sistemas surgen frecuentemente cuando se resuelve numricamente las ecuaciones en derivadas parciales. El mtodo del gradiente conjugado se puede utilizar tambin para resolver los problemas de optimizacin sin restricciones como la minimizacin de la energa. Ejemplo: Etapa 1: (Punto inicial). Se toma x(1) = (0, 0)T. De nuevo, la direccin de bsqueda es , por lo que no se repite, y se hace: t=2 y x2 = (0,1/2)T. MTODO DE GRADIENTE CONJUGADO
25. 25. Etapa 2: (Generacin de la direccin de bsqueda). Se obtiene y se calcula la direccin de bsqueda como:
26. 26. Etapa 3: (Comprobacin de optimalidad). Como d(2) 0, se trata de una direccin de descenso. Etapa 4: (Bsqueda lineal). Para calcular el salto, se resuelve el problema Minimizar puesto que
27. 27. Se obtiene el valor ptimo de la bsqueda lineal es: 2=1 > 0. Etapa 5: (Actualizacin). Se hace Etapa 6: (Comprobacin de optimalidad). Puesto que x(3) satisface se ha alcanzado el ptimo, y el algoritmo para
28. 28. La programacin estocstica trata los problemas de programacin matemtica en los que algunos de los parmetros implicados son variables aleatorias, generalmente de distribucin conocida. Se han desarrollado distintos modelos dentro de la programacin estocstica. En particular, uno de los problemas que ms se ha estudiado es el de las distintas formas de la funcin objetivo, o por expresarlo mejor, los distintos criterios posibles de optimizacin. PROGRAMACIN ESTOCSTICA
29. 29. ALGORITMOS PARA LA OPTIMIZACIN CON RESTRICCIONES El problema de la optimizacin con restricciones puede resolverse mediante los siguientes mtodos: 1. Mtodos duales: Resuelven el problema dual en vez del problema primal. 2. Mtodos de penalizacin: Transforman el problema restringido en uno nuevo en el que las restricciones e incorporan a la funcin objetivo por medio de una seleccin adecuada de parmetros de penalizacin. Estos algoritmos transforman el problema restringido en una sucesin de problemas sin restricciones. 3. Mtodos de linealizacin parcial: Extienden los algoritmos de direccin descendente al caso de restricciones. Ahora se fuerza a que las direcciones sean admisibles. 4. Mtodo de los multiplicadores o del lagrangiano aumentado: Son mtodos de penalizacin cuadrtica que usan el lagrangiano aumentado como funcin objetivo.
30. 30. 5. Mtodos de programacin secuencial cuadrtica: Resuelven una secuencia de problemas de programacin cuadrtica que aproximan el problema original. Cuanto mayor sea el nmero de iteraciones mayor ser la aproximacin obtenida.
31. 31. MTODOS DUALES La principal razn para usar los mtodos duales es que en la mayora de los casos resulta una funcin cncava en un conjunto convexo muy sencillo, por lo que no tiene mximos locales no globales. Deben plantearse dos cuestiones: a) Cmo obtener la solucin del primal tras resolver el dual. b) Cmo resolver el problema dual. Sea el problema Minimizar Sujeto a ( )PZ f x ( ) 0 ( ) 0 h x g x Donde son continuas.: , : y :n l n m f h g
32. 32. El problema dual es: Maximizar Donde la funcin dual es Con dominio de definicin Para evaluar la funcin dual para (t) y (t) es necesario resolver el problema que se llama Problema lagrangiano. Para discutir la primera cuestin, se define el conjunto ( , ); 0DZ 1 1 ( , ) ( ) ( ) ( ) l m x k k j j k j Infimo f x h x g x ( , ) 0, existe el minimo ( , , )D L x ( ) ( ) ( , , )t t xMinimo L x
33. 33. ( , ) minimiza ( , , )x x x L x Si no existe la holgura dual, es decir, , y somos capaces de resolver el problema dual y obtener como valores ptimos , entonces cualquier punto factible resuelve el problema primal. El teorema que sigue justifica que para los problemas convexos no existe la holgura dual, y que se puede obtener una solucin primal basndose en las soluciones del problema dual. Teorema 1 (Condicin suficiente para una solucin primal basada en la dual.) Sea una solucin del problema dual y supngase que . Es diferenciable en Entonces cualquier elemento resuelve el problema primal. * * D PZ Z * * ( , ) * * * ( , )X X * * ( , ) ( , ) * * * ( , )X X
34. 34. MTODOS DE PENALIZACIN Los mtodos de penalizacin transforman el problema restringido original en una secuencia de problemas sin restringir mediante funciones de penalizacin. La idea de convertirlos en problemas no restringidos es muy atractiva, pues stos se resuelven muy fcil y eficientemente. Puesto que todos los mtodos tratan las igualdades de la misma forma, stos se clasifican por la forma de tratar las desigualdades. Hay dos tipos de mtodos: 1. Mtodos del punto exterior. La secuencia de soluciones de los problemas sin restricciones contiene slo puntos no factibles (exteriores a la regin factible). 2. Mtodos del punto interior o mtodos barrera. La secuencia de soluciones de los problemas sin restricciones contiene slo puntos factibles (interiores a la regin factible). Un caso particular interesante es el mtodo del punto interior que se analiza posteriormente.
35. 35. MTODO DEL PUNTO EXTERIOR En el mtodo del punto exterior la penalizacin impuesta al punto x aumenta cundo ste se desva de la regin factible. De nuevo, al actualizar los parmetros de penalizacin, la sucesin correspondiente de puntos mnimos de los problemas penalizados converge a la solucin ptima del problema inicial. En este caso los puntos de la sucesin estn fuera de la regin factible.
36. 36. PROGRAMACIN SEPARABLE Una funcin separable es aquella que puede expresarse como la suma de funciones de una nica variables. Estas funciones tienen la ventaja de que los trminos no lineales pueden ser aproximados por trminos lineales a tramos (piecewise). Utilizando esta tcnica se puede escribir un programa lineal entero, e incluso lineal continuo para estas funciones. El trmino separable puede aparecer en la funcin objetivo o en las restricciones de un problema de optimizacin La programacin separable es un caso especial de programacin convexa, en donde la suposicin adicional es Todas las funciones f(x) y g(x) son funciones separables. Una funcin separable es una funcin en la que cada trmino incluye una sola variable, por lo que la funcin se puede separar en una suma de funciones de variables individuales. Por ejemplo, si f(x) es una funcin separable, se puede expresar como:
37. 37. son cada tina funciones de una sola variable x1 y x2, respectivamente. Usando el mismo razonamiento. Es importante distinguir estos problemas de otros de programacin convexa, pues cualquier problema de programacin separable se puede aproximar muy de cerca mediante uno de programacin lineal y, entonces, se puede aplicar el eficiente mtodo smplex.
38. 38. PROGRAMACIN GEOMTRICA Soluciona un caso especial de problemas de programacin no lineal. Este mtodo resuelve al considerar un problema dual asociado los siguientes dos tipos de programacin no lineal. Problema geomtrico no restringido:
39. 39. Problema geomtrico restringido:
40. 40. La Programacin Geomtrica fue diseada por Duffin, Peterson y Zener. La lgica de la Programacin Geomtrica se basa en la desigualdad de Cauchy (desigualdad de media aritmtica - geomtrica) :
41. 41. PROGRAMACIN CUADRTICA La programacin cuadrtica (QP) es el nombre que se le da a un procedimiento que minimiza una funcin cuadrtica de n variables sujeta a m restricciones lineales de igualdad o desigualdad. Un programa cuadrtico es la forma ms simple de problema no lineal con restricciones de desigualdad. La importancia de la programacin cuadrtica es debida a que un gran nmero de problemas aparecen de forma natural como cuadrticos (optimizacin por mnimos cuadrados, con restricciones lineales), pero adems es importante porque aparece como un subproblema frecuentemente para resolver problemas no lineales ms complicados. Las tcnicas propuestas para solucionar los problemas cuadrticos tienen mucha similitud con la programacin lineal. Especficamente cada desigualdad debe ser satisfecha como igualdad. El problema se reduce entonces a una bsqueda de vrtices exactamente igual que se haca en programacin lineal.
42. 42. Donde c es un vector de coeficientes constantes; A es una matriz (m x n) y se asume, en general que Q es una matriz simtrica Existen diferentes tipos de problemas de programacin cuadrtica, los cuales se pueden clasificar en: Problemas cuadrticos de minimizacin sin restricciones, requieren minimizar la funcin cuadrtica f (x) sobre el espacio completo. Problemas cuadrticos de minimizacin sujetos a restricciones de igualdad, requieren minimizar la funcin objetivo f (x) sujeta a restricciones lineales de igualdad Ax = b.
43. 43. Problemas cuadrticos convexos. Son cualquiera de los mencionados arriba, en el cual la funcin objetivo a ser minimizada, f (x) es convexa. Problemas cuadrticos no convexos. Son cualquiera de los mencionados arriba, en el cual la funcin objetivo a ser minimizada, f (x) es no convexa. Problemas de complementariedad lineal. Son problemas especiales con un sistema de ecuaciones en variables no negativas, en el cual las variables estn formadas en varios pares llamados pares complementarios.
44. 44. Histricamente, las funciones cuadrticas fueron prominentes porque provean modelos locales simples para funciones no lineales generales. Una funcin cuadrtica, es la funcin no lineal ms simple, y cuando es usada como una aproximacin para una funcin no lineal general, esta puede capturar la informacin importante de la curvatura, lo que una aproximacin lineal no puede. El uso de aproximaciones cuadrticas para resolver problemas con funciones no lineales generales se remonta mucho tiempo atrs. Entre los mtodos ms destacados, tenemos al mtodo de Newton y el mtodo de gradiente conjugado. Para la programacin cuadrtica se pueden encontrar mnimos locales, mnimos globales, puntos estacionarios o de KKT, (son los que satisfacen las condiciones de KKT del problema).
45. 45. La programacin no convexa incluye todos los problemas de programacin no lineal que no satisfacen las suposiciones de programacin convexa. En este caso, aun cuando se tenga xito en encontrar un mximo local, no hay garanta de que sea tambin un mximo global. Por lo tanto, no se tiene un algoritmo que garantice encontrar una solucin ptima para todos estos problemas; pero s existen algunos algoritmos bastante adecuados para encontrar mximos locales, en especial cuando las formas de las funciones no lineales no se desvan demasiado de aquellas que se supusieron para programacin convexa. Ciertos tipos especficos de problemas de programacin no convexa se pueden resolver sin mucha dificultad mediante mtodos especiales. PROGRAMACIN NO CONVEXA
46. 46. PROGRAMACIN FRACCIONAL Suponga que la funcin objetivo se encuentra en la forma de una fraccin, esto es, la razn o cociente de dos funciones, Estos problemas de programacin fraccional surgen, por ejemplo, cuando se maximiza la razn de la produccin entre las horas- hombre empleadas (productividad), o la ganancia entre el capital invertido (tasa de rendimiento), o el valor esperado dividido entre la desviacin estndar de alguna medida de desempeo para una cartera de inversiones (rendimiento/riesgo). Se han formulado algunos procedimientos de solucin especiales1 para ciertas formas de f1(x) y f2 (x)
47. 47. Cuando se puede hacer, el enfoque ms directo para resolver un problema de programacin fraccional es transformarlo en un problema equivalente de algn tipo estndar que disponga de un procedimiento eficiente. Para ilustrar esto, suponga que f(x) es de la forma de programacin fraccional lineal. donde c y d son vectores rengln, x es un vector columna y c0 y dQ son escalares. Tambin suponga que las funciones de restriccin g (x)son lineales, es decir, las restricciones en forma matricial son Ax < b y x > 0. Con algunas suposiciones dbiles adicionales, el problema se puede transformar en un problema equivalente de programacin lineal si se establece
48. 48. que se puede resolver con el mtodo smplex. En trminos generales, se puede usar el mismo tipo de transformacin para convertir un problema de programacin fraccional con /(x) cncava, f2 (x) convexa y g (x) convexas, en un problema equivalente de programacin convexa.