11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Alt Feb 6 '14 at 5:20
  • $\begingroup$ 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). $\endgroup$ – dineshdileep Feb 6 '14 at 6:03
  • $\begingroup$ $\mathbb{S}$ can be any 2-D convex shape. $\endgroup$ – dineshdileep Feb 6 '14 at 6:04
  • $\begingroup$ I have deleted an answer I had made, which was false. My apologies. $\endgroup$ – Pierre-Guy Plamondon Feb 6 '14 at 12:20
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "$=\min_{y\geq 1/p}(...)$" what is $y$ in the outer minimization? It is very easy to show that this equality doesn't hold. $\endgroup$ – Alt Feb 7 '14 at 3:03
  • $\begingroup$ @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. $\endgroup$ – dineshdileep Feb 7 '14 at 4:23
  • $\begingroup$ @apt1002 I am working on verifying your proof. Did you mean $h$ is non-decreasing in $p$ or $y$? $\endgroup$ – dineshdileep Feb 7 '14 at 4:25
  • $\begingroup$ @apt1002 and dineshdileep: You are right! sorry I had misunderstood the notation. $\endgroup$ – Alt Feb 7 '14 at 4:47
  • $\begingroup$ $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. $\endgroup$ – apt1002 Feb 11 '14 at 17:34
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "where $g$ is strictly increasing and concave" - please can you explain why? $\endgroup$ – apt1002 Feb 11 '14 at 17:49
  • $\begingroup$ "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. $\endgroup$ – apt1002 Feb 11 '14 at 17:52
  • $\begingroup$ I think maybe it would be clear if you defined $g$ for an arbitrary $\mathbb{S}$. $\endgroup$ – apt1002 Feb 11 '14 at 18:10
  • $\begingroup$ actually it's just increasing, not strictly increasing $\endgroup$ – Bjørn Kjos-Hanssen Feb 11 '14 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.