Proposition of a better convergion criterion in multimin

Proposition of a better convergion criterion in multimin

[Philippe Huber]

Hi all,

I found that the stopping criterion proposed in
gsl_multimin_test_gradient suffers from scale problems. Typically, if
you have variables of magnitude 1.0e0 and a function of magnitude 1.0e5,
it can be impossible to minimize the norm of the gradient under 1.0e-2.
Dennis and Schnabel in "Numerical Methods for Unconstrained Optimization
and Nonlinear Equations", p.160 propose another criterion:
relgrad = gradfi * xi / f,
where gradfi is the ith component of the gradient and xi the ith
variable. The criterion is ||relgrad||inf < epsabs, with ||.||inf is the
infinite norm: ||x||inf=max(|xi|).
Here is a proposition of a new routine called gsl_multimin_test_relgrad:

int
gsl_multimin_test_relgrad (const gsl_vector *g, const gsl_vector *x,
double f, double epsabs)
{
  int i;
  double relgrad;

  if (epsabs < 0.0)
    {
      GSL_ERROR ("absolute tolerance is negative", GSL_EBADTOL);
    }
  relgrad=fabs(gsl_vector_get(g,0)*gsl_vector_get(x,0)/f);
    for(i=1;i<g->size;i++)
 
relgrad=gsl_max(relgrad,fabs(gsl_vector_get(g,i)*gsl_vector_get(x,i)/f))
;

  if (relgrad < epsabs)
    {
      return GSL_SUCCESS;
    }

  return GSL_CONTINUE;
}

Take care

Phil

Re: Proposition of a better convergion criterion in multimin

[Brian Gough]

Philippe Huber writes:
 >  I found that the stopping criterion proposed in
 > gsl_multimin_test_gradient suffers from scale problems. Typically,
 > if you have variables of magnitude 1.0e0 and a function of
 > magnitude 1.0e5, it can be impossible to minimize the norm of the
 > gradient under 1.0e-2.  Dennis and Schnabel in "Numerical Methods
 > for Unconstrained Optimization and Nonlinear Equations", p.160
 > propose another criterion: relgrad = gradfi * xi / f, where gradfi
 > is the ith component of the gradient and xi the ith variable. The
 > criterion is ||relgrad||inf < epsabs, with ||.||inf is the infinite
 > norm: ||x||inf=max(|xi|).  Here is a proposition of a new routine
 > called gsl_multimin_test_relgrad:

How about scaling the components of g? This would be invariant under
x->x+constant, f->f+constant which seems like a useful property.