# Find subset of data that optimizes a given function [closed]

I have a dataset composed of $N$ iid observations ($x_1, x_2, ..., x_N$) and a function $f(x_i,\, i{=}1,..M$) that takes as input a subset of fixed length $M$ of unique elements from the original dataset (where $M{<}N$ and it is known). This function is basically a comparision of two kernel density estimators (one is always fixed, the other is generated with the elements in $M$), where the exact same value is returned for the same input values. I need to find the subset $M^*$ that maximizes $f(x_i)$.

I can think of a few strategies:

1. Process all the possible subsets of length $M$ that can be created from my $N$ observations, evaluate all of them in $f(x_i)$, and keep the one that gives the maximum value. This is prohibitively time-consuming for even small numbers of $N$ and $M$.
2. Process only a random subset out of all the possible combinations defined above, keep the one that gives the maximum likelihood value. This is the easiest method, but I'm not sure how large the random subset of combinations should be to get a somewhat meaningful (trustworthy?) answer.
3. Use some optimization/MCMC algorithm? This is the option that seems more reasonable, but I'm not sure which one is best suited for this task.

Which method would you recommend?

• What can you tell us about the function f? Do you have a closed-form representation of f? For any given input combination, will it produce a deterministic, o.e., perfectly repeatable, answer? Commented Jun 11, 2018 at 14:53
• As @Mark indicates, everything depends on $f$. Until you can tell us something about it, there's little one could add except to refer you to a textbook on combinatorial optimization.
– whuber
Commented Jun 11, 2018 at 15:27
• I've added what Mark asked about $f$. Commented Jun 11, 2018 at 16:09
• I don't understand the question because the notation is vague: what exactly does "$f(x_i)$" refer to? A value of $f$ at a specified observation? The set of values of $f$ at all observations? The function $f$ itself, where $x_i$ is intended to refer to an arbitrary element of its domain? If $f$ is a KDE, then apparently your notation implies "$f(x_i)$" is function, rather than a number, so what does it mean to maximize it?
– whuber
Commented Jun 11, 2018 at 20:35
• $f(x_i)$ means the function $f$ evaluated using $M$ elements from my dataset. It is a shorter version of the more explicit form shown above: $f(x_i, i=1,..,M)$. Not sure how else to put it. $f$ is not a KDE, but a comparision of two KDEs (one of which is generated using the $x_i, i=1,..,M$; the other one is fixed), hence it is a real number. Commented Jun 11, 2018 at 21:09