We are trying to prove Von-Neumann's MINIMAX Theorem namely
$$\max_{x\in\Delta_{n}}\min_{y\in\Delta_{m}}y^{T}Ax=\max_{x\in\Delta_{n}}\min_{1\leqslant i\leqslant n}(Ax)_{i}$$
(Here $\Delta_k$ is the set of all probability distributions over $k$ elements)
We are stuck in the stage where we have to prove that the dual program of
$$\begin{eqnarray*} \mbox{maximize }t\\ s.t.:\\ & \sum_{i=1}^{n}a_{ij}x_{i}\geqslant t\\ & \sum x_{i}=1\\ & \forall i,x_{i}\geqslant0 \end{eqnarray*} $$
is
$$\begin{eqnarray*} \mbox{minimize }w\\ s.t.:\\ & \sum y_{j}^{T}a_{ij}\geqslant w\\ & \sum y_{j}=1\\ & \forall j,y_{j}\geqslant0 \end{eqnarray*} $$
How to do it?
Thank you
Rewriting the original problem as $$ \max \:t = \min \: -t\\ s.t.\quad Ax \succeq t\mathbf{1} \\ \mathbf{1}^Tx = 1 \\ x \geq 0 $$
We can form the dual using Lagrange multipliers $w, y$, and $z$. We are now trying to minimize
$$L = -t + y^T(t\mathbf{1}-Ax) + w(\mathbf{1}^Tx-1) - z^Tx\\ = t(-1 -y^T\mathbf{1}) +(-y^TA+w\mathbf{1}^T-z^T)x - w $$ over all $x,t$. We see that the terms corresponding to the primal variables can grow unbounded unless the coefficients in the dual variables are zero. Thus, the dual problem is
$$ \max \:-w = \min w\\ s.t. \quad -A^Ty + w\mathbf{1} = z \\ y^T\mathbf{1} = 1\\ z,y \succeq 0 $$
We can eliminate $z$ by rewriting: $$ \min \:w\\ s.t. \quad -A^Ty + w\mathbf{1} \succeq 0 \implies A^Ty \preceq w\mathbf{1}\\ y^T\mathbf{1} = 1\\ y \succeq 0 $$