1. REPBLICA BOLIVARIANA DE VENEZUELA INSTITUTO UNIVERSITRIO
POLITCNICO SANTIAGO MARIO INGENIERA DE SISTEMAS Profesor: Wilfreddy
Inciarte Autores: Marienny Ysea Wilber Coello
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. 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. 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. 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. 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. 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. 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. Tabla 1. Resultados de los Mtodos de Newton y quasi-
Newton.
10. Bsquedas Lineales sin Derivadas Ajuste Cuadrtico Figura 1.
Funcin objetivo a minimizar junto a una parbola interpolante.
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. 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. Figura 2. Ilustracin de los casos 1a y 1b de la bsqueda
lineal mediante interpolacin cuadrtica
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. 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. 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. Optimizacin Multidimensional sin Restricciones Figura 3.
Ilustracin de las direcciones de descenso en R2.
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. 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. 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. 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. 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. 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. 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. Etapa 2: (Generacin de la direccin de bsqueda). Se obtiene
y se calcula la direccin de bsqueda como:
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. 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. 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. 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. 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. 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. 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. ( , ) 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. 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. 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. 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. 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. 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. Problema geomtrico restringido:
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. 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. 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. 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. 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. 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. 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. 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. 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.