5

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!

Rodrigo de Azevedo
  • 20,693
  • 5
  • 43
  • 100
Keith
  • 83
  • 7

2 Answers2

5

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!

Theo Bendit
  • 47,913
  • 3
  • 46
  • 99
  • Thank you so much for the answer! If I add the following assumptions of the set $C(x)$, what happened? 1. compactness, 2. continuity – Keith Dec 24 '21 at 07:32
  • 2
    Nice answer. I want to add, that the condition that the set $\{(x,y) , y\in C(x)\}$ is convex leads to a positive result (and applies to the concrete case of the OP). – Dirk Dec 24 '21 at 07:33
  • @Dirk I appreciate your comment. I would like to know the reason why. – Keith Dec 24 '21 at 08:10
  • 1
    @Keith The convexity of $S = \{(x, y)|y\in C(x)\}$ is a sufficient but not necessary condition for the convexity of $g(x)$. I have given a proof in my answer. – Zieac Dec 24 '21 at 08:28
  • @Keith My example already has compact images. If you want a counterexample with continuity, replace $D(x)$ with a non-convex continuous function on $\Bbb{R}$, e.g. $D(x) = -x^2$. – Theo Bendit Dec 24 '21 at 09:39
  • @Dirk Indeed. This corresponds to adding the convex indicator function $\iota_S$ (i.e. the function that is $0$ on $S$, and $\infty$ elsewhere) to the function $f$. The original result applies to $f + \iota_S$, and so the new result holds. – Theo Bendit Dec 24 '21 at 09:42
  • @Zieac An example could (slightly less straightforwardly) be created by substituting $D$ in my example for a convex function, e.g. $D(x) = x^2$. The resulting $g(x) = x^2$ is convex, but the set $S$ is the graph (not the epigraph) of the function $D(x) = x^2$. This is not a convex set! – Theo Bendit Dec 24 '21 at 09:44
  • @TheoBendit Yes. We can just use arbitrary $D(x)$. The idea of considering $C(x)$ as a singleton is quite smart! – Zieac Dec 24 '21 at 10:11
4

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.

Zieac
  • 501
  • 2
  • 6