Re: [Help-gsl] Help-gsl Digest, Vol 107, Issue 6

[Brian Hawkins]

Mikko and Rhys,

This looks like an issue with finite precision.  If you print the bits of
the value of the objective function they stop changing:

999997 f() = 238.8119354938235404 = 406dd9fb60250de1 size =
0.0000004931914997
999998 f() = 238.8119354938235404 = 406dd9fb60250de1 size =
0.0000004941216761
999999 f() = 238.8119354938235404 = 406dd9fb60250de1 size =
0.0000004931914997

So there's no way for the solver to proceed.  Your options are to either
change your objective function to one that "fits" in a double or relax the
convergence criteria.  I tried a few scaling tricks that got me closer to
f=0 but ultimately also failed to converge.  Maybe there's some
relationship between the problem dimension and the entropy of the objective
function (thus bits required).

Regards,
Brian

On Tue, Sep 18, 2012 at 9:00 AM, <address@hidden> wrote:
>
> Message: 2
> Date: Tue, 18 Sep 2012 08:03:43 -0500
> From: Rhys Ulerich <address@hidden>
> To: Mikko Olkkonen <address@hidden>
> Cc: GSL Help Mailing List <address@hidden>
> Subject: Re: [Help-gsl] Multidimensional minimization problem
> Message-ID:
>         <CAKDqugTWHOQ1iV+pnxVaoB=
> address@hidden>
> Content-Type: text/plain; charset=ISO-8859-1
>
> Oops.  This time with the list CCed...
>
> > I am running multidimensional minimization along the lines of the
> examples
> > in chapter 36.9 of the manual. gsl_multimin_fminimizers seem to converge
> to
> > the correct answers when dimension of the problem is low.
> >
> > e.g. setting VECLEN=10 (see code below) delivers:
> >
> >>converged to minimum at
> >> 6606 f() =   0.000 size = 0.000
> >
> > However when I raise dimension e.g. to 18 the algorithms seem to get
> stuck
> > into clearly wrong answer
> >
> >>999999 f() = 237.603 size = 0.000
>
> I agree that it seems gsl_multimin_fminimizer_nmsimplex probably
> should get this one right, but I'm afraid I don't know the guts of the
> algorithm.  Printing more precision I see it get stuck in some sort of
> a hiccup a la
>   74915 f() =   238.8119354938235404 size = 0.0000004931914997
>   74916 f() =   238.8119354938235404 size = 0.0000004941216761
>   74917 f() =   238.8119354938235404 size = 0.0000004931914997
>   74918 f() =   238.8119354938235404 size = 0.0000004941216761
>   74919 f() =   238.8119354938235404 size = 0.0000004931914997
>   74920 f() =   238.8119354938235404 size = 0.0000004941216761
>   74921 f() =   238.8119354938235404 size = 0.0000004931914997
>   74922 f() =   238.8119354938235404 size = 0.0000004941216761
>   74923 f() =   238.8119354938235404 size = 0.0000004931914997
> where you can see the iterates oscillating.  Changing the STEPSIZE
> sumply changes where the algorithm gets stuck:
>   49020 f() =   117.9245273558944547 size = 0.0000002658725425
>   49021 f() =   117.9245273558944547 size = 0.0000002659099457
>   49022 f() =   117.9245273558944547 size = 0.0000002658725425
>   49023 f() =   117.9245273558944547 size = 0.0000002659099457
>   49024 f() =   117.9245273558944547 size = 0.0000002658725425
>   49025 f() =   117.9245273558944547 size = 0.0000002659099457
>   49026 f() =   117.9245273558944547 size = 0.0000002658725425
>   49027 f() =   117.9245273558944547 size = 0.0000002659099457
>   49028 f() =   117.9245273558944547 size = 0.0000002658725425
>   49029 f() =   117.9245273558944547 size = 0.0000002659099457
>   49030 f() =   117.9245273558944547 size = 0.0000002658725425
>
> I do see gsl_multimin_fminimizer_nmsimplex2 getting the VECLEN 18
> problem to f() = 0.50421136 given TOLERANCE 2e-15 in about 1.5M
> iterations.  I haven't checked if it similarly gets stuck with
> oscillating iterates.
>
> I'd be interested to hear if you track down the source of these
> oscillating iterates.
>
> To be fair, you're cheating when you say it's a simple problem.  :)
> You intuitively know the derivatives but neither
> gsl_multimin_fminimizer_nmsimplex nor
> gsl_multimin_fminimizer_nmsimplex2 does.
>
> Hope that helps,
> Rhys
>