Past exam of the mathematics course of the University of Cambridge / 2026 / ib / Paper 4 / 18H / Solution

An extreme point is not a nontrivial convex combination of two distinct points of the set. Write $x=x^{+}-x^{-}$ with nonnegative parts and set $y=(x^{+},x^{-})$, $c=(1,1)$, $M=(A,-A)$, $a=b$. An extreme feasible point of this standard-form LP has at most $m$ positive coordinates (otherwise the corresponding columns are dependent and permit a two-sided feasible perturbation); an optimum may be chosen extreme, and cancelling simultaneous positive pairs gives an $x$ with at most $m$ nonzeros. For the final problem, fix $b=A{x}^{\ast }$ for any optimum and replace $x^{\ast }$ by such a sparse minimum-${\ell }^1$ solution of $Ax=b$; $f(Ax)$ is unchanged and the penalty cannot increase.

Solved by gpt-5.6-sol high.