Machine Learning for Optimization

Question

I have a function which takes 100+ coefficients and outputs $x$. I wish to optimise $x$.

Running the simulation 50 000 times will take around 15 minutes, however, this happens in parallel - and the separate CPUs do not communicate with each other.

When I try usual gradient descent methods I end up with something which I am confident is a local minimum. Methods which are more likely to find a global maximum, such as simulated annealing I can only get to run "linearly", so I cannot run the simulation in parallel, and so is prohibitively slow.

I was thinking that machine learning might have a potential solution when dealing with this dimensionality of data, and hopefully, one which is readily accessible (read: function I can call). I would run a lot of training sets, then ask the machine learning algorithm to help identify and predict maxima (even if it isn't the global one).

I understand at the heart of most machine learning problems lies optimisation. But, I seem to find that mots machine learning algorithms which are used for different generic goals (i.e., classification, clustering, regression). I cannot easily find many which would guide an optimisation algorithm. Is there any which would help in this case?

Answer 1

The general idea that you have of learning an easy to compute model from results of your detailed simulation model and then optimizing the easy to compute model is long-established. The easy to compute model is typically called a surrogate model or a response surface model. Once the surrogate is available, you can use conventional optimization techniques to find the minimum of the surrogate. It's always a good idea to go back to the original high fidelity model and rerun it using the optimal parameters that you've obtained to make sure that the surrogate did approximate the full model well enough.

You could use a neural network as your surrogate, or you could use some other kind of machine learning model. In computational practice, quadratic regression models are often used because they can be made convex and because optimizing over the surrogate is extremely easy. In comparison, the function computed by a fitted neural network is likely to be non-convex and your optimization routine is likely to get stuck in a local minimum.

Note that 50,000 samples is very small for a 100-dimensional space. Using a deep neural network, you'd need a regularization strategy to avoid overfitting the surrogate model.

If your high fidelity model uses some kind of Monte Carlo algorithm, then the outputs will be somewhat noisy- keep this in mind to avoid overfitting the results.

In many cases like this, some of the parameters are relatively insignificant while others are significant but completely independent of the other parameters. It is generally wise to use screening strategies to eliminate or fix those parameters before optimizing over a smaller set of critical parameters.