3
$\begingroup$

Let $X$ and $Y$ be two nonempty sets and let $h:X\times Y\rightarrow \mathbb{R}$ have a bounded range in $\mathbb{R}$.Let $f:X\rightarrow \mathbb{R}$ and $g:Y\rightarrow \mathbb{R}$ defined by $f(x)=\sup\{h(x,y):y\in Y\}$ and $g(y)=\inf\{h(x,y):x\in X\}$Then can we prove that $\sup\{g(y):y\in Y\} \leq \inf\{f(x):x\in X\}?$

  • 0
    This is related to the weak duality inequality in convex optimization, with $ h $ corresponding to the Lagrangian and $ f $ and $ g $ corresponding to the primal and dual objective functions.2015-11-07

3 Answers 3

5

If $A$ and $B$ are bounded subsets of $\mathbb R$, then $\sup A\leq \inf B$ is equivalent to the statement that for all $a\in A$ and $b\in B$, $a\leq b$. Thus, it suffices to show that for each $x\in X$ and $y\in Y$, $g(y)\leq f(x)$.

Let $x_0\in X$ and $y_0\in Y$ be fixed but arbitrary. Then $g(y_0)\leq h(x_0,y_0) \leq f(x_0)$.

2

Clearly $g(y)=\inf_{x\in X} h(x,y)\le h(x,y)\le \sup_{y\in Y}h(x,y)\le f(x)\ \forall x\in X,y\in Y$ Then $g(y)\le \inf_{x\in X} f(x)\le f(x)\ \forall y\in Y$ and so $g(y)\le \sup_{y\in Y}g(y)\le \inf_{x\in X} f(x)$

  • 0
    Yes. +1 now. ${}$2012-12-27
0

$g(y)\leq f(x)$ $\forall$ $x\in X,y\in Y\implies g(y)\leq \inf\{f(x):x\in X\}$ $\forall$ $y\in Y\implies$$\sup\{g(y):y\in Y\} \leq \inf\{f(x):x\in X\}$