# Convex functions and Hahn-Banach application

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!

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).
• 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? – N-7 Aug 16 '13 at 8:30
• @N-7 Yes, but you can also do it more directly: solve the linear equation $\psi(a)=\beta$ for variable $z\in\mathbb R$. – user90090 Aug 16 '13 at 19:09
• 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. – N-7 Aug 19 '13 at 4:56
• 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))$. – N-7 Aug 19 '13 at 13:49