Each map $x\mapsto\langle a_i,x\rangle+b_i$ is an <affine function>. For $0\leq t\leq1$, the <pointwise maximum of convex functions> satisfies
$$
\begin{aligned}
f(tx+(1-t)y)
&=\max_i\{t(\langle a_i,x\rangle+b_i)+(1-t)(\langle a_i,y\rangle+b_i)\}\\
&\leq t f(x)+(1-t)f(y),
\end{aligned}
$$
so $f$ is <convex>.

A vector $g$ is a <subgradient> of a <convex function> $f$ at $x$ when
$$
f(y)\geq f(x)+\langle g,y-x\rangle
$$
for every $y$. Choose any active index $j\in I(x):=\{i:f(x)=\langle a_i,x\rangle+b_i\}$. Then
$$
f(y)\geq\langle a_j,y\rangle+b_j
=f(x)+\langle a_j,y-x\rangle,
$$
and hence $\boxed{a_j\in\partial f(x)}$. More generally, every <convex combination> of the active vectors is a subgradient, and in fact
$$
\partial f(x)=\operatorname{conv}\{a_i:i\in I(x)\}.
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 339 / 1 / a / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-339/1/a/solution