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.

No hay comentarios.:

Publicar un comentario