= Solution
A function $f:\mathbb R^n\to\mathbb R$ is a <convex function> when
$$
f((1-t)x_0+tx_1)\leq(1-t)f(x_0)+tf(x_1)
$$
for every $x_0,x_1$ and $t\in[0,1]$.
Fix $b_0,b_1\in\mathbb R$, $t\in[0,1]$, and $\varepsilon>0$. Since the <value function> is finite, choose $x_i$ with
$$
g(x_i)\leq b_i,
\qquad
f(x_i)\leq\phi(b_i)+\varepsilon.
$$
For the <convex combination> $x_t=(1-t)x_0+tx_1$, convexity of $g$ gives
$$
g(x_t)\leq(1-t)b_0+tb_1,
$$
so $x_t$ is feasible for the intermediate right-hand side. Convexity of $f$ then gives
$$
\phi((1-t)b_0+tb_1)
\leq f(x_t)
\leq(1-t)\phi(b_0)+t\phi(b_1)+\varepsilon.
$$
Letting $\varepsilon\downarrow0$ proves
$$
\boxed{\phi((1-t)b_0+tb_1)\leq(1-t)\phi(b_0)+t\phi(b_1),}
$$
so \b[$\phi$ is convex.]
Back to article page
