programacion convexa

Universidad de OrienteNúcleo de Monagas

Ingeniería de SistemasModelo de Operaciones I

Profesora: Ing. Francy Tononi

Elaborado por: Ortiz, Mary

Rama de la programación MatemáticaQue 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.

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

Sea f : Rn → R.

Nota: Una función f es cóncava si – f es convexa.

Decimos que f es convexa:

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

Se dice que C es un conjunto convexo si para cualesquiera dos elementos que pertenezcan a C, la línea que los une es también un subconjunto de C. O sea, C es convexo si para todo x1, x2 en C y para cualquier número real t, 0 ≤ t ≤ 1, se satisface que:

Una region es convexa si todos los puntos de una línea que conecta dos puntos de la región están en dicho conjunto

Convexo No- Convexo

• Esto significa que el segmento que une (x1, f (x1)) y (x2, f (x2)), o sea, la cuerda que va de x1 a x2, se encuentra sobre la gráfica de f.

Geométricamente una función es convexa si:

(x1, f (x1))(x2, f (x2))

La minimización de una función convexa sobre una región convexa tiene la siguiente propiedad:

¡Un mínimo local es también un mínimo global!

Según Hillier-Lieberman 8va. edición

Se han estudiado algunos casos especiales de programación convexa en distintas secciones a mencionar:

Según Hillier-Lieberman 8va. edición

La función objetivo: f(x) que se debe

maximizar es cóncava y las funciones derestricción gi(x) son

convexas.

En este caso se presentará brevemente algunos tipos deenfoques usados para resolver el problema general de programación convexa donde:

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.

Categorias

La mayor parte de estos algoritmos cae dentro de las categorías

1-Algoritmos de gradiente

2-Algoritmos secuenciales

no restringidos

3- Algoritmos de aproximación

secuencial

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.

Un método de gradiente popular es el método gradiente reducido generalizado (GRG). El Excel Solver emplea el método GRG para resolver problemas de programación convexa.

Por ejemplo:

Estos algoritmos convierten el problema de optimización restringida original en una sucesión de problemas de optimización no restringida cuyas soluciones óptimas convergen a la solución óptima del problema original.

Estos Algoritmos incluyen:

1.Método de Finalización

2.Método de Barrera

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 violación de cualquier restricción o aun al hecho de estar cerca de los límites.

Estos Algoritmos incluyen:

1.Método de Finalización

2.Método de Barrera

Los problemas de optimización no restringida se puede resolver por medio del procedimiento de búsqueda del gradiente.

Para problemas de optimización linealmente restringidos, estas aproximaciones permiten la aplicación repetida de los algoritmos de programación lineal o cuadrática.

Estos Algoritmos incluyen:

1.Método de Aproximación Lineal

2.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

Algoritmo de Frank-Wolfe

para el caso de programación convexa linealmente restringida. Este procedimiento es bastante directo; combina aproximaciones lineales de la función objetivo (que permiten usar el método símplex) con el procedimiento para la optimización no restringida de una variable

Algoritmo de Frank-Wolfe

Se encuentra una solución de prueba factible inicial x(0), por ejemplo, al aplicar los procedimientos de programación lineal para encontrar una solución BF.

Se hace k = 1.

Paso inicial

Algoritmo de Frank-Wolfe

Iteración k:

Algoritmo de Frank-Wolfe

Iteración k:

Algoritmo de Frank-Wolfe

Iteración k:

Algoritmo de Frank-Wolfe

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.

Algoritmo de Frank-Wolfe

Generalmente donde los supuestos asociados a la proporcionalidad no se cumplen como en las economías o economías de escala, en. Telecomunicaciones, toma de decisiones empresariales, automatización de procesos, diseños electrónicos, simulaciones , modelados, entre otros

Considere el siguiente problema de programación convexa linealmente restringido:

Sujeta a :