16
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I think this question may be on-topic for CV b/c it seems to be about understanding the ideas rather than help w/ R per se. $\endgroup$ – gung - Reinstate Monica Mar 14 '14 at 2:33
  • $\begingroup$ I'm not sure I have a lot to suggest in this case beyond going bit-by-bit through the papers and the FORTRAN code (which is included in the src directory of cran.r-project.org/src/contrib/minqa_1.2.3.tar.gz ) and seeing precisely what's going on when this error (error code 430 in the code) gets triggered ... $\endgroup$ – Ben Bolker Mar 14 '14 at 12:40
  • 1
    $\begingroup$ Quickly skimming over the paper I think the warning indicates that the optimizer cannot find a direction in which the quadratic approximation, Q, to the function you want to minimize, F, decreases. That is, the optimizer is at a point that is most likely not optimal but it does not know what way to go to improve the objective. Hence, it is stuck. $\endgroup$ – Sven Aug 2 '16 at 18:13
  • 1
    $\begingroup$ which of the two papers did you skim, and approximately where did you find this info? (I've skimmed too but wasn't able to make the correspondence between paper & code that easily ...) $\endgroup$ – Ben Bolker Aug 2 '16 at 19:05
  • $\begingroup$ I read the BOBYQA paper. I went over the first half in about 5 mins to get a broad idea of what they are going and what Q is. Can't really point to a specific page. $\endgroup$ – Sven Aug 4 '16 at 5:33
13
+50
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ this is very helpful; I don't think I'm going to do better, awarding bounty ... $\endgroup$ – Ben Bolker Aug 8 '16 at 18:44
  • $\begingroup$ @BenBolker. So should I be concerned about what's going on here, or is this really just a nuisance in the code? (In other words, does this warning mean my results are not valid??) $\endgroup$ – theforestecologist May 26 '18 at 23:10
  • 1
    $\begingroup$ the general advice in this case is what's stated in ?lme4::convergence: short of exhaustive/detailed evaluation of the optimization procedure, your best best is to compare results from different optimizers. $\endgroup$ – Ben Bolker May 27 '18 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.