2
$\begingroup$

The gradient descent I learnt uses $x^{k+1} = x^k + t\triangledown f(x)$ and we learnt to set $t$ heuristically. Am I right to say that exact line search simply computes the optimal value of $t$ that minimizes the $f(x) ?$

Wouldn't I be able to look for the global minima in 1 iteration in that case ? I can't see the negatives of this algorithm eg being stuck in a local minima. Can someone give an example ?

$\endgroup$
4
  • $\begingroup$ What if the global minimum isn't on the line you're searching along? $\endgroup$
    – user856
    Mar 9, 2018 at 12:27
  • $\begingroup$ I am finding it extremely hard to vizualize an example in 3D. All I can do is vizualize one in 2D $\endgroup$
    – Kong
    Mar 9, 2018 at 12:48
  • $\begingroup$ do you have a link to a webpage with a 3d example $\endgroup$
    – Kong
    Mar 9, 2018 at 12:49
  • $\begingroup$ please tell me what is the heuristic method of setting $t$, I'm not sure how to get the $t = argmin_{s\ge0} f(x+s\Delta x)$ while implementing the descent $\endgroup$
    – ALEX
    Jul 16, 2019 at 16:20

1 Answer 1

Reset to default
6
$\begingroup$

Exact line search computes the global solution of the one-dimensional problem $$ \min_{t\in \mathbb R} f(x_k - t\nabla f(x_k)). $$ This might be easy if $f$ has nice structure (quadratic).

If the global minima of $f$ are not on the line $x_k - t\nabla f(x_k)$, then you will not find the global minimum in the current step.

$\endgroup$
2
  • $\begingroup$ Hi thanks. My question was why the global solution of the one-dimensional problem may not be the global solution of the original n-dimensional problem ? $\endgroup$
    – Kong
    Mar 9, 2018 at 13:58
  • 2
    $\begingroup$ Because the gradient at a given point does not necessarily point towards the exact solution. $\endgroup$
    – Michael Grant
    Mar 9, 2018 at 18:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .