0

Suppose you have two functions $f:\mathbb{R}^2\mapsto\mathbb{R}$, $g:\mathbb{R}^2\times\mathcal{A}\mapsto\mathbb{R}$, where $\mathcal{A}$ is a convex set $\mathcal{A}\subseteq\mathbb{R}^2$, and $r\in\mathbb{R}^2$ is some arbitrary but known point in space. Does $$sup_{\boldsymbol{x}}\{f(\boldsymbol{x})-sup_{\boldsymbol{y}\in\mathcal{A}}\{g(\boldsymbol{x},\boldsymbol{y}) \} \} = sup_{\boldsymbol{x},\boldsymbol{y}\in \mathcal{A}}\{ f(\boldsymbol{x}) - g(\boldsymbol{x},\boldsymbol{y}) \}$$ hold? For example $$sup_{\boldsymbol{x}}\{\boldsymbol{x}^T\boldsymbol{r}-sup_{\boldsymbol{y}\in \mathcal{A}}\{ \boldsymbol{x}^T\boldsymbol{y}\} \} = sup_{\boldsymbol{x},\boldsymbol{y}\in \mathcal{A}}\{ \boldsymbol{x}^T\boldsymbol{r} - \boldsymbol{x}^T\boldsymbol{y}\}$$ ? So that if $\mathcal{A}=\{\boldsymbol{y}\in\mathbb{R}^2 | A\boldsymbol{y}\leq\boldsymbol{b}\}$ is a convex polyhedron, then $$sup_{\boldsymbol{x}}\{\boldsymbol{x}^T\boldsymbol{r}-sup_{\boldsymbol{y}}\{ \boldsymbol{x}^T\boldsymbol{y}:A\boldsymbol{y}\leq\boldsymbol{b}\} \} = sup_{x,y}\{ \boldsymbol{x}^T\boldsymbol{r} - \boldsymbol{x}^T\boldsymbol{y}:A\boldsymbol{y}\leq\boldsymbol{b}\}?$$ Can I do this? I think this question is somewhat related to this question but here, the problem involves not only one function.

EDIT: In this thread the rules for supremum and infimum used in LinAlgs answer are discussed. Also, the book "Lojasiewicz, S. (1988). An Introduction to the Theory of Real Functions. John Wiley & Sons, Inc." is referenced, where further rules/properties can be found in the introduction.

link
  • 128

1 Answers1

0

Does $$\sup_{\boldsymbol{x}}\{f(\boldsymbol{x})-\sup_{\boldsymbol{y}\in\mathcal{A}}\{g(\boldsymbol{x},\boldsymbol{y}) \} \} = \sup_{\boldsymbol{x},\boldsymbol{y}\in \mathcal{A}}\{ f(\boldsymbol{x}) - g(\boldsymbol{x},\boldsymbol{y}) \}$$ hold?

No. You have $$\sup_{\boldsymbol{y}\in\mathcal{A}}\{g(\boldsymbol{x},\boldsymbol{y})=-\inf_{\boldsymbol{y}\in\mathcal{A}}\{-g(\boldsymbol{x},\boldsymbol{y})\},$$ so $$\sup_{\boldsymbol{x}}\{f(\boldsymbol{x})-\sup_{\boldsymbol{y}\in\mathcal{A}}\{g(\boldsymbol{x},\boldsymbol{y}) \} \} = \sup_{\boldsymbol{x}}\{f(\boldsymbol{x})+\inf_{\boldsymbol{y}\in\mathcal{A}}\{-g(\boldsymbol{x},\boldsymbol{y}) \} \} = \sup_{\boldsymbol{x}}\inf_{\boldsymbol{y}\in\mathcal{A}}\{f(\boldsymbol{x}) -g(\boldsymbol{x},\boldsymbol{y}) \}.$$ If you want $\sup \sup$, you can apply LP duality to $y$.

You can also apply the same steps in a different order: $$\sup_{\boldsymbol{x}}\{f(\boldsymbol{x})-\sup_{\boldsymbol{y}\in\mathcal{A}}\{g(\boldsymbol{x},\boldsymbol{y}) \} \} =\sup_{\boldsymbol{x}} \{-\sup_{\boldsymbol{y}\in\mathcal{A}}\{-f(\boldsymbol{x})+g(\boldsymbol{x},\boldsymbol{y}) \} \} = \sup_{\boldsymbol{x}}\inf_{\boldsymbol{y}\in\mathcal{A}}\{f(\boldsymbol{x}) -g(\boldsymbol{x},\boldsymbol{y}) \}.$$

LinAlg
  • 19,822
  • Thank you for your response. I don't understand why you need to use the relation $sup{(\cdot)}=-inf{-( \cdot )}$ here? Why are you not allowed to combine the first expression in your second equation, but you can combine them after you used that said relationship which expresses the same thing since equality holds for the inf-sup relationship? – link Oct 21 '20 at 08:36
  • @link it has to do with the minus sign. You can only move sup or inf if there is a + in front of it. Let me give a small example on $\mathbb{R}$: Take $f(x) = -x^2$ and $g(x,y) = -y^2$, then $\sup_x { f(x) - \sup_y (-y^2) } = 0$. However, $\sup_x \sup_y x^2 + y^2 = \infty$. – LinAlg Oct 21 '20 at 12:53
  • can you give a resource which explains why that is the case or which gives other rules for these types of problems? I understand your example, even though I think you mean $sup_x sup_y -x^2+y^2$ which has neither minimum nor maximum, but the general rule is not at all obvious to me. I always think of a difference as a special case of addition which is why this confuses me. – link Oct 21 '20 at 13:08
  • @link perhaps a book in calculus. I think the only rules used here are (1) $\sup_x f(x) = -\inf_x -f(x)$, (2) $c + \sup_x f(x) = \sup_x { c + f(x) }$. You can apply those two rules in any order (I have expanded my answer to apply them in the other order as well). – LinAlg Oct 21 '20 at 13:33
  • Thank you very much. I think I also found a resource: Lojasiewicz, S. (1988). An Introduction to the Theory of Real Functions. John Wiley & Sons, Inc. Took a while to figure out what to search for. – link Oct 21 '20 at 14:04