I am implementing an unconstrained optimization algorithm using gradient descent. I am evaluating a cost function at a given point, evaluating the gradient at this point, and selecting the next evaluation point along a gradient descent direction using a line search method.
I discussed this algorithm with my supervisor, a very knowledgeable person, who argued that function evaluations are not needed, and that I should be able to perform the whole optimization with only gradient evaluations.
I believe that this is not possible. It is true that we can check necessary conditions for optimality by only evaluating gradients, and we can check sufficient conditions by only evaluating hessians. However, in order to efficiently search for a local minimum we need to use line search methods to choose the optimal step size along a descent direction, and these methods require many function evaluations.
Is the above argument correct?
Should I be able to perform optimization without gradient evaluations? If so, I would appreciate references to algorithms doing so.