Formulation of a constrained optimization problem with probabilities

Question

we are given four probabilities for an event. We shall adapt these probabilities in order to maximize the entropy given a constraint $4 = \sum_{i = 1}^4 2p_ii \Leftrightarrow 2 = \sum_{i = 1}^4 p_ii$.

The task asks also if we need additional constraints. So since we consider probabilities, the probabilities must be non negative and they must sum up to $1$.

My approach for the optimization problem would be

$ \begin{align} \underset{p}{\max}\qquad & H(p) = \sum_{i = 1}^4 p_i \log_2 p_i\\ \text{s.t.}\qquad & 2 = \sum_{i = 1}^4 p_ii\\ & 1 = \sum_{i = 1}^4p_i\\ & p_i \geq 0,\ i \in \{1, 2, 3, 4\}\\ \end{align} $

Do we really have these much constraints? In a further task we shall formulate the Langrangian of this problem and if I understood it right, we need one Langrangian multiplier per constraint, so in this case at least six multiplier. In fact we need some more multiplier, because our given "recipe" for formulating the Langrangian works only with inequalities.

Is it really that high dimensional?

Answer 1

Yep. Luckily though you're maximizing a concave function over a convex set, so it's not too hard to solve algorithmically. It's also easy to plug in the Karush–Kuhn–Tucker conditions. See https://davidrosenberg.github.io/ml2015/docs/convex-optimization.pdf .

Answer 2

Just to be sure. Can someone tell me, if my further approach is right:

I formulated now the following optimization problem:

$ \begin{align} \underset{p}{\max}\qquad & H(p) = \sum_{i = 1}^4 p_i\log_2p_i\\ \text{s.t.}\qquad & \pm (\sum_{i = 1}^4(p_ii) - 2) \leq 0\\ & \pm (\sum_{i = 1}^4(p_i) - 1) \leq 0\\ & -p_i \leq 0,\ i \in \{1, 2, 3, 4\} \end{align} $

So we have in total eight constraints. We shall now formulate the Langrangian of this problem, which is defined as $\mathcal{L}(\mathbf{p}, \mathbf{\lambda}) = H(\mathbf{p}) + \mathbf{\lambda}^\top \mathbf{g}(\mathbf{p})$, where $\mathbf{g}$ is the vector of constraints.

Hence we have

$ \begin{align} \mathcal{L}(\mathbf{p}, \mathbf{\lambda}) &= \sum_{i = 1}^4p_i\log_2 p_i + (\lambda_1 - \lambda_2)(\sum_{i = 1}^4(p_ii) - 2) + (\lambda_3 - \lambda_4)(\sum_{i = 1}^4(p_i) - 1) - \lambda_5p_1 - \lambda_6p_2 - \lambda_7p_3 - \lambda_8p_4 \end{align} $

We shall then calculate the partial derivatives w.r.t. each variable. Here we have for instance

$ \begin{align} \frac{\partial \mathcal{L}}{\partial p_1} &= \log_2p_1 + \frac{1}{\ln2} + \lambda_1 - \lambda_2 + \lambda_3- \lambda_4 - \lambda_5\\ \frac{\partial\mathcal{L}}{\partial\lambda_1} &= p_1 + 2p_2 + 3p_3 + 4p_4 - 2 \end{align} $

Now comes a part, where I really don't know how to do this. We should formulate the dual function and solve it analytically. Although the Karush-Kuhn-Tucker conditions are mentioned above, we must go the "hard" way and calculate it step by step. If I understood the dual function right, we firstly must solve $\max_\mathbf{p} \mathcal{L}(\mathbf{p}, \mathbf{\lambda})$, i.e. set the partial derivatives w.r.t. $p_i$ equal to zero and rearrange them to $p_i$ to find a solution $\mathbf{p}^*$ as a function of $\mathbf{\lambda}$. Then we replace $\mathbf{p}^*$ in the Langrangian what results in

$G(\mathbf{\lambda}) = H(\mathbf{p}^*) + \mathbf{\lambda}^\top\mathbf{g}(\mathbf{p}^*)$

and finally we have to solve $\min_\mathbf{\lambda} G(\mathbf{\lambda})$.

With help of the first partial derivative above we have for instance $p_1 = 2^{-1/\ln(2) - \lambda_1 + \lambda_2 - \lambda_3 + \lambda_4 + \lambda_5}$, if we set it equal to zero. Further we have $\partial\mathcal{L}/\partial\lambda_5 = -p_1$. If we substitute $p_1$ with the previous term and set it to zero as well, we get

$ 0 = -2^{-1/\ln(2) - \lambda_1 + \lambda_2 - \lambda_3 + \lambda_4 + \lambda_5} $

To solve this, we must use the logarithm to the base 2, but this is negative infinity for zero. So I don't know, where my fallacy is.