1
$\begingroup$

The following optimization problem is related to relative entropy and to the limit of the iterative proportional fitting procedure.

For $1 \leq i,j \leq n$ and fixed $w_{ij} \geq 0$, and fixed $a_i, b_i > 0$ with $\sum_i a_i = \sum_i b_i$:

minimize $\sum_{i,j} x_{ij} \ln{\frac{x_{ij}}{w_{ij}}}$

subject to $\sum_j x_{ij} = a_i$, $\quad \sum_i x_{ij} = b_j$, $\quad x_{ij} \geq 0$, $\quad x_{ij} = 0 \Leftrightarrow w_{ij} = 0$

with the convention that $0\cdot\ln\frac00 := 0$.

I read in a paper from the 60s that "it can be shown that" any feasible solution is optimal if and only if

$\displaystyle \frac{x_{ac} / w_{ac}}{x_{ad} / w_{ad}} = \frac{x_{bc} / w_{bc}}{x_{bd} / w_{bd}}$,

whenever $w_{ac}, w_{ad}, w_{bc}, w_{bd} > 0$.

I am very interested in the connection between these ratios and the minimization problem, but I cannot find a proof.

So my question is: how to prove this?

$\endgroup$
  • $\begingroup$ Have you tried solving the KKT system? or equivalently, writing the Lagrangian and computing the first order conditions? $\endgroup$ – Cristóbal Guzmán Aug 1 '14 at 15:45
  • $\begingroup$ I tried it before with no success. However, motivated by your comment, I tried it again; this time I found the trick how to make use of the KKT conditions! So, the proof can indeed be carried out this way. I will publish it here within the next days. $\endgroup$ – cubic lettuce Aug 4 '14 at 7:54
  • $\begingroup$ I am sorry for not answering below, but people here are very strict with non research-level questions. Great that you solved it! $\endgroup$ – Cristóbal Guzmán Aug 4 '14 at 16:07
  • $\begingroup$ "The Uncertain Reasoners Companion" has a whole chapter on feasibility of inference processes, though I'm not 100% if it contains what you're looking for. Defo worth a read though. $\endgroup$ – samthebest Aug 5 '14 at 17:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.