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.

The goal is to maximize the following function: \begin{align} K_p(q) = q\log \frac{q}{p} + (1-q)\log \frac{1-q}{1-p} \end{align} where \begin{align} 0 \leq q \leq 1 \end{align} and $p \in (0,0.5)$ and is some constant. In other words, I'm maximizing the KL divergence in terms of one Bernoulli variable with success parameter $q$ with regard to another Bernoulli with success parameter $p$. The way I've set it up, I can see without formal calculations that it's maximized when $q=1$.

However, I'd like to use the KKT conditions to solve this problem formally and I'm running into problems doing that.

First, I set up the Lagrangian to minimize with the KKT conditions: \begin{align} \mathcal{L}(q,\mu,\lambda) & = -K_p(q) - \mu(1-q) - \lambda q \newline \textrm{where} \quad & \mu, \lambda \geq 0 \newline & 0 \leq q \leq 1 \newline & \mu(1-q) = 0 \newline & \lambda q = 0 \end{align} I then set the derivative in terms of $q$ to zero and plug it back in and get the following dual form: \begin{align} D(\mu,\lambda) & = -\mu + \log(1-p+pe^{\mu-\lambda}) \newline & = \log(e^{-\mu}-pe^{-\mu}+pe^{-\lambda}) \end{align} which I'm supposed to maximize.

But again, I run into the problem where the maximum of the dual is attained when $\mu,\lambda=0$ (and I got these values again by looking at the equation because setting derivatives to zero was infeasible). Which, according to the KKT conditions, means that q is neither zero nor one. But that can't be right, because the maximum of $K$ is attained when $q=1$.

And my obvious question is: what am I doing wrong? And how is this done correctly?

share|improve this question
add comment

2 Answers

Is there any specific reason, you need to use KKT conditions to solve this problem? I have written a formal way of solving it below.

$$f(q) = q \log \left( \frac{q}{p} \right) + \left( 1-q \right) \log \left( \frac{1-q}{1-p} \right)$$ $$\frac{\partial f}{\partial q} = \log \left( \frac{q}{p} \right) + q \times \frac{p}{q} \times \frac{1}{p} - \log \left( \frac{1-q}{1-p} \right) + \left( 1-q \right) \times \frac{1-p}{1-q} \times \frac{-1}{1-p} = \log \left( \frac{q}{p} \frac{1-p}{1-q} \right)$$

Now $q = p$ gives the minimum of $0$ since $\frac{\partial^2 f}{\partial q^2} = \frac{1}{q} + \frac{1}{1-q} = \frac{1}{q (1-q)} > 0$

Note that when $q>p$, $f'(q) > 0$ and when $q<p$, $f'(q) <0$. This means that the function starts at $q=0$ decreases to a minimum value of $0$ at $q=p$ and then increases and ends at $q=1$. So the maximum can occur either at $q=1$ or $q=0$.

$q=0$ gives us $f(0) = - \log(1-p)$ and $q=1$ gives us $f(1) = - \log(p)$.

So if $p \in (0,0.5]$, then the maximum occurs at $q=1$ with the maximum being $- \log(p)$ and if $p \in [0.5,1)$, then the maximum occurs at $q=0$ with the maximum being $- \log(1-p)$

share|improve this answer
    
Thanks for the reply. But I'm solving this to learn about and get practice applying the KKT conditions. I just thought maximizing KL divergence for two Bernoullis would be nice toy problem for this. In real applications, I think I've only come across cases where people try to minimize KL divergence, not maximize it. As well they should, since I can't really see any use for maximizing it. –  JasonMond Feb 27 '11 at 8:05
    
But if this happens to be a problem where KKT conditions can't be applied towards a solution, and you happen to know why, I'd be just as happy to find out. –  JasonMond Feb 27 '11 at 8:08
    
@JasonMond: I think you got the sign of $\mu$ wrong. You have $0 \leq q \leq 1$. The way you have written it you need $\mathcal{L}(q,\mu,\lambda) = -K_p(q) + \mu(1-q) - \lambda q$ –  user17762 Feb 27 '11 at 8:15
    
@Sivaram Ambikasaran According to the textbook I got it from ("Numerical Optimization" by Nocedal and Wright), the sign in front of the multiplier is negative if the constraint is positive. –  JasonMond Feb 27 '11 at 17:48
    
@Jason: Minimize $f$ subject to $g \leq 0$ then the function $\mathcal{L}$ is $f+ \mu g$ where $\mu g = 0$, $g \leq 0$ and $\mu \geq 0$ and hence your $\lambda$ and $\mu$ both must be both of the opposite sign. –  user17762 Feb 27 '11 at 20:02
show 2 more comments

Setting the derivative of $\mathcal{L}$ to zero does not guarantee that you obtain the minimum of it. I believe $\mathcal{L}$ is a concave function of $q$ at least for some $p,\lambda,\mu$.

And also, the function $K_p$ to maximize is a convex function; therefore, solving the dual problem may not give you an optimal solution to the primal problem.

share|improve this answer
    
Yes, I suspected as much after sleeping on this for a few days. I'm still not entirely comfortable with using Lagrange multipliers when it comes to inequality constraints. If you should ever come up with a way of maximizing $K_p$ using Lagrange multipliers, please share. –  JasonMond Mar 1 '11 at 8:01
    
@JasonMond To find KKT points with inequalities, you can consider all possible cases, that is, for your problem (i) q=1, lambda=0, (ii) q=0, mu=0. For each case, you can determine other variables and see if they all satisfy all other KKT conditions. If all conditions are met, then you obtained a KKT point. –  FEQ Mar 1 '11 at 14:43
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.