# Convexity of $f(\boldsymbol{p}) = \sum_i p_i \log \sum_j p_j \frac{4 a_i a_j}{(a_i + a_j)^2}$

## Question

Given that $$\boldsymbol{a} > 0$$, how to prove

$$f(\boldsymbol{p}) = \sum_i p_i \log \sum_j p_j \frac{4 a_i a_j}{(a_i + a_j)^2}$$

is a convex function of probability distribution $$\boldsymbol{p}$$? Is it possible to generalize from the convexity of the negative entropy $$p \log p$$?

## Attempts

• Midpoint convex + continuous => convex: to prove $$f\left(\frac{\boldsymbol{p} + \boldsymbol{q}}{2}\right) \le \frac{f(\boldsymbol{p}) + f(\boldsymbol{q})}{2}$$ It reduces to $$\prod_i \left(\sum_j \frac{p_j+q_j}{2} \frac{4 a_i a_j}{(a_i + a_j)^2}\right)^{p_i+q_i} \le \prod_i \left(\sum_j p_j \frac{4 a_i a_j}{(a_i + a_j)^2}\right)^{p_i} \left(\sum_j q_j \frac{4 a_i a_j}{(a_i + a_j)^2}\right)^{q_i}$$ and the original GM-HM trick for $$p \log p$$ does not work. It looks very similar to Holder's inequality but I failed to gain more insights...

• Hessian: the $$(m,n)$$ entry of Hessian is $$\frac{b_{m,n}}{\sum_j p_j b_{m,j}} + \frac{b_{n,m}}{\sum_j p_j b_{n,j}} - \sum_i p_i \frac{b_{i,m} b_{i,n}}{(\sum_j p_j b_{i,j})^2}$$ where $$b_{i,j} = \frac{4 a_i a_j}{(a_i + a_j)^2}$$. Simulation suggests the Hessian is generally positive semidefinite, but finding a proof seems nontrivial.

Thank you very much for the attention.

• have you tried checking if $\log\left(\sum_j p_j \dfrac{a_ia_j}{(a_i+a_j)^2}\right)$ is convex ? If it is, then non-negative weighted sum of convex functions are convex. You can ignore the $4$ btw. Commented Jun 14, 2023 at 12:52
• @dezdichado I believe it is concave since it is a composition of affine and nondecreasing concave functions. Commented Jun 14, 2023 at 14:06
• @SnowzTail See this question where I show an interesting result math.stackexchange.com/questions/4677765/… using Karamata's inequality and a method due to the excellent Vasile Cirtoaje . Perhaps it could inspire you .Good luck in your effort .Ps: look at Callebaut inequality on AOPS inspiring too . Commented Jun 14, 2023 at 15:27

I also want to add some context for Hessian.

The Gram matrix $$\boldsymbol{G}$$ contains all possible inner products of a set of vectors $$\{\boldsymbol{v}\}$$, and its $$(m,n)$$ entry is $$g_{m,n} = \boldsymbol{v}_m^\mathsf{T} \boldsymbol{v}_n = \sum_i [\boldsymbol{v}_m]_i [\boldsymbol{v}_n]_i$$.

According to Wikipedia,

The Gram matrix is positive semidefinite, and every positive semidefinite matrix is the Gramian matrix for some set of vectors.

If we can write the Hessian as a Gram matrix, then it is positive semidefinite.

The $$(m,n)$$ entry of the Hessian is \begin{align} [D^2 f]_{m,n} & = \frac{b_{m,n}}{\sum_j p_j b_{m,j}} + \frac{b_{n,m}}{\sum_j p_j b_{n,j}} - \sum_i p_i \frac{b_{i,m} b_{i,n}}{(\sum_j p_j b_{i,j})^2}\\ & = \sum_i p_i \frac{[\boldsymbol{c}_{m,n}]_i}{\left(\sum_j p_j \frac{4 a_m a_j}{(a_m + a_j)^2}\right) \left(\sum_j p_j \frac{4 a_n a_j}{(a_n + a_j)^2}\right) \left(\sum_j p_j \frac{4 a_i a_j}{(a_i + a_j)^2}\right)^2}\\ & \stackrel{?}{=} \sum_i [\boldsymbol{v}_m]_i [\boldsymbol{v}_n]_i, \end{align} where $$[\boldsymbol{c}_{m,n}]_i={\frac{4 a_m a_n}{(a_m + a_n)^2} \left(\sum_j p_j \frac{4 a_m a_j}{(a_m + a_j)^2} + \sum_j p_j \frac{4 a_n a_j}{(a_n + a_j)^2}\right) \left(\sum_j p_j \frac{4 a_i a_j}{(a_i + a_j)^2}\right)^2 - \left(\sum_j p_j \frac{4 a_m a_j}{(a_m + a_j)^2}\right) \left(\sum_j p_j \frac{4 a_n a_j}{(a_n + a_j)^2}\right) \frac{4 a_i a_m}{(a_i + a_m)^2} \frac{4 a_i a_n}{(a_i + a_n)^2}}$$

If we can write $$[\boldsymbol{c}_{m,n}]_i = [\boldsymbol{c}_{m}]_i [\boldsymbol{c}_{n}]_i$$ then the Hessian is Grammian and the proof can be completed.

Please correct me If I am wrong. For midpoint convex:

Starting from the binary input $$L=2$$ case, where the inequality reduces to

$$\left(\frac{p_1+q_1}{2}+\frac{p_2+q_2}{2}b\right)^{p_1+q_1} \cdot \left(\frac{p_1+q_1}{2}b+\frac{p_2+q_2}{2}\right)^{p_2+q_2} \le (p_1+p_2b)^{p_1} \cdot (q_1+q_2b)^{q_1} \cdot (p_1b+p_2)^{p_2} \cdot (q_1b+q_2)^{q_2},$$

where $$b=\frac{4a_1a_2}{(a_1+a_2)^2}$$. Note both sides are symmetrical and it is sufficient to prove the inequality for the first half.

Let $$p_1 = p$$, $$q_1 = q$$ and the first half becomes $$\left(\frac{p+q+(1-p)b+(1-q)b}{2}\right)^{p+q} \le \Bigl(p+(1-p)b\Bigr)^{p} \Bigl(q+(1-q)b\Bigr)^{q},$$ that is, $$\left(\frac{(1-b)(p+q)}{2}-b\right)^{p+q} \le \Bigl((1-b)p+b\Bigr)^p \Bigl((1-b)q+b\Bigr)^q.$$ Since $$0 < b \le 1$$, we have $$\text{LHS} \le \left(\frac{(1-b)(p+q)}{2}\right)^{p+q},\quad \Bigl((1-b)p\Bigr)^p \Bigl((1-b)q\Bigr)^q \le \text{RHS}.$$ On the other hand, using $$\left(\frac{p+q}{2}\right)^{p+q} \le p^p q^q$$ [proof] gives $$(1-b)^{p+q} \left(\frac{p+q}{2}\right)^{p+q} \le (1-b)^{p+q} p^p q^q,$$ that is, $$\left(\frac{(1-b)(p+q)}{2}\right)^{p+q} \le \Bigl((1-b)p\Bigr)^p \Bigl((1-b)q\Bigr)^q,$$ which proves $$\text{LHS} \le \text{RHS}$$ and completes the proof for $$L=2$$.

For $$L>2$$, the proof extends by starting from $$L=2$$ and iteratively splitting one input probability to two.

• When I briefly tried this, the inductive is the only non-trivial part. Commented Jun 17, 2023 at 18:29