Trabajo De Campo

Programacion convexa

Es la rama de la programación matemática que trabaja con la teoría y los métodos de minimización de funciones convexas sobre conjuntos convexos definidas mediante sistemas de igualdades y desigualdades. La programación cuadrática es una rama dentro de la programación convexa.

Sea f : R → R.

Decimos que f es convexa:

Si el dominio f es un conjunto convexo.

Si para toda x1, x2 que pertenecen al dominio de f

Si para todo número real t entre 0 y 1, se satisface que

f (tx1 + (1 – t)x2) < t∙f (x1) + (1 – t)∙f (x2)

Algoritmos

No existe un algoritmo estándar único que se pueda usar siempre para resolver problemas de programación convexa.

Se han desarrollado muchos algoritmos diferentes, cada uno con ventajas y desventajas, y la investigación continúa activa en esta área.

Algoritmo de gradiente:

Se modifica de alguna manera el procedimiento de búsqueda del gradiente de los problemas No Restringidos para evitar que la trayectoria de búsqueda penetre la frontera de restricción, por ejemplo un metodo de gradiente popular es el metodo de gradiente reducido generalizado (GRG) el excel emplea el GRG para resolver problemas de programacion convexa.

Algoritmos secuenciales no restringidos:

Estos Algoritmos incluyen

Método de Finalización

Método de Barrera

Estos algoritmos convierten el problema de optimizacion restringida original en una sucesion de problemas de optimizacion no restringida cuyas soluciones óptimas convergen a la solucion óptima del problema original. Los problemas de optimizacion no restringidas se pueden resolver por medio del procedimiento de busqueda de gradiente, Esta conversión se logra al incorporar las restricciones a una función barrera que se resta de la función objetivo con el fin de imponer un castigo grande a la violacion de cualquier restriccion o aun al hecho de estar cerca de los limites.

Algoritmos de aproximacion secuencial:

Estos Algoritmos incluyen:

Método de Aproximación Lineal

Método de Aproximación Cuadrática

Estos algoritmos sustituyen la función objetivo no lineal por una sucesión de aproximaciones lineales o cuadráticas para problemas de optimizacion linealmente restringidos.

Algoritmo de Frank-Wolfe

Paso inicial: se encuentra una solucion de prueba factible inicial X(0), por ejemplo al aplicar los procedimeientos de programacion lineal para encontrar una solucion.

Se hace K=1

Iteracion K

Para j= 1,2….,n, se evalua

(∂ f (x))/(∂x j) en x = x^((k-1) )

y se iguala cj a este valor

Se encuentra una solucion optima x_LP^((k)) para el siguiente problema de programacion lineal.

Maximizar g (x) = ∑_(j=1)^n▒〖cj xj〗

Sujeta a

A x≤b y x ≥0

Para la variable t ( 0≤t ≤1), se establece

h(t)

= f(x) para x = x^((k-1)) + t 〖(x〗_LP^((k))- x^((k-1)))

De manera que h(t) proporciona el valor de f(x) sobre el segmento de recta entre x(k − 1) (donde t = 0) y (donde t = 1).

Se aplica algún procedimiento como el de búsqueda en una dimensión para maximizar h(t) en 0 ≤ t ≤ 1 y se establece x(k) igual a la x correspondiente.

Regla de detencion: si x^((k-1)) y x^((k)) estan lo suficientemente cerca, el proceso se detiene y se usa x^((k)) ( o una extrapolacion de x^((0)), x^((1)),…. x^((k-1)), x^((k))) como la estimacion de una solucion optima. De otra manera se hace k= k+1 y se realiza otra iteracion.

Ejemplo.

Considere el siuiente problema de programacion convexa linealmente restringido:

Maximizar F (x) = 〖5x〗_(1-) x_(1+)^2 8_x2-〖2x〗_2^2

Sujeta a

3_x1+〖2x〗_2≤6

Y

X1 ≥0, X2 ≥0

Observe que

∂f/∂x1=5-2 x_(1,) ∂f/∂x2=8-4x_2

Por lo que el maximo no restringido x= 5/2 , 2 viola las restrincciones funcionales. Por lo tanto, se necesita trabajar un poco mas para encontrar el maximo restringido.

Iteracion 1: como X= (0,0), es claro que es factible ( y corresponde a la solucion inicial BF de las restrinciones de programacion lineal), se elige como la solucion de prueba inicial x^((0)) para el algoritmo de Frank Wolfe, al sustituir X1= 0 y X2= 0 en las expresiones de las derivadas parciales se obtiene C1= 5 y C2= 8, con lo que g(x)= 〖5x〗_1 + 〖8x〗_2 es la primera aproximacion lineal de la funcion objetivo. Con la solucion grafica de este problema de programacion lineal (vea figura 12,17) a) se llega a X_LP^((K))=(0,3). En la parte 3 del paso iterativo, los puntos en el segmento de recta que une a (0,0) y (0,3), que se muestran en la figura12.17a, se expresan por

〖(X〗_1, X2) – (0,0) t [(0,3) –(0,0)] para 0≤ t ≤1 = (0,3t)

Como se muestra en la sexta columna de la tabla 12.6. Esta expresion da entonces

h(t) = f (0,3t) = 8(3t) – 2〖(3t)〗^2

= 24t – 〖18t〗^2

De modo que el valor t= t* que maximiza h(t) en el intervalo 0≤ t ≤ 1 se puede obtener, en este caso, al establecer (dh(t))/dt = 24 – 36 t = 0

Por lo que t* = 2/3 este resultado conduce a la solucion de prueba

x^1 = (0,0) + 2/3 [(0,3) - (0,0)] lo cual completa la primera iteracion

Iteracion 2: para esbozar los calculos que conducen a los resultados del segundo renglon de la tabla 12.6, x^((1)) = (0,2) da

C1= 5 -2 (0) = 5

C2= 8 -4 (2) = 0

Al resolver el problema en una grafica con la funcion objetivo g(x) = 〖5x〗_1 en la region factible de la figura 12.16 se obtiene 〖 X〗_LP^((1)) = (2,0). De esta forma, la expresion para el segmento de recta entre x^1 y X_LP^((2)) es x =( 0,2 ) + t [(2,0) – (0,2)]

= ( 2t, 2- 2t)

De manera que

h(t) - f (2t, 2 – 2t)

= 5 (2t ) – 〖(2t)〗^2 + 8 ( 2-2t ) – 2 (2 - 〖2t)〗^2

8 + 10 t - 12t^2

(dh (t))/dt = 10 – 24t = 0

Se llega a t* 5/12 [(2,0) – (0,2)]

=( 5/6, 7/6)

Con lo que se completa la segunda iteracion.

En la fig 12.17 se observa como las soluciones de prueba adquieren valores de puntos alternados entre dos trayectorias que parecen cruzarse aproximadamente en el punto x = ( 1, 3/2 ). En realidad, este punto es la solucion óptima.

FIGURA 12.17

x_2 X_LP^((1))

3

24= 5 x_1 + 8x_2

2

1

x_0 X_LP^((2))

0 1 2 x_1

FIGURA 12.17

x_2 X_LP^((1))

3

x^((1)) 24= 5 x_1 + 8x_2

2

1 x^((2))

x_0 X_LP^((2))

0 1 2 x_1

TABLA 12.6 aplicación del algoritmo de frank-wolfe

k x^((k-1)) C1 C2 x□(b/p) X para h(t) h(t) t^k x^((b))

1 (0,0) 5 8 (0,3) (0,3t) 24t-18

t^2 2/3 (0,2)

2 (0,2) 5 0 (2,0) (2t, 2-2t) 8+10t-12t^2 5/12 5/(7 ),7/6

FIGURA 12.17

x_2 X_LP^((1))

3

X^((1))

2 N^5 Solución óptima

X^((5))

X^((2)) X^((4))

1

x_0 X_LP^((2))

0 1 2 x_1

x_2 X_LP^((1))

3

X^((1))

2 N^5 Solución óptima

X^((5))

X^((2)) X^((4))

1

x_0 X_LP^((2))

0 1 2 x_1

...