13
$\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$
4
  • $\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, 2014 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$ Feb 6, 2014 at 6:03
  • $\begingroup$ $\mathbb{S}$ can be any 2-D convex shape. $\endgroup$ Feb 6, 2014 at 6:04
  • $\begingroup$ I have deleted an answer I had made, which was false. My apologies. $\endgroup$ Feb 6, 2014 at 12:20

2 Answers 2

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$
5
  • $\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, 2014 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$ Feb 7, 2014 at 4:23
  • $\begingroup$ @apt1002 I am working on verifying your proof. Did you mean $h$ is non-decreasing in $p$ or $y$? $\endgroup$ Feb 7, 2014 at 4:25
  • $\begingroup$ @apt1002 and dineshdileep: You are right! sorry I had misunderstood the notation. $\endgroup$
    – Alt
    Feb 7, 2014 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, 2014 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$
4
  • $\begingroup$ "where $g$ is strictly increasing and concave" - please can you explain why? $\endgroup$
    – apt1002
    Feb 11, 2014 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, 2014 at 17:52
  • $\begingroup$ I think maybe it would be clear if you defined $g$ for an arbitrary $\mathbb{S}$. $\endgroup$
    – apt1002
    Feb 11, 2014 at 18:10
  • $\begingroup$ actually it's just increasing, not strictly increasing $\endgroup$ Feb 11, 2014 at 18:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .