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).