# 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?

• Is $S\subset R^2$? Or just the positive orthant? Specially sign of $y$ is important because first $\frac{1}{0}$ is not defined, secondly, I think you should constrain $p$ in the following form: $p\in [\min(p_L,p_R),\max(p_L,p_R)]$, unless you know $y<0$. A last question is about $S$, do you have idea about the shape of this convex set, for example, is it an ellipsoid or a polyhedron? – Alt Feb 6 '14 at 5:20
• You can assume $\mathbb{S}$ is always a subset of the positive quadrant (all co-ordinates are strictly positive), as I already said in the question (first line). – dineshdileep Feb 6 '14 at 6:03
• $\mathbb{S}$ can be any 2-D convex shape. – dineshdileep Feb 6 '14 at 6:04
• I have deleted an answer I had made, which was false. My apologies. – Pierre-Guy Plamondon Feb 6 '14 at 12:20

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

• "$=\min_{y\geq 1/p}(...)$" what is $y$ in the outer minimization? It is very easy to show that this equality doesn't hold. – Alt Feb 7 '14 at 3:03
• @Alt I am somehow convinced with that line. Can you show why that doesn't hold?. I think what he meant is that you fix $y$ and then select the best $x$. Now you do this over all $y$ and you will get the solution. – dineshdileep Feb 7 '14 at 4:23
• @apt1002 I am working on verifying your proof. Did you mean $h$ is non-decreasing in $p$ or $y$? – dineshdileep Feb 7 '14 at 4:25
• @apt1002 and dineshdileep: You are right! sorry I had misunderstood the notation. – Alt Feb 7 '14 at 4:47
• $h$ is non-decreasing in its argument, be it $y$, $y'$ or $1/p$. Please tell me which parts of the proof you would like me to expand, and I will improve my answer. – apt1002 Feb 11 '14 at 17:34

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.

• "where $g$ is strictly increasing and concave" - please can you explain why? – apt1002 Feb 11 '14 at 17:49
• "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$" - again, please can you explain why? I think you need an argument that starts from an arbitrary $\mathbb{S}$, computes $f$, and then shows how to construct an equivalent $\mathbb{S}'$ of the form you want. – apt1002 Feb 11 '14 at 17:52
• I think maybe it would be clear if you defined $g$ for an arbitrary $\mathbb{S}$. – apt1002 Feb 11 '14 at 18:10
• actually it's just increasing, not strictly increasing – Bjørn Kjos-Hanssen Feb 11 '14 at 18:26