[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [Help-gsl] On conjugate gradient algorithms in multidimentional minimisa

**From**: |
Max Belushkin |

**Subject**: |
[Help-gsl] On conjugate gradient algorithms in multidimentional minimisation problems. |

**Date**: |
Tue, 29 Nov 2005 20:50:45 +0100 |

**User-agent**: |
Thunderbird 1.5 (X11/20051025) |

Hello list,

` I apologize in advance for this rather long email, it is a collective
``description of the common problem I have failed to gain an understanding
``of, having tried for many months now.
`

` Over the last couple of years, I have made some observations on
``conjugate gradient algorithms that I would like to seek some advice
``about. This experience is related to gsl-1.6 and gsl-1.7, as of late.
`
-- Part 1 --

` The typical problem at hand is a parameter space of 20 dimensions or
``more. That is, a chi-squared function is built, which is to be
``minimized, that depends on 20 or more independent parameters passed to
``the minimization routine.
`

` The most common problem is the minimizer eventually bailing out with
``an error of "iterations not progressing toward a solution" (the exact
``message may be a bit different, I do not remember off-hand). Thus, I
``took up to restarting the minimizer with
``gsl_multimin_fdfminimizer_restart. However, it still does not help. Here
``is what happens. If we take a toy sample from the examples, and modify
``it a little, we get:
`do {
tryagain:
iter++;
status = gsl_multimin_fdfminimizer_iterate(s);

` if (status) {printf ("Restarting minimizer point 1\n");
``gsl_fdfminimizer_restart(s); goto tryagain;};
` status = gsl_multimin_test_gradient (s->gradient, 1e-3);
if (status == GSL_SUCCESS) { printf ("converged to minimum\n"); break;};

` if (status!=GSL_CONTINUE) { gsl_fdfminimizer_restart(s); printf
``("Restarted minimizer point 2\n"); status = GSL_CONTINUE;};
`} while (status == GSL_CONTINUE && iter < 10000);

` what happens is that we will always sit on "Restarting minimizer
``point 1", and status will always be "iterations not progressing toward a
``solution". Removing the goto has the same effect, only I [without any
``proof, just a feeling] believe it should also ruin the calls to
``test_gradient in some way.
`

` Now, if we remove the restart at point 1 and break there, then take
``the parameter vector we ended up with, plug it in, and start the program
``all over again, it will run for another 5000 iterations or so, then bail
``out with the same error at the same point. Repeat. And repeat...
`

` At this point, I was somehow thinking it may be an issue with my
``parameter space. However, recently, my colleague, who has some code in
``Fortran, asked me to come up with a C library employing GSL routines
``that would minimize his problem, which is completely different from
``mine, but the number of parameters is also large, around 15. So I came
``up with a module that could be linked with a Fortran program, and the
``exact same phenomenon appears there.
`

` I must admit I am no huge expert in the mathematics underlying the
``methods (Fletcher-Reeves, Polak-Ribiere and
``Broyden-Fletcher-Goldfarb-Shanno give the exact same results, up to an
``arbitrary constant in terms of the number of iterations), but I do know
``they have to be restarted from time to time. I did things like "if (iter
``% 50) gsl_fdfminimizer_restart(s)". No effect. So why does restarting
``the iteration all over (restarting the program) from that point works,
``and sometimes reduces the chi squared quite significantly over several
``such runs? And is there any way to force the minimizer to keep going, or
``have any more control over the convergence process?
`
-- Part 2 --

` This is somewhat related to Part 1. If I look at the convergence by
``the value chi squared takes per iteration, a typical [example] picture
``looks like this:
`50->30->20.1->20.0->19.99->19.981->19.9809->....<keep basically idle
for some 100s of iterations>->19.97->19.5->19.0->18.3->
17.8->17.79->....<hang here for another century>...->...

` The iteration process shows huge plateaus. What can this be an
``indication of? This is also very common and is seen on a wide range of
``problems, thus I am assuming this is a well known fact. Perhaps someone
``has a solution of speeding up the iteration and not sitting on those
``plateaus where nothing seems to be happening much?
`

` I apologize once again for the long email, and would be most grateful
``for any help on this subject.
`
Thanks!

**[Help-gsl] On conjugate gradient algorithms in multidimentional minimisation problems.**,
*Max Belushkin* **<=**