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:

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

O equivalentemente resolviendo el siguiente problema:

Que puede ser resuelto mediante el Método Simplex. Denotamos por la solución óptima de . El método contempla en seguida una minimización de un problema unidimensional que equivale a escoger un escalar de modo que:

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

Que equivale a definir  como la solución óptima de f restringida al conjunto de puntos que determina al segmento que une con .

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.

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

La resolución es trivial y puede ser alcanzada de forma gráfica con Geogebra. La solución óptima es según se aprecia a continuación:

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

Finalmente se obtiene 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 . (Hint: La solución óptima se alcanza en .