1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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}

$\endgroup$
  • 1
    $\begingroup$ I have added an explicit counterexample for Question 2. $\endgroup$ – Iosif Pinelis Nov 21 '18 at 15:22
  • $\begingroup$ 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. $\endgroup$ – sigmatau Nov 22 '18 at 7:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Iosif Pinelis Nov 22 '18 at 12:43
  • $\begingroup$ 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. $\endgroup$ – sigmatau Nov 22 '18 at 13:05

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.