I have the following optimization problem:

I have a (random and very noisy) objective function $f(A, P)$, where $A$ is a vector of "observable" parameters of the input and $P$ is the parameters that I can control.

I'd like to find $P(A)$ for every $A$, such that $f(A, P(A))$ is maximized.

For example, I'm writing a game; I know a bunch of facts about every user (their age, gender, level, various in-game statistics), and I can control the difficulty of monsters they face and the scarcity of resources they find on their journey. The objective function $f$ is, for example, how much money they spend.

I think a reasonable approach to this would be to:

1) cluster the users by $A$ in some way, such that within a single cluster, the shape of $f$ with respect to $P$ is approximately the same;

2) run some guided optimization/experimentation algorithm within every cluster, taking advantage of the fact that a single user's data point gives me information about the whole cluster, but avoiding meaningless comparisons between dissimilar users.

The problem here is that I cannot use a conventional clustering method "as is" to cluster by A, because I don't know which dimensions of $A$ are important - and perhaps some dimensions are important only in some regions of the $A$ space. So it's not clear how to formulate the distance function $D(A,A)$.

Is this indeed a reasonable approach? Does it have a name? What's some existing research in this area?

  • $\begingroup$ Why not optimize $f$ directly instead of clustering $A$ first? $\endgroup$ – Victor May Jan 20 '14 at 19:34
  • $\begingroup$ The reason for that is explained in #2 : clustering, or some measure of similarity between points of A, would mean that I could optimize P within a whole cluster (at least I could get a very good approximation to the optimum), rather than at each individual point. $\endgroup$ – jkff Jan 22 '14 at 16:37
  • $\begingroup$ So it's an of issue of runtime optimization? $\endgroup$ – Victor May Jan 22 '14 at 16:54
  • $\begingroup$ Not necessarily runtime, but every measurement has a high cost (and still higher cost if I pick a bad value of P), so I'd like to minimize the number of measurements - naturally, reusing measurements between similar species of A would help greatly. $\endgroup$ – jkff Jan 23 '14 at 16:13
  • $\begingroup$ What do you mean by a measurement? Evaluating $f$ for a fixed value of A and different values of P? $\endgroup$ – Victor May Jan 24 '14 at 17:01

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.