2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. Can you remind me why if $\log(\sum_{y=1}^M \exp(r_k))$ is convex, then the objective function is concave? $\endgroup$ – TEX May 26 '18 at 11:22
  • 1
    $\begingroup$ @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. $\endgroup$ – A.Γ. May 26 '18 at 11:24

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.