#1




9.7.2 Bug in Newton Method?
I am puzzled by the code at the end of page 481 beginning 482 that examines potential spurious convergence by checking for zero gradient. When gradient is not sufficiently small newt still sets check=false. This value is supposed to indicate that root was found but function value test failed convergence criteria a few lines earlier. I would expect the code to return an indication of internal error in such a case. Is it a bug or do I miss something?

#2




Here's what is happening:
1) lnsrch sets check to true if it is unable to make any further progress in finding a better value of x. 2) newt then tests convergence on function values f(x). If there is convergence, check is ignored by setting it to false. 3) Otherwise, if check was true on exit from lnsrch, the gradient is tested and possibly spurious convergence is reported (check = true) if it is close to zero. 4) Otherwise (check false on exit from lnsrch) convegence on x is tested. Hope this helps. Saul Teukolsky 
#3




Saul, Thanks for your reply.
I'll try to clarify by describing the behavior that I observed while debugging my example: 1. lnsrch is not able to make progress and sets check to true. 2. newt tests and discovers lack of convergence w.r.t. function values. 3. Since the check was set to true gradient is tested and discovered that it is NOT sufficiently close to zero. 3.1 When gradient test fails newt sets check to false (as if a root was found) and then immediately returns leaving a caller with a false impression that everything was fine. Hope that now you have a better sense of the situation. I also run into another issue related to lnsrch implementation of backtracking. A check for sufficient function decrease is done by a line: } else if ( f <= fold + ALF * alam * slope) return; In my example ALF * alam * slope is non zero. However its value is sufficiently small that adding it to fold looses all significant digits. Right hand side become equal to fold while fold is equal to f; lnsrch does not detect that it is not making progress and that leads to extra iterations by newt. I could imagine that in some cases such premature returns from lnsrch may even lead to insufficient backtracking and harmful consequences in newt. I wonder if it would make sense to use 'less' instead of 'less or equal' comparison on the line in question? Last edited by LRaiz; 04062012 at 01:03 PM. Reason: corrected typos 
#4




It sounds like newt is doing as well as can be expected on your problem. lnsrch can't backtrack, so you have essentially converged on x and you are not at a minimum. This is the best newt can do for your given inputs.
In the text after newt, there is a warning about scaling of x and f. If these quantities are not of order unity, you can have the problems you report. The fix is to define new f's and x's by scaling your old ones with constants before you invoke newt. Also, if your inputs are not smooth in the mathematical sense and you ask for too much precision, newt may fail. Saul Teukolsky 
#5




1. You are correct Saul that newt is doing as well as can be expected on my problem. I appreciate your responses and value the suggestion of scaling both unknowns and function values. The only thing I am suggesting is that since newt has validated that neither function values nor gradient are zero then may be it should pass alone some sort of an indication about loss of precision/roundoff problem to the caller. By the way  my equations are C2 w.r.t. to unknowns.
2. I also would appreciate very much if you express your expert opinion if a replacement of '<=' with '< in lnsrch might have some undesired consequences. 
#6




1) It is very difficult to put in a "warning" of the kind you suggest. Testing for convergence on f (function values) is errorprone, unless you force the user to specify ahead of time what "sufficiently small" f means. This comes back to scaling f to be of order unity. So most root finding routines focus on convergence on x, on the assumption that scaling x isn't as difficult or as crucial. Bottom line: you are supposed to inspect f on exit from newt.
2) I haven't looked into what might happen if you change <= to <. The theorem on which this algorithm is based uses <= (see the reference to the book by Dennis and Schnabel). Saul Teukolsky 
Thread Tools  
Display Modes  Rate This Thread 

