Proof of infimum of a convex function being convex In Boyd's convex optimization book, he gave this proof. I'm not sure how did he claim that
$f(x_i, y_i) \leq g(x_i) + \epsilon$
And how does it relate to Jensen's Inequality.
 A: Short version : Assumes $\sup_{y\in C} f(x,y) = \infty$
$f$ is convex, and therefore continuous. Since $g(x)$ is the infimum of $f(x,y)$ over all $y$, we know $f(x,y) \geq g(x)$ for all $y\in C$. But by continuity of $f$ that means that $f(x,y)$ takes on all values in $(g(x),g(x)+\epsilon)$ (intermediate value theorem)
Hence, $\exists y_1,y_2 \in C: f(x,y_1),f(x,y_2) \in (g(x),g(x)+\epsilon)\;\;\square$

Longer discussion: More details and handle case where $\sup_{y\in C} < \infty$
By definition, we know that for $f,C$ convex, $f(x,y) \geq g(x)\;\forall y \in C$ and that $f$ is continuous; therefore $f(x,y)$ is a univariate convex function of $y$ for any $x$.
Let $m(x) = \sup_{y \in C} f(x,y)$. Clearly $m(x) \geq g(x)$.
For $\epsilon > 0$, by the continuity of $f$ we see:
$$\exists c\in C: f(x,c) \leq \min (g(x)+\epsilon,m(x)) \leq g(x)+\epsilon$$
So we see that $g(x)\leq f(x,c) \leq g(x) + \epsilon$
Let $y_x^* = k:\lim_{y\to k} f(x,k) = g(x)$
Then
$$f(x,y) \in \Big(g(x),f(x,c)\Big] \;\;\forall y \in (y^*_x,c] $$
$(y^*_x,c]$ has a continuum of points, so we can definitely find two of them.
