Workaround for BFGS with non simple constraints?

Question

In one sentence (thanks to @Brian Borchers), I want to minimize the function f(x, y, ...), with gradient g(x, y, ...), subject to constraints that aren't given explicitly, but are defined by situations where the routines that compute f and g return an error.

The domain for f isn't linear and it is not simple to change variables. I approximated a boxed constraints within which the parameters only occasionally (still infinitely many) fall out of the domain.

(think of f and g as a black box, it throws exceptions when parameters are not in the domain. I am only able to create wrappers so as to catch exceptions and returns some values.)

So, I used L-BFGS-B, and f to be very large when the parameters not in the domain. And I set g at those points to be 1.

In most case the optimization just works fine. However, sometimes it would trigger error like "ABNORMAL_TERMINATION_IN_LNSRCH", I guess it is just because my g doesn't agree with f at those nasty points.

What's the best practice in general in such case?

Answer 1

Unfortunately, L-BFGS-B simply isn't designed to handle this kind of problem.

Here are a couple of suggestions that might be helpful.

1. If you can define a smooth extension to your function $f(x)$ which increases very rapidly in value outside of the feasible region, then you may be able to get reasonable results using L-BFGS-B or some other unconstrained or bounds constrained optimization code.

2. If you can define a smooth function $g(x)$ such that $g(x)<0$ outside of the feasible region and $g(x) \geq 0$ inside the feasible region then you can use a constrained optimization routine to try to solve the problem.

3. If the objective function $f(x)$ is convex and the feasible region is convex, then there are lots of methods that can be applied. You could use the method of steepest descent for example. You could also use L-BFGS-B and simply restart the method with a steepest descent step every time the method tries to step outside of the feasible region.

4. In the general case where $f$ is nonconvex or the feasible region is nonconvex, the problem is hopeless.

Answer 2

It depends on what you care about. Another possibility is to pick the largest box in your feasible that you know doesn't contain any points outside the domain of $f$ and $g$. Assuming that $f$ and $g$ are smooth and convex, solving this problem will get you an upper bound on the optimal objective function value. Sometimes that upper bound can be helpful. Other times, it's simply not enough information.

Generally speaking, though, I would try some combination of 2 and 3 from BrianBorchers' approach. If you feel very strongly about using a BFGS-type method, using his suggestions, you could augment it with a gradient projection method, where BFGS steps are projected onto the feasible set to ensure that each iterate remains feasible. If $f$ is extended so that it is artificially very large outside of its domain, then restarting with gradient descent is probably a fine approach and gradient projection is a little overkill.