search

SciML / NonlinearSolve.jl

High-performance and differentiation-enabled nonlinear solvers (Newton methods), bracketed rootfinding (bisection, Falsi), with sparsity and Newton-Krylov support.
https://docs.sciml.ai/NonlinearSolve/stable/
MIT License
228 stars 41 forks source link

Fix bug in Levenberg #226

Closed avik-pal closed 11 months ago

avik-pal commented 11 months ago

Updated Version

nr  Problem                                            n     NewtonRaphson       TrustRegion         LevenbergMarquardt  LevenberdMarquardt (LSOptim)
1   Generalized Rosenbrock function                    10    NaN                 0.0                 1.0214e-14          5.8944e-11          
2   Powell singular function                           4     7.0435e-16          6.8342e-16          1.0538e-15          2.3573e-7           
3   Powell badly scaled function                       2     0.0                 0.0                 8.7431e-5           2.5957e-11          
4   Wood function                                      4     1.8586e-14          1.0663e-14          1.2104e-14          3.8075e-12          
5   Helical valley function                            3     6.2775e-30          9.4526e-23          5.2326e-19          6.8803e-13          
6   Watson function                                    2     NaN                 NaN                 NaN                 NaN                 
7   Chebyquad function                                 2     5.5511e-17          1.6653e-16          2.0053e-15          4.4854e-12          
8   Brown almost linear function                       10    0.0                 6.6613e-16          4.2061e-14          2.1603e-11          
9   Discrete boundary value function                   10    5.4548e-16          6.9388e-17          3.1544e-15          3.7241e-11          
10  Discrete integral equation function                10    2.7807e-15          3.4694e-17          3.1457e-15          1.2691e-11          
11  Trigonometric function                             10    1.8884e-15          0.0052868           0.0052874           0.0052868           
12  Variably dimensioned function                      10    0.0                 0.0                 5.124e-12           1.345e-13           
13  Broyden tridiagonal function                       10    1.2803e-15          1.3414e-15          6.4287e-15          1.5726e-12          
14  Broyden banded function                            10    1.4002e-15          1.4002e-15          6.37e-15            1.4637e-13          
15  Hammarling 2 by 2 matrix square root problem       4     1.1102e-16          2.4973e-6           7.3386e-6           2.9137e-6           
16  Hammarling 3 by 3 matrix square root problem       9     1.1102e-16          2.1418e-6           7.3386e-6           2.9119e-6           
17  Dennis and Schnabel 2 by 2 example                 2     0.0                 0.0                 13.143              3.7942e-15          
18  Sample problem 18                                  2     0.0                 5.2861e-18          2.8025e-10          7.6511e-11          
19  Sample problem 19                                  2     9.5092e-16          9.5092e-16          7.0792e-6           1.058e-6            
20  Scalar problem f(x) = x(x - 5)^2                   1     0.0                 1.9689e-24          5.1828e-18          6.4853e-11          
21  Freudenstein-Roth function                         2     0.0                 6.9988              6.9988              6.9988              
22  Boggs function                                     2     0.0                 7.3505e-17          4.9882e-16          5.6927e-12          
23  Chandrasekhar function                             10    5.4389e-16          5.4389e-16          1.5933e-14          1.7902e-13

Previous Version

nr  Problem                                            n     NewtonRaphson       TrustRegion         LevenbergMarquardt  LevenberdMarquardt (LSOptim)
1   Generalized Rosenbrock function                    10    NaN                 0.0                 4.9193              5.8944e-11          
2   Powell singular function                           4     7.0435e-16          6.8342e-16          0.021633            2.3573e-7           
3   Powell badly scaled function                       2     0.0                 0.0                 1.0031e-14          2.5957e-11          
4   Wood function                                      4     1.8586e-14          1.0663e-14          8550.5              3.8075e-12          
5   Helical valley function                            3     6.2775e-30          9.4526e-23          50.0                6.8803e-13          
6   Watson function                                    2     NaN                 NaN                 NaN                 NaN                 
7   Chebyquad function                                 2     5.5511e-17          1.6653e-16          0.34127             4.4854e-12          
8   Brown almost linear function                       10    0.0                 6.6613e-16          16.53               2.1603e-11          
9   Discrete boundary value function                   10    5.4548e-16          6.9388e-17          5.9887e-15          3.7241e-11          
10  Discrete integral equation function                10    2.7807e-15          3.4694e-17          9.0812e-15          1.2691e-11          
11  Trigonometric function                             10    1.8884e-15          0.0052868           0.084117            0.0052868           
12  Variably dimensioned function                      10    0.0                 0.0                 1.5725e-12          1.345e-13           
13  Broyden tridiagonal function                       10    1.2803e-15          1.3414e-15          1.373e-13           1.5726e-12          
14  Broyden banded function                            10    1.4002e-15          1.4002e-15          1.165e-13           1.4637e-13          
15  Hammarling 2 by 2 matrix square root problem       4     1.1102e-16          2.4973e-6           0.91487             2.9137e-6           
16  Hammarling 3 by 3 matrix square root problem       9     1.1102e-16          2.1418e-6           1.0506              2.9119e-6           
17  Dennis and Schnabel 2 by 2 example                 2     0.0                 0.0                 17.262              3.7942e-15          
18  Sample problem 18                                  2     0.0                 5.2861e-18          2.1951              7.6511e-11          
19  Sample problem 19                                  2     9.5092e-16          9.5092e-16          76.367              1.058e-6            
20  Scalar problem f(x) = x(x - 5)^2                   1     0.0                 1.9689e-24          2.5564e-18          6.4853e-11          
21  Freudenstein-Roth function                         2     0.0                 6.9988              20.012              6.9988              
22  Boggs function                                     2     0.0                 7.3505e-17          2.0                 5.6927e-12          
23  Chandrasekhar function                             10    5.4389e-16          5.4389e-16          8.8121e-14          1.7902e-13
avik-pal commented 11 months ago

Setting $\alpha = 0.5$

nr  Problem                                            n     NewtonRaphson       TrustRegion         LevenbergMarquardt  LevenberdMarquardt (LSOptim)
1   Generalized Rosenbrock function                    10    NaN                 0.0                 5.561e-15           5.8944e-11          
2   Powell singular function                           4     7.0435e-16          6.8342e-16          1.2732e-15          2.3573e-7           
3   Powell badly scaled function                       2     0.0                 0.0                 0.00014565          2.5957e-11          
4   Wood function                                      4     1.8586e-14          1.0663e-14          4.7746e-13          3.8075e-12          
5   Helical valley function                            3     6.2775e-30          9.4526e-23          5.2326e-19          6.8803e-13          
6   Watson function                                    2     NaN                 NaN                 NaN                 NaN                 
7   Chebyquad function                                 2     5.5511e-17          1.6653e-16          2.0053e-15          4.4854e-12          
8   Brown almost linear function                       10    0.0                 6.6613e-16          2.2701e-13          2.1603e-11          
9   Discrete boundary value function                   10    5.4548e-16          6.9388e-17          3.1558e-15          3.7241e-11          
10  Discrete integral equation function                10    2.7807e-15          3.4694e-17          3.1571e-15          1.2691e-11          
11  Trigonometric function                             10    1.8884e-15          0.0052868           0.0052872           0.0052868           
12  Variably dimensioned function                      10    0.0                 0.0                 5.2571e-12          1.345e-13           
13  Broyden tridiagonal function                       10    1.2803e-15          1.3414e-15          8.9626e-15          1.5726e-12          
14  Broyden banded function                            10    1.4002e-15          1.4002e-15          8.9667e-15          1.4637e-13          
15  Hammarling 2 by 2 matrix square root problem       4     1.1102e-16          2.4973e-6           8.8246e-6           2.9137e-6           
16  Hammarling 3 by 3 matrix square root problem       9     1.1102e-16          2.1418e-6           7.0345e-6           2.9119e-6           
17  Dennis and Schnabel 2 by 2 example                 2     0.0                 0.0                 1.0667e-14          3.7942e-15          
18  Sample problem 18                                  2     0.0                 5.2861e-18          1.8389e-9           7.6511e-11          
19  Sample problem 19                                  2     9.5092e-16          9.5092e-16          8.5271e-6           1.058e-6            
20  Scalar problem f(x) = x(x - 5)^2                   1     0.0                 1.9689e-24          5.1828e-18          6.4853e-11          
21  Freudenstein-Roth function                         2     0.0                 6.9988              6.9988              6.9988              
22  Boggs function                                     2     0.0                 7.3505e-17          2.5885e-15          5.6927e-12          
23  Chandrasekhar function                             10    5.4389e-16          5.4389e-16          5.545e-14           1.7902e-13

But that can be done by the user if needed. The paper also suggests 0.75

codecov[bot] commented 11 months ago

Codecov Report

Merging #226 (68d303d) into master (fd4ae4b) will increase coverage by 1.69%. The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master     #226      +/-   ##
==========================================
+ Coverage   93.64%   95.33%   +1.69%     
==========================================
  Files           8        8              
  Lines         771      772       +1     
==========================================
+ Hits          722      736      +14     
+ Misses         49       36      -13
Files Coverage Δ
src/levenberg.jl 98.48% <100.00%> (+0.77%) :arrow_up:

... and 2 files with indirect coverage changes

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more

oscardssmith commented 11 months ago

This also probably needs a comment for why you are doing the computation in the log domain. It's not obvious why it would make a difference.

avik-pal commented 11 months ago

That can be reverted, actually. The values of accept condition seemed to yield values which were clearly incorrect, and my initial guess was some weird rounding off errors since the norm_v was $~10^{-300}$

avik-pal commented 11 months ago

The main fix is the A a = b A matrix which was incorrectly set to be the Jacobian