How do I convert max min problem into a linear programming problem? Let $A$ be a given $m \times n$ matrix, $c$ a given $n$-vector, and $b$ a given $m$-vector.
Show that this problem
$$\max_{x \ge 0} \min_{y \ge 0} (c^T x - y^T Ax + b^Ty)$$
can be reduced to a linear programming problem.
 A: Consider that the following problem ($*$)
\begin{alignat}{3}
\min_y && b^\top y \tag{$*$}\\
&&A^\top y \geq c\\
&&y\geq0
\end{alignat}
has the Lagrangian (with dual variables $x$)
\begin{align}
L(y;x) := b^\top y + x^\top (c-A^\top y).
\end{align}
Then the dual function is defined as
\begin{align}
d(x) := \min_y L(y;x) := \min_y \left\{ b^\top y + x^\top (c-A^\top y) \right\}
\end{align}
and the dual problem is
\begin{alignat}{3}
\max_x && d(x) \tag{$**$}\\
&&x\geq0
\end{alignat}
or
$$
\max_{x\geq0}\min_{y\geq0} \left\{ b^\top y + c^\top x -y^\top A x \right\} \tag{$**$$*$}.
$$
Provided that both are feasible, strong duality says that ($*$) has the same objective value as ($**$), so we have shown that ($**$$*$) can be expressed as ($*$).
Or, again using strong duality, we can express ($**$$*$) as a feasibility problem (simplified LP)
\begin{alignat}{3}
\min_{x,y} && 0\\
&&
\begin{bmatrix}
A^\top & 0\\ 0 & -A\\I&0\\0&I
\end{bmatrix}
\begin{bmatrix}
y\\x
\end{bmatrix}
\geq
\begin{bmatrix}
c\\-b\\0\\0
\end{bmatrix}
\end{alignat}
