Given is an expression of the form $P=P_1\times P_2\times\dots\times P_n$, where each $P_i$ is a sum of some distinct elements from $\{x_1,x_2,\dots,x_k\}$. (For example, $P=x_1(x_1+x_2)(x_1+x_3)$.) We want to maximize this expression subject to the constraints $x_i\geq 0$ for all $i$, and $\sum_{i=1}^k x_i=1$. Let $A$ be the value of $P_1$ at the maximum. Let $B$ be the value of $P_1$ at the maximum if we instead maximize the expression $P'=P_2\times P_3\times\dots\times P_n$, subject to the same constraints.

Is it true that $A\geq \frac{n-1}{n}B+\frac{1}{n}$?

  • $\begingroup$ not necessarily. Take $q_1 = 1, q_j = 0$ for $j=2,...,n$ and $p_2=1, p_j = 0$ for $j \neq 2$, and $S_1 = \{ 1 \} $ $\endgroup$ – Francisco Jul 30 '18 at 10:56
  • $\begingroup$ @Francisco Your choice of $p_i$'s doesn't maximize the given product - it gives value $0$, whereas if we take $p_1=1$ we would get value $1$. $\endgroup$ – nan Jul 30 '18 at 11:52
  • $\begingroup$ oh.. I see... then $q_j$ must be zero for any $j \in S_1$. That makes it easy, no? just need to prove that $\sum_{j \in S_1}p_j \geq 1/n$ for $j \in S_1$. Which does not seems so difficult to prove. $\endgroup$ – Francisco Jul 30 '18 at 12:01
  • $\begingroup$ @Francisco No, it's not necessary that $q_j=0$ for $j\in S_1$. $\endgroup$ – nan Jul 30 '18 at 12:09
  • $\begingroup$ what do you mean by "sum of distinct elements"? Each $x_i$ is in at most one $P_j$? $\endgroup$ – LinAlg Aug 2 '18 at 16:52

For what it's worth, I tried some Lagrange multipliers: Let $X=(x_1,...,x_k)$ and $Y_i\in \{0,1\}^k$ be such that $P_i=Y_i\cdot X$. Putting $$L(X)=\sum_i \ln(Y_i\cdot X)-\lambda(\textbf 1\cdot X-1)$$ gives for each $j$, either $x_j=0$ or $(\sum_i \frac1 {P_i}Y_i)_j=\lambda=n$. A couple observations:

  1. $P_i=Y_i\cdot X$, so the above can be rewritten as $(\sum_i X+Z_i)_j=n$ where $Z_i\cdot X=0$.
  2. $(\sum_i \frac1 {P_i}Y_i)\cdot X=n$

Hopefully this leads to something useful...

  • $\begingroup$ Let $\displaystyle P = \prod_{i=1}^n\sum_{j=1}^k y_{ij}x_j$ and $\displaystyle Q = \prod_{i=2}^n\sum_{j=1}^k y_{ij}x_j$, where $y_{ij} \in \{0, 1\}$ are given constants and $x_j$ are the variables which we can optimize. Not sure if this elementary result will help to kick start of the problem: By the definition of the maximum, $\displaystyle \frac {P^*} {A} \leq Q^*$ and $\displaystyle BQ^* \leq P^*$ which implies $\displaystyle A \geq \frac {P^*} {Q^*} \geq B$ $\endgroup$ – BGM Aug 10 '18 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.