2

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 ?

Kong
  • 884
  • What if the global minimum isn't on the line you're searching along? –  Mar 09 '18 at 12:27
  • I am finding it extremely hard to vizualize an example in 3D. All I can do is vizualize one in 2D – Kong Mar 09 '18 at 12:48
  • do you have a link to a webpage with a 3d example – Kong Mar 09 '18 at 12:49
  • 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 – ALEX Jul 16 '19 at 16:20

1 Answers1

6

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.

daw
  • 49,113
  • 2
  • 38
  • 76
  • 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 ? – Kong Mar 09 '18 at 13:58
  • 2
    Because the gradient at a given point does not necessarily point towards the exact solution. – Michael Grant Mar 09 '18 at 18:53