I need to solve
$$ \max_x \min_y x^T M y $$
subject to
$$ \sum_{i=1}^n y_i = 1, \sum_{j=1}^m x_j = 1,\\ x \geq 0, y \geq 0 $$
where $ M \in \mathbb{R}^{m\times n} $, $ x \in \mathbb{R}^m $ and $ y \in \mathbb{R}^n $.
I know the way to get a around this, is to make use of the duality theorem.
My question is: What is the reason why duality is needed here?
- Is it, because $ \min_y x^T M y $ is not linear? I don't know why this is the case.
- Is it, because $ \min_y x^T M y $ is not solvable using lin prog?
- Is it, because of another reason?