Let $v\_i \in \mathbb{R}^{n}, \ i=1, \ldots, m, \ \ $ $\mathcal{S}$ a convex polyhedron and $x \in \mathbb{R}^{n}$ be given. Consider the following solution $(s^{\*},i^{\*})$ to the problem 


\begin{equation}
\underset{s \in \mathcal{S}}{\max} \underset{j=1, \ldots, m}{\min} \langle v\_j, s-x\rangle
\end{equation} 


I would like to conclude the following **Claim**: 


Let $i \in \{1, \ldots, m\}$ be arbitrary, then it holds that


\begin{equation}
\langle v\_i, s^{\*}-x \rangle \geq \langle v\_{i^{\*}}, s^{\*}-x \rangle \ . 
\end{equation} 


**Question 1**: Is the claim true?


**Motivation**: Why I think it might not be true: Consider first maximizing with repsect to $s \in S$, giving us an optimal $s$ for each $j=1, \ldots, m$, which we denote by $s^{(j)}$. Then minimzing with respect to $j$ the expressions $\langle v\_j, s^{(j)}-x \rangle$, and denoting with $j^{(\*)}$ the index where the minimum is attained. It is clear, that then 


\begin{equation}
\langle v\_i, s^{(j^{\*})}-x \rangle \geq \langle v\_{j^{\*}}, s^{(j^{\*})}-x \rangle
\end{equation} 


Does **not** hold for arbitrary $i$, indeed it would only hold if we replace $s^{(j^{\*})}$ with $s^{(i)}$ on the left hand side. So it is clear that if it is possible to exchange $\max$ and $\min$ in our expression, then the claim is false. This motivates my second question


**Question 2** Can we exchange $\max$ and $\min$ ans still get the same solution to the optimization problem?



About exchanging min and max and correctness of an inequality
Let $S:=\mathcal{S}$ and $a\cdot b:=\langle a,b \rangle$. Without loss of generality $x=0$ (or replace $S$ by $S-x$). That $(s^\*,i^\*)$ is a solution to the max-min optimization problem means the following: 
$\forall s\in S$ $\exists i\_s\in[m]:=\{1,\dots,m\}$ $\forall i\in[m]$
\begin{equation}
 v\_i\cdot s\ge v\_{i\_s}\cdot s \tag{1}
\end{equation}
and $\forall s\in S$
\begin{equation}
 v\_{i^\*}\cdot s^\*\ge v\_{i\_s}\cdot s, \tag{2}
\end{equation}
where $i^\*:=i\_{s^\*}$. 
So, (1) immediately implies 
\begin{equation}
 v\_i\cdot s^\*\ge v\_{i\_{s^\*}}\cdot s^\*= v\_{i^\*}\cdot s^\*,
\end{equation}
which answers your Question 1 affirmatively. 


As for Question 2, selecting $S$ and $v\_i$'s at random easily provides a counterexample, resulting in the answer "No" to Question 2. E.g., let $n=2$, $x=0\in\mathbb R^2$, $S:=\{(z,w)\in\mathbb R^2\colon z\ge-10,w\ge-10,z+w\le20\}$, $v\_1=(3,9)$, $v\_2=(8,2)$. Then 
\begin{equation}
 \max\_{s\in S}\min\_{j\in[m]} v\_j\cdot s=110<220=\min\_{j\in[m]}\max\_{s\in S} v\_j\cdot s. 
\end{equation}


