Lbfgsb with box constraints failing

[hugandr]

It looks like the L-BFGS-B solver doesn't work properly. I added a simple test case in my fork:

The problem is this check:

auto noConvergence =
    [&](Vector<Dtype> & x, Vector<Dtype> & g)->bool {
      return (((x - g).cwiseMax(lboundTemplate).cwiseMin(uboundTemplate) - x).template lpNorm<Eigen::Infinity>() >= 1e-4);
    };

I don't really understand what it does, but it looks like it's not correct.

To check if the current value is still inside the box, one could just use something like this: (here with tolerance)

auto outOfDomain =
    [&](Vector<Dtype> & x)->bool {
      return (uboundTemplate-x).minCoeff() > -1e-4 && (x-lboundTemplate).maxCoeff() > -1e-4;
    };

I guess the step/step-size in the algorithm is chosen s.t. the new position is still inside the box, so there must be an error in the algorithm implementation.

[hugandr]

Another remark: In src/test/verify.cpp you have some cases to test the Lbfgsb class, but in all those examples, you didn't set a lower/upper bound. I think one should not allow to use Lbfgsb when hasLowerBound or hasUpperBound is false, since for these cases, the library provides other classes.

[hugandr]

I almost forgot: I find it always very confusing that you have to set the lower/upper bounds on the problem object and not on the Lbfgsb object. This doesn't make much sense to me. If you add the upper/lower bound as mandatory constructor argument to the solver, the remark above would also be resolved.

[PatWie]

Aren't bounds problem specific?
I have to look in my MATLAB-implementation of LBFGSB if I messed something up in the cpp version about the convergence check.

[hugandr]

Hmm, I see your point, but since the bounds are only used in a few solvers and control the behaviour of the minimization it makes more sense to me to move these properties into the solver where needed.

However, this is just a small remark.

[spinicist]

Hello,
I think I ran into this problem as well this week. LBFGSB was taking a step outside of the box constraints, which in my case means the problem returns NaN as the function cost.

I agree with @hugandr - because not all the solvers have bounds, it makes more sense for the bounds to be set on the solver not the problem. A user might set bounds on a problem and then use an unbound solver! In practice I don't think it is common to re-use solvers for multiple problems (I don't).

[PatWie]

I think this projection is correct:

auto noConvergence =
    [&](Vector<Dtype> & x, Vector<Dtype> & g)->bool {
      return (((x - g).cwiseMax(lboundTemplate).cwiseMin(uboundTemplate) - x).template lpNorm<Eigen::Infinity>() >= 1e-4);
    };

This is essentially projecting the deepest descent direction (see eq. 2.2 in the pdf)
lbfgsb.pdf

• set x = x-g
• all x entries smaller than lower bound set to lower bound
• all x entries greater than upper bound set to upper bound
• substract x

See eq. 2.2

I agree with @hugandr - because not all the solvers have bounds

Make sense. Ok.

[jdumas]

In the case of simple box constraints, why can't you simply clamp the values of the variables to their respective lower & upper boxes as a default behavior? If the user function is not defined outside the box domain anyway, I imagine the result of a gradient descent or conjugate gradient would still be quite reasonable? The solver class can also issue a warning, or throw an error, if it can really not handle boxed constraints. That way you keep the setLowerBound method in the Problem class.

[PatWie]

In the case of simple box constraints, why can't you simply clamp the values of the variables to their respective lower & upper boxes as a default behavior?

While this seems practical I think this is a bad workaround, since the entire optimization iterations can run along the constraints without hitting the minima. A projection seems to be the better way. But I am open, if this solves the problem.

Is there any simple objective, that causes this issue? If I have to guess the error, I think it will be inside the step-size function.

[jdumas]

I can't think of a real example right now. But at the very least, if want to keep the bound definition tied to the Problem class and not the solvers (which I think makes more sense: bounds are a property of a problem instance, not a solver), then other solvers should have a default behavior which throws an error if they are given a bounded problem, but they cannot handle bounded problems.

[spinicist]

Okay - how about we provide a BoundedProblem subclass, and move the upper/lower bounds to that. Then solvers that can cope with bounds can provide a minimise() that takes a BoundedProblem. This would remove the need for the hasLowerBounds/hasUpperBounds checks as well.

I can work on this but it will take a couple of days.

[jdumas]

Sounds reasonable to me. However, you'll probably need to keep the hasLowerBounds/hasUpperBounds check for partially bounded problem (e.g. with only a lower bound). Or the unset bound could default to +/- infinity, and the solver should recognize that.

[PatWie]

What about implementing a log-barrier method to support box-constraints for solvers that do not support these constraints by default?

[spinicist]

Closing this because of @43. Let me know if there's problems.