Finding and characterization of local optima in the \(\pi^*\) problem for two-way contingency tables (Q2754988)

Let \(M\) be a model of two-way contingency tables and \(F,G\) cell probabilities. The index \(\pi^*\) that measures the distance of the observations \(P\) from \(M\) is defined by NEWLINE\[NEWLINE\pi^*=\inf \{\pi : P=(1-\pi)F+\pi Q,\;F\in M,\;Q\;\text{arbitrary},\;0\leq \pi\leq 1\}.NEWLINE\]NEWLINE Two different algorithms for calculating \(\pi^*\) have been previously suggested, namely, the EM (expectation and maximization) and the SQP (sequential quadratic programming). Both of them have some difficulties in practice.NEWLINENEWLINENEWLINEOne of the most important models \(M\) is the model of independence. The author proposes a new algorithm, called `greedy', for computing \(\pi^*\) in this case. This greedy algorithm starts with row-column updating. Using graph theory and the Kuhn-Tucker theorem, sufficient and necessary conditions for local optimality are given. The greedy algorithm also leads to a local optimum point, similarly as EM and SQP, but characterizes well the problem of finding \(\pi^*\). The author conjectures that this problem is equivalent to that of the travelling salesman.