0
$\begingroup$

I have a complex physical system that depends on many continuous input parameters (let's say 10 important ones) and produces an output that I can boil down to one continuous figure of merit. I want to optimize this system and find the set of parameters that produces the best output.

The challenges are the following:

  1. The system is sufficiently complicated that I cannot predict the behavior well enough to build a useful model. I have to treat it as a black box and do all tests with the actual system.
  2. The input parameters are generally correlated. So, optimizing the parameters individually is not enough.
  3. The system is slow to react. When changing the parameters it takes some time until an equilibrium state is reached again, depending also on the magnitude of the change.
  4. The system is noisy. Even when not touching the system the output figure of merit will fluctuate strongly. I want to optimize the long-term average of the figure of merit, but in order to get a good estimate of that I have to measure for some time (many minutes if I wanted to bring the noise down to a negligible level).

On the other hand, the system is relatively well behaved when it comes to the shape of the function to optimize:

  1. I know that I'm already close to the global optimum and there are probably no local optima to get stuck in.
  2. I expect no sudden changes of the figure of merit. The gradients vary by not more than maybe two orders of magnitude over the permissible parameter space.

Question: What is a good technique to apply to this problem? Naïve approaches like a simple grid search are prohibitively time-intensive.

It seems like there will be a trade-off between long averaging and dealing with noisy data. So I would either need an algorithm that makes as few queries as possible, or one that's very robust to noise.

$\endgroup$
  • 1
    $\begingroup$ Sounds like a good fit for Bayesian optimization. $\endgroup$ – Emre Oct 30 '16 at 21:21
  • $\begingroup$ Most optimisation algorithms I've come across assume the cost of evaluating F(x) is independent of the cost of F(x'), so you can wander around the parameter space fairly freely. I'm not sure how you'd optimise if Cost(F(x)) = G(|x-x'|) where G is an increasing function and x' is the previous parameters. That's point (3) in your first list, mathematically, yes? $\endgroup$ – Spacedman Oct 31 '16 at 15:17
  • $\begingroup$ @Emre: Bayesian optimization sounds like it might be a good fit for the problem. I'll do some reading on it. In the meantime, if somebody feels like writing a full answer about it, that would be great! $\endgroup$ – Emil Oct 31 '16 at 15:53
  • $\begingroup$ @Spacedman: Yes, that's correct. But it might be enough to neglect this point at first. I'd already be glad to learn about an algorithm that's specifically tailored for costly function evaluations. $\endgroup$ – Emil Oct 31 '16 at 16:00
  • 1
    $\begingroup$ Paper here compares various algorithms for noisy functions and includes plot of accuracy/number of evaluations for them for various noise scenarios (fig 6.3) optimization-online.org/DB_FILE/2015/07/5006.pdf $\endgroup$ – Spacedman Oct 31 '16 at 17:01
1
$\begingroup$

Are you a petroleum engineer by any chance? This sounds very like the sort of optimization you have to perform in oilfield waterflood operations; you have to allocate your limited budget of injection water and/or lift gas to maximize oil production, with the additional complication that the optimal set point changes as the reservoir depletes and/or wells get drilled or abandoned.

The oilfield case has the useful feature that the overall objective function (field oil flowrate) is a simple sum of well flow rates. Each production well is generally only sensitive (in the short term!) to a small local subset of the inputs (gas lift rate in the production well, and water injection rate in near-offset water injection wells).

I would generalise the solution employed in the oilfield as follows:

  • Regularly perturb the inputs
  • Measure the affected local outputs
  • Maintain a simple linear or low-order polynomial model of the system and its parts
  • Use the model to optimize day to day
  • Keep good records to ensure that the model is up to date with reality
  • Monitor local and global model fidelity to decide what to perturb and recalibrate next

This works because the small perturbations that you keep on making (for model calibration purposes) are of short duration and local effect, so they don't take the overall system very far away from the optimum. The trade-off between keeping the system optimized, and "de-optimizing" it to calibrate the model, works out favorably. The system reacts on a timescale of days to months, and the measurements generally take a day or two to accomplish.

Try Googling waterflood optimization and gaslift optimization for some more detailed pointers, although a lot of the trade literature is paywalled.

Looking forward to learning what approaches have been taken in other fields with this kind of problem.

$\endgroup$
  • $\begingroup$ No, I'm not a petroleum engineer. ;) I'm a physicist working in the field of gravitational-wave detection. But of course the basic problem is a very general one and, as you say, it's interesting to see how different fields tackle it. So thanks a lot for your very interesting answer. $\endgroup$ – Emil Oct 31 '16 at 12:43
  • $\begingroup$ One thing we do not have is the local outputs that you describe. (Or rather, we have them, but I'm interested in the case where the information gained from them is already exhaustively used.) The idea of perturbing the inputs is indeed used in our field as well: We call this a dither locking scheme and it's used to actively drive individual parameters to their optimum setting. However, if I'm only ever perturbing individual parameters, I won't gain any information about their correlations. Is there an approach to systematically test for correlations? $\endgroup$ – Emil Oct 31 '16 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.