miércoles, 29 de junio de 2016

Programación no convexa - Técnica secuencial de miniización no restringida (IV)

Cuántos problemas son suficientes para permitir la extrapolación? Cuando el problema original satisface las suposiciones de programación convexa, se cuenta con información útil como guía en esta decisión. En particular, si x es un máximo global de P(x;r), entonces

martes, 28 de junio de 2016

Programación no convexa - Técnica secuencial de miniización no restringida (III)

Obsérvese que para valores factibles de x, el denominador de cada término es proporcional a la distancia de x  a la frontera de restricciones para la restricción funcional o de no negatividad correspondiente. En consecuencia, cada término es un término de rechazo de frontera que tiene las tres propiedades anteriores, con respecto a esta frontera de restricción específica. Otra caracteristica atractiva de esta B (x) es que cuando se satisfacen todas las suposiciones de programación convexa, P(x; r) es una función cóncava.

Como B(x) mantiene la búsqueda lejos de la frontera de la región factible, una pregunta natural es: qué pasa si la solución que se quiere está ahí? Esta preocupación es la razón por la cual esta técnica incluye la solución de una sucesión de estos problemas de optimización no restringida para valores cada vez más pequeños de r que se acercan a cero (cuando la solución prueba final de cada uno se convierte en la solución prueba inicial del siguiente). Por ejemplo, cada nueva r se puede obtener a partir de la anterior al multiplicar por una constante θ (0 < θ < 1), en donde un valor usual es θ = 0.01. Acercarse r a cero, P(x,r) se acerca a f(x) de manera que el máximo local correspondiente de P(x;r) converge a un máximo local del problema original. Por ello, sólo es necesario resolver problemas de optimización no restringida, hasta que se puedan extrapolar sus soluciones a eta solución límite.

lunes, 20 de junio de 2016

Programación no convexa - Técnica secuencial de miniización no restringida (II)

Así, si se inicia el procedimiento de búsqueda con una solución prueba inicial factible y después se intenta incrementar P(x; r), entonces B(x) proporciona una barrera que evita que la búsqueda curce (o llegue a) la frontera de la región factible del problema original.

La elección más natural para B(x) es

domingo, 19 de junio de 2016

Programación no convexa - Técnica secuencial de miniización no restringida (I)

Como su nombre lo indica, esta técnica sustituye el problema original por una sucesión de problemas de optimización no restringida, cuyas soluciones convergen a una solución (máximo local) del problema original. Este enfoque es muy atractivo, que es mucho más sencillo resolver los problemas de optimización no restringida (véas el procedimiento de búsqueda del gradiente en la sección 14.5) que los que tienen restricciones. Cada uno de los problemas no restringidos de esta sucesión incluyen la sección de un valor estrictamente positivo (cada vez más pequeño) de un escalar r y después la obtención de x para

viernes, 17 de junio de 2016

Programación no convexa (II)

Un procedimiento de este tipo que se ha usado ampliamente desde su origen en la década de 1960 es la técnica de minimización no restringida secuencial. En realidad, existen dos versiones de esta técnica, una de las cuales es un algortimo de punto exterior que maneja soluciones no factibles y que al mismo tiempo utiliza una función de penalización para forzar la convergencia a la región factible. Se describirá la otra versión, que es un algoritmo de punto interior que tabaja directamente con soluciones factibles y que utiliza al mismo tiempo una función de barrera para forzarlas a mantenerse dentro de esa región factible. Aunque la técnica secuencial de minimización no restringida en un principio se presentó como una técnica de minización, se convertirá aquí en una técnica de maximización, con el fin de que sea consistente con el resto del capítulo. Se continuará suponiendo entonces, que el problema se encuentra en la forma dada al principio y que todas las funciones son diferenciables.

jueves, 16 de junio de 2016

Programación no convexa (I)

Las suposiciones de programación convexa son muy convenientes, pues aseguran que cualquier máximo local es también un máximo global. Desafortunadamente los problemas de programación no líneal en la práctica muchas veces apenas cumple estas suposiciones y de hecho tienen algunas disparidades menores. Qué tipo de enfoque conviene usar para manejar estos problemas de programación no convexa?

Una manera usual es aplicar un procedimiento de búsqueda algorítimico que se detenga cuando encuentre un máximo local y después reiniciarlo varias veces a partir de distintas soluciones pruebas iniciales, con el fin de encontrar cuantos máximos locales distintos sea posible. Se elige el mejor de estos máximos locales para llevarlo a la práctica. Por lo general, se usa un procedimiento de búsqueda planeado para encontrar un máximo global cuando se cumplen todas las suposiciones de programación convexa, pero que también puede encontrar un máximo local cuando no sea así.

miércoles, 15 de junio de 2016

Programación convexa - Resumen de algorimo de Frank-Wolfe - Ejemplo (IV)

En conclusión, se debe hacer notar que el algoritmo Frank-Wolfe es sólo un ejemplo de los algortimos de aproximación secuencial. Muchos de ellos utilizan aproximaciones cuadráticas en lugar de lineales en cada iteración, porque la aproximación cuadrática proporciona un ajuste mucho mejor al problema original y permite que la sucesión de soluciones converja mucho más rápidamente hacia la solución óptima que en caso de la figura 14.4b. Por esta razón, aun cuando el uso de los métodos de aproximación lineal secuencial, como el algoritmo de Frank-Wolfe, sea bastante sencillo, en general se prefieren los métodos de aproximación cuadrática Entre estos, los que más se usan son los métodos cuasi-Newton (o de variables métricas), que calculan una aproximación cuadrática a la curvatura de una función no lineal sin calcular explícitamente las segundas derivadas (parciales). (En los problemas de optimización linealmente restringida, esta función no lineal es la función objetivo, mientras que si se tienen restricciones no lineales, se trata de la función de Lagrange descrita en el apéndice 2.) Algunos algortimos cuasi-Newton no formularan  ni resuelven siquiera, de manera explícita, una aproximación al problema de programación cuadrática en cada iteración; más bien incorporan algunos de los ingredientes básicos de los algoritmos de gradiente.

Para mayor información sobre la situación actual de los algoritmos de programación convexa.

martes, 14 de junio de 2016

Programación convexa - Resumen de algorimo de Frank-Wolfe - Ejemplo (III)


En la figura 14.14b se puede observar cómo las soluciones prueba adquieren valores de puntos alternados entre dos trayectorias que parecen intersecarse aproximadamente en el punto x = (1, 3/2). De hecho, este punto es la solución óptima, como se puede verificar si se aplican las condiciones KKT de la sección 14.6.

Este ejemplo ilustra una característica común del algoritmo de Frank-Wolfe: que las soluciones prueba alternan entre dos (o más) trayectorias. Cuando esto ocurre, se pueden extrapolar las trayectorias al punto aproximado en que se cruzan para estimar una solución óptima. Esta estimación tiende a ser mejor que usar la última solución prueba generada. Esto se debe a que la convergencia de las soluciones prueba hacia la solución óptima tiende a ser lenta y por ello es posible que la última solución esté todavía alejada del óptimo.

viernes, 10 de junio de 2016

Programación convexa - Resumen de algorimo de Frank-Wolfe - Ejemplo (I)

Considérese el siguiente problema de programación convexa linealmente restringido

martes, 7 de junio de 2016

domingo, 5 de junio de 2016

Programación convexa - Resumen de algorimo de Frank-Wolfe (I)

Paso inicial

Se encuentra una solución prueba factible inicial x^(0), por ejemplo, aplicando los procedimientos de programación líneal para encontrar una solución básica factible. Se hace k = 1

sábado, 4 de junio de 2016

Programación convexa - Un algoritmo (Frank-Wolfe) de aproximación lineal secuencial (II)

Después se aplica el método símplex (o el procedimiento gráfico, si n = 2) al problema de programación lineal que resulta a un de obtener su solución óptima xLP Nótese que la función objetivo lineal necesariamente se incrementa cuando se hace un recorrido sobre el segmento de la recta desde x' hasta xLP (que se encuentra en la frontera de la región factible); pero la aproximación lineal puede no ser buena para una x lejana a x', por lo que quizá la función objetivo no continuará creciendo durante toda la trayectoria desde x' hasta xLP. Así, en lugar de aceptar xLP como la siguiente solución prueba, se elige el punto sobre este segmento de recta que maximiza la función objetivo no lineal. Este punto se puede encontrar realizando una búsqueda en una dimensión con el procedimiento de la sección 14.4, en donde la única variable para los propósitos de sta búsqueda es la fracción t de la distancia total de x'a xLP. Este punto se convierte entonces en una nueva solución prueba para iniciar la siguiente iteraccióndel algoritmo, como se acaba de describir. La sucesión de soluciones prueba generados por las iteraciones converge a una solución óptima para problema original, de manera que el algoritmo se detiene en cuanto las soluciones prueba están los suficientemente cerca entre si como para poder concluir que se llegó a esta solución óptima.

viernes, 3 de junio de 2016

Programación convexa - Un algoritmo (Frank-Wolfe) de aproximación lineal secuencial

DAda una solución prueba factible x', la aproximación lineal que se usa para la función objetivo f(x) es la expansión de primer orden por series de Taylor, de f(x) alrededor de x = x', a saber:


jueves, 2 de junio de 2016

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.

miércoles, 1 de junio de 2016

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.