1
$\begingroup$

Let $Z$ be a convex subset of a real vector space, and $f:Z \to \mathbb{R}^m$ be such that every component $f_i:Z \to \mathbb{R}$ is a convex function. Let $S:\mathbb{R}^m \to \mathbb{R}$ be defined as $$S(y) = \max\{y_1,\ldots,y_m\}.$$ Show that there exists a linear functional $\phi:\mathbb{R}^m \to \mathbb{R}$ such that for all $y \in \mathbb{R}^m$, $$\phi(y) \leq S(y)$$ and $$\inf_{z \in Z} \phi(f(z)) \geq \inf_{z \in Z} S(f(z)).$$

The case when $\inf_{z \in Z} S(f(z)) = -\infty$ is immediate, since any linear functional $\phi$ will satisfy this. But when $\inf_{z \in Z} S(f(z)) = \alpha > -\infty$, then it isn't so straightforward. Apparently the strategy is to apply the Hahn-Banach theorem to the functional $T:\mathbb{R}^m \to \mathbb{R}$ defined by $$T(y) = \inf_{\lambda \geq 0} \inf_{z \in Z} \{S(y + \lambda f(z)) - \lambda \alpha\}.$$ I've shown that $T(y) \leq S(y)$ and that $T$ satisfies the hypotheses of the Hahn-Banach theorem, so we get some linear $\phi$ such that $\phi(y) \leq T(y)$. But from here I don't know how to proceed to show that $\inf_{z \in Z} \phi(f(z)) \geq \inf_{z \in Z} S(f(z))$. Any ideas? Thanks!

$\endgroup$
1
$\begingroup$

I usually think of such problems in terms of separating the graphs of functions with a hyperplane. More precisely, let $$\begin{split}A&=\{(y,z)\in\mathbb R^m\times \mathbb R:z> S(y)\} \\ B&=\{(y,z)\in\mathbb R^m\times \mathbb R: y\in f(Z), z\le \inf_{f(Z)}S\} \end{split}$$ The existence of $\phi$ will follow if we can separate $A$ from $B$ with a hyperplane. These sets are disjoint, and $A$ is convex. Unfortunately, $B$ is not necessarily convex, so we take its convex hull, which is
$$ C=\{(y,z)\in\mathbb R^m\times \mathbb R: y\in \operatorname{conv}(f(Z)), z\le \inf_{f(Z)}S\} $$ Now the problem reduces to showing that $A\cap C=\varnothing$; after that the Hahn-Banach separation theorem can be applied. In other words, we must prove that $$\inf_{\operatorname{conv}(f(Z))}S = \inf_{f(Z)}S \tag1$$ This is a neat and attractive statement, isn't it? Better yet, it's true. Indeed, let $y_0$ be a convex combination of $ f(z_1),\dots, f(z_n)$ for some $z_1,\dots,z_n\in Z$ (subscripts are not coordinates here). Let $z^*$ be the convex combination of $z_1,\dots,z_n$ with the same coefficients. The convexity of the components of $f$ implies that $f(z^*)\le y_0$ componentwise. Hence $$S(y_0)\ge S(f(z^*))\ge \inf_{f(Z)}S$$ which proves (1).

$\endgroup$
  • $\begingroup$ To clarify, Hahn-Banach guarantees a linear $\psi$ such that $\psi(a) < \beta \leq \psi(c)$ for $a \in A, c \in C$. I'm guessing the separating hyperplane is defined using $\psi$, and $\phi$ is defined using the hyperplane? $\endgroup$ – N-7 Aug 16 '13 at 8:30
  • $\begingroup$ @N-7 Yes, but you can also do it more directly: solve the linear equation $\psi(a)=\beta$ for variable $z\in\mathbb R$. $\endgroup$ – user90090 Aug 16 '13 at 19:09
  • $\begingroup$ You're right, that's much more direct. Now it remains to argue that for all $z \in Z, x < \alpha$, then $\psi(f(z),x) > \beta$. I'm convinced it's true but maybe I'm missing something obvious to prove it. $\endgroup$ – N-7 Aug 19 '13 at 4:56
  • $\begingroup$ @N-7 I don't understand the statement you are trying to argue for. $\endgroup$ – user90090 Aug 19 '13 at 12:45
  • $\begingroup$ We need to show that $\inf_{z \in Z} \phi(f(z)) \geq \inf S(f(z)) = \alpha$. We've defined $\phi(y)=x \iff \psi(y,x)=\beta$. So I think we need to show that we can't have $\psi(f(z),x) = \beta$ when $x < \alpha$. Otherwise we would have $\inf_{z \in Z} \phi(f(z)) \leq \phi(f(z))=x < \alpha = \inf_{z \in Z} S(f(z))$. $\endgroup$ – N-7 Aug 19 '13 at 13:49

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.