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.
Best Answer
$\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$?