About exchanging min and max and correctness of an inequality

Question

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?

Answer 1

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}