= Solution
Write $a_i^T$ for row $i$ of $A$, and define affine functions
$$
\ell_0(x)=c^Tx,
\qquad
\ell_i(x)=(c+Ma_i)^Tx-Mb_i
\quad(1\leq i\leq m).
$$
Then
$$
f(x)=\max_{0\leq i\leq m}\ell_i(x).
$$
The <pointwise maximum of convex functions> is convex, so $f$ is a <convex function>. Moreover,
$$
|f(x)-f(y)|
\leq L\lVert x-y\rVert_2,
\qquad
L=\max\left\{\lVert c\rVert_2,
\max_i\lVert c+Ma_i\rVert_2\right\},
$$
so $f$ has <Lipschitz continuity>. The simpler bound $L\leq\lVert c\rVert_2+M\max_i\lVert a_i\rVert_2$ is also valid.
Let $I(x)=\{i:\ell_i(x)=f(x)\}$ be the active set. The <subdifferential> is
$$
\partial f(x)=
\operatorname{conv}\left(
\{c:0\in I(x)\}\cup
\{c+Ma_i:i\in I(x),\ i\geq1\}
\right),
$$
the <convex hull> of all active slopes. In particular, choosing any active index gives the <subgradient>
$$
g(x)=
\begin{cases}
c,&0\in I(x),\\
c+Ma_j,&j\in I(x),\ j\geq1.
\end{cases}
$$
At a tie, every convex combination of the tied slopes is also valid.
Back to article page
