# Maximize product of sums

Let $$n,k\geq 2$$ be positive integers. For each $$1\leq i\leq n$$, let $$I_i$$ be a nonempty subset of $$\{1,2,\dots,k\}$$. Let $$P_i=\sum_{j\in I_i}x_j$$, and let $$P=P_1\cdot P_2\cdot\dots\cdot P_n$$. (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\cdot P_3\cdot\dots\cdot P_n$$, subject to the same constraints.

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

Equality can be obtained, e.g., for any value of $$n$$, when $$P_1=x_1$$ and $$P_i=x_2$$ for $$i=2,\dots,n$$ (so $$A=1/n$$ and $$B=0$$).

Another example: $$n=2$$, $$P_1=x_1$$ and $$P_2=x_1+x_2$$. Then $$A=1$$ and $$B$$ can be anything in $$[0,1]$$, so the inequality always holds.

• – Hans
Aug 8, 2018 at 20:00
• Doesn't $P=x_1(x_1+x_2)$ give $A=1$, $B\in[0,1]$ and hence violate this inequality? Aug 9, 2018 at 13:11
• I guess all sets $I_i$ should be non-empty, yes? Aug 17, 2018 at 15:29
• Which quantities are fixed in your optimization problem? $I_i$ ? Nov 7, 2018 at 12:25

Yes, that is true. Here is a sketch of the argument. It needs some polishing in places but, I hope, it makes clear what is going on here.

We will show that if $$P_1,P_2,\dots, P_m$$ are of the above form and maximize $$F=\sum_k a_k\log P_k$$ (so they are viewed as functions of $$a=(a_1,\dots,a_m)\in (0,+\infty)^m$$), then $$\frac{\partial P_1}{\partial a_1}\ge (1-P_1)(\sum_k a_k)^{-1}$$ (to be precise, we are talking about the right derivative here). The desired result can be obtained from here by an appropriate integration.

Since everything is homogeneous in $$a$$, we can assume without loss of generality that $$\sum_k a_k=1$$. Let $$da_1$$ be a small (infinitesimal) positive increment of $$a_1$$. Let $$dP_i$$ be some admissible increments of $$P_i$$ ($$P_i$$ are running over some convex polyhedron, so locally the set of admissible increments is an infinitesimal cone in general). Then we have the following increment of $$F$$ (up to third order terms): $$dF-da_1\log P_1\approx \sum_k a_k\frac {dP_k}{P_k}+ da_1\frac {dP_1}{P_1}-\frac 12\sum_k a_k\left(\frac {dP_k}{P_k}\right)^2\,.$$ The true increment $$dP$$ should essentially maximize the RHS. Notice that if you consider the true maximizer $$dP=(dP_1,\dots,dP_m)$$, then you can compare it with $$tdP$$ for $$t$$ close to $$1$$ and obtain that the linear in $$dP$$ part of the RHS should be twice as large as the maximum itself (all I'm saying here is that $$ut-\frac 12vt^2$$ attains its maximal value $$\frac {u^2}{2v}$$ at $$t=u/v$$ where the linear part $$ut$$ equals $$\frac{u^2}{v}$$). Since we must have $$\sum_k a_k\frac {dP_k}{P_k}\le 0$$ because $$P$$ is the point of maximum and the admissible domain is convex, we conclude that at the true $$dP$$, we must have $$da_1dP_1$$ at least as large as twice the maximum of the RHS.

Now it remains to estimate that maximum using some particular perturbation. The simplest one will be $$x_i\mapsto (1+\tau)x_i$$ for $$x_i$$ participating in $$P_1$$ and $$x_j\mapsto \left(1-\tau\frac{P_1}{1-P_1}\right)x_j$$ for $$x_j$$ not participating in $$P_1$$. Note that this perturbation is admissible for both small positive and small negative $$\tau$$ unless one of the variables is $$1$$, which means that all $$P_k=1$$, in which case there is nothing to prove. Thus for $$dP$$ corresponding to this perturbation, we have $$\sum_k a_k\frac {dP_k}{P_k}=0\,.$$ We also have $$\frac{dP_1}{P_1}=\tau$$ and $$-\frac{P_1}{1-P_1}\tau\le\frac{dP_k}{P_k}\le\tau$$ for all $$k$$. Recalling that for a mean zero real function $$f$$ on $$[0,1]$$ squeezed between $$-u$$ and $$v$$, we have $$\int_0^1 f^2\le uv$$, we conclude that for this perturbation $$\frac 12\sum_k a_k\left(\frac{dP_k}{P_k}\right)^2\le \frac 12\frac{P_1}{1-P_1}\tau^2$$ whence we can take $$\tau=da_1\frac{1-P_1}{P_1}$$ and see that the maximum of the RHS is at least $$\frac 12 (da_1)^2\frac {1-P_1}{P_1}$$. Since $$da_1\frac{dP_1}{P_1}$$ for the true maximizing increment should be at least twice that large, we get $$dP_1\ge (1-P_1)da_1$$, as desired.

• @nan The formula is just the second order Taylor formula, isn't it? If you want total rigor, you should care a bit about the error term, which I'm just ignoring, and spend some time explaining why $P$ is a locally Lipschitz function of $a$. As to "integration", we have the inequality $\frac{P'}{1-P}\ge \frac 1{n-1+a}$. What do you get when integrating this from $0$ to $1$? On the other hand I admit that it is rather sketchy, so feel free to ask more questions and I'll try to answer :-) Nov 12, 2018 at 13:43
• I'm not sure what we get when integrating $\frac{P'}{1-P}$. Erm... Then, I'm afraid, it's going to be a longer story than I thought it would. You get the increment of $-\log(1-P)$, so the result is $-\log(1-P(1))+\log(1-P(0))\ge\log\frac{n}{n-1}$, i.e., $1-P(1)\le \frac{n-1}n(1-P(0))$, which is equivalent to your inequality. Also we do not keep the sum of $a_k$ fixed in the argument. We just assume that it is $1$ at the original moment not to drag it along. Nov 12, 2018 at 19:32
• @nan We have the maximal value at $P$ and the $\tau$-perturbation can be used with both positive and negative $\tau$, so the first derivative has to be $0$. The inequality follows from $da_1\frac{dP_1}{P_1}\ge 2\frac 12(da_1)^2\frac{1-P_1}{P_1}$ (see the last two sentences in the argument) Nov 12, 2018 at 21:02
• @nan No, $P$ refers to $(P_1,\dots,P_m)$. Sorry for the change in the notation. Yes, by the "linear part" I mean this sum. The comparison is just the observation that the point $P+tdP=(P_1+tdP_1,\dots,P_m+tdP_m)$ shouldn't give a larger value to the RHS than $P+dP$, i.e., that when you move from $P$ in the direction of $dP$, you should reach the vertex of the parabola and stop there. Literally it is not true: you can guarantee only that the value of the RHS should not deviate from that maximum by more than $O((da_1)^3)$ (the cubic error), but that is enough. Nov 12, 2018 at 22:41
• The Taylor formula is just that $\log (X+dX)\approx\log X+\frac{dX}X-\frac 12\left(\frac{dX}{X}\right)^2$. Nov 12, 2018 at 22:45