Line Search vs Limited Line Search

Line Search vs Limited Line Search

de Alvaro Valdes -
Número de respuestas: 1

Ignacio, Matías,

Me quedan un par de dudas del obligatorio.

1) Tanto para el ejercicio 4 como para el 5 hablan de Line Search y no de Limited Line Search.

Lo había implementado por Limited Line Search, pero veo que es posible hallar el paso óptimo de forma analítica.

¿Qué es lo que esperan?

2) En el ejercicio 5 me queda una duda sobre la búsqueda del paso óptimo.

a) hallar el s / argmin de f(xk - sk*grad(f)(xk))

b) hallar el s / argmin de f(PX[xk - sk*grad(f)(xk)])  

La diferencia es que en b) tomo la proyección de xk+1, y recién luego el valor funcional y me quedo con sk que me minimiza los valores funcionales de los puntos proyectados. En a) solamente busco el mínimo de la función del xk+1.   

La letra apunta mas a la opción a). Entre a) y b) me cambian la cantidad de iteraciones (b) tiene menos), y si elijo hacer el paso de forma analítica (solo puedo resolverlo en a), si es b) la Proyección le agrega complejidad) son mas iteraciones lo cual me suena algo contradictorio.

Desde ya agradezco el tiempo invertido en la respuesta.

Saludos,

Alvaro

En respuesta a Alvaro Valdes

Re: Line Search vs Limited Line Search

de Matías Valdés -

Buenas.

Para los ejercicios 4 y 5 lo que pide la letra es resolver cada problema de line search de forma exacta. En ambos casos es posible porque la función  f es cuadrática.

En particular en el Ejercicio 5, parte c, lo que pide la letra es hacer el line search de  s_k antes de proyectar. La otra opción que mencionás, que resuelve line search después de proyectar, también tiene sentido. Pero la desventaja es que queda difícil resolver el problema de line search de forma exacta.

Con respecto a la comparación de cantidad de iteraciones que comentás al final: no sería raro que hallar el paso de forma exacta resulte en más iteraciones que hallarlo de forma aproximada. Acordate que estos métodos son locales. Es decir, no ven la función de forma global. Por lo tanto, lograr el mayor descenso local en cada iteración (paso exacto en la dirección de máximo descenso local), no necesariamente es la mejor estrategia. Mas en este caso en que después vas a proyectar.

Espero haberte aportado algo. Cualquier cosa preguntá de nuevo y seguimos.

Saludos.

Matías V.