# Calculating exact/approximate solution to a formula

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)$$

• In update 1: Can you check the validity of your first inequality again? Thanks. – Vivek Bagaria Apr 19 '14 at 9:34
• 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)$$ – Daniel Apr 19 '14 at 21:06
• Yes. The one in the above comment is correct. Please reflect the change in your question. – Vivek Bagaria Apr 20 '14 at 10:35
• OK, tnx for letting me know. – Daniel Apr 20 '14 at 21:46