2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The first kind of equations contains many equations? $i,j$ are different. $\endgroup$ – W. mu Jun 9 '18 at 2:03
  • $\begingroup$ @W.mu Edited to clear up the confusion $\endgroup$ – jonem Jun 9 '18 at 2:06
  • $\begingroup$ I’m not sure your proposed optimal solution satisfies the equality constraint (it also assumes the $a_{ij}>0$) $\endgroup$ – David M. Jun 9 '18 at 2:57
  • $\begingroup$ @DavidM. Oops, it should read $a_{ij}>0$. As for the equality constraint, let $a = \sum_k\sum_la_{kl}$, so $\sum_i\sum_j\frac{n\sum_k\sum_la_{kl}}{a_{ij}} = a\sum_i\sum_j\frac{n}{a_{ij}} = a\frac{n}{a} = n$. $\endgroup$ – jonem Jun 9 '18 at 3:03
  • 1
    $\begingroup$ No need for 2 indices. Treat $ x $ and $ a $ as vectors. It might make things easier. $\endgroup$ – Royi Jun 9 '18 at 20:01
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks Alex. Any ideas on what the optimal could be? $\endgroup$ – jonem Jun 9 '18 at 16:29
  • $\begingroup$ I don't believe there is an optimum which you can find analytically. But you can get very close by solving a one-dimensional optimuzation problem numerically (e.g. bisection) by using duality. $\endgroup$ – Alex Shtof Jun 9 '18 at 16:37
  • $\begingroup$ Thanks. Does your statement that all $x_{ij}^*$ are nonzero hold in general? Intuitively, it seems like it should. If it does, I can solve the KKT equations to get an optimal (I've added it to my original question). $\endgroup$ – jonem Jun 9 '18 at 16:41
  • 2
    $\begingroup$ The problem is convex, so if you can find $x^*$ such that $x^*_{ij}>0$ for all $i,j$ and it satisfies the KKT conditions, then it’s optimal $\endgroup$ – David M. Jun 9 '18 at 17:06

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.