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 
es cuadrática.
En particular en el Ejercicio 5, parte c, lo que pide la letra es hacer el line search de 
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.