6

Consider a loss funcation $\ell(x,y)$ with a penalty $g(x,y)$

If I want to consider the worst case robust scenario, that is

\begin{equation} \min_x \max_y \ell(x,y) + g(x,y) \end{equation}

Is it equivalent to consider the maximin version

\begin{equation} \max_y \min_x \ell(x,y) + g(x,y) \end{equation}

If yes, does it mean that I can consider the problem as an ordinary optimization problem once

\begin{equation} \min_x \ell(x,y) + g(x,y) \end{equation}

or

\begin{equation} \max_y \ell(x,y) + g(x,y) \end{equation}

has close form solution ?

Rein
  • 1,174
  • What are the assumptions about $\ell,g$? What do you mean by ordinary optimization problem? (These may be silly questions, since I have no experience whatsoever with optimization terminology, but answering those might help others like me help you.) – tomasz Jun 20 '14 at 04:53

1 Answers1

5

In general, if $X$ and $Y$ are non-empty sets and $f:X\times Y\to\mathbb R$, then $$\sup_{x\in X}\inf_{y\in Y}f(x,y)\leq\inf_{y\in Y}\sup_{x\in X}f(x,y)\quad(*)$$ and strict inequality is possible.

For example, let $X=Y=\mathbb R$ and $$f(x,y)=\begin{cases}0&\text{if $x=y$,}\\1&\text{otherwise.}\end{cases}$$ In this case, for any given $x^*\in X$, $f(x^*,x^*)=0$, so $\inf_{y\in Y}f(x^*,y)=0$. Since this is true for all $x^*\in X$, it follows that $\sup_{x\in X}\inf_{y\in Y}f(x,y)=0$, so the left-hand side of $(*)$ vanishes. On the other hand, for any given $y^*\in Y$, $f(y^*+1,y^*)=1$, so $\sup_{x\in X}f(x,y^*)=1$ and this is true for all $y^*\in Y$, so $\inf_{y\in Y}\sup_{x\in X}f(x,y)=1$. In this case, $(*)$ holds strictly.

At any rate, there do exist so-called minimax theorems establishing sufficient conditions on $X$, $Y$, and $f$ for $(*)$ to hold with equality.

To see why $(*)$ holds, suppose that it does not, so that $$\sup_{x\in X}\inf_{y\in Y}f(x,y)>\inf_{y\in Y}\sup_{x\in X}f(x,y).$$ We can derive a contradiction: By the definition of supremum (the least upper bound), there must exist some $x^*\in X$ such that $$\inf_{y\in Y}f(x^*,y)>\inf_{y\in Y}\sup_{x\in X}f(x,y).$$ Similarly, by the definition of infimum (the greatest lower bound), there exists some $y^*\in Y$ such that $$\inf_{y\in Y}f(x^*,y)>\sup_{x\in X}f(x,y^*).\quad(\spadesuit)$$ Also, $$f(x^*,y^*)\geq\inf_{y\in Y}f(x^*,y)\quad(\heartsuit)$$ and $$\sup_{x\in X}f(x,y^*)\geq f(x^*,y^*).\quad(\clubsuit)$$ Putting $(\heartsuit)$, $(\spadesuit)$, and $(\clubsuit)$ together yields $$f(x^*,y^*)\geq\inf_{y\in Y}f(x^*,y)>\sup_{x\in X}f(x,y^*)\geq f(x^*,y^*),$$ which is a contradiction.

triple_sec
  • 23,377
  • 1
    @littleO You're right, it's simpler. Let me rephrase it in a somewhat more transparent notation: \begin{align}f(x^,y^)\leq\sup_{x\in X}f(x,y^),\forall (x^,y^)\in X\times Y\Longrightarrow\inf_{y\in Y}f(x^,y)\leq&,\inf_{y\in Y}\sup_{x\in X}f(x,y),\forall x^\in X\Longrightarrow\\sup_{x\in X}\inf_{y\in Y}f(x,y)\leq&,\inf_{y\in Y}\sup_{x\in X}f(x,y).\end{align*} – triple_sec Jun 20 '14 at 07:06
  • Ah, that notation is better! I'm going to delete my original comment now since your version is more clear. – littleO Jun 20 '14 at 08:12
  • @triple_sec In your proof by contradiction, is there a typo in the way $x^$ and $y^$ are defined? Should equation $(\spadesuit)$ involve a $\sup \inf$ somewhere? – EthanAlvaree Apr 04 '16 at 10:17
  • @EthanAlvaree The way I defined $y^$ via ($\spadesuit$) stems from the inequality one line above (the one already involving $x^$), not from the inequality two lines above (the one with the $\sup\inf$). Maybe I should change the “similarly” so that it doesn’t create the wrong impression. – triple_sec Apr 04 '16 at 16:48