2
$\begingroup$

My intuition says that the third equation must be "the length of the gradient squared less than epsilon".

$x_{k+1} = x_k - f(x_k)$
$x_{k+1} = x_k + 1$
$|f(x_k)|^2 < \epsilon$

However, I am not sure whether it is the standard form.

How would you write the standard form of the gradient method, and particularly its ending rule?

$\endgroup$
  • $\begingroup$ this seems more like a question for the or-exchange. $\endgroup$ – shabbychef Feb 2 '11 at 16:29
  • 1
    $\begingroup$ Yes. It's also vague: whose "standard method" are we talking about? Whose "third equation"? Moreover, these issues are discussed extremely well in Numerical Recipes, www.nr.com , chapter 10. $\endgroup$ – whuber Feb 2 '11 at 18:29
  • 1
    $\begingroup$ The second equation makes no sense and appears to contradict the first. What are these equations supposed to be doing? If we take $x_k$ to be a vector then the first equation looks like an update step. The second and third equations are not. The third equation is part of the usual termination criteria. Another part of those criteria is that $|F(x_{k+1})-F(x_k)|$ should be small, where $F$ is the objective function (of which $f$ is its (scaled) gradient). $\endgroup$ – whuber Feb 2 '11 at 21:45
  • $\begingroup$ I think the OP meant the second equation to be $k = k+1$. We should also not take $f(x)$ to be the function to be minimized, I believe. $\endgroup$ – shabbychef Feb 2 '11 at 21:58
  • $\begingroup$ I agree that this is off-topic, but possible relevant sites are in production... It could work on SO, but I'm eager to let it stay while it was answered. $\endgroup$ – user88 Feb 2 '11 at 23:21
3
$\begingroup$

Interpreting your function $f(x)$ as a (scaled) version of the gradient, your termination rule is equivalent to $|f(x)| < \sqrt{\epsilon}$, i.e. "terminate when you've taken a step that is too small." This seems perfectly reasonable.

$\endgroup$
  • 1
    $\begingroup$ I agree, this question needs another exchange site :) $\endgroup$ – deps_stats Feb 3 '11 at 19:54
2
$\begingroup$

A simplified version of the gradient descent algorithm is as follows:

You begin with $k=0$, $x_k$, $\alpha_k$ and a backtracking parameter $c \in (0,1)$.

The descent direction is given by $p_k = - \nabla f(x_k)$.

Each iterate is computed as follows, $x_{k+1} = x_k + \alpha p_k$.

Remember that $\alpha$ is interpreted as step-length and must satisfy the sufficient descent condition, $f(x_k + p_k ) \leq f(x_k) + c \alpha_k \nabla f(x_k)^T p_k$. The value of $\alpha$ must be calculated using the backtracking procedure.

The algorithm is as follows:

data: k=0; x; alpha; c; tol
begin:
compute the gradient;
while( norm(grad) > tol ){
  compute alpha using backtracking;
  p = -grad;
  x = x + alpha*p;
}

The parameter tol is the tolerance for the stopping rule, it basically ensures that your gradient is close enough to zero. If the gradient is close to zero you can proof that your current iteration is close to a local minimum.

I hope this answers your question.

For further reference you may check Numerical Optimization by Nocedal & Wright.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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