0
$\begingroup$

My problem is quite cumbersome. In general, it can be modelled as a non-linear programming problem, with linear constraints and non-linear objective function. The objective function is conditional entropy, and I dont know if it is convex or not.

In specific, $s$ and $u$ are both $2$-bit binary string. For each pair $(s,u)$ (where $s$ is equal to or dominated by $u^{[1]}$), there is a variable associated with it, $pr(s,u)$. That is, we have $9$ variables $pr(00,**),pr(01,*1),pr(10,1*),pr(11,11)$. There are also four constant $pr(**)$.

In my optimisation problem, constraints are linear, $ \begin{cases} pr(00,00) + &pr(00,01) + &pr(00,10) + &pr(00,11) &= pr(00) \\ &pr(01,01) & + &pr(01,11) &= pr(01) \\ & &pr(10,10) + &pr(10,11) &= pr(10) \\ & & &pr(11,11) &= pr(11) \\ \end{cases} $

For constants, we have following constraints too.

$ \begin{cases} pr(00) + pr(01) + pr(10) + pr(11) &= 1 \\ pr(00) &> 0 \\ pr(01) &> 0 \\ pr(10) &> 0 \\ pr(11) &> 0 \\ \end{cases} $

Objective function is non-linear, it is in a similar form like entropy. And I need to minimise it, \sum_{s,u}{pr(s,u)\log{pr(s,u)} - \sum_{u}{\big(\sum_{s}{pr(s,u)}\big)\log{\big(\sum_{s'}{pr(s',u)}\big)}}}

Which is,

$\scriptsize \begin{align} pr(00,00)\log{pr(00,00)} & + pr(00,01)\log{pr(00,01)} & + pr(00,10)\log{pr(00,10)} & + pr(00,11)\log{pr(00,11)} \\ &+pr(01,01)\log{pr(01,01)} & & + pr(01,11)\log{pr(01,11)} \\ &&+pr(10,10)\log{pr(10,10)} & + pr(10,11)\log{pr(10,11)} \\ &&&+pr(11,11)\log{pr(11,11)}\\ \end{align} $

$\scriptsize \begin{align} &-\big(pr(00,01)+pr(01,01)\big)\times \log{\big(pr(00,01)+pr(01,01)\big)} \\ &-\big(pr(00,10)+pr(10,10)\big)\times \log{\big(pr(00,10)+pr(10,10)\big)} \\ &-\big(pr(00,11)+pr(01,11)+pr(10,11)+pr(11,11)\big)\times \log{\big(pr(00,11)+pr(01,11)+pr(10,11)+pr(11,11)\big)} \\ \end{align} $

Non-linear programming may be hard and general. But is there any quick technique to solve this special kind of optimisation problem?

cite [1]: $s$ is dominated by $u$ means every bit $1$ in $s$ must also be $1$ in $u$. For example, $01$ is dominated by $11$, but not by $00$.

  • 0
    true, $pr$ is probability, and text is updated accordingly. Actually, I have tried Lagrange multipliers, which boils down to solving a non-linear equation set. Still dont know how to solve that.2012-02-14

1 Answers 1

1

Finally, I solve the problem, inspired by http://en.wikipedia.org/wiki/Lagrange_multiplier#Example:_entropy.

In specific, after computing partial derivatives, a non-linear equation set is obtained. \begin{align*} pr(s,u) - b^{\lambda_s}\sum_{s'}{pr(s',u)} & = 0 \\ pr(s) - \sum_{u'}{pr(s,u')} & = 0 \end{align*}

Thus, \frac{pr(s_1,u_1)}{pr(s_1,u_2)} = \frac{\sum_{s'}{pr(s',u_1)}}{\sum_{s'}{pr(s',u_2)}}= \frac{pr(s_2,u_1)}{pr(s_2,u_2)}

For $s_2=11$, $u_2=11$ and $u_1\neq{11}$, it leads to $pr(s_2,u_1)=0$ (cause $s_2$ dominates $u_1$), and hence, $\frac{pr(s_2,u_1)}{pr(s_2,u_2)}=0$. This applies to the case where $s_1\neq{11}$. Thus, we have the optimal solution at $pr(s,u)=\begin{cases}pr(s), & \text{if } u \text{ is all bit } 1 \\0, & \text{otherwise.}\end{cases}$