Optimization algorithm selection for 3 variable integer

Question

I have a cost function: $f(x,y,z) \rightarrow \mathbb{R}$

• it is very expensive to evaluate
• $x,y,z \in \mathbb{Z}$
• 0 < x < 10
• 0 < y < 30
• 0 < z < 100
• I thought it was convex, not sure now based on @Brian's commentary.
• $f$ can only be evaluated at integers ( I pondered trying to evaluate at real's but it would be fairly insanely difficult to try & the result would be totally bogus).
• $f$ is smooth but only at the integer values. So the gradient could only be computed using re-evaluating $f$ at intervals - but again that's really expensive.

I'm looking for suggestions on algorithms, and libraries ( C++ preferred, C acceptable ).

I've spent a couple of days trying to brush up on the topics, but its pretty dense. I've been looking at COIN-OR, specifically OSI, but I can't seem to figure out how to formulate my problem into the API. I've also looked at EasyLocal++, but haven't really dug in yet.

Answer 1

You haven't said whether $f$ can be evaluated at points where $x$, $y$, and $z$ are real numbers within the specified ranges that aren't integers. If this makes no sense, than the function isn't actually convex. You also haven't said whether $f$ is smooth (e.g. is it twice continuously differentiable?)

Conventional gradient based optimization algorithms will typically require quite a few function evaluations (e.g. for line searches) as well as requiring the gradient of $f$ (which can be approximated by finite differences, but that implies even more function evaluations.) If the function is convex but not smooth, and you can't describe the non-smoothness in more detail, then these algorithms aren't appropriate anyway.

For a low dimensional problem with very expensive (or noisy) function evaluations, its often a good choice to use a "response surface method" to build a regression model of the function, minimize over the simple (e.g. quadratic)function that you've built using regression, and then (as many times as you can afford) narrow your search and build a new regression model.

Can you afford to do 27 function evaluations at $x=0, 5, 10$, $y=0, 15, 30$, and $z=0, 50, 100$? That should be enough to construct a first quadratic model of the response surface.

Answer 2

The convexity of $f$ (over the continuous relaxation of the domain) does not matter as far as choosing the outermost solver: you will need a branch-and-bound algorithm if you choose to solve your problem deterministically because you have binary decision variables. I presume $f$ is nonlinear? If that is the case, you will need an MINLP solver like Bonmin. The convexity of $f$ will help in solving lower bounding problems; if you relax all of the binary variables to continuous variables, you should be able to find a lower bound on your solution with a nonlinear programming solver like IPOPT. Feasible solutions will give you an upper bound. I'll see if I can dig around to find a good online reference about branch-and-bound algorithms in integer programming. You could also solve the nonlinear problems using derivative-free methods, to save on function evaluations.

If $f$ is linear, you'll probably want to use something like CBC, which is a branch-and-cut framework (similar in spirit to branch-and-bound). However, given that $f$ is expensive to evaluate, I doubt it is linear.

These methods don't lend themselves to problems with expensive function evaluations. Are you willing to give up some some accuracy in the solution for a faster algorithm, and if so, how much?