# 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

I think the standard notation requires the restrictions to be $f_j(p)\leq0$ for a minimization, and then multipliers can be nonnegative, so the lagrangian is always lower than the cost function.

Minimize h(p)

S. To

Sum(p)=1, let $\lambda_0$ be the asoc. Mult.

$p_j \geq0$, let $\lambda_j$ be the asoc. Mult.

Now to find the optimum candidates:

$dL/dp_j=-\log p_j -1 +\lambda_0-\lambda_j=0$

and kkt:

$\sum p=1$

$\sum p_j \lambda j=0$

Note from this last eq that, as both $\lambda_j$ and $p_j$ are positive, sum equals zero means every element is zero, i.e., either $\lambda_j$ or $p_j$ equals zero. This and 'the convention' let you solve the multipliers, but well skip to a faster road:

1. Look for $i: \lambda_i=0$

This implies $p_i= \exp{\lambda_0-1}$, which does not depend on anything else, so it must be a constant.

Let $p_i= \exp{\lambda_0-1}\triangleq 1/k$, where k is the sumber of non-zero mass elements.

1. The old problem now becomes:

Minimize $-\sum 1/k \log 1/k=\log k$

Subject to

$k \in Z, k\geq 1$

And clearly the optimum is achieved for k=1, which is the least entropic (degenerate ) distribution.

Note: to be thorough, you should also consider the other, non-zero multipliers, then solve for $\lambda_0$, then the rest multipliers, which have to be equal... But this is enough for the question I think

-