0
$\begingroup$

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.

$\endgroup$
3
+50
$\begingroup$

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}$.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ – jjet Aug 20 '19 at 20:24
  • $\begingroup$ 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. $\endgroup$ – Tom Chen Aug 21 '19 at 11:09
  • $\begingroup$ 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. $\endgroup$ – jjet Aug 21 '19 at 12:58
  • $\begingroup$ 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}$? $\endgroup$ – jjet Aug 21 '19 at 13:00
  • $\begingroup$ 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$. $\endgroup$ – Tom Chen Aug 21 '19 at 13:53
1
$\begingroup$

This is easy to implement and numerically solve in CVXPY, using the supplied function entr .

The entropy maximization example at https://www.cvxpy.org/examples/applications/max_entropy.html?highlight=entropy can be modified for your problem by changing the constraints.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.