Convexity of infimum function

Question

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!

Answer 1

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!

Answer 2

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.