Function approximation

Question

I have a function,

P (x0, x1, ..., xn)

which takes 100 integers as input and gives an integer as output. P is a slow function to evaluate (it can vary from 30 seconds to several minutes).

I need to know which point values ​​will maximize the resulting value from P.

What methods can I use to achieve this? I know that in general, people use genetic algorithms for this, but I'm afraid that it will take a lot of time to calculate them, since even with a small population and several generations (say, population = 50, generations = 50), P to calculate it It will take more than 40 hours.

Is there a cheaper way to do this? Maybe an iterative process? I do not need it to be really optimal, but I have no idea how it behaves (I tried linear / quadratic / exponential, but it does not seem to give any good values. I know that P can return values at least 5-10 times better than what I get).

It should be something that is easier to implement (i.e. I have to implement it myself).

thanks

edit: P is a stochastic process.

Answer 1

As the first line algorithm for this type of problem, I would recommend Simulated Annealing. SA is a great choice because you can clearly control your starting point and launch time.

If you know something about the structure of your 100-dimensional space, with SA you can choose a good starting point and this can greatly affect the quality of your result. Also with SA, you can control the “cooling rate”, which affects both the running time and the quality of your results - naturally, in opposite directions. I usually start with a relatively high cooling rate, first to find good starting vectors, and then slow down the cooling rate in subsequent series to improve the results. A type of meta-SA method that can be automated.

I have successfully used SA to maximize the very high dimensional function used to model neutron proton interactions in the past.

In addition, I would like to reduce the size of P () if possible. Are all 100 variables necessary for your specific problem? If you can fix 1/2 of them, you will speed up any optimizer and get better results.

(And SA is easy to implement.)

Answer 2

Simulated annealing , closely related to the Markov Monte Carlo chain (MCMC) . The option you probably want is Metropolis-Hastings . When you get it, it's pretty good. Perhaps there are some ways to optimize it, because your inputs and output are integers. This is computational intensity and may require some tuning, but it is pretty reliable, and I'm not sure what other methods can do better.

Here is some kind of brain code for this:

const int n = 100; // length of vector to optimize int a[n]; // the vector to optimize double P(a){..} // Get the probability of vector a. // This is the function to optimize. // for a large number of a samples for (i = 0; i < large_number; i++){ // get P(a) double p = P(a); // for each element of vector a for (j = 0; j < n; j++){ // get an amount by which to change it. This choice has to be symmetric. // this is called the Proposal Distribution int step = uniform_random_choice_from(-2, -1, 1, 2); // make the change to a[j], and get p1, the new value of p a[j] += step; double p1 = P(a); bool bKeepTheStep = true; // if p1 is better than p, keep the step // if p1 is worse than p, then keep the step p1/p of the time if (p1 < p){ bKeepTheStep = (unif(0,1) < p1/p); } if (bKeepTheStep) p = p1; else a[j] -= step; } // now a is a sample, and p is its value // record a and p } // what you have now is a large random sampling of vectors from distribution P // now you can choose the best one, the average, the variance, // any statistic you like 

Customization methods are expanding or narrowing the distribution of the proposal, so this requires larger or smaller steps, or you can complete the larger steps first and then the smaller steps. What you are looking for is the percentage of steps that are not too high or too low. You probably want to have a “burn” phase of the initial 1k or so samples that you throw out while they hunt for the regimen area.

And, by all means, P.'s profile. It should be as fast as possible. Here is my favorite way to do this.

Answer 3

Maybe a significant part of your algorithm is parallel? If so, have you considered code parallelization?

Answer 4

Take a look at the various stochastic optimization methods listed here . I recommend simulated annealing .

Answer 5

There are many well-known global optimization algorithms (simulated annealing, stochastic tunneling, etc.) that MAY find a global maximum, but no one can find it within a reasonable amount of time without making assumptions about the shape of the function.

You won't find a quick / easy way to optimize a 100-dimensional, non-trivial function. You will need a lot of processing power and time. Assuming you don’t want to write optimization code yourself (depending on your question), you will also need good math software (like Mathematica).

Answer 6

Another not-so-serious answer, but food for thought:

This problem looks so big that you rightfully need something like SETI @Home's efforts to solve it. Thousands of computers do intelligent work of this kind. But I'm not sure how you will reach thousands of computer users to access their computers.

Actually, yes. Please carry me for a moment, ignoring the legality of it all.

There are botnets managed by some people hiding behind the former iron curtain. I recently saw an offer to rent a botnet for $ 70 in 24 hours. Think of thousands of toner computers ready to make your suggestions! Instead of having their DDOS Internet sites, you could make them brandish your problem. :)

Two final tips on this:

• Do not pay them your credit card :)
• Do not use the legal advice of strangers on SO :)

Good luck

Answer 7

Assumptions:

First, the variables must be integers.
Secondly, the object function P () is nonlinear.

Observation:

In general, nonlinear integer programming is very difficult to solve. In fact, as recommended above, helping to solve the rounding by loosening the integer constraint can help.

There are general unlimited optimization methods. One approach that comes from experimental design is the "response surface" method. Very useful when the cost of the experiment is significant. The approach is to start a set of experiments, starting from one point and rejecting each of your inputs using a given increment. Then you calculate the gradient for each input and take a step in that direction for each, and then repeat. Fletcher - Practical methods of optimization, as well as statistics of hunters and hunter hunters for experimenters - this is the place to search.

Answer 8

Neural Networks : D or Taylor Series ?

Answer 9

If you have access to Matlab, you can parallelize your code pretty quickly and easily. Even he can make simple linear for loops parallel to his parfor loop

Answer 10

If Microsoft's solution is an option, check out the Solver Foundation . I heard about the Scott Hanselman podcast ( # 191 ).