Suppose we have a set of variable $\mathbf{y} = \left(y_1, ..., y_n \right)$. Also consider the set of functions $g_i(y_i), 1 \leq i \leq n$. Note that $g_i()$ is dependent only on $y_i$.

Consider the program: $$ \sum_{\mathbf{y} \in C} \prod_{i=1}^n g_i(y_i) $$ Where $C$ is the feasible space for $\mathbf{y}$. The question is how to find this equation(or an approximation to it) efficiently?

Note that naively computing this is $m^n$ (assuming that each $y_i$ can take $m$ possible values, although some of these combinations might not lie in the feasible space $\mathcal{C}$). To make it more clear consider the following example: $$ \begin{cases} \sum_{(y_1, y_2) \in C} g_1(y_1) g_2(y_2) \\ \mathcal{C}: y_1 + y_2 \leq 1 \\ y_1 \in \lbrace 0, 1 \rbrace \\ y_2 \in \lbrace 0, 1 \rbrace \end{cases} $$

You can make the following assumptions (but not limited to):

  • $\mathcal{C}$ is be represented with a linear constraint: $$ A\mathbf{y} \leq b $$
  • $g_i(y_i)$ is bounded above with some number $M$.
  • g_i(y_i) is a convex/super-convex function
  • Or any other necessary assumption that can help to solve or approximate this.

Update1: It might be useful to know that $$ \ln \sum_{\mathbf{y} \in C} \frac{ \prod_{i=1}^n g_i(y_i) } { |C| } \leq \frac{1}{|C|} \sum_{\mathbf{y} \in C} \ln \prod_{i=1}^n g_i(y_i) = \frac{1}{|C|} \sum_{\mathbf{y} \in C} \sum_{i=1}^n \ln g_i(y_i) $$

  • $\begingroup$ In update 1: Can you check the validity of your first inequality again? Thanks. $\endgroup$ – Vivek Bagaria Apr 19 '14 at 9:34
  • $\begingroup$ Isn't it Jensen's inquality? You mean it should me like this? $$ \ln \sum_{\mathbf{y} \in C} \frac{ \prod_{i=1}^n g_i(y_i) } { |C|} \leq \frac{1}{|C|} \sum_{\mathbf{y} \in C} \ln \prod_{i=1}^n g_i(y_i) $$ $\endgroup$ – Daniel Apr 19 '14 at 21:06
  • $\begingroup$ Yes. The one in the above comment is correct. Please reflect the change in your question. $\endgroup$ – Vivek Bagaria Apr 20 '14 at 10:35
  • $\begingroup$ OK, tnx for letting me know. $\endgroup$ – Daniel Apr 20 '14 at 21:46

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.