Programación convexa - Ejemplo aproximación secuencial

Como un ejemplo de algoritmo de aproximación secuencial se presentará el algoritmo de FRank-Wolfe para el caso de programación convexa linealmente restringida (de manera que las restricciones son Ax ≤ b, x ≥ 0, en forma matricial). Este procedimiento es bastante directo, combina aproximaciones lineales de la función objetivo (que permita usar el método símplex) con el procedimiento de búsqueda en una dimensión de la sección 14.4.

Programación convexa - los algorimos de aproximación secuencial

La tercera categoría, los algoritmos de aproximación secuencial, incluye métodos de aproximación lineal y aproximación cuadrática. Estos algoritmos constituyen la función objetivo no lineal por una sucesión de aproximaciones no lineales o cuadráticas. Para problemas de los algoritmos de programación lineal o cuadrática. Este trabajo se logra mediante otro análisis que conduce a una sucesión de solucioens que convergen a una solución óptima para el problema orginal. Aunque estos algoritmos son adecuados en especial para problemas de optimización linealmente restringida, algunos se pueden extender a problemas con funciones de restricción no lineales, si se usan las aproximaciones lineales adecuadas.

Programación convexa - Algoritmos secuenciales no restringidos

La segunda categoría, los algoritmos secuenciales no restringidos, incluye los métodos de función de penalización y de función barrera. 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. Cada uno de estos problemas de optimización no restringida se puede resolver por el procedimiento de búsqueda del gradiente de la sección 14.5. Esta conversión se logra al incorporar las restricciones a una función de penalización (o 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 aún al hecho de estar cerca de los límites). En la siguiente sección se verá un ejemplo de esta categoría de algoritmos.

Programación convexa - Algoritmos de gradientes

Una cateogoría la constituyenlos algoritmos de gradiente, en los que se modifica de alguna manrea el procedimiento de búsqueda del gradiente de la sección 14.5 para evitar que la trayectoria de búsqueda penetre la frontera de restricción. Por ejemplo, un método de gradiente popular es el método generalizado de gradiente reducido (CRG).

Programación convexa

En las secciones anteriores se presentaron algunos casos especiales de programación convexa no restringida, con función objetivo cuadrática y restricciones lineales y con funciones separables. También se vio, en la sección 14.6, una parte de la teoría para el caso general (condiciones necesarias y suficientes para la optimalidad). En esta sección se presentarán brevemente algunos tipos de enfoques usados para resolver el problema general de programación convexa (en donde la función objetivo f(x) que se va a maximizar es cóncava y las funciones de restricción gi(x) son convexas y después se presentará un ejemplo de un algoritmo para programación convexa.

No existe un algoritmo estándar único que se pueda usar siempre para resolver problemas de programación convexa. Se han construido muchos algoritmos diferentes, cada uno con ventaja y desventajas, y la investigación continúa activa en esta área. En términos generales, la mayor parte de estos algoritmos cae dentro de alguna de las tres categorias siguientes.

Formulacion Propiedad esencial de programación separable - Extensiones (II)

Una deficiencia de la aproximación de funciones por medio de funciones lineales por partes que se describió en esta sección, es que sólo se logra una buena aproximacióncon un número muy grande de segmentos de recta (variables), mientras que una malla fina de intervalos nada más se necesita en la vecindad inmediata de la solución óptima. Se han desarrollado enfoques más elaborados que usan una sucesión de funciones líneales por partes de dos segmentos, para obtener aproximaciones cada vez más cercanas dentro de esta vecindad inmediata. Este tipo de enfoques tiende a ser tanto más rápido como más exacto al aproximar una solución óptima.

Formulacion Propiedad esencial de programación separable - Extensiones (I)

Hasta ahora, la presentación se ha centrado en el caso especial de programación separable, en el que la única función no lineal es la función objetivo f(x). Ahora considérese brevementeel caso general en el que las funciones de restricción gi(x) no tienen que ser lineales, pero son convexas y separables, de manera que cada gi(x) se puede expresar como son una suma de funciones de variables individuales,