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

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

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

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

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

Parte 2: se encuentra una solución óptimo

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

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.

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: