minimizing the weighted summation of two sequences

Question

how can I minimize the following function:

$$\sum_{i=1}^n \sum_{j=1}^na(i)x^2(i,j)b(j) $$ assuming $$\sum_{i=1}^n x^2(i,j) = 1 , j=1..n$$ $$\sum_{j=1}^n x^2(i,j) = 1 , i=1..n$$

here x(i,j) are the variables and a(i) and b(j) are non increasing constant sequence of numbers

Answer 1

You can rewrite the problem as follows:

$$ \mbox{Minimize}\quad \sum_{i,j=1}^n c_{ij} y_{ij} $$ subject to $$ \sum_{i=1}^n y_{ij} = 1 \quad \forall j = 1,...,n\\ \sum_{j=1}^n y_{ij} = 1 \quad \forall i = 1,...,n $$

where $y_{ij}=x^2(i,j)$ and $c_{ij}=a(i)b(j)$. Now, since $x^2(i,j)\ge 0$, you can assume $y_{ij}\ge 0$. This is a minimum cost flow problem (easy to solve) on a complete weighted bipartite graph $G=(V_1\times V_2,E)$ with :

• $V_1=V_2=\{1,...,n \}$
• $E= \{ (i,j)\; |\; i \in V_1, j \in V_2 \} $
• a weight function $\omega: (i,j) \rightarrow c_{ij}$ on each edge