1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Saeed Jan 17 '19 at 20:05
  • $\begingroup$ you are right. It should be $1/M$ strongly convex. $\endgroup$ – MoonKnight Jan 17 '19 at 21:53
1
$\begingroup$

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

$\endgroup$

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.