1

So I have a problem with the multidimensional minimization procedures in the GSL (the one I'm trying to use is gsl_multimin_fdfminimizer_vector_bfgs2, but the others produce the same problem). I have defined my target function and its gradient and I can start the iteration, but the algorithm always stays at the same point.

Now, I thought I would have a math error in my function or gradient somewhere. However, for a specific set of data I know the optimum and plugging in those values produces a gradient that is 0 everywhere.

If I start the iteration at the optimum, the algorithm correctly stops and reports success, but if I disturb the starting vector only minimally, the iteration runs forever and never finds the optimum.

I also reimplemented the function and gradient in R. I checked that the C version and the R version produce the same output for the same input, which they do. Using the BFGS algorithm in R, the optimum is found in just a few iterations.

I initialize the algorithm with

 const gsl_multimin_fdfminimizer_type *T;
 gsl_multimin_fdfminimizer *s;

 gsl_multimin_function_fdf lindsey_func;
 const gsl_vector * p[] = {x, y};

 lindsey_func.n = J;
 lindsey_func.f = lindsey_loglik;
 lindsey_func.df = lindsey_gradient;
 lindsey_func.fdf = lindsey_gf;
 lindsey_func.params = p;

 T = gsl_multimin_fdfminimizer_vector_bfgs2;
 s = gsl_multimin_fdfminimizer_alloc(T, J);     

 gsl_multimin_fdfminimizer_set(s, &lindsey_func, beta0, .001, 1e-4);

and the iteration looks like this:

 do
 {
  iter++;
  status = gsl_multimin_fdfminimizer_iterate(s);
  printf("%d\n", status);
  if (status)
       break;

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

  if (status == GSL_SUCCESS)
  {
     printf("Minimum found at: ");
     printf("[");
     for (j = 0; j < J; j++)
     {
      printf("%.5f, ", gsl_vector_get(s->x, j));
     }
     printf("]\n");
  }
 } while (status == GSL_CONTINUE && iter < iter_max);

The only parameter that I can tweak are the initial step size and the accuracy of the line minimization in gsl_multimin_fdfminimizer_set (gsl_multimin_fdfminimizer * s, gsl_multimin_function_fdf * fdf, const gsl_vector * x, double step_size, double tol). Trying different values there has a small effect (sometimes the algorithm moves a little bit), but I can't find any values that actually make the algorithm move around.

Thanks for any suggestions!

5
  • I should add that my function has 8 free parameters. If I constrain the problem to only 2 or 3 parameters it converges. With 4 parameters it already fails. However, I'm thinking that BFGS should be able to handle more than 3 dimensions.
    – oceanhug
    Apr 13, 2011 at 20:02
  • You said the gradient is 0 everywhere. It should only be 0 at the optimum. Is that a typo? Apr 13, 2011 at 20:15
  • I would double-check that gradient function & make sure it is good in all 8 dimensions, & has no discontinuities. Apr 13, 2011 at 20:25
  • No, the gradient is only 0 when I plug in the optimal parameters. I know that the gradient is correct because I get the same numerical values in R and the optimization runs fine there.
    – oceanhug
    Apr 13, 2011 at 21:15
  • Well then, in your shoes, I would get the source of the solver and step into it. Not fun, I know. It should work more or less like OPTIF9, picking a descent direction, doing a line search with Newton steps, and repeating. BTW, I'm fond of Metropolis-Hastings. Apr 14, 2011 at 0:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.