Solved – Meaning of a convergence warning in glmer

convergenceglmmlme4-nlmeoptimizationr

I am using the glmer function from the lme4 package in R, and I'm using the bobyqa optimizer (i.e. the default in my case). I am getting a warning, and I'm curious what it means. 

Warning message:
In optwrap(optimizer, devfun, start, rho$lower, control = control,  :
  convergence code 3 from bobyqa: bobyqa -- a trust region step failed to reduce q

I searched "a trust region step failed to reduce q." Found some information in the minqa package, which said "Consult Powell for explanation." I did (you can too, if you want! see the references and links to them below), but I fail to understand. In fact, I failed to find anything about reducing q.

M. J. D. Powell (2007) "Developments of NEWUOA for unconstrained minimization without
derivatives", Cambridge University, Department of Applied Mathematics and Theoretical Physics,
Numerical Analysis Group, Report NA2007/05, http://www.damtp.cam.ac.uk/user/na/NA_papers/NA2007_05.pdf.

M. J. D. Powell (2009), "The BOBYQA algorithm for bound constrained optimization without
derivatives", Report No. DAMTP 2009/NA06, Centre for Mathematical Sciences, University of
Cambridge, UK. http://www.damtp.cam.ac.uk/user/na/NA_papers/NA2009_06.pdf.

P.s. I know I can change the optimizer, and I will to see if I can get output without warnings or errors. I will also check the gradient and Hessian if I can, as per a comment/answer by Ben Bolker. I'm using glmer within dredge from MuMIn and I'm not sure if Ben's answer will work without some additional tinkering, but I'll work on it once my computer finishes what it's doing, anyway, I digress.

Update

As per Dr. Bolker's comment below, I began looking through the FORTRAN code (Here is the code for anyone interested in looking but not downloading it). "430" appears in the bobyqb.f portion of the code. Simply search for "430" or "reduce Q" to find the relevant code.

This is my first encounter with FORTRAN code, but I think the code says that if the following conditions are met, produce the warning: NTRITS > 0, VQUAD >= 0, IPRINT > 0. "The integer NTRITS is set to the number "trust region" iterations that have occurred since the last "alternative" iteration." VQUAD appears several times, and I'm not yet clear on it's significance as its value seems to be dependent on a variety of other variables, the values of which sometimes depend on other variables.From bobyqa.f: "The value of IPRINT should be set to 0, 1, 2 or 3, which controls the amount of printing. Specifically, there is no output if IPRINT=0 and there is output only at the return if IPRINT=1.".

So, it seems the task is to figure out the significance of VQUAD being >= 0 and, perhaps, understanding how / when IPRINT became > 0. I'll have to go back to the paper to have a look, but the math, or at least its symbolic expression, is a bit of a barrier for me. Unless, someone knows about the algorithm or has the desire to learn about it, I think I'll have to iteratively increase my understanding of the warning by going back and forth between the papers, the code, and the internet until I understand what it means.

Best Answer

Before going in to the code, allow me to give you a quick primer on trust region methods. Let $f(x)$ be your objective function and $x_k$ be your current iterate. Iteration $k$ of a generic trust region method looks something like this:

  • Pick a maximum step size, $\Delta_k$
  • Build an model of $f(x)$ at $x = x_k$; call it $Q(x)$.
  • Find the step, $s_k$, that minimizes $Q_k(x_k + s_k)$ subject to the constraint $||s_k|| \leq \Delta_k$
  • If $s_k$ is "good enough", let $x_{k+1} = x_k + s_k$
  • Otherwise, refine your model and try again

One of the the ways you determine if $s_k$ is "good enough" is by comparing the decrease predicted by the model to the actual decrease in the objective function. This is what the portion of the code after 430 does. However, before that, there's a quick sanity check to see if the model predicts a decrease AT ALL. And that's what's happening at 430.

To understand the value of VQUAD, we first have to understand a few other variables. Fortunately, there are good comments right below the declaration of SUBROUTINE BOBYQB. The salient variables are:

  • GOPT, the gradient of the model
  • HQ, the Hessian of the model
  • D, the trial step (I called this $s_k$ above)

Beginning a few lines above 410, you'll see DO 410 J=1,N. This begins a for-loop (and a nested for-loop) that evaluates the change predicted by the model using trial step D. It accumulates the predicted change in VQUAD. The first part of the for-loop evaluates the first-order terms and the nested for-loop evaluates the second-order terms. It would probably be easier to read if the loops were indented, like this:

    DO 410 J=1,N
        VQUAD=VQUAD+D(J)*GOPT(J)
        DO 410 I=1,J
            IH=IH+1
            TEMP=D(I)*D(J)
            IF (I .EQ. J) TEMP=HALF*TEMP
410         VQUAD=VQUAD+HQ(IH)*TEMP

There's another for-loop after this to incorporate other parameters in to the model. I have to admit, I don't fully understand this - my best guess is that it's particular to how they build the model.

At the end of all this, VQUAD holds the change in objective function predicted by the model. So if VQUAD is non-negative, that's bad. Now this particular solver can use an alternative step computation (probably a line search), which is where NTRITS comes in to play. So the logic at 430 is saying, "If the last iteration used the alternative step computation AND the model does not predict a decrease AND IPRINT > 0, print the warning message." Note that the solver is going to terminate regardless of the value of IPRINT.

Speaking of IPRINT, that value is passed to BOBYQA by the calling function. In this case, your R routine is the calling function. There's a verbose parameter to glmer - I would be dimes to dollars that same value is passed to BOBYQA. Try setting verbose to 0 and you probably won't see the warning. But it won't change what's going on under the hood, of course.

Related Question