6

$$f(x_1,\dots,x_n)=\sum\limits_{i=1}^nx_i\ln x_i-\left(\sum\limits_{i=1}^nx_i\right)\ln\left(\sum\limits_{i=1}^nx_i\right)\rightarrow R_{++}^n$$

How can I prove this is convex on $R_{++}^n$? I tried using the Hessian and couldn't prove it. There is a solution using the gradient and Jensen but very long and complicated.

Mr D
  • 63
  • 2
    Hello, welcome to Math Stack Exchange. To get the best answers at your level, learn most, and prevent people form giving hints, please include your attempt – what have you tried using Hessian? You can edit your post to include this. – wythagoras May 14 '15 at 09:36
  • For instance, why don't you share the Hessian with us. Others might see the crucian final step of proving positive semidefiniteness. – Michael Grant May 14 '15 at 12:25
  • Also asked here. http://math.stackexchange.com/questions/1281612/convexity-proof-of-a-function-including-ln-and-sums#comment2602514_1281612 – Michael Grant May 14 '15 at 19:07

1 Answers1

5

Taking the Hessian gives $$ \frac{\partial^2}{\partial x_j\partial x_k}f(x) =\overbrace{\begin{bmatrix} \frac1{x_1}&0&0&\cdots&0\\ 0&\frac1{x_2}&0&\cdots&0\\ 0&0&\frac1{x_3}&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&\frac1{x_n} \end{bmatrix}}^{\small\displaystyle\frac{\partial^2}{\partial x_j\partial x_k}\sum_{i=1}^nx_i\log(x_i)} -\overbrace{\frac1{\sum\limits_{i=1}^nx_i} \begin{bmatrix} 1&1&1&\cdots&1\\ 1&1&1&\cdots&1\\ 1&1&1&\cdots&1\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&1&1&\cdots&1 \end{bmatrix}\vphantom{\begin{bmatrix}\frac1{x_1}\\\frac1{x_1}\\\frac1{x_1}\\\vdots\\\frac1{x_1}\end{bmatrix}}}^{\small\displaystyle\frac{\partial^2}{\partial x_j\partial x_k}\left(\sum_{i=1}^nx_i\right)\log\left(\sum_{i=1}^nx_i\right)} $$ Thus, by Hölder's Inequality, $$ \begin{align} u^T\frac{\partial^2}{\partial x_j\partial x_k}f(x)u &=\sum_{i=1}^n\frac{u_i^2}{x_i} -\frac{\left(\sum\limits_{i=1}^nu_i\right)^2}{\sum\limits_{i=1}^nx_i}\\ &=\frac1{\sum\limits_{i=1}^nx_i}\left(\sum_{i=1}^nx_i\sum_{i=1}^n\frac{u_i^2}{x_i}-\left(\sum\limits_{i=1}^nu_i\right)^2\right)\\ &\ge0 \end{align} $$ The Hessian Matrix is positive semi-definite, so $f$ is convex.

robjohn
  • 345,667
  • how is this holders inequality? what's p and what's q? – Maverick Meerkat May 20 '20 at 13:17
  • hm - p=q=2 , but consider $x = (\sqrt x_1....), u = (\sqrt u_1....)$ – Maverick Meerkat May 20 '20 at 13:28
  • So it's Cauchy-Schwarz, which is a special case ($p=q=2$) of Hölder:$$\sum_{i=1}^nx_i\sum_{i=1}^n\frac{u_i^2}{x_i}\ge\left(\sum_{i=1}^nu_i\right)^2$$ – robjohn May 20 '20 at 14:29
  • @robjohn I've got this problem too and can you solve this by showing the first sum is sum on convex and the second one is affine change where $(\sum x_i)(\ln(\sum x_i)=z\ln(z)$ but i got stcuk here – convxy Nov 16 '20 at 08:14
  • @ronkurman: I am not sure what inequality you are trying to show. – robjohn Nov 16 '20 at 23:01
  • @robjohn, can you please explain the how did you expand $u^T \nabla f u$? I don't understand the first transition (with $\left( \sum{u_i} \right)^2$). I got the following: $$u^T \nabla f u=\sum_{i=1}^{n}{\frac{u_i^2}{x_i}}-\frac{1}{\sum_{i=1}^{n}{x_i}} \sum_{i \neq j}{u_i u_j}$$ – Dennis May 05 '21 at 08:57
  • @Dennis: the only difference between your result and mine is that yours does not include the terms with $i=j$ in the second sum. Why would those terms not be there? – robjohn May 05 '21 at 13:14
  • @robjohn, when I tried again to do the multiplication matix-wise I got your result. But as far as I know, expressing quadratic form as summation equals $$\sum_{j=1}^n\sum_{i=1}^nx_ia_{ij}x_j$$ If we want to split the sum into two sums, where one is for $i=j$ and the second one is for $i \neq j$, shouldn't it be as I suggested? – Dennis May 05 '21 at 13:30
  • I don't want to split the sum like that. – robjohn May 05 '21 at 13:35