1

Let $v_1<\cdots<v_n$ and $\mu\in(v_1,v_n)$ be real numbers. Consider set $$X=\left\{(p_1,\ldots,p_n)\in[0,1]^n\ |\ \sum_{i=1}^np_i=1,\ \sum_{i=1}^np_iv_i=\mu\right\},$$ which is convex (easy) and compact. Consider entropy $$H:X\to\mathbb R,\ H(p_1,\ldots,p_n)=-\sum_{j=1}^np_j\log_2p_j,$$ and let us look for maximum. $H$ is strictly concave continuous function on compact convex set, therefore there is unique $x^*\in X$ such that $H(x^*)=\max\{H(x)\,|\,x\in X\}.$ Construct Langrangian as \begin{align*} \mathcal{L}(p_1,\ldots,p_n;\lambda_1,\lambda_2)&=-\sum_{j=1}^np_j\log_2p_j+\lambda_1\left(1-\sum_{j=1}^np_j\right)+\lambda_2\left(\mu-\sum_{j=1}^np_jv_j\right)= \\ &=\lambda_1+\lambda_2\mu-\sum_{j=1}^np_j\left(\lambda_1+\lambda_2v_j+\log_2p_j\right), \end{align*} from which I received system of $n+2$ equations $$p_j=2^{-\lambda_1-\lambda_2v_j}/e,\quad\sum_{k=1}^np_k=1,\quad\sum_{k=1}^np_kv_k=\mu.$$

Now, I would like to provide a reason that the previous system has a solution. Moreover, if the solution were unique, I would not need to bother with the boundary points. But is there any feasible way how to show that? (I want to avoid second partial derivative test.)

At first, I thought the maximum cannot be achieved on a boundary, but $[-1,0]\to\mathbb R,x\mapsto -x^2$ provides a counterexample.

byk7
  • 865
  • Look at Weierstrass' Theorem and at strict convexity. Uniqueness does not mean that the solution cannot be on the boundary. – LinAlg Mar 08 '19 at 00:24
  • @LinAlg Is that just a general comment? Because, I'm sorry, but is it useful? – byk7 Mar 11 '19 at 13:56
  • It answers some of your question. "I would like to provide a reason that the previous system has a solution" is answered by Weierstrass' theorem, and "if the solution were unique" is answered by strict convexity. Overall, the KKT conditions should help you find the solution. – LinAlg Mar 11 '19 at 14:09
  • @LinAlg Still I feel like I miss something. If the maximum is attained on the boundary, then the system does not have a solution, so how does Weierstrass' theorem work here? – byk7 Mar 11 '19 at 17:02
  • Also would you also need to show that the Lagrangian solution, when it does exist, is actually the maximum point, and that it is unique? – Hans Aug 03 '22 at 23:46

1 Answers1

0

Plug $p_j=2^{-\lambda_1-\lambda_2v_j}/e$ into the last two equations \begin{align*} &\sum_{k=1}^np_k=1\ \ \Rightarrow\ \ \sum_{k=1}^n2^{-\lambda_1-\lambda_2v_k}/e=1\ \ \Rightarrow\ \ \sum_{k=1}^n2^{-\lambda_2v_k}=e2^{\lambda_1} \\ &\sum_{k=1}^np_kv_k=\mu\ \ \Rightarrow\ \ \sum_{k=1}^nv_k2^{-\lambda_1-\lambda_2v_k}/e=\mu\ \ \Rightarrow\ \ \sum_{k=1}^nv_k2^{-\lambda_2v_k}=e\mu2^{\lambda_1} \\ &\Longrightarrow\ \ \sum_{k=1}^nv_k2^{-\lambda_2v_k}=\mu\sum_{k=1}^n2^{-\lambda_2v_k}\ \ \Rightarrow\ \ \sum_{k=1}^n(v_k-\mu)2^{-\lambda_2v_k}=0 \end{align*} and the last equation has a solution.

Second partial derivative test says it would be a maximum as $p_j>0.$ (In fact, the test is quite pleasant since the Hessian is a diagonal matrix.) The obtained solution is unique from strict concavity. (Hence, there is no maximum on the boundary.)

byk7
  • 865