4
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Can you evaluate the gradient without the function evaluation? If yes, the supervisor is right, if not, the supervisor is wrong. $\endgroup$
    – usεr11852
    Aug 17, 2023 at 12:32
  • $\begingroup$ Yes,we can evaluate the gradient without function evaluations. We have a close-form expression for the gradient, that is different from that of the function. However, I do not know of any efficient method that will allow me to find local minima without function evaluations. If you know of any, please let me know. Thanks. $\endgroup$ Aug 17, 2023 at 13:40
  • $\begingroup$ 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. $\endgroup$
    – usεr11852
    Aug 17, 2023 at 14:34
  • 1
    $\begingroup$ Very clear. If you post your comment as an answer I will accept it. Thanks. $\endgroup$ Aug 18, 2023 at 17:15

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ Thanks for your response. I don't think you can efficiently find stationary points with only gradient evaluations. I believe that in order to to so you need to use a line search method, and these methods require multiple function evaluations. I am interested in learning if there are efficient algorithms (not brute force ones) to find local minima with only gradient evaluations. $\endgroup$ Aug 17, 2023 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.