Convexity of infimum function This question asks about the convexity of the function
$$ g(x)=\inf_{y\in\Re^n} f(x,y) $$
where $f \colon \Re^n \times \Re^m \to \Re$ is convex in $(x,y)$. I would ask a more advanced case that if the set given in the inner minimization problem depends on the upper variable $x$, i.e., $\Re^n$ is replaced by $C(x)$, the convexity still holds? That is, I would know the convexity of the following function $g\colon\Re^n\to\Re$:
$$
g(x)=\inf_{y\in C(x)} f(x,y),
$$
where $C(x)$ is always convex for any $x\in\Re^n$, and $f$ is convex in $(x,y)$.
My question would also be the generalization of Example 3.17 in Boyd & Vandenberghe's Convex Optimization, which is the convexity of the following case:
$$ g(x) = \inf \left\{ h(y) \mid Ay = x \right\}. $$
It would be grateful if you could answer the question above.
Thank you!
 A: No, not in general. The ability to adjust $C(x)$, with only the constraint of convexity of the images, is far too powerful. We could make each $C(x)$ a singleton (which, of course, is convex), but essentially choose $C(x)$ to be any single-valued function we like (non-convex, even totally discontinuous).
As a concrete example, consider:
$$f : \Bbb{R} \times \Bbb{R} : (x, y) \mapsto y$$
and
$$C(x) = \{D(x)\}, \text{ where } D(x) = \begin{cases} 1 & \text{if } x \in \Bbb{Q} \\ 0 & \text{if } x \in \Bbb{R} \setminus \Bbb{Q}.\end{cases}$$
Then
$$g(x) = \inf_{y \in C(x)} f(x, y) = \inf_{y \in C(x)} y = D(x),$$
which is very much not a convex function. You can see how I could adjust $C(x)$ to get any pathological function I wish!
A: As is proved above, the answer is NO.
But it will work if you add the condition $S = \{(x, y)|y\in C(x)\}$ is convex.
I shall give a possible proof for this conclusion for a reference.
From the definition of $g(x)$, we can find $\overline{y}\in C(x)$ for any $\varepsilon > 0$ such that
$$ f(x, \overline{y}) - \varepsilon < g(x) \le f(x, \overline{y}) $$
Now for any $x_1, x_2$ and $\lambda\in(0, 1)$, there exists $\overline{y}_1\in C(x_1)$ and $\overline{y}_2\in C(x_2)$ for any $\varepsilon > 0$ such that
\begin{equation}
    \begin{aligned}
        \lambda g(x_1) + (1 - \lambda)g(x_2) & > \lambda f(x_1, \overline{y}_1) + (1 - \lambda)f(x_2, \overline{y}_2) - \varepsilon \\
        & \ge f(\lambda x_1 + (1 - \lambda)x_2, \lambda \overline{y}_1 + (1 - \lambda)\overline{y}_2) - \varepsilon \\
        & \ge g(\lambda x_1 + (1 - \lambda)x_2) - \varepsilon \\
    \end{aligned}
\end{equation}
where the second inequality is due to the convexity of $f$ and the last inequality is because $S$ is convex so $\lambda \overline{y}_1 + (1 - \lambda)\overline{y}_2 \in C(\lambda x_1 + (1 - \lambda)x_2)$.
The above inequality holds for any $\varepsilon > 0$, which leads to the convexity of $g(x)$.
Note that the convexity of $S$ is just sufficient condition, but not necessary.
A direct example is $f(x, y) = 1$ which is convex and thus $g(x) = 1$ is convex, where $C(x)$, and $S$, can be any arbitrary set.
