Convexity of a complicated function

Solution 1:

$$\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.