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

...