# Characterization of the optimal solution in relative entropy minimization

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?

• Have you tried solving the KKT system? or equivalently, writing the Lagrangian and computing the first order conditions? – Cristóbal Guzmán Aug 1 '14 at 15:45
• 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. – cubic lettuce Aug 4 '14 at 7:54
• I am sorry for not answering below, but people here are very strict with non research-level questions. Great that you solved it! – Cristóbal Guzmán Aug 4 '14 at 16:07
• "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. – samthebest Aug 5 '14 at 17:56