[Help-gsl] Re: Help: working with large gsl_vector

[Toan T Nguyen]

Hi, thank you for the analysis. Apparently, my analytical calculation is able 
to guess the minimum reasonably good, so I need only 20000 iterations to find 
the minimum. 

However, the strange thing is if I take the final minimized vector and run it 
through the conjugate gradient routine again, the energy (my function to 
minimize) keeps going down for a few more 1000s iterations (albeit it change 
only the 4th significant digit). Do you know what's wrong?

I follow the example in the GSL document and set my success criteria as

status = gsl_multimin_test_gradient (s->gradient, 1e-20);

The initial setup of the vector is

T = gsl_multimin_fdfminimizer_conjugate_pr;
s = gsl_multimin_fdfminimizer_alloc (T, 3*nparts);
gsl_multimin_fdfminimizer_set (s, &energy, x, 0.001, 1e-12);

For clarity, I used dimensionless units so ALL the nearest neighbor distances 
and the coupling constants are of the order of unity. nparts is the number of 
particles which is about 100000.

Could you give some advises? Thanks a lot in advance.

Toan



On Monday 13 December 2004 10:50, Fabrice Rossi wrote:
> Toan T Nguyen wrote:
> > I'm using the multidimensional minimization procedure in GSL and have
> > problem with large vectors. The dimensionality of my vectors is 300000
> > which means my index variable is of long integer type.
>
> Hum. I authored the initial version of the multidimensional minimization
> functions which have been improved by others, but I don't think they
> have been improved in such a way that optimization in dimension 300 000
> is possible. Even for a quadratic function and using a conjugate
> gradient algorithm, it will take 3e5 iterations to the algorithm to
> complete. As each iteration implies a linear search for minimum that
> will use at least around 10 evaluations of your function, your a looking
> for 3e6 function evaluation. Unless you have a very special problem, I
> would guess that a function evaluation take at least 3e5 operations to
> complete, which implies 9e11 operations (a.k.a. 2^39 operations). That's
> a lot. And we are talking about a quadratic form, remember ?
>
> Perhaps you could tell us a little bit more about your application ?
>
> Fabrice
>
> PS : Support Vector Machine algorithms have proven that it is indeed
> possible to do quadratic optimization under constraints in high
> dimensional space (like 10000 dimensions), but they use _very_ complex
> methods.