2
$\begingroup$

I have a function of the form $f(x,y) = \frac{x}{c+y}$ where $c$ is a positive constant, $c \ge x \ge 0$, and $y \ge 0$. I would like to find a convex upper-bound for this function. Is there a principled way for doing this? How about if the upper-bound has to be convex and piecewise linear? Is there a way to find the optimal upper-bound in terms of the number of linear pieces?

Update: Sorry I changed the boundary conditions on $x$ and $y$ so it suits my problem better.

$\endgroup$
2
  • 1
    $\begingroup$ Let's first make sure that we speak the same language: "convex" means $f(\frac{a+b}2)\le\frac{f(a)+f(b)}2$. Are you sure that you mean this and not the opposite inequality, which I would normally call "concavity"? $\endgroup$
    – fedja
    Dec 6, 2012 at 1:53
  • $\begingroup$ The function f is quasiliner. It has convex parts eg. when one sets $x=1$ and only varies $y$, $f(x,y) = f(y) = \frac{1}{c+y}$, and concave parts, eg. when one sets $y = x$, and so $f(x,y) = f(x) = \frac{x}{c+x}$. I would like to find a convex upper-bound for $f$ if possible. $\endgroup$
    – Norouzi
    Dec 6, 2012 at 3:17

2 Answers 2

1
$\begingroup$

If you really mean $d\ge x$, then $f(x,y)\le f(d,y)$ which is convex, or even $f(x,y)\le f(d,0)$.

If it was a typo and the true domain is $[d,+\infty)\times[0,+\infty)$, the convex function $g(x,y):=f(x,0)+f(d,y)-f(d,0)=\frac{x}{c}+\frac{d}{c+y}-\frac{c}{d}$ has $g(d,y)=f(d,y)$ for all $y\ge 0$ and $g_x(x,y)\ge f_x(x,y)$ for all $x\ge d$ and $y\ge0$ , so $g\ge f$ on $[d,+\infty)\times[0,+\infty)$.

$\endgroup$
0
1
$\begingroup$

Not exactly the answer, but I think $g(x,y) = \frac{x^2}{(c+y)^2}$ is a reasonable convex lower-bound for $f$. With the assumption that $c \ge x$, then $1 \ge f(x,y) \ge 0$, and so $f(x,y)^2 \le f(x,y)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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