0
$\begingroup$

Assume we have three finite sets $A_1, A_2, A_3$. It seems to me that two following optimization problems are equivalent. Am I right? if I am, how can we show that?

$\min_{x_1 \in A_1, x_2 \in A_2, x_3 \in A_3} \max_{i \in \{1,2,3\}} x_i = \max_{i \in \{1,2,3\}} \min_{x_i \in A_i} x_i$


What I have tried:

for any triple $(x_1,x_2,x_3) \in (A_1, A_2, A_3)$ it is true that $\max_{i \in \{1,2,3\}} x_i \geq x_j \quad \forall j \in \{1,2,3\}$. So it still holds when we minimize over $A_1, A_2, A_3$, that is, $\min_{x_1 \in A_1, x_2 \in A_2, x_3 \in A_3} \max_{i \in \{1,2,3\}} x_i \geq \min_{x_j \in A_j} x_j \quad \forall j \in \{1,2,3\}$. Finally, since the last inequality is true for any $j \in \{1,2,3\}$, it is true when me maximize over the right hand side of inequality: $\min_{x_1 \in A_1, x_2 \in A_2, x_3 \in A_3} \max_{i \in \{1,2,3\}} x_i \geq \max_{j \in \{1,2,3\}} \min_{x_j \in A_j} x_j$.

If the above proof is correct, this shows one side. What can we do to show the other side, that is $\min_{x_1 \in A_1, x_2 \in A_2, x_3 \in A_3} \max_{i \in \{1,2,3\}} x_i \leq \max_{j \in \{1,2,3\}} \min_{x_j \in A_j} x_j$?

$\endgroup$
1
$\begingroup$

Since the $\max_{i\in {1,2,3}} x_i$ is non decreasing in each of $x_i$, it is minimized when each of $x_i$ is minimized individually. That is, $$\min_{x_1\in A_1, x_2\in A_2, x_3\in A_3} \max_{i\in {1,2,3}} x_i = \max_{i\in\{1,2,3\}} \min(A_i)\\=\max_{i\in\{1,2,3\}}\min_{x_i \in A_i} x_i.$$

$\endgroup$
  • $\begingroup$ What you have written is exactly the intuition I had why it is correct, but it doesn't seem a formal proof to me. $\endgroup$ – m0_as Mar 5 '17 at 8:11
  • $\begingroup$ Okay. Now after looking at your edit, I understand what kind of solution you are looking for. I'll try if I can prove it that way. $\endgroup$ – biswajitsc Mar 8 '17 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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