Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I presume that $pr$ means probability. If so, you can add a fifth constraint, that is, the total probability must add up to $1$. Then assuming continuous values for the distribution of $pr$, you could try Lagrange multipliers. –  William Feb 14 '12 at 20:29
    
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. –  Richard Feb 14 '12 at 20:32
add comment

1 Answer

up vote 0 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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