Exercise 1.2 (Sum of convex functions)

Question

Suppose that $f_1,\ldots,f_m$ are convex functions from $\mathfrak{R}^n$ into $\mathfrak{R}$ and let $f(\mathbf{x}) = \sum_{i=1}^{m} f_i(\mathbf{x})$.
\begin{enumerate}[label=(\alph*)]
\item Show that if each $f_i$ is convex, so is $f$.
\item Show that if each $f_i$ is piecewise linear and convex, so is $f$.
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item \begin{proof}
Let $\mathbf{x},\mathbf{y} \in \mathfrak{R}^n$ and $\lambda \in [0,1]$. By convexity assumption on each of $f_i$, we have
\begin{align*}
f\left(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\right)
&= \sum_{i=1}^{m} f_i\left(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\right)\[5pt]
&\leq \sum_{i=1}^{m} \lambda f_i\left(\mathbf{x}\right)+(1-\lambda)f_i\left(\mathbf{y}\right)\[5pt]
&= \lambda \sum_{i=1}^{m} f_i\left(\mathbf{x}\right)+(1-\lambda)\sum_{i=1}^{m} f_i\left(\mathbf{y}\right)\[5pt]
&= \lambda f\left(\mathbf{x}\right) + (1-\lambda) f\left(\mathbf{y}\right).
\end{align*}
\end{proof}

\item \begin{proof}
We induct on the number of functions $m$. The base case $m=1$ is trivial. Now assume inductively that we have proven the theorem assertion for some $m \in \mathfrak{N}$. We then have
\begin{align*}
f\left(\mathbf{x}\right)
&= \sum_{i=1}^{m+1} f_i\left(\mathbf{x}\right)
= \sum_{i=1}^{m} f_i\left(\mathbf{x}\right) + f_{m+1}\left(\mathbf{x}\right)
\end{align*}
By definition, we can write $f_{m+1}(\mathbf{x}) = \max_{j=1,\ldots,k'} \left(\mathbf{f}_j'\mathbf{x} + g_j\right)$ for some vectors $\mathbf{f}_1,\ldots,\mathbf{f}_{k'}$ and scalars $g_1,\ldots,g_{k'}$. At this point, we can employ the induction hypothesis and find some $\mathbf{c}_1,\ldots,\mathbf{c}_{k}\in\mathfrak{R}^n$ and $d_1,\ldots,d_{k} \in \mathfrak{R}$ such that $\sum_{i=1}^{m} f_i(\mathbf{x}) = \max_{i=1,\ldots,k} (\mathbf{c}_i'\mathbf{x} + d_i)$. We then have
\begin{align*}
f\left(\mathbf{x}\right) &= \max_{i=1,\ldots,k} \left(\mathbf{c}_i'\mathbf{x} + d_i\right) + \max_{j=1,\ldots,k'} \left(\mathbf{f}_j'\mathbf{x} + g_j\right)
\end{align*}
Using the fact that $\max_i a_i + \max_j b_j = \max_{ij} a_i + b_j$, we obtain
\begin{align*}
f\left(\mathbf{x}\right) &= \max_{i=1,\ldots,k;\,j=1,\ldots,k'} \left(\mathbf{c_i}'+\mathbf{f_j}'\right)\mathbf{x} + \left(d_i + g_j\right)
\end{align*}
Enumerating all tuples $(i,j)$ and renaming the (at most $k\cdot k'$) vectors and scalars, we see that $f$ is piecewise convex linear \textit{per definitionem}. This closes the induction.
\end{proof}
\end{enumerate}

Exercise 1.2 (Sum of convex functions)

Answers

Comments

Exercise 1.2 (Sum of convex functions)

Answers

Comments

Add answer