I want to find the solution for the maximum entropy distribution with a cost constraint. The specific problem setup is as follows:
-
Let $\bf{x}$ be a probability distribution.
-
Let $\bf{c}$ be the cost vector associated with the distribution.
-
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$.
-
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.
Best Answer
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}$.