How to find minimum of linear matrix function?

217 Views Asked by At

Suppose I wish to minimise

$$A = 1^T_{n_1} B C 1_{n_1}$$

where $B$ is a matrix of unknowns of dimension $n_1 \times n_2$ and $C$ is a constant matrix of dimension $n_2 \times n_1$, and $1_{n_1}$ is a vector of ones of length $n_1$. Hence, $A$ is a scalar.

All columns of $B$ sum to $1$ and all rows sum to some value (say, $w$).

Is there any standard methods which I could use to find the elements of $B$ which minimises $A$?

1

There are 1 best solutions below

0
On BEST ANSWER

Consider $A = 1^T_{n1}B*C1_{n_1}$. Dimension of $B$ is $n_1 \times n_2$> Let $B=(B_1, B_2,..B_{n_2})$, where $B_i = (B_{i1}, B_{i2}, ..B_{in_1})$ is the $i^{th}$ columns of $B$. One of the given constraints is that all columns of $B$ sum to one i.e., $\sum_{j=1}^{n_1} B_{ij} = 1$ for $i=1,2,..n_2$.

Consider \begin{equation} \begin{split} Z = 1^T_{n1}B &= (1,1,..1)_{1 \times n_1} (B_{1}, B_{2}, ..B_{n_2})_{n_1 \times n_2} \\ &= (\sum_{j=1}^{n_1} B_{1j}, \sum_{j=1}^{n_1} B_{2j}, ..\sum_{j=1}^{n_1} B_{n_2j}) \\ &= (1,1,..1)_{1 \times n_2} \\ &= 1^T_{n2} \end{split} \end{equation} So, basically $A$ can be written as $1^T_{n2} C 1_{n_1} $, which is independent of $B$. Since $C$ is a constant matrix, the value of A will be same (sum of all the elements of $C$), no matter what the elements of B are subject to given constraints.