Progressive discrete multifunction optimization

Question

I have a set of functions $F$.

The functions effectively take a set $S$ that is always a subset of a global set of all possible values $G$, where $|G|>1000$. (alternatively, they could take a $|G|$tuple of booleans, if that's easier). The functions return a real result. I want to minimize over $S$ the average value of these functions if all of them are given the same parameter $S$.

$$\min_{S\,\subset\, G}\left(\sum_{f\,\in\,F}f(S)\right)$$

Now here's the catch:

The functions take a fantastic amount of time to run (say, a few hours), and I intend to have a huge collection of such functions (say $|F|>1000$ to start). Every so often, a new function will be created and be added to the set. There is no bound to the size of $F$.

Obviously, I can't just use closed form optimization (I'll be dead before it'll finish), so I'm interested in an algorithm that can find an approximate solution and progressively refine it over time as new function results and new functions come in (and hopefully converge faster than brute force).

We can have a better-than-brute-force because the functions $F$ behave similarly. Namely, $f(S) \approx f(T)$ when $S\approx T$ and $k_aF_a(S) \approx k_bF_b(S)$ for all $S$ ($k$ is constant). There are, of course, many exceptions.

---

Now, I am new in the CS field so I have no idea what things are called. AFAIK I haven't learned how to do this in Into to ML, but it has the feel of a Genetic Algorithm problem. If anyone could point me to a technique or a name, I'd be very happy.

Answer 1

There are two techniques that I suspect might be worth trying in this context:

1. Simulated annealing. Simulated annealing is a heuristic for optimization that works well when the objective function varies smoothly as a function of its parameters, based loosely upon some structure in the parameter space. You can find a good discussion of how to use simulated annealing, in Steven Skiena's The Algorithm Design Manual.

   In your context, you'll need some operations that tweak $S$ by a little bit. Basically, you start from a specific choice of $S$ and then make small modifications, seeing which modifications increase the value of $\Phi(S)$, where $\Phi$ is the objective function. When you find a $S'$ that increases the objective function, you keep that one and start modifying it. This is basically hillclimbing. Simulated annealing improves on that by doing random jumps to get out of local optima.

   In your context, the objective function is

   $$\Phi(S) = \sum_{f \in F} f(S).$$

   There are many candidates for how to tweak $S$. You could try adding a random element of $G$ to $S$ (or adding $k$ randomly chosen elements of $G$ to $S$) as one operation; removing a random element (or removing $k$ elements) as another operation; and so on. Typically you take advantage of your domain knowledge to select a set of operations that might potentially make sense as "sensible" ways to vary $S$ by a little bit. Then, you let the simulated annealing algorithm take over from there.

   The useful thing about your context is that when you've found an optimal value of $S$ for functions $f_1,\dots,f_n$ (i.e., for objective function $\Psi(S) = f_1(S) + \dots + f_n(S)$), and then you later get an additional function $f_{n+1}$ to add to the set, now $S$ is a reasonable starting point to start the optimization process for $f_1,\dots,f_{n+1}$ (i.e., for objective function $\Psi'(S) = f_1(S) + \dots + f_{n+1}(S)$). In particular, given your structure, we might expect that the optimum for $\Psi'$ might be "close" or "similar" to an optimum for $\Psi$, so the optimum for $\Psi$ is a good place to start the hill-climbing/simulated annealing for $\Psi'$.

   To extend on that idea, you might also try remembering multiple values of $S$ from the previous round: say, sets $S_1,\dots,S_m$ that give the $m$ largest values of $\Phi(\cdot)$ that you encountered during your optimization with the objective function $\Psi$. Now, when you add another function in the next round and want to find an optimum for $\Psi'$, you could try starting from each of $S_1,\dots,S_m$ as candidate starting values for the hill-climbing / simulated annealing. This might be effective in practice -- you'd have to try it out to see.

2. Memoization. Since computing $f(S)$ is very expensive, you might use memoization to ensure you never compute it more than once. In particular, you might keep a hashtable with mappings $(f,S) \mapsto f(S)$, so that you never need to compute $f(S)$ for any particular combination of a function $f$ and a set $S$ more than once. This might help you out.

   Also, when starting the optimization process for the objective function $\Psi'$, you might try computing $\Psi'(S)$ for each $S$ such that you computed $\Psi(S)$ in the previous round. Since $\Psi'(S) = \Psi(S) + f_{n+1}(S)$, the memoization will ensure that (if you computed $\Psi(S)$ previously) $\Psi'(S)$ can be computed relatively efficiently: it only requires evaluating $f_{n+1}(S)$, since $f_1(S),\dots,f_n(S)$ will already be in the memoization table.

Finally, if you know anything more about the structure of the $f$'s, you might try looking into branch-and-bound style techniques.

Again, these are just ideas. You are in the space of heuristics, so there are no guarantees. You'll have to try out these techniques in your particular application domain to see how well they work. In practice often you may need to try out different parameter settings and make some application-specific tweaks to these general techniques, so be prepared to experiment and try out different stuff.