Question about the cause of "negative curvature" warning

[navid-hoseini]

First of all thank you for sharing your implementation of l-bfgs-b. I have faced an issue I hope you can help me with. During optimization, I constantly get the warning" negative curvature detected, skipping L-BFGS update". Since I am implementing an algorithm named REPS from [1], I'm sure the problem is convex. So could you please tell me what might have I done wrong that causes this warning? My setting for L-BFGS-B is :

lbnd=[-inf; 0.01];
ubnd = [inf; inf];
lbfgsOpts = struct('display', true, 'xhistory', false, 'tol', 1.0e-5, 'max_iters', 20,'m', 500);
p0 = [theta; eta];
[optimizedParams] = LBFGSB(func, p0, lbnd, ubnd, lbfgsOpts,...
%some more parameters to be passed to objective function
);

[1] Peters, Jan, Katharina Mülling, and Yasemin Altun. "Relative Entropy Policy Search." AAAI. 2010.

Thank you and best regards,
Navid.

[bgranzow]

Hi Navid, thanks for the information.

Unfortunately, I think it is likely that you haven't actually done anything incorrect, and that this implementation is not actually that robust. My motivation for writing this was for a class project, and I really only tested some small problems with a small number of design variables (which can be seen in the .pdf in this repository). Also unfortunately, I don't have real plans to further maintain this project.

I'm sorry this answer isn't much help. If you would like to use the L-BFGS-B algorithm with Matlab, I'd encourage you take a look at this wrapper around the original L-BFGS-B implementation, if you haven't already.

Cheers,
Brian

[user929292]

In most cases, I got that warning after "M = inv(MM);" often caused "Warning: Matrix is close to singular or badly scaled."
(The latter can easily be suppressed in MATLAB.)

In all cases, I was able to get rid of the warning by modifying the code so that a step is taken only if the new x has a lower f-value than the old one.

That way I also got much better results. Maybe the same happens to you, depending on your function.

Moreover, I had to make the following additions to avoid lbfgsb.m return x values out of the search space (which was likely caused by the almost-singularity of MM):

xbar = max(l,min(u,xbar)); %project to search space
end

function [alpha] = strong_wolfe(func,x0,f0,g0,p)

Just the first line was added. The others (old lines) just show the location in the code.

[alpha] = min(1, strong_wolfe(func,x,f,g,xbar-x)); %"min(1,)" added

where strong_wolfe was called.

Finally, there was a bug:

  if (k < m) 

should read

  if (size(Y,2) < m) 

as else early "negative curvature" causes
Error in LBFGSB (line 81)
Y(:,1:m-1) = Y(:,2:end);

[bgranzow]

@user929292 feel free to make a pull request, I will be happy to merge it if the two test files run.