Maximize slow function [duplicate]

Question

So from experience (don't judge me, it was years ago...) I know that when a person with little knowledge about a field try to explain a problem to someone with a lot of experience it can easily lead to a lot of misunderstandings, everyone gets frustrated and more often than not nothing good comes out of it. So this time I will try with an analogy that (some) children can understand in order to explain my question. If you are too lazy, simply scroll down for my most likely terrible attempt on a short explanation.

Story

Once upon a time there was a guy called Bob, Bob was a great mechanic and he wanted to build a racing-car, and as anyone who wants to build a racing-car he wanted it to go as fast as possible. He knew his highschool maths and physics, however he knew that it would not be enough for finding out how to make the fastest car. Bob was very lucky because he had gotten his hands on a machine that calculated how fast a car would go based on a lot of knobs and switches that controlled things like, car height, type of engine, shape and etc. Unfortunately the machine was very slow and used around 5-10 minutes for one calculation. Bob knew he could make an other machine that would try a lot of different random combinations and try to find the best one, but he also knew that there were so many combinations that he would never be able to try all of them. Another problem is that Bob has no idea of how his machine works and he thinks there is no way he could find out.

Question is: how to help Bob?

tl;dr

I have a very slow and complex function $f(x_1 \cdots{} x_n)$ and I would like to find the best way to maximize/minimize this function with the least number of runs.

Answer 1

If you are interesting in maximizing some expensive-to-evaluate $f(x_1, \ldots, x_n)$ for which there is little structure (e.g. no convexity or other nice properties) over a large space of input values, then you are in the space of simulation optimization, and you should look into the various methods that have been proposed in this area of optimization.

A quick google search turned up a review of solution methods; as you can see there are many approaches.

One possibility is heuristic methods like genetic algorithms, tabu search, simulated annealing, coordinate descent, etc. In general these approaches won't be guaranteed to return the best possible solution, but they often in practice yield high-quality solutions while only exploring a small fraction of the input space.

Approaches based on estimated gradients like finite difference estimation, perturbation analysis, etc. can be used in iterative methods to take steps toward some locally optimal solution. Again, assuming $f(\cdot)$ has no nice convexity properties, these will not be guaranteed to yield optimal solutions but in some cases can guarantee locally optimal solutions.

A third approach is the response surface methodology. These approaches rely on sampling the space of input values and fitting a meta-model (popular ones are the gaussian process meta-model and linear regression meta-model) that predicts the simulated value given the input values and therefore provides a cheap-to-compute approximation to the simulation model. You can then use the meta-model to identify promising areas in the input space and simulate further values in those areas; for instance, a popular approach to determining the next point to sample is called Efficient Global Optimization (EGO). EGO and similar approaches balance the competing objectives of broadly exploring the input space to make sure we haven't missed promising areas and carefully exploring promising areas of the space to find the best solution in that area.

Answer 2

This is way too vague a question to provoke useful answers.

If this question were answerable, almost any problem would be solveable because almost ANYTHING can be represented as an optimization problem.

Some outlandish optimization problems:

1. Let $f(\boldsymbol{x})$ be the expected cost of going to the Mars as a function of a massive, choice vector $\boldsymbol{x}$ which represents a complete specification of the spacecraft, crew, research budget etc... Minimizing $f$ over $\boldsymbol{x}$ would find the lowest cost way to travel to Mars.
2. Let $f(\boldsymbol{x}) = -g(\boldsymbol{x})$ where $g(\boldsymbol{x})$ is the expected wins for the Chicago Cubs for the next season and $\boldsymbol{x}$ is the player roster. Minimizing $f$ is equivalent to maximizing expected wins.
3. Let $f(\boldsymbol{x}) = -g(\boldsymbol{x})$ where $g(\boldsymbol{x})$ is the expected number of upvotes I get and $\boldsymbol{x}$ is a vector representing the text I write in this answer. Minimizing $f$ is equivalent to choosing text that maximizes my expected up votes.
4. Let $f(\boldsymbol{x})$ be the number of moves before I can force a win in chess where $\boldsymbol{x}$ is my current move. Minimizing $f$ is equivalent to forcing a win in the fewest moves.

If your question is answerable, these problems are solvable.

A less flip answer...

A key question is whether your function $f$ is convex. If $f$ is convex, there may be hope in finding an optimum with very few function evaluations. For a general $f$ though, it's a total disaster.