# Show this function is convex.

Could someone point me in the right direction for proving the following?

Given that $f:\mathbb{R}^n\rightarrow \mathbb{R}^m$ is an affine map given by $f(x)=A\mathbf{x}+\mathbf{b}$, $g:\mathbb{R}^m\rightarrow \mathbb{R}$ is convex, and that $g(A\mathbf{x}+\mathbf{b})$ is also convex, prove that $h(x)=\max \{\mathbf{a}_1^T\mathbf{x}+b_1,\mathbf{a}_2^T\mathbf{x}+b_2,\dots,\mathbf{a}_m^T\mathbf{x}+b_m\}$ is a convex function.

I know that $\max\{x_1,x_2,...,x_m\}$ is a convex function, but I am not sure how to use it to prove this. I previously proved that the composition $g\circ f$ is convex.

-
Since you know that $g \circ f$ is convex when $g$ is convex and you know that $\max$ is convex, it then follows that $h=\max \circ f$ is convex. –  copper.hat Nov 30 '12 at 7:50
I guess what is confusing me at this point is that indeed $h=\max \circ f$. –  kaiserphellos Nov 30 '12 at 7:55

$\def\R{\mathbb R}$You know, as you write that $\max\colon \R^n \to \R$ is convex, right. Now for $x,y \in \R^n$ and $\lambda \in [0,1]$ you have $$f\bigl((1-\lambda)x + \lambda y\bigr) = (1-\lambda)f(x) + \lambda f(y)$$ As $f$ is affine ($x \mapsto Ax$ is linear, so this holds and it holds also for the constant part. Knowing this, we apply $\max$, and obtain $$(\mathord\max \circ f)\bigl((1-\lambda)x + \lambda y\bigr) = \max\bigl( (1-\lambda)f(x) + \lambda f(y)\bigr)$$ Can you conlude, using the convexity of $\max$?
Since $\max$ is convex, $\max((1-\lambda)f(x)+\lambda f(y))\leq (1-\lambda)f(x)+ \lambda f(y)$ and so $\max\circ f$ is convex? –  kaiserphellos Nov 30 '12 at 7:40
You omitted two $\max$ on your right hand side, you should have $(1-\lambda)\max f(x)$ and $\lambda\max f(y)$. Otherwise: Exactly. –  martini Nov 30 '12 at 7:41
Right, sorry about that. So $\max\circ f$ is exactly the $h(\mathbf{x})$ defined above then? –  kaiserphellos Nov 30 '12 at 7:43