# Maximum Entropy Distribution with Constraint

I want to find the solution for the maximum entropy distribution with a cost constraint. The specific problem setup is as follows:

1. Let $$\bf{x}$$ be a probability distribution.

2. Let $$\bf{c}$$ be the cost vector associated with the distribution.

3. Let $$m$$ be the maximum allowable cost of the distribution. In other words, $$\textbf{c}^\top\textbf{x} = \sum_{i=1}^n c_i x_i \le m$$.

4. I want to maximize the entropy of $$\bf{x}$$ subject to this constraint. Mathematically, this is equivalent to minimizing, $$\textbf{x}^\top \log(\textbf{x}) = \sum_{i=1}^n x_i \log(x_i)$$.

I'm struggling to calculate the analytic solution using Lagrangian duality. I'm also unable to implement a numeric solution in Python. Solutions to either of these approaches would be much appreciated.

Setting up the Lagrangian, \begin{align*} L = \sum_{i=1}^{n}x_i \log(x_i) + \lambda\left(\sum_{i=1}^{n}c_i x_i - m\right) + \mu\left(\sum_{i=1}^{n}x_i - 1\right) \end{align*} Computing the stationary points, \begin{align*} \frac{\partial L}{\partial x_i} = \log(x_i) + 1 + \lambda c_i + \mu\overset{\text{set}}{=} 0 \implies x_i = e^{-1 - \lambda c_i - \mu} \end{align*} This stationary point is already $$\ge 0$$, so we just need to ensure $$\sum_{i=1}^{n} c_ix_i = m$$ and $$\sum_{i=1}^{n} x_i = 1$$. Using the second constraint, we can solve for $$\mu$$ \begin{align*} \mu = \log\left(\sum_{i=1}^{n}e^{-1 - \lambda c_i}\right) \end{align*} Plugging this into the first constraint, we have \begin{align*} \sum_{i=1}^{n}(c_i - m)e^{-1 - \lambda c_i} = 0 \end{align*} At this point, you may use numerical methods like Newton-Raphson to find $$\lambda$$. As a sanity check, letting $$c_i = m$$ does result in $$x_i = \frac{1}{n}$$.
• Does this approach take into account that the solution needs to be a probability distribution (additional constraints: $x_i \ge 0$ and $\sum_{i=1}^n x_i = 1$)? I just tried it out and got a weird solution on a sample problem where $m=1$, $n=7$ and $\textbf{c}=[6, 5, 4, 3, 2, 1, 0]^\top$. If you can show what the solution is in this case, I can go ahead and accept the answer. – jjet Aug 20 '19 at 20:24
• Edited, apologies for not realizing earlier. With the above edit, the one-step solution trick no longer works, and you need to iterate through Newton-Raphson, or some other general iterative procedure, directly. Letting $\lambda = 0$ seems like a good starting point. – Tom Chen Aug 21 '19 at 11:09
• Ok, this is what I thought the solution was but wanted to confirm. I'm fine with using numerical methods for $\lambda$. I was having difficulty optimizing $n$ parameters but optimizing one is simple. – jjet Aug 21 '19 at 12:58
• As a side note, if some $c_i=m$, I'm not sure how that leads to $x_i=\frac{1}{n}$. For instance, if all the other $c_j$'s are greater than $m$, then $x_i=1$ and the rest are zero. Did you mean if each $c_i=\frac{m}{n}$ then each $x_i=\frac{1}{n}$? – jjet Aug 21 '19 at 13:00
• For $c_i = m$, the equation is always satisfied for any $\lambda$. At the same time, we arrive at $\mu = \log\left(\sum_{i=1}^{n}e^{-1-\lambda m}\right)$ and $x_i = e^{-1-\lambda m}/\sum_{i=1}^{n}e^{-1-\lambda m} = 1/n$. – Tom Chen Aug 21 '19 at 13:53
This is easy to implement and numerically solve in CVXPY, using the supplied function entr .