[Help-gsl] Problems with conjugate gradient

[Jonathan Taylor]

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