3
$\begingroup$

I have a time-dependent (dynamic) optimization problem: $$ f_t : [0;1]^2 \mapsto \mathbb{R}^+; t \in [1, \dots, n] $$ $f_t$ is to be maximized. That is for each $t$ I would like to find a relatively high value of $f_t$. Mostly, $f_t$ is a relatively simple, continuous, unimodal function. It changes with time, but not much and not predictably. I know only that the scale of the function goes down exponentially.

The problem is that at each time I can perform only a handful (5-10) of evaluations of $f_t$.

I am absolutely new to dynamic optimization and therefore I am looking for some simple approach. Any suggestions or references to literature are welcome.

I have considered particle swarm optimization, but the papers on PSO I read are usually dealing with at least 10 dimensional problems, so PSO may be an overkill. Also I do not know if it is appropriate to use just 5-10 particles.

$\endgroup$
  • $\begingroup$ @D.W. Thank you for your suggestion and sorry for the confusion. I tried to edit the question to answer all your questions as well as I could. $\endgroup$ – Martin Drozdik Oct 26 '14 at 7:52
2
$\begingroup$

Many optimization procedures are based upon successive approximation: they start with a value of $x$, and try to successively refine $x$ to move it closer and closer to the optimum. For instance, hill climbing and gradient ascent both have this structure.

You can use this structure to solve your problem. Let $x_t$ be the maximum for $f_t$. Then you can use $x_t$ as the starting point (the initial approximation) when looking for the maximum for $f_{t+1}$. Now iterate, using the maximum for the previous time period as the starting point for hill climbing / gradient ascent / .... in the next time period. If the maximum for $f_{t+1}$ is close to the maximum for $f_t$, this might work reasonably well.

There are many different possible ways to instantiate this basic approach. Here are some possible examples of how this might look:

  • With gradient ascent, you evaluate $f_{t+1}$ three times at three points near $x_t$: e.g., at $x_t$, $x_t+(\varepsilon,0)$, and $x_t+(0,\varepsilon)$. You use the result to estimate the gradient around $x_t$, and then move in the direction of the gradient.

    As a possible optimization/variation, you might align the axes in the direction of the gradient for $f_t$. For instance, if the gradient was maximum in the angle $\theta$ for $f_t$, you might evaluate $f_{t+1}$ at the three points $x_t$, $x_t+(\varepsilon \cos \theta, \varepsilon \sin \theta)$, $x_t + (\varepsilon \cos (\theta+\pi/2), \varepsilon \sin (\theta+\pi/2))$, then use those values to estimate the gradient.

  • As another possible optimization, you could follow this with a line search. Suppose $\delta$ is the direction that maximizes the gradient. Then you could evaluate $f_{t+1}$ at $x_t,x_t+\delta,x_t+2\delta,x_t+3\delta,x_t+4\delta,\dots$, stopping at the first one that stops providing any improvement. Or, you could evaluate $f_{t+1}$ at $x_t,x_t+\delta,x_t+2\delta,x_t+4\delta,x_t+8\delta,\dots$. You could even follow this with an iteration or two of binary search to find the best stopping point, though that might not be worthwhile.

  • If you are trying hill-climbing, you will do something simple like this: pick a random point $x'$ in the neighborhood of $x_t$, and if $f_{t+1}(x') > f_{t+1}(x_t)$, then move to $x'$. You can repeat this a few times.

Of course, you can combine these methods. There may be many other variations you could try. I would suggest that you read about methods for optimization, brainstorm other similar methods, and then try them all to see which work best.

Also, you might want to try a simulation: choose $f_t$ that you believe to be representative and where you can evaluate them as many times as desired to find the true maximum and their shape, and then simulate each of these strategies to see how well they work. You might also want to visualize the shape of the $f_t$ and what these strategies are doing (what points they are visiting), in case that helps you refine them or choose suitable constants that are appropriate for your particular application domain.

$\endgroup$
  • $\begingroup$ Thank you! However I can use only 5-10 evaluations. How can I do a gradient search? Do you mean to use 4 evaluations to estimate the gradient around the maximum of $f_t$ and then one evaluation to move in the direction of the gradient?. $\endgroup$ – Martin Drozdik Oct 26 '14 at 23:47
  • $\begingroup$ @MartinDrozdik, I've extended my answer to elaborate on these points. See the updated answer. $\endgroup$ – D.W. Oct 27 '14 at 17:12

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.