2
$\begingroup$

I'm trying to solve a specific problem related to my work in experimental physics. However, I'll try to keep my question as general as possible so that it is useful to a wider audience. If some context would be useful to clarify things, please ask!

What I'm trying to do is construct an algorithm to optimize an observable $f(x)$ that depends on a single variable $x$. I call it an observable because it is not some known function that I can differentiate, but some quantity that I probe (observe) for an input value of $x$. Observing the value of $f(x)$ is relatively cheap; changing the value of $x$ is at least 5 times as expensive (time wise). Might be useful to know.

Now, the function $f(x)$ has a maximum, which is what I am trying to find. It is actually also not a terribly complicated function; it more or less resembles a parabola, with a single maximum. I therefore believe it belongs to the class of hill finding optimization problems. Or maybe pattern finding? Derivative-free optimization?

But there are some complications. The first is that the system exhibits hysteresis; if I trace out a path $\{x_0, x_1, \dots, x_N\}$ and measure $f(x)$ at each point two times in a row (or trace the path back in reverse) I will not obtain the same values, and the maximum will not be in the same spot. The curve is generally shifted; 'history' is thus not fully trustworthy. So I can't simply do an exhaustive search over the parameter values and go back to it as the maximum will likely have moved. In addition there is also some noise in the system; this mainly means that taking very small steps is risky, and that finding a direction in which $f(x)$ increases does not guarantee that this is the direction leading to the maximum, it might have been that there was simply a noise spike. This is generally avoided by taking large enough steps (so that $f(x)$ changes by more than noise could obscure) but it should be taken into account in making things robust.

I was wondering if anyone has an idea on how to tackle this. Perhaps to further illustrate what I am trying to do I will provide some pseudo-code for my own algorithm, which I have been using up to now. This works in a rather robust way, but it is a bit slow, and I'd love to get some input from people who actually know about optimization.

inputs: initial_step, minimal_step

direction = 1
step = initial_step
x_current = x #measure the current value of x, basically free
f_current = observe_f() #observe the value of f(x) at the current x, costs a little

while step => minimal_step:
     x = x_current + step*direction #set a new value of x, somewhat expensive
     f = observe_f() #observe the new value of f
     if f < f_current:
          direction = direction*-1
          f_current = f
               if direction == 1:
                    step = step/2
     else:
          f_current = f

What this does is simply step x (starting from a specified initial step) and see if f increased or decreased. If it increased, continue stepping in that direction. If it decreased, step in the opposite direction. If it decreased twice in a row, half the step size, as we are overshooting the maximum. The problem halts when the step size falls below some specified minimum. Now, this seems to be quite robust, because you find the maximum by overshooting it less and less. And if you're led astray by noise/hysteresis, you'll usually end up back on the right track after some time, as all it will do it point you in the wrong direction for an iteration or two.

But the algorithm is not particularly clever. If minimal_step is many times smaller than initial_step, you'll wiggle around about the maximum for a rather long time, gaining very little, while performing these small, useless steps is expensive (time wise). That is one of the things I'd like to improve upon, but perhaps you also have other insights?

Edit: what I forgot to add initially, but is also important, is that I'd like to specify a maximal step size to be taken. Otherwise I run the risk of losing sight of $f(x)$.

$\endgroup$
  • $\begingroup$ It is programmatically straightforward to perform optimization in Python without the use of gradients by using scipy's Differential Evolution genetic algorithm, where you would minimize negative f instead of maximizing positive f. $\endgroup$ – James Phillips Jan 4 at 13:13
  • $\begingroup$ docs.scipy.org/doc/scipy-0.15.1/reference/generated/… is what you're referring to? I will read through the documentation, especially to see how it'd deal with hysteresis/noise. I'm a little hesitant though because it looks rather complex, making it hard (without fully understanding all of the code) to prevent runaway situations/make it fully robust. $\endgroup$ – user129412 Jan 4 at 13:49

Your Answer

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

Browse other questions tagged or ask your own question.