I am attempting to use the conjugate gradient solver gsl_multimin_fdfminimizer_conjugate_pr, but am finding it takes far too many evaluations to converge. My problem is a rather complex graph-length minimization problem (I am doing a sort of autocorrelation I guess), and I haven't yet managed to reduce it down to a small test program that demonstrates the issue. However I have turned on debug logging in the solver and have noticed some very strange behaviour - I wonder if anybody familiar with these algorithms might be able to suggest the problem before I spent longer trying to dig deeper.
The problem (or at least a symptom) seems to be that in conjugate_pr_iterate(), xa and xc are identical (see debug output below). This means that it gets very confused trying smaller and smaller step sizes to find a point between them in intermediate_point() - understandably! Does anybody know how this has ended up happening, or where I should be looking to understand the problem? I am using a tolerance of 0.1 and stopping on the condition gsl_multimin_test_gradient(s->gradient, 1e-4). My only thought was that my calculation of the gradient was maybe wrong, which I could imaging would completely confuse the algorithm, but I have verified that approximately using finite differences, so that seems to be ok. Does anybody have any bright ideas based on this rather limited description? Many thanks Jonny. ------ got stepc = 0.1 fc = 0.00693957 trying stepb = 0.0144149 fb = 2.697778445904686073e-03 trying stepb = 0.00715726 fb = 2.671006683520049663e-03 ok! trying stepm = 0.00711345 fm = 2.671004412641564407e-03 p: 0.00588296 0.0161519 g: 0.00563168 -0.00624944 gnorm: 8.412567254502806985e-03 pg: -6.780910479189250365e-05 orth: 0.468907 trying stepm = 0.00708341 fm = 2.671003961247642167e-03 p: 0.00588296 0.0161519 g: 0.0056327 -0.00615491 gnorm: 8.343272460645591651e-03 pg: -6.627624061429551044e-05 orth: 0.462114 trying stepm = 0.00708336 fm = 2.671003961246420921e-03 p: 0.00588296 0.0161519 g: 0.0056327 -0.00615476 gnorm: 8.343167332821872784e-03 pg: -6.627390672587840171e-05 orth: 0.462103 trying stepm = 0.00708336 fm = 2.671003961246753988e-03 trying stepm = 0.00708338 fm = 2.671003961246642966e-03 trying stepm = 0.00708337 fm = 2.671003961246420921e-03 p: 0.00588296 0.0161519 g: 0.0056327 -0.00615479 gnorm: 8.343183613308536445e-03 pg: -6.627426816223239234e-05 orth: 0.462105 trying stepm = 0.00708337 fm = 2.671003961246976033e-03 trying stepm = 0.00708337 fm = 2.671003961246976033e-03 trying stepm = 0.00708337 fm = 2.671003961246976033e-03 trying stepm = 0.00708337 fm = 2.671003961246976033e-03 updated conjugate directions p: 0.008338 0.00127271 g: 0.0056327 -0.00615479 --- status -2, gradient 5.6327021514e-03 -0.0061547851 --- status -2, gradient 5.4416583599e-03 -0.0102750450 --- status -2, gradient 5.0767964535e-03 -0.0184895644 --- status -2, gradient 4.3981728357e-03 -0.0349475236 got stepc = 0.056667 fc = 0.00270968 trying stepb = 0.00521663 fb = 2.491500939798996228e-03 trying stepb = 0.000661013 fb = 2.479001874339692435e-03 trying stepb = 8.65819e-05 fb = 2.477502853117541370e-03 trying stepb = 1.13892e-05 fb = 2.477307907605919013e-03 trying stepb = 1.49899e-06 fb = 2.477282288191551274e-03 trying stepb = 1.97305e-07 fb = 2.477278916694358735e-03 trying stepb = 2.59706e-08 fb = 2.477278472927113562e-03 trying stepb = 3.41843e-09 fb = 2.477278414515726723e-03 trying stepb = 4.49957e-10 fb = 2.477278406827210233e-03 trying stepb = 5.92267e-11 fb = 2.477278405815241946e-03 trying stepb = 7.7946e-12 fb = 2.477278405682015183e-03 trying stepb = 1.02532e-12 fb = 2.477278405664584682e-03 trying stepb = 1.30613e-13 fb = 2.477278405662031169e-03 trying stepb = 2.30203e-14 fb = 2.477278405661809124e-03 trying stepb = 1.15102e-14 fb = 2.477278405661587080e-03 ok! trying stepm = 0.0233661 fm = 2.552135811738187599e-03 trying stepm = 0.0100192 fm = 2.505854742383517575e-03 trying stepm = 0.00436432 fm = 2.489079931938809054e-03 trying stepm = 0.00191389 fm = 2.482331142445115546e-03 trying stepm = 0.000841748 fm = 2.479477080356895513e-03 trying stepm = 0.000370684 fm = 2.478242083236104065e-03 trying stepm = 0.000163331 fm = 2.477702137702264551e-03 trying stepm = 7.19848e-05 fm = 2.477464985310429135e-03 trying stepm = 3.17293e-05 fm = 2.477360612487045088e-03 trying stepm = 1.39862e-05 fm = 2.477314635870309090e-03 updated conjugate directions p: 0.00439817 -0.0349475 g: 0.00439817 -0.0349475 --- status -2, gradient 4.3981728357e-03 -0.0349475236 got stepc = 1.15102e-14 fc = 0.00247728 # Presumably this tiny value for stepc is the root of the problem, but why is it so infinitesimal when it looks to me like we are not yet particularly close to convergence? trying stepb = 4.51789e-15 fb = 2.477278405661698102e-03 trying stepb = 1.33062e-15 fb = 2.477278405661809124e-03 trying stepb = 1.15956e-16 fb = 2.477278405661587080e-03 trying stepb = 5.79782e-17 fb = 2.477278405661587080e-03 trying stepb = 2.89891e-17 fb = 2.477278405661587080e-03 trying stepb = 1.44945e-17 fb = 2.477278405661587080e-03 trying stepb = 7.24727e-18 fb = 2.477278405661587080e-03 trying stepb = 3.62363e-18 fb = 2.477278405661587080e-03 trying stepb = 1.81182e-18 fb = 2.477278405661587080e-03 trying stepb = 9.05909e-19 fb = 2.477278405661587080e-03 trying stepb = 4.52954e-19 fb = 2.477278405661587080e-03 trying stepb = 2.26477e-19 fb = 2.477278405661587080e-03 trying stepb = 1.13239e-19 fb = 2.477278405661587080e-03 trying stepb = 5.66193e-20 fb = 2.477278405661587080e-03 trying stepb = 2.83096e-20 fb = 2.477278405661587080e-03 trying stepb = 1.41548e-20 fb = 2.477278405661587080e-03 trying stepb = 7.07741e-21 fb = 2.477278405661587080e-03 trying stepb = 3.53871e-21 fb = 2.477278405661587080e-03 trying stepb = 1.76935e-21 fb = 2.477278405661587080e-03 trying stepb = 8.84676e-22 fb = 2.477278405661587080e-03 trying stepb = 4.42338e-22 fb = 2.477278405661587080e-03 trying stepb = 2.21169e-22 fb = 2.477278405661587080e-03 trying stepb = 1.10585e-22 fb = 2.477278405661587080e-03 trying stepb = 5.52923e-23 fb = 2.477278405661587080e-03 trying stepb = 2.76461e-23 fb = 2.477278405661587080e-03 trying stepb = 1.38231e-23 fb = 2.477278405661587080e-03 trying stepb = 6.91153e-24 fb = 2.477278405661587080e-03 trying stepb = 3.45577e-24 fb = 2.477278405661587080e-03 trying stepb = 1.72788e-24 fb = 2.477278405661587080e-03 trying stepb = 8.63942e-25 fb = 2.477278405661587080e-03 trying stepb = 4.31971e-25 fb = 2.477278405661587080e-03 trying stepb = 2.15985e-25 fb = 2.477278405661587080e-03 trying stepb = 1.07993e-25 fb = 2.477278405661587080e-03 trying stepb = 5.39964e-26 fb = 2.477278405661587080e-03 trying stepb = 2.69982e-26 fb = 2.477278405661587080e-03 trying stepb = 1.34991e-26 fb = 2.477278405661587080e-03 trying stepb = 6.74955e-27 fb = 2.477278405661587080e-03 trying stepb = 3.37477e-27 fb = 2.477278405661587080e-03 trying stepb = 1.68739e-27 fb = 2.477278405661587080e-03 trying stepb = 8.43693e-28 fb = 2.477278405661587080e-03 trying stepb = 4.21847e-28 fb = 2.477278405661587080e-03 trying stepb = 2.10923e-28 fb = 2.477278405661587080e-03 trying stepb = 1.05462e-28 fb = 2.477278405661587080e-03 trying stepb = 5.27308e-29 fb = 2.477278405661587080e-03 trying stepb = 2.63654e-29 fb = 2.477278405661587080e-03 trying stepb = 1.31827e-29 fb = 2.477278405661587080e-03 trying stepb = 6.59135e-30 fb = 2.477278405661587080e-03 trying stepb = 3.29568e-30 fb = 2.477278405661587080e-03 trying stepb = 1.64784e-30 fb = 2.477278405661587080e-03 trying stepb = 8.23919e-31 fb = 2.477278405661587080e-03 trying stepb = 4.1196e-31 fb = 2.477278405661587080e-03 trying stepb = 2.0598e-31 fb = 2.477278405661587080e-03 trying stepb = 1.0299e-31 fb = 2.477278405661587080e-03 trying stepb = 5.14949e-32 fb = 2.477278405661587080e-03 trying stepb = 2.57475e-32 fb = 2.477278405661587080e-03 trying stepb = 1.28737e-32 fb = 2.477278405661587080e-03 trying stepb = 6.43687e-33 fb = 2.477278405661587080e-03 trying stepb = 3.21843e-33 fb = 2.477278405661587080e-03 trying stepb = 1.60922e-33 fb = 2.477278405661587080e-03 trying stepb = 8.04609e-34 fb = 2.477278405661587080e-03 trying stepb = 4.02304e-34 fb = 2.477278405661587080e-03 trying stepb = 2.01152e-34 fb = 2.477278405661587080e-03 trying stepb = 1.00576e-34 fb = 2.477278405661587080e-03 trying stepb = 5.0288e-35 fb = 2.477278405661587080e-03 trying stepb = 2.5144e-35 fb = 2.477278405661587080e-03
