Prove that $v(z) := \min \{f (x) | x ∈ X , Ax − b = z\}$ is a convex function

Question

Suppose that $f$ is a convex function and $X$ is a closed convex set. Prove: $v(z) := \min \{f (x) | x ∈ X , Ax − b = z\}$ is a convex function in $z$.

Answer 1

Fix $z, z'$ and $\alpha \in [0,1]$. Let $x \in X$ (resp. $x'\in X$) such that $Ax - b = z$ (resp. $Ax'-b = z'$). Notice that $x_\alpha \colon \!= \alpha x + (1-\alpha) x' \in X$ since $X$ is convex and that $$Ax_\alpha - b = A(\alpha x + (1-\alpha)x') - b = \alpha (Ax - b) + (1-\alpha)(Ax'-b) = \alpha z + (1-\alpha)z'= \colon z_\alpha.$$ Therefore, since $f$ is convex, we get $$\begin{multline*}\alpha f(x) + (1-\alpha)f(x') \geqslant f(\alpha x + (1-\alpha)x') \\= f(x_\alpha)\geqslant \min \{f(x'')| x'' \in X, \, Ax''-b = z_\alpha\} = v(z_\alpha).\end{multline*}$$ Taking the infimum over all $x \in X$ such that $Ax -b =z$, we get $$\alpha v(z) + (1-\alpha) f(x') \geqslant v(z_\alpha).$$ Similarly, taking the infimum over all $x' \in X$ such that $Ax'-b = z'$, we get $$\alpha v(z) + (1-\alpha) v(z') \geqslant v(z_\alpha) = v(\alpha z + (1-\alpha)z'),$$ i.e. the function $v$ is convex.

Answer 2

A function is convex if and only if its epigraph is convex. But the epigraph $$\{(t,z)~:~t\geq v(z)\}$$ is a projection of the set $$\{(t,x, z)~:~t\geq f(x),\ x\in X,\ Ax-b=z\}$$ which is obviously convex.