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, 2015 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, 2015 at 12:25
  • $\begingroup$ Also asked here. math.stackexchange.com/questions/1281612/… $\endgroup$ May 14, 2015 at 19:07

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .