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

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+\frac{\alpha}{2}\|y-x\|^2$$ or $$\left \geq \alpha\|y-x\|^2$$

for all $$x,y$$.

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

• I added two equivalent definition of $\alpha$-strongly convex functions. In the last two lines $1/x_i \geq 1/M$, $\nabla^2 f \geq 1/M$ and $1/M$ strongly convex. – Saeed Jan 17 '19 at 20:05
• you are right. It should be $1/M$ strongly convex. – MoonKnight Jan 17 '19 at 21:53

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