6
$\begingroup$

$$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.

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – wythagoras
    May 14 '15 at 9:36
  • $\begingroup$ For instance, why don't you share the Hessian with us. Others might see the crucian final step of proving positive semidefiniteness. $\endgroup$ May 14 '15 at 12:25
  • $\begingroup$ Also asked here. math.stackexchange.com/questions/1281612/… $\endgroup$ May 14 '15 at 19:07
5
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ how is this holders inequality? what's p and what's q? $\endgroup$ May 20 '20 at 13:17
  • $\begingroup$ hm - p=q=2 , but consider $x = (\sqrt x_1....), u = (\sqrt u_1....)$ $\endgroup$ May 20 '20 at 13:28
  • $\begingroup$ 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$$ $\endgroup$
    – robjohn
    May 20 '20 at 14:29
  • $\begingroup$ @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 $\endgroup$
    – convxy
    Nov 16 '20 at 8:14
  • $\begingroup$ @ronkurman: I am not sure what inequality you are trying to show. $\endgroup$
    – robjohn
    Nov 16 '20 at 23:01

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.