3
$\begingroup$

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.

  • 0
    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.2012-11-30
  • 0
    I guess what is confusing me at this point is that indeed $h=\max \circ f$.2012-11-30

1 Answers 1

2

$\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$?

  • 0
    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?2012-11-30
  • 0
    You omitted two $\max$ on your right hand side, you should have $(1-\lambda)\max f(x)$ and $\lambda\max f(y)$. Otherwise: Exactly.2012-11-30
  • 0
    Right, sorry about that. So $\max\circ f$ is exactly the $h(\mathbf{x})$ defined above then?2012-11-30