Convexity of a complicated function Let $\mathbb{S}$ be a $2$-D convex set in the positive quadrant. Let us define 
\begin{align}
y_L=\min_{(x,y)\in\mathbb{S} }y \\
y_R=\max_{(x,y)\in\mathbb{S} }y 
\end{align}
 For any positive number $p\in[p_L,p_R]$ where $p_L=\frac{1}{y_R}$ and $p_R=\frac{1}{y_L}$, define the function 
\begin{align}
f(p)=\min_{(x,y)\in\mathbb{S} }px~,~\text{s.t.}~~py\geq 1
\end{align}
where s.t. means "subject to". What is the nature of $f(p)$? Is it convex or concave?
 A: $$\begin{eqnarray}
f(p) & = & \min_{(x,y)\in\mathbb{S}\text{ s.t. }py\geq1} px \\
& = & \min_{y\geq1/p} \left( \min_{x\text{ s.t. }(x, y)\in\mathbb{S}} px \right) \\
& = & p \min_{y\geq1/p} \left( \min_{x\text{ s.t. }(x, y)\in\mathbb{S}} x \right) \\
& = & p\,h(1/p)
\end{eqnarray}$$
where
$$\begin{eqnarray}
h(y') & = & \min_{y\geq y'} g(y) \\
g(y) & = & \min_{x\text{ s.t. }(x, y)\in\mathbb{S}} x
\end{eqnarray}$$
All dependence of $f$ on $\mathbb{S}$ factors via the functions $g$ and $h$.
Since $\mathbb{S}$ is convex, $g$ is convex, by which I mean that a straight-line function of $y$ can exceed $g(y)$ only in a connected interval of $y$. For any convex function $g'$ in the relevant quadrant, we might have $\mathbb{S} = \left\{ (x,y) \mid x\geq g'(y)\right\}$ and therefore $g = g'$. Therefore we know nothing else about $g$; it is an arbitrary convex function.
$h$ inherits the convexity property, and in addition is non-decreasing. For any convex non-decreasing function $h'$ in the relevant quadrant, we might have $g = h'$ and therefore $h = h'$. Therefore, we know nothing else about $h$; it is an arbitrary non-decreasing convex function.
So what can we say about $f(p) = p\,h(1/p)$? It is easy to fine examples where it decreases and examples where it increases, so we cannot say anything interesting about its monotonicity. However, it is convex, as I will now show.
Suppose, if possible, that $s(p) = mp+c$ is straight line that disproves the convexity of $f(p)$, i.e. there exist at two values $p_1$ and $p_2$ such that $s(p_1) = f(p_1)$ and $s(p_2) = f(p_2)$ but $s(p) < f(p)$ for all $p_1<p<p_2$.
Let $y_1 = 1/p_1$ and $y_2 = 1/p_2$ and define the straight line $t(y) = c'y+m'$ through the points $(y_1, h(y_1))$ and $(y_2, h(y_2))$.
By convexity of $h$, we have $h(y) \leq t(y)$ for $y_2 < y < y_1$.
Therefore, $f(p) = p\,h(1/p) \leq p\,t(1/p)$ for $p_1 < p < p_2$.
Let $u(p) = p\,t(1/p) = m'p + c'$, also a straight line. Since $u(p_1) = s(p_1)$ and $u(p_2) = s(p_2)$, we have $u = s$.
Therefore $f(p) \leq s(p)$ in this range. However, we assumed $s(p) < f(p)$ in this range. This is the required contradiction.
A: I think $f$ has to be convex. Let
$$
\mathbb S=\{(x,y)\mid x\ge 0\text{ and }0\le y\le g(x)\}
$$
where $g$ is increasing and concave. I believe we may assume $\mathbb S$ is of this form, in the sense that $\mathbb S$ is contained in a minimal such set which will have the same function $f$.
Then in terms of $u=1/p$,
$$
u \cdot f(1/u)=\min \{ x : \exists y\ge u\; (x,y)\in\mathbb S\} = g^{-1}(u)
$$
so
$$
f(p)=p\cdot h(1/p)
$$
where $h=g^{-1}$. Since $g$ is concave, $h$ is convex, which implies $f$ is convex:
$$
f'(p)=h(1/p)+p\cdot h'(1/p)\cdot (-p^{-2}) = h(1/p)- h'(1/p)\cdot (p^{-1})
$$
$$
f''(p)=h'(1/p)(-p^{-2}) - h''(1/p)(-p^{-2})\cdot (p^{-1})-h'(1/p)(-p^{-2})
$$
$$
-p^2 f''(p)= h'(1/p) - h''(1/p)\cdot (p^{-1})-h'(1/p) = - h''(1/p)\cdot (p^{-1})
$$
$$
p^3 f''(p) = h''(1/p) > 0
$$
Actually I found this question at MathOverflow, and my answer only deals with the differentiable case. 
