If you find any mistakes, please make a comment! Thank you.

## Solution to Mathematics for Machine Learning Exercise 7.4

Consider whether the following statements are true or false:

(a) The sum of any two convex functions is convex.

Solution: True. Let $f_1(\mathbf x)$ and $f_2(\mathbf x)$ be two convex functions. Suppose their domains are $\mathcal C_1$ and $\mathcal C_2$, respectively. Then $\mathcal C_1$ and $\mathcal C_2$ are convex sets, by Definition 7.3. Hence by Exercise 7.3 (a), the intersection $\mathcal C_1\cap \mathcal C_2$ is also convex. Note that $\mathcal C_1\cap \mathcal C_2$ is also the domain of $f_1+f_2$. Hence the domain of  $f_1+f_2$ is convex. Now we only need to check the condition (7.30) in the textbook.

For any $\mathbf x,\mathbf y$ in $\mathcal C_1\cap \mathcal C_2$ and $0\leq \theta \leq 1$, we have\begin{align*}&\ (f_1+f_2)(\theta \mathbf x+(1-\theta)\mathbf y) \\ = &\ f_1((\theta \mathbf x+(1-\theta)\mathbf y))+f_2((\theta \mathbf x+(1-\theta)\mathbf y))\\ \leq &\ \theta f_1(\mathbf x)+(1-\theta)f_1(\mathbf y) +\theta f_2(\mathbf x)+(1-\theta)f_2(\mathbf y)\\ = &\ \theta f_1(\mathbf x) +\theta f_2(\mathbf x)+(1-\theta)f_1(\mathbf y) +(1-\theta)f_2(\mathbf y)\\ = &\ \theta (f_1+f_2)(\mathbf x)+(1-\theta)(f_1+f_2)(\mathbf y).\end{align*}In the inequality, we used equation (7.30) for $f_1$ and $f_2$ as they are convex. Therefore, $f_1+f_2$ is also convex.

(b) The difference of any two convex functions is convex.

I will use the following well-known fact: If $f''(x)\geq 0$ holds for all $x$ in the domain (assumed to be convex) of $f$, then $f(x)$ is convex.

Solution: False. For example, let $f_1(x)=x^2$ and $f_2(x)=2x^2$. Then $f_1$ and $f_2(x)$ are convex, but $$(f_1-f_2)(x)=f_1(x)-f_2(x)=-x^2$$ is not convex. Please fill the details.

(c) The product of any two convex functions is convex.

Solution: False. Let $f_1(x)=x^2$ and $f_2(x)=x$. Then $f_1$ and $f_2(x)$ are convex, but $$(f_1f_2)(x)=f_1(x)f_2(x)=-x^3$$ is not convex. Please fill the details, e.g. use $\theta=1/2$, $x=-1$ and $y=0$ to get a counterexample.

(d) The maximum of any two convex functions is convex.

Solution: True. Let $f_1(\mathbf x)$ and $f_2(\mathbf x)$ be two convex functions. Let $f(x):=\max\{f_1(x),f_2(x)\}$ be the maximum of them. Suppose their domains are $\mathcal C_1$ and $\mathcal C_2$, respectively. Then $\mathcal C_1$ and $\mathcal C_2$ are convex sets, by Definition 7.3. Hence by Exercise 7.3 (a), the intersection $\mathcal C_1\cap \mathcal C_2$ is also convex. Note that $\mathcal C_1\cap \mathcal C_2$ is also the domain of $f(x)$. Hence the domain of  $f(x)$ is convex. Now we only need to check the condition (7.30) in the textbook.

Note that for any $\mathbf x$ in $\mathcal C_1\cap \mathcal C_2$, we have $f_1(\mathbf x)\leq f(\mathbf x)$ and $f_2(\mathbf x)\leq f(\mathbf x)$.

For any $\mathbf x,\mathbf y$ in $\mathcal C_1\cap \mathcal C_2$ and $0\leq \theta \leq 1$, we have\begin{align*}&\ f_1(\theta \mathbf x+(1-\theta)\mathbf y) \\ \leq &\  f_1(\mathbf x)+(1-\theta)f_1(\mathbf y) \\ \leq &\ \theta f(\mathbf x) +(1-\theta)f(\mathbf y).\end{align*}In the inequality, we used equation (7.30) for $f_1$ as it is convex. Similarly, we have $$\ f_2(\theta \mathbf x+(1-\theta)\mathbf y)\leq \theta f(\mathbf x) +(1-\theta)f(\mathbf y).$$Therefore, we have $$f(\theta \mathbf x+(1-\theta)\mathbf y)\leq \theta f(\mathbf x) +(1-\theta)f(\mathbf y).$$Hence $f$ is also convex.

Remark: Here, we used the fact that if $x \leq a$ and $y\leq a$, then $\max\{x,y\}\leq a$.