12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Hans Aug 8 '18 at 20:00
  • $\begingroup$ Doesn't $P=x_1(x_1+x_2)$ give $A=1$, $B\in[0,1]$ and hence violate this inequality? $\endgroup$ – martin cripps Aug 9 '18 at 13:11
  • $\begingroup$ I guess all sets $I_i$ should be non-empty, yes? $\endgroup$ – Fedor Petrov Aug 17 '18 at 15:29
  • $\begingroup$ Which quantities are fixed in your optimization problem? $I_i$ ? $\endgroup$ – Taro NGUYEN Nov 7 '18 at 12:25
4
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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 :-) $\endgroup$ – fedja Nov 12 '18 at 13:43
  • $\begingroup$ 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. $\endgroup$ – fedja Nov 12 '18 at 19:32
  • $\begingroup$ @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) $\endgroup$ – fedja Nov 12 '18 at 21:02
  • $\begingroup$ @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. $\endgroup$ – fedja Nov 12 '18 at 22:41
  • $\begingroup$ The Taylor formula is just that $\log (X+dX)\approx\log X+\frac{dX}X-\frac 12\left(\frac{dX}{X}\right)^2$. $\endgroup$ – fedja Nov 12 '18 at 22:45

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.