How to show negative entropy function $f(x)=\sum_{i=1}^nx_i\log(x_i)$ is strongly convex?

Question

Let $x \in \mathbb{R}^n$ belongs to $S$ where $$ S= \{x \in \mathbb{R}^n \mid x \succ 0, \|x\|_{\infty} \leq M\} $$ where $\succ$ is the generalized inequality which means all elements of $x$ are positive and $\log$ is natural logarithm. Use the following theorem to show that $f(x)=\sum_{i=1}^nx_i\log(x_i)$ is $\frac{1}{M}$-strongly convex over $S$.

Theorem: f is $\alpha$-strongly convex if and only if $\nabla^2f(x) \succeq \alpha I$ for all $x$.

Definition:$f$ is $\alpha$-strongly convex if there exist a constant $\alpha$ such that $$ f(y) \geq f(x)+\left<f '(x),y-x\right>+\frac{\alpha}{2}\|y-x\|^2$$ or $$ \left<f'(y)-f '(x),y-x\right> \geq \alpha\|y-x\|^2$$

for all $x,y$.

Answer 1

First of all, It seems to me that in the definition of $\alpha$-strongly convex function should have a coefficient of $\alpha$ but not $\frac{\alpha}{2}$.

Now here goes the proof $$ \begin{aligned} \frac{\partial^2 f}{\partial x_i \partial_j} & = &\frac{\partial}{\partial x_j}[\log(x_i) + 1] \\ & = & \left \{ \begin{aligned} 1/x_i \quad \text{if } i =j \\ 0 \quad \text{if } i \neq j \end{aligned} \right . \end{aligned} $$

Since $0<x_i\leq M$, then $1/x_i \geq 1/M$

Thus $\nabla^2 f \geq \frac{1}{M} I$, which is the theorem for $1/M$-strongly convex function.

Answer 2

Perhaps you are interested the fact that the negative entropy is (1/M)-strongly convex w.r.t. $\left\|\cdot\right\|_{1}$ (and not only w.r.t. $\left\|\cdot\right\|_{2}$). Here is the proof:

W.l.o.g. M=1. Let be $f^{*}$ the convex conjugate of $f$: \begin{equation*} f^{*}(y)=\max_{x\in S}\left<y,x\right>-f(x). \end{equation*} It holds: \begin{equation*} \partial_{y_{i}} f^{*}(y)=\exp(y_{i}-1)\quad \text{if}\quad\sum_{j}\exp(y_{j}-1)\leq 1, \end{equation*} and otherwise: \begin{equation*} \partial_{y_{i}} f^{*}(y)=\frac{\exp(y_{i}-1)}{\sum_{j}\exp(y_{j}-1)}. \end{equation*} Thus $\left\|\nabla f^{*}(y)\right\|_{\infty}\leq 1$ and consequently $f^{*}$ is 1-smooth w.r.t. $\left\|\cdot\right\|_{\infty}$. By e.g. Theorem 3 in https://arxiv.org/pdf/0910.0610.pdf it follows that $f$ is $1$-strongly convex (on $S$) w.r.t. $\left\|\cdot\right\|_{1}$.