Is optimization without function evaluations (and with only gradient evaluations) possible?

Question

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.

Many thanks

Answer 1

If $f'(x)=0$ and $f′′(x)>0$ then $f$ has a local minimum at $x$. So keep going with your gradient evaluations/updates. When reaching a $f′(x)$ of almost $0$ (or $0$), check the Hessian. In that regard, if we know that the function $f$ is convex we do not even have to evaluate the Hessian as by definition $f$'s second derivative is non-negative on its entire domain.

Answer 2

You can find stationary points with only gradient evaluations, but not the global max.

If $f'(x_1) = f'(x_2) = 0$, assuming these are local maxima, and at least one is the global max, there are three possible scenarios

1. $f(x_1) = f(x_2)$ - no single global maxima
2. $f(x_1) > f(x_2)$ - $x_1$ is the maximiser
3. $f(x_1) < f(x_2)$ - $x_2$ is the maximiser

Without knowing what $f(x_1)$ and $f(x_2)$ are, we cannot find the solution to $x^{*} = \text{arg max}_{x \in X} f(x)$.