1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Look at Weierstrass' Theorem and at strict convexity. Uniqueness does not mean that the solution cannot be on the boundary. $\endgroup$
    – LinAlg
    Commented Mar 8, 2019 at 0:24
  • $\begingroup$ @LinAlg Is that just a general comment? Because, I'm sorry, but is it useful? $\endgroup$
    – byk7
    Commented Mar 11, 2019 at 13:56
  • $\begingroup$ 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. $\endgroup$
    – LinAlg
    Commented Mar 11, 2019 at 14:09
  • $\begingroup$ @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? $\endgroup$
    – byk7
    Commented Mar 11, 2019 at 17:02
  • $\begingroup$ 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? $\endgroup$
    – Hans
    Commented Aug 3, 2022 at 23:46

1 Answer 1

0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .