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.
No hay comentarios.:
Publicar un comentario