Finding subgradients

Question

How would I find the subgradients of this :

$$ f(x) = \max_{i=1,\ldots,n} a_i^Tx + b_i$$

I'm new to subgradients and any hint on how to start this would be useful for me.

Answer 1

Let $I(x) = \{ i \mid a_i^T x + b_i = f(x) \}$. So $I(x)$ is the set of "active" indices.

Then \begin{equation*} \partial f(x) = \textbf{conv} \, \{ a_i \mid i \in I(x) \}. \end{equation*}

This is discussed in chapter 4 ("subgradients") of Vandenberghe's 236c notes. See slide 4-16.