# Unconventional optimization over the space of combinations $C(N,n)$

I have an unconventional optimization problem. At least for me.

PROBLEM: $$\max_{c \in C(N,n)} F(c)$$ where:

• $C(N,n)$ is the space of the combinations of $n$ objects, out of $N$;
• $F: C(N,n) \rightarrow \mathbb{R}$;
• $F$ is computationally very heavy to evaluate;
• Exists $G: C(N,n) \rightarrow \mathbb{R}$ that (empirical observation):
• can be computed very quickly, for any combination $c \in C(N,n)$;
• it is positively related to high values of $F$, that is: $$\uparrow G(c) \mbox{ } \Longrightarrow \mbox{ } \uparrow F(c)$$
• does NOT fully describe $F$, that is: $F$ can be high even if $G$ is low: $$\downarrow G(c) \mbox{ } \nrightarrow \mbox{ } \downarrow F(c)$$
• I am mostly interested in the case $N=10^3$ and $n=3$, which leads to a space $C(1000,3)$ of more than 166 millions of possible combinations.

QUESTIONS:

1. Is there any way to approach such a problem? like Monte-Carlo Markov-Chain over the combinations space...
2. How could I use the information carried by $G$, to eventually reduce the dimension of the search space $C(N,n)$, or alternatively to drive the search?
3. I'm ok with a dimension reduction approach, but I'd like to be sure that there is still some chance that the entire space $C(N,n)$ would be explored.

Any comment/idea is more then welcomed. Thank you all.

• Did you have any luck with this? It would be nice to know how you solved it :) – Ferdinando Randisi Mar 13 '17 at 13:16

I don't think I followed all of the setup of the problem, but it doesn't seem to be useful to solve your question.

It seems that the best that you can do is:

1. minimising $G$ on your space with one of the usual minimisation algorithms ( I know that FIRE seems to be the best on continuous spaces, but it might be so even on discrete spaces)
2. Use the value of $G_{min}$ that you just found as a starting guess for the minimum of $F$, and then minimise $F$ with the same method as above.
3. See if you can invalidate your estimate by computing $F$ at some randomly generated points of your space too, and/or maybe near some local minimum of $G$. This might be helful if we assume that local minima of $G$ are more likely to correspond to local minima of $F$.

Needless to say, this approach is not rigorous at all and might fail spectacularly. I would try to extract some other information regarding the relationship between $F$ and $G$ (maybe searching the literature or asking some combinatorial mathematician), or investigating whether faster methods to compute $F$ might exist. Maybe someone wrote a library to compute any of those quantities faster, or maybe you can use a look-up table or something like that.

P.S. the detailed explanation currently present in the question almost scared me away and I'm sure that it's scaring away many other perspective repliers, so you might want to shorten it/delete it/stress that it's not needed to provide an answer. :)

• Deleted ;) Btw, I'm wondering whether it is possible to interpret it in a bayesian learning framework: learning the optimal combination $c$, as the most probable one of a posterior induced by the ranking induced by $F$, say $f(c)$, incorporating the a priori info of $G$ in a prior $g(c)$ induced by the ranking of the combinations induced by $G$. Then a MCMC would be guaranted to sample from the posterior. The optimal $c$ is the most visited one. But I need a likelihood $p(data|model)$ and I still don't understand what $data$ and $model$ could be in my case. Just thinking loudly I guess – Gabriele Pompa Feb 26 '17 at 20:47
• – Gabriele Pompa Feb 26 '17 at 22:35