# About exchanging min and max and correctness of an inequality

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

$$$$\underset{s \in \mathcal{S}}{\max} \underset{j=1, \ldots, m}{\min} \langle v_j, s-x\rangle$$$$

I would like to conclude the following Claim:

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

$$$$\langle v_i, s^{*}-x \rangle \geq \langle v_{i^{*}}, s^{*}-x \rangle \ .$$$$

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

$$$$\langle v_i, s^{(j^{*})}-x \rangle \geq \langle v_{j^{*}}, s^{(j^{*})}-x \rangle$$$$

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?

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]$$ $$$$v_i\cdot s\ge v_{i_s}\cdot s \tag{1}$$$$ and $$\forall s\in S$$ $$$$v_{i^*}\cdot s^*\ge v_{i_s}\cdot s, \tag{2}$$$$ where $$i^*:=i_{s^*}$$. So, (1) immediately implies $$$$v_i\cdot s^*\ge v_{i_{s^*}}\cdot s^*= v_{i^*}\cdot s^*,$$$$ 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 $$$$\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.$$$$
• Could you add some details to why a solution to the max min problem satisfies equation $(1)$ and equation $(2)$ at the same time, maybe starting from the definitions? I have thought about it but I can't see it. Nov 22 '18 at 7:48
• @sigmatau : I believe that a solution to the max-min problem is defined by (1) and (2). How else would one define it? Indeed, (1) (with the quantifiers) means precisely that the minimum of $v_i\cdot s$ in $i\in[m]$ occurs at some $i_s$, and (2) means that the maximum in $s$ of the minima occurs at some $s^*$ (with $i^*=i_{s^*}$). If you have another definition of a solution, you can show it to me, and then we can work from there. Nov 22 '18 at 12:43
• Perfect, now I got it. I missed the fact that expression $(1)$ is the condition on the minimum while $(2)$ ist he one on the maximum. Thank you. Nov 22 '18 at 13:05