How to discuss convex/concave behavior of sum of product terms

Question

If we have function in constraint as $\prod_{i=1}^Nx_i$, $x_i\in[0,1]$, we can take logarithm. Then it can be written as a summation and we can discussion convex/concave behavior of the constraint.

However, I have a constraint as sum of product terms such as $\prod_{i=n_1}^{N_1} x_i+\prod_{i=n_2}^{N_2} x_i+\cdots+\prod_{i=n_M}^{N_M} x_i$ which can be written as in general $\sum_m\prod_{i=n_m}^{N_m} x_i$. In this case, I cannot take the logarithm because of $\sum_m$.

Can someone please guide me what kind of approach I should use?

Answer 1

Each product has an indefinite Hessian and so is neither concave no convex. The sum will be neither concave nor convex. (The product and sum are linear in each individual $x_i$ though.)

If your constraint is of the form $g(x)\leq 0$ and you want a convex constraint set, then it is enough that $g$ is quasiconvex. If your constraint is of the form $g(x)\geq 0$, then it is enough that $g$ is quasiconcave. In your case, each product is quasiconcave so long as $x_i\geq 0$ for all $i$ (I am not sure about the sum).

To show each individual product is quasiconcave, note that $$\prod_{i=1}^Nx_i=\exp\sum_{i=1}^N \ln x_i.$$ The sum is concave because each $\ln x_i$ is concave. It follows that the product is quasiconcave because it is a monotonic transformation of a concave function.

Answer 2

The function, as you gave it, is neither convex nor concave. However, $\leq$ inequality constraints with this function can be transformed to convex constraints given that you know that $x_i > 0$ (note that $x_i$ cannot be zero for this transformation to work).

Assume that you have the constraint (in variables $x,t$): $$ \prod_{i=n_1}^{N_1} x_i+\prod_{i=n_2}^{N_2} x_i+\cdots+\prod_{i=n_M}^{N_M} x_i \leq t $$ By adding auxiliary variables $t_1, \dots, t_M$ you can transform it to the following equivalent system of inequalities: $$ \begin{aligned} \sum_{j=1}^M t_j &\leq t \\ \prod_{i=n_j}^{N_j} x_i &\leq t_j, \quad j = 1, \dots, M \end{aligned} $$ You can make another transformation by making a change of variables $x_i = \exp(y_i)$, which is possible since $x_i > 0$, and get the following system: $$ \begin{aligned} \sum_{j=1}^M t_j &\leq t \\ \exp\left(\sum_{i=n_j}^{N_j} y_i\right) &\leq t_j, \quad j = 1, \dots, M \end{aligned} $$ Now, you can take the logarithm on both sides in the $\exp$ constraints, and get the following convex inequalities: $$ \begin{aligned} \sum_{j=1}^M t_j &\leq t \\ \sum_{i=n_j}^{N_j} y_i - \ln(t_j) &\leq 0, \quad j = 1, \dots, M \end{aligned} $$