Hello Max,
To the part two of your question.
I am no matematician either, but could it be that when you see the
mentioned plateau it is not actually a plateau, but one (or more) of
your parameters has a very small influence on the RSQ? Eg several order
of magnitudes smaller than others? 19.9809->....<keep basically idle
for some 100s of iterations>->19.97->19.5->
is really
19.9809->....<19.9809000040 -> 19.9809000036 -> 19.9809000003 .....
->19.97->19.5->
I am not too much into the details of the minimizing, but i seem to
recall it minimizes over one parameter at a time.
Is that a possibility?
Cheers
Soren
Fra: Max Belushkin
Sendt: on 30-11-2005 06:50
Til: address@hidden
Emne: [Help-gsl] On conjugate gradient algorithms in multidimentional
minimisation problems.
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 mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-gsl