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?

  • $\begingroup$ this seems more like a question for the or-exchange. $\endgroup$
    – shabbychef
    Commented Feb 2, 2011 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
    Commented Feb 2, 2011 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
    Commented Feb 2, 2011 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
    Commented Feb 2, 2011 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
    Commented Feb 2, 2011 at 23:21

2 Answers 2


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.

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

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


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.