Under what conditions is the following set convex?

Question

Consider two real-valued function $f_1$ and $f_2$ of two real variables (continuous, or even differentiable, if you like). I would like to find conditions on $f_1$ and $f_2$ that guarantee that the following set is convex: $$Y = \left\{\right (y_1, y_2)\in \mathbb{R}^2: \exists(x_1,x_2) \in \mathbb{R}^2\, s.t.\, y_1 \leq f_1(x_1, x_2),\, y_2 \leq f_2(x_1, x_2)\}$$

Does concavity of the $f_i$ suffice? If this is the case, I would very much appreciate an explanation or a reference.

I am also interested in the case in which $x_1$ and $x_2$ are restricted to be non-negative numbers.

Answer 1

Yes, concavity of both $f_i$ is sufficient for $Y$ to be convex: If $(y_1,y_2)\in Y$ is witnessed by $(x_1,x_2)$ and $(y_1',y_2')\in Y$ is witnessed by $(x_1',x_2')$, then for their convex combination $(ty_1+(1-t)y_1',ty_2+(1-t)y_2')$, $0\le 1\le 1$, we have $$ty_i+(1-t)y_i'\le tf_i(x_1,x_2)+(1-t)f_i(x_1',x_2')\le f_i(tx_1+(1-t)x_1',tx_2+(1-t)x_2').$$ Apparently, we can replace $(x_1,x_2)\in\Bbb R^2$ with $\mathbf x\in C$ for any convex set $C$.