2
$\begingroup$

I am solving an unconstrained convex optimization problem, which can easily have a million variables. I am trying to get a working system with a toy problem of around 200 variables. I am noticing that the Newton steps are becoming of very small magnitude, even though the gradient is still not as close to zero as desired. I then tried simple gradient descent with line search and I am getting extremely small step sizes after a few iterations, even though the gradient is not that small. What could be happening?

Update 1: Thanks to Prof. Borchers and Prof. Bangerth for sharing your knowledge. I need to investigate further along these lines, to reach a conclusion.

Update 2: Indeed there was a bug in the implementation of the gradient. Thanks for your inputs for verifying the gradient and for a good rule of thumb to terminate optimization problems.

Improve this question
$\endgroup$
5
  • $\begingroup$ Are you using a line search with Newton's method? Is the line search limiting the step length, or is the step that you get from solving the linear system small before you start the line search? $\endgroup$
    – Brian Borchers
    Feb 28, 2015 at 17:34
  • $\begingroup$ Yes, I am using a line search with Newton's method. For some strange reason, line search results in an extremely small step. $\endgroup$
    – Hari
    Feb 28, 2015 at 21:21
  • $\begingroup$ It's quite possible that your implementation of the gradient isn't returning correct values, or that you've made poor choices in the criteria for stopping the line search. Have you tested your gradient vs. a finite difference approximation? $\endgroup$
    – Brian Borchers
    Feb 28, 2015 at 21:38
  • $\begingroup$ And also double check your Hessian. $\endgroup$
    – Brian Borchers
    Feb 28, 2015 at 22:29
  • $\begingroup$ The fact that you get very short step lengths from the line search even with gradient descent points to either a problem with your line search or a problem with your implementation of the gradient. You should start by checking your gradient function against a finite difference approximate gradient- incorrect gradients are very often the cause of slow (or no) convergence in optimization. $\endgroup$
    – Brian Borchers
    Mar 1, 2015 at 4:26

1 Answer 1

Reset to default
4
$\begingroup$

If you converge, you would expect the steps to get small. Ideally, a step $\delta x_k$ in an optimization algorithm would go from the current iterate $x_k$ to the exact solution $x^\ast$, so $\|\delta x_k\| \approx \|x_k-x^\ast\|$ which is, as you approach the solution, going to be small.

Now you say that $\delta x_k$ is getting small even though the gradient is still large. That, of course, depends on how you define "large". Is $10^3$ small or large? By itself, there is no way to say this. It depends on the units of the thing, as well as on what you compare with. Compared with the typical size of objects we have around us, $10^3$ light years is clearly large. $10^3$ nanometers is pretty small, however. But if you're a cosmologist, then $10^3$ light years is small. And if you're looking at atomic distances, then $10^3$ nanometers is large. In other words, you need to investigate what exactly it means for the gradient to be large in your case, and whether a number that is, for example, not on the order of $10^{-7}$ but rather $10^7$ really means that you're still far from the solution.

In the context of optimization problems, you need to ask "what is small?" when you look at the gradient. One way to approach this is to ask "what is a typical size for the gradient?". To give an example, let us say that you have a spring-mass system for which you'd like to find the minimum energy position. Let's assume that the springs are all around 10cm long, then a typical displacement of springs might be $\Delta x=1cm$. Choose two positions for the bodies and connecting springs that are approximately $\Delta x$ apart and evaluate the energies for these two positions to get a corresponding "typical energy difference" $\Delta E$. Then a "typical size of the gradient" would be $\Delta E/\Delta x$. If your optimization algorithm has produced a position for which the gradient is $\|g_k\| \le 10^{-3} \left|\Delta E/\Delta x \right|$, then you can say that you're converged.

Improve this answer
$\endgroup$
4
  • $\begingroup$ In your opinion, is the relative residual a reliable way to monitor convergence, or is there a more generally robust method? It has worked for me in the past, but I can imagine that it may fail in some places. $\endgroup$
    – Tyler Olsen
    Mar 1, 2015 at 8:53
  • $\begingroup$ I've updated my answer to give an idea of what works in optimization methods. $\endgroup$
    – Wolfgang Bangerth
    Mar 1, 2015 at 15:29
  • $\begingroup$ Is there a rule of thumb for stopping size of the gradient, which will be a function of the number of optimization variables? Say, $∥gk∥≤10^{−3}f(n)$. What is a good choice for $f(n)$? $\endgroup$
    – Hari
    Mar 2, 2015 at 5:50
  • $\begingroup$ Like I say in my answer, there can be no absolute $f(n)$. It needs to depend on the typical size of a gradient, not on the number of unknowns. Beyond that, it depends on the accuracy with which you want to compute the solution. I would think that if $f$ is well chosen as the typical size of a gradient, then $10^{-3}f$ is probably good enough for most engineering problems. If you use a Newton method, then quadratic convergence implies that if you chose it to be $10^{-6}f$, it would only take a few additional iterations. $\endgroup$
    – Wolfgang Bangerth
    Mar 2, 2015 at 14:32

Your Answer

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

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