$$\min_{\theta_i} \sum_{i=1}^K - \alpha_i \log(\theta_i)$$ s.t. $$1 \geq \theta_i \geq 0$$ $$\sum_{i=1}^K \theta_i = 1$$ $\alpha_i \geq 0$, but not all $\alpha_i$ is 0.

I know that for $K=2$, $\theta^*_i = \frac{\alpha_i}{\sum_{j=1}^K \alpha_j}$. But, I am not sure if the same expression holds for K>2. Even if it does, how I can show it?

  • $\begingroup$ can you write down the KKT conditions? $\endgroup$ – LinAlg Mar 14 at 18:28

Short answer : yes.

Long answer:

Let us set $f(\theta_1,\theta_2, ..., \theta_K):=\sum_{i=1}^K - \alpha_i \log(\theta_i)$ and for simplicity $\alpha_i \neq 0$ for all $i$.

Let us set $g(\theta_1,\theta_2, ..., \theta_K):=\sum_{i=1}^K \theta_i $ Furthermore let us define a constant $c:=1$ Then the problem has the format which can be solved with the Method of Lagrange Multipliers: $$\min_{g(x)=c} f(x)$$

Acording to Lagrange there is a local minimum $x$ for that problem and a constant $\lambda$ and such that

$$ \nabla f(x) = \lambda \nabla g(x) \\ g(x) =c $$

So we get (note that $\lambda$ cannot be 0) $$ - \alpha_i / \theta_i = \lambda \qquad(i=1,..,K)\\ \theta_i = - \alpha_i /\lambda \qquad(i=1,..,K) $$ Summing the last equations we get $$1=\sum_{i=1}^K \theta_i=-\lambda /\sum_{i=1}^K \alpha_i$$ so $\lambda=-\sum_{i=1}^K \alpha$. If we now substitute $\lambda$ in $- \alpha_i / \theta_i = \lambda$ we get $$\theta_i =\alpha_i/\sum_{j=1}^K \alpha_j$$

Since $f$ is a sum of convex function it is convex itself and therefore the local minimum is also a global minimum.

  • $\begingroup$ You forgot to involve the constraint $1 \geq \theta_i \geq 0$. Although if you would have done it wouldn't effect on your answer. $\endgroup$ – Red shoes Mar 15 at 5:53
  • $\begingroup$ @Red shoes: Well, $1 \geq \theta_i \geq 0$ is redundant in the assumptions , as $log(\theta_i)$ is only defined for $ \theta_i > 0 $ and from this $1 \geq \theta_i$ is a direct consequence of $\sum \theta_i =1$. $\endgroup$ – Maksim Mar 15 at 9:23
  • $\begingroup$ I want to tell you if you want to write a rigorous answer from mathematical point of you, you need to discuss all details. So as you pointed out the function is not continuous on feasible solution so you might have no optimal solution while you do have KKT points. But it is easy to show that the optimal solution exists an it lies somewhere in $1 > \theta_i > 0$. This allows you to drop this constraint. and write optimality condition. $\endgroup$ – Red shoes Mar 17 at 18:29
  • $\begingroup$ May I ask you to supply a rigorous proof for the problem, so that I can learn how a real valid precise and rigorous proof can be written? $\endgroup$ – Maksim Mar 17 at 21:59
  • $\begingroup$ Sure to understand your mistake, let switch the objective function by $\sum_{i=1}^K + \alpha_i \log(\theta_i)$. Then observe that you do have stationary point, but you dont have a minimum point. $\endgroup$ – Red shoes Mar 17 at 23:50

Setting $f(\theta):=\sum_{i=1}^K - \alpha_i \log(\theta_i)$, where $\theta =(\theta_1,\theta_2, ..., \theta_K)$. Now assume $\theta$ is a point satisfying constraints. Observe that for any $i$ we have $$ \lim_{\theta_i \to 1^{-}} f(\theta) = +\infty \quad \quad \mbox{and} \quad \quad \lim_{\theta_i \to 0^{+}} f(\theta) = +\infty $$

This tells us the minimum of $f$ over that constraint set exists and lies somewhere in $ 0< \theta_i <1$ for all $i$ ($f$ is continuous there). This minimum is one of the $KKT$ points, and here $KKT$ condition reduces to the Lagrangian multipliers method, because inactive inequality constraints are not appeared in $KKT$ condition. and then the rest of the above answer....


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.