0
$\begingroup$

I am trying to solve the following problem:

$$\min_{(x,y) \in \mathcal{D}}f(x,y) = \min_{(x,y) \in \mathcal{D}} \max_{x,y}(f_1(x,y), f_2(x,y), f_3(x,y))$$ So the max function is a pointwise maximum of the three functions, and I want to calculate the minimum possible location $(x^*,y^*)$ (and therefore value) of this pointwise maximum on some domain $\mathcal{D}$. The domain here is $[-1,1] \times [-1,1]$. The specific functions in this case are: $$f_1(x,y) = |1 -y||1-x|, f_2(x,y) = |1 + y||1+x|, f_3(x,y) = |\frac{x+y}{2} -y||\frac{x+y}{2} -x| $$

The problem I am having is that calculating the max function itself is difficult and I know it's not the expected way to solve the problem. I think there is some shortcut to discovering how to calculate the minimum location $(x^*,y^*)$, but I am not experienced enough to find it.

If it helps at all, the solution to locate the minimum point is where $f_1(x,y) = f_2(x,y) =f_3(x,y)$, but I no idea how this conclusion was reached and can't seem to work backwards from there either. Using the domain given, this leads to $(x^*,y^*) = (\pm \sqrt{\frac{1}{2}}), \mp \sqrt{\frac{1}{2}})$.

Any help would be greatly appreciated. Thanks!

$\endgroup$
1
$\begingroup$

The conclusion that $f_1(x,y)=f_2(x,y)=f_3(x,y)$ in optimum can be argued by showing that if $f_i(x,y)>\max\{f_j(x,y), f_k(x,y)\}$ ($i,j,k$ is a permutation of $1,2,3$), then we can always find some $(x',y')$ in the neighborhood of $(x,y)$ such that $f_i(x,y)>f_i(x',y')>\max\{f_j(x',y'), f_k(x',y')\}$, which then implies that $(x,y)$ does not achieve the minimum in your problem.

The argument should not be difficult, but is just a little bit mass. A straightforward way is to consider the partial derivatives of each of the three functions (notice that the absolute value sign in $f_1$ and $f_2$ can be dropped for free, while $f_3(x,y)$ can be rewritten as $(x-y)^2/4$, by which all three are actually smooth and calculus works).

For example, we argue that it is impossible to have \begin{equation}f_1(x,y)>\max\{f_2(x,y), f_3(x,y)\}\end{equation} in optimum. To this end, let $A=f_1(x,y)$ and $B=\max\{f_2(x,y), f_3(x,y)\}$, where $A>B$, and we denote $\theta=A-B$. It is clear that $A>B\ge 0$, which then implies that $x,y<1$, and thus there exists some $\delta>0$ such that $\max\{x,y\}+\varepsilon<1$ for all $\varepsilon\in (0,\delta)$. Since $$\frac{\partial f_1}{\partial x}=y-1<0,\,\,\,\,\,\frac{\partial f_2}{\partial y}=x-1<0,$$ it is clear that for all $\varepsilon\in (0,\delta)$, $f_1(x+\varepsilon, y+\varepsilon)<f_1(x,y)$. Also, since all three functions are continuous, there exists some $\delta'>0$ such that for all $(x',y')$ that are at most $\delta'$-distant from $(x,y)$, $|f_i(x',y')-f_i(x,y)|<\theta/3$, $i=1,2,3$. Therefore, pick $x''=x+\min\{\delta, \delta'\}/\sqrt 2$ and $y''=y+\min\{\delta, \delta'\}/\sqrt 2$. We thus have $$f_1(x'',y'')>f_1(x,y)-\frac{\theta}{3}>\max\{f_2(x,y), f_3(x,y)\}+\frac\theta 3\ge\max\{f_2(x'', y''), f_3(x'', y'')\}$$ while $$f_1(x'',y'')<f_1(x,y),$$ showing that $(x,y)$ fails to achieve the optimum to the minmax problem.

$\endgroup$
  • $\begingroup$ Thanks a lot for the answer! Can you elaborate/provide a reference for how to show the three functions must be equal? I am wondering how you came up with the argument (This is the first optimization style problem I have ever done) $\endgroup$ – Slade Mar 3 at 6:05
  • 1
    $\begingroup$ @Slade Ok, I provided all details for showing that $f_1(x,y)>\max\{f_2(x,y), f_3(x,y)\}$ is impossible in optimum. You can mimic it and show that $f_2(x,y)>\max\{f_1(x,y), f_3(x,y)\}$ and $f_3(x,y)>\max\{f_1(x,y), f_2(x,y)\}$ are also impossible in optimum. Then the desired conclusion follows. $\endgroup$ – OnoL Mar 3 at 9:35
  • $\begingroup$ How come the second to last inequality you wrote isn't strict? $\endgroup$ – Slade Mar 3 at 12:53
  • 1
    $\begingroup$ @Slade It might be, but there is no need to make this sure as weak inequality is already good enough for our conclusion. Also, even if it is strict, it is also true to put it weak, i,e., $a>b$ always implies $a\ge b$. $\endgroup$ – OnoL Mar 3 at 14:41
  • $\begingroup$ Okay got it, thanks! Last thing, what is the partial derivative approach? I have taken the partial derivatives of the 3 functions and set them equal to $0$, but don't seem to find any conclusive info from that. The conditions that result are: (from $f_1$ to $f_3$ order) $x = y = 1$, $x = y = -1$, and $x = y$. But I am not sure how to interpret this since the other approach leads to $x = -y$. $\endgroup$ – Slade Mar 3 at 16:11

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.