# Minimise the entropy of a probability vector using Lagrange multipliers

Problem statement:

The entropy of a probability vector $p = (p_1, ... , p_n)^T$ is defined as $H(p)= - \sum\limits_{i=1}^{n} p_i \log{p_i}$, subject to $\sum\limits_{i=1}^{n} p_i = 1 \mbox{ and } p_i \geq 0$, where $0\log{0} = 0$ by convention.

What is the largest and smallest entropy of any probability vector?

Discussion

I can maximise the expression using Lagrange multipliers without a problem. It's also equally easy to prove that the smallest entropy of any probability vector is 0, by noting that it must be non-negative, and providing an example with entropy 0.

However, I would very much like to prove that the minimum value is 0 using Lagrange multipliers (the fact that I can't seems to me to suggest that there is something that I haven't understood).

I set up the Lagrangian: $L(p, \lambda) = - \sum p_i\log{p_i} + \lambda(\sum p_i - 1)$ and by differentiating to find stationary points obtain the system: ${\frac{\partial{L}}{\partial{p_i}}}= -\log{p_i} - 1 + \lambda = 0$. The obvious solution to this gives me my maximum point, but I am expecting another solution for the minimum.

• Am I misusing Lagrange multipliers?
• Is there another solution to my system that I am missing (maybe involving the "convention" about $0\log{0} = 0$)?
• Do I need to worry about slackness and the condition $p_i \geq 0$ to find the minimum?
• Is finding this minimum beyond the scope of this method for some reason, and my lecturers are in fact expecting me to resort to the "easy" method described above?

-
The inequality constraints do not appear in the Lagrangian, so can have no 'effect'. A bigger issue is that the objective is not differentiable at the boundary. In this case, it would be more straightforward to note that $H(p) \geq 0$, and that $H(p) = 0$ is only attained when each $p_i$ is 0 or 1. –  copper.hat Oct 3 '12 at 18:34
Hi, thank you for your answer - I hadn't understood that the Lagrange method fails to provide extrema that lie on the boundary of the set of possible values for p. –  Joshua Pepper Oct 3 '12 at 19:00
There are two separate issues here. One is just the fact that the function is not differentiable on the whole domain. The second is that the inequality constraints $p_i \geq 0$ need to be incorporated. Handling the latter would involve a generalization using KKT conditions. Both are issues here. –  copper.hat Oct 3 '12 at 19:09

(the fact that I can't seems to me to suggest that there is something that I haven't understood).

Than something is more basic than Lagrange multipliers: is that extrema of functions not necesarily correspond to critical points (i.e. points where it's derivative is zero). You have to check also points where the function is not diferentiable, and/or the domain boundary.

For example, suppose you must have the extrema of the function $f(x)= (x-2)^3 - 3 x + 6$ in the domain $x \ge 0$ . Setting the derivative to zero, you get the critical points $x_1 = 1$ (maximum) and $x_2 = 3$ (minimum). But you forget the minimum that occurs at $x_0 = 0$, which you must check individually.

The same applies to Lagrange multipliers, which also find extrema that corresponds to critical points (along a restricted curve).

-
Hi, thank you for your valuable insight. It turns out this was precisely the point that I was struggling with. Would I be correct in stating that the boundary of this particular problem is the union of all positive axes in R^n? –  Joshua Pepper Oct 3 '12 at 18:53
No, you need to consider the plane $p_1+\cdots+p_n = 1$ as well. –  copper.hat Oct 3 '12 at 18:59
Yes, you have $0\le p_i \le 1$, so the boundary is given here by $p_i =0$ for some $i$ (which already includes the case $p_j=1$) –  leonbloy Oct 3 '12 at 19:15
Let me try again with more precision - if $X$ is the set on which the Lagrangian operates (excluding the $\lambda$-dimension), satisfying $p_i \geq 0$, and $X(p) \subset X$ is the feasible set where $\sum p_i = 1$ , then the boundary $B_1$ of $X$ is the union of positive axes, $X(p)$ corresponds to the edges of an n-dimensional pyramid (right-angled at the origin) that do not intersect with the axes, and the boundary $B_2$ of $X(p)$ is $B_1 \cap X(p)$, corresponding to the vertices of the pyramid, excluding the origin. @copper.hat –  Joshua Pepper Oct 3 '12 at 19:17
The boundary $B_1 = \{ (p_1, p_2 \cdots p_n) : p_1=0 \cup p_2=0 \cup \cdots \cup p_n=0\}$ is rather made of the union of the faces of that piramid, not the edges. You can also consider the union of the faces of the unitary hipercube. –  leonbloy Oct 3 '12 at 19:23