Consider the following problem \begin{align*} \min_{x}\quad\sum_i\sum_j&\exp(-a_{ij}x_{ij})\\ \text{subject to}\quad\sum_i\sum_j&x_{ij}=n\\ &x_{ij}\ge0\,\,\forall i,j \end{align*} where $x\in\mathbb{R}^{I\times J}$ is the optimization variable and each $a_{ij}>0$, $i=1,\ldots,I$, $j=1,\ldots,J$, and $n\in\mathbb{N}$ are given. The optimal solution is claimed to be (from a paper) $x_{ij}^* = n\frac{1/a_{ij}}{\sum_i\sum_j1/a_{ij}}$ -- I am trying to prove this.
My attempt:
Since the problem is convex, the KKT conditions are necessary and sufficient. First write the problem as \begin{align*} \min_{x}\quad\sum_i\sum_j&\exp(-a_{ij}x_{ij})\\ \text{subject to}\quad\sum_i\sum_j&x_{ij}-n=0\\ &-x_{ij}\le0\,\,\forall i,j \end{align*} and associate dual variable $\lambda$ with the first constraint and $\mu_{ij}$ with each of the next $IJ$ constraints. Following the definition, the KKT conditions for the above problem are:
- Stationarity: \begin{align*} a_{ij}\exp(-a_{ij}x_{ij}^*) = \lambda-\mu_{ij}\,\,\forall i,j \end{align*} (as pointed out by David M. in the comments/chat, since the gradients of $-x_{ij}\le0$ form a basis, the stationarity condition takes this form)
- Primal feasibility: \begin{align*} \sum_i\sum_jx_{ij}^*-n&=0\\ -x_{ij}^*&\le0\,\,\forall i,j \end{align*}
- Dual feasibility: \begin{align*} \mu_{ij}\ge0\,\,\forall i,j \end{align*}
- Complementary slackness: \begin{align*} \mu_{ij}x_{ij}^*=0\,\,\forall i,j \end{align*}
Using the stationarity condition, I obtain \begin{align*} x_{ij}^* = -\frac{1}{a_{ij}}\log\left(\frac{\lambda - \mu_{ij}}{a_{ij}}\right) \end{align*}
To use the primal feasibility condition, sum \begin{align*} \sum_i\sum_jx_{ij}^* &= -\sum_i\sum_j\frac{1}{a_{ij}}\log\left(\frac{\lambda - \mu_{ij}}{a_{ij}}\right)\\ &= -\sum_i\sum_j\frac{1}{a_{ij}}[\log(\lambda - \mu_{ij})-\log(a_{ij})]\\ &= -\sum_i\sum_j\frac{\log(\lambda - \mu_{ij})}{a_{ij}}+\sum_i\sum_j\frac{\log(a_{ij})}{a_{ij}} \end{align*} so primal feasibility states that \begin{align*} -\sum_i\sum_j\frac{\log(\lambda - \mu_{ij})}{a_{ij}}+\sum_i\sum_j\frac{\log(a_{ij})}{a_{ij}} = n \end{align*}
If we can show that all $x_{ij}^*$ are nonzero (is this true?) then $\mu_{ij}=0$ by complementary slackness and the above equations can be solved to give \begin{align*} x_{ij}^* = \frac{1}{a_{ij}}\left(\log(a_{ij})+\frac{n-\sum_k\sum_l\frac{\log(a_{kl})}{a_{kl}}}{\sum_k\sum_l\frac{1}{a_{kl}}}\right) \end{align*}
This seems to satisfy the KKT conditions, so it appears the original claim of the optimal solution is incorrect.
Question/Update:
Thanks to Alex, the proposed solution was shown to be incorrect. I've derived what I think is that optimal (but I'm questioning if $x_{ij}^*$ is indeed positive). Thanks to all for the help.
Note, that since you are not asked to find the optimal solution, but only prove that the given one is optimal, you don't need to solve the KKT system. You only need to substitute the given solution and show that there exist $\lambda, \mu$ such that the the KKT system holds. From convexity and Slater any point is optimal if and only if this point satisfies KKT.
First, note that primal feasibility indeed holds - all the given $x_{ij}^*$ sum to $n$, and they are all non-negative.
From complementarity slackness, since all $x_{ij}^*$ are nonzero, you get that $\mu_{ij} = 0$.
Substituting $\mu_{ij} = 0$ into stationarity, we get $$ a_{ij} exp(-a_{ij} x_{ij}^*) = \lambda $$ Substituting the given $x_{ij}^*$ we get $$ a_{ij} exp \left (-\frac{n}{\sum_i \sum_j \frac{1}{a_{ij}}} \right) = \lambda $$ And whoops - we get a contradiction! The equation above can be true only if all $a_{ij}$ are equal! Otherwise, it cannot be true!
So unless I made some algebraic mistake here, the point you think is optimal cannot be optimal in general.