# Show $\max_{r\equiv (r_1,…, r_M) \in \mathbb{R}^M} \sum_{k=1}^M \mu_k r_k - \log\Big(\sum_{k=1}^M \exp(r_k) \Big)= \sum_{k=1}^M \mu_k \log(\mu_k)$

I am struggling with the following maximisation problem. Take a vector $\mu\equiv (\mu_1,..., \mu_M)\in \mathbb{R}^M$ such that $\mu_k\in [0,1]$ $\forall k=1,...,M$ and $\sum_{k=1}^M \mu_k=1$.

I want to show that

$$\max_{r\equiv (r_1,..., r_M) \in \mathbb{R}^M} \sum_{k=1}^M \mu_k r_k - \log\Big(\sum_{k=1}^M \exp(r_k) \Big)= \sum_{k=1}^M \mu_k \log(\mu_k)$$

I write first order conditions $$\begin{cases} \mu_1-\frac{\exp(r_1)}{\sum_{k=1}^M \exp(r_k)}=0\\ ...\\ \mu_M-\frac{\exp(r_M)}{\sum_{k=1}^M \exp(r_k)}=0\\ \end{cases}$$ $$\Updownarrow$$ $$\begin{cases} r_1=\log(\mu_1)+\log(\sum_{k=1}^M \exp(r_k))\\ ...\\ r_M=\log(\mu_M)+\log(\sum_{k=1}^M \exp(r_k)) \end{cases}$$ and assuming that this is the maximum, we can put it in the objective function and get the result.

Now I need to ensure that we have a maximum and at this point I'm lost in the computation of the Hessian because I get many zeros. Could you help me with that part?

You are done if you prove that the function is concave, that is the function log-sum-exp is convex. Two ways to do it is here and here. Another way is to use induction: prove first that $\ln(1+\exp{t})$ is convex and increasing. Then

1. $\ln(\exp{r_1}+\exp{r_2})=r_1+\ln(1+\exp(r_2-r_1))$ is convex.
2. Assume $\ln(\sum_{i=1}^M\exp{r_i})$ convex. Then $$\ln\Big(\sum_{i=1}^{M+1}\exp{r_i}\Big)=r_{M+1}+\ln\Big(1+\sum_{i=1}^M\exp(r_i-r_{M+1})\Big)=r_{M+1}+\ln\Big(1+\exp\underbrace{\ln\sum_{i=1}^Me^{r_i-r_{M+1}}}_{\text{convex}}\Big)$$ is convex.

P.S. You can also prove it via Hessian.

• Thanks. Can you remind me why if $\log(\sum_{y=1}^M \exp(r_k))$ is convex, then the objective function is concave? – TEX May 26 '18 at 11:22
• @CGT From the general properties: linear is concave, negative convex is concave, sum of two concave is concave. For concave functions, a critical point is the global maximum. – A.Γ. May 26 '18 at 11:24