Ejemplo del Método de Frank Wolfe en Programación No Lineal

El método o algoritmo de Frank Wolfe fue propuesto en 1956 por Marguerite Frank y Philip Wolfe y se aplica a problemas de optimización matemática con una función objetivo no lineal convexa y cuyo dominio de soluciones factibles esta compuesto exclusivamente por restricciones lineales, es decir, es un conjunto convexo (en consecuencia el problema es convexo).

Consideremos el siguiente problema que asumiremos cumple con el formato anteriormente descrito:

formato-estandar-frank-wolf

Dada una aproximación x^{k} a la solución óptima del problema, podemos resolver un problema más sencillo que aproxime al problema P), suponiendo x^{k} factible.

formato-frank-wolfe-2

O equivalentemente resolviendo el siguiente problema:

formato-frank-wolfe-3

Que puede ser resuelto mediante el Método Simplex. Denotamos por x_{PL}^{k} la solución óptima de PL_{k}. El método contempla en seguida una minimización de un problema unidimensional que equivale a escoger un escalar \alpha _{k} de modo que:

funcion-unidimensional-fran

En seguida se define la siguiente aproximación al óptimo como:

xk-frank-wolfe

Que equivale a definir x^{k+1} como la solución óptima de f restringida al conjunto de puntos que determina al segmento que une x^{k} con x_{PL}^{k}.

Ejemplo: Aplicar el método de Frank Wolfe al siguiente problema no lineal restringido (convexo). Notar que la matriz hessiana o de segundas derivadas de la función objetivo es positiva definida.

ejemplo-frank-wolfe

Realizamos la primera iteración del método que da origen al siguiente problema de Programación Lineal:

pl-frank-wolfe

La resolución es trivial y puede ser alcanzada de forma gráfica con Geogebra. La solución óptima es x_{PL}^{0}=(0,3) según se aprecia a continuación:

solucion-pl-frank-wolfe

Luego buscamos la solución para el problema unidimensional en términos del parámetro \alpha :

g-alfa-frank-wolfe

Finalmente se obtiene x^{1}=x^{0}+\frac{2}{3}(x_{PL}^{0}-x^{0})=(0,2) concluyendo una iteración del método de Frank Wolfe. Se propone al lector seguir las iteraciones a contar de este punto. Por ejemplo se puede verificar que x_{PL}^{1}=(2,0). (Hint: La solución óptima se alcanza en (x_{1},x_{2})=(1,\frac{3}{2}).

solucion-optima-frank-wolfe

Rating: 5.0. From 2 votes.
Please wait...

, , , , , , ,

Sin Comentarios aun. Se el primero en comentar!

Deja un comentario