<p>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$. </p>

<p>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?  </p>

<p>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}
$$</p>

<p>You can make the following assumptions (but not limited to): </p>

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

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

CC BY-SA 3.0
2014-04-19T09:34:16.703Z
In update 1: Can you check the validity of your first inequality again? Thanks.
Vivek Bagaria
CC BY-SA 3.0
2014-04-19T21:06:15.333Z
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
CC BY-SA 3.0
2014-04-20T10:35:34.827Z
Yes. The one in the above comment is correct. Please reflect the change in your question.
Vivek Bagaria
CC BY-SA 3.0
2014-04-20T21:46:44.383Z
OK, tnx for letting me know.
Daniel
<approximation-algorithms><approximation-hardness><dynamic-programming><approximation>
Calculating exact/approximate solution to a formula
Daniel
# Calculating exact/approximate solution to a formula

(Asked by: username_0 on 2014-04-19)

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

**Tags:** approximation-algorithms, approximation-hardness, dynamic-programming, approximation
> **Comments:**
> **username_1**: In update 1: Can you check the validity of your first inequality again? Thanks.  
> **username_0**: 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)  $$  
> **username_1**: Yes. The one in the above comment is correct. Please reflect the change in your question.  
> **username_0**: OK, tnx for letting me know.  

---

## 0 answers

