-1
$\begingroup$

Define the multi-dimension concave function $f(x): \mathbb{R}^n_+ \rightarrow \mathbb{R}_+$ where $x \in \mathbb{R}^n_+$, here I use $\mathbb{R}_+$ to represent the range $[0, \infty)$ and we let $f(\mathbf{0}) = 0$ . Suppose we have a vector $x^* = [1, ..., 1]$, let $x^*_{-i} = [1, ..., 0, ..., 1]$ whose $i^{th}$ element is 0. Note the value of $x^*$ can be any positive value, I just use $1$ for convenience.

Let $a = f(x^*)$ and $b = \sum\limits_{i=1}^{n} f(x^*_{-i})$, I have an intuition that \begin{equation} (n - 1) \cdot a \geq b \end{equation} because of the concavity of $f(x)$. But I cannot think out a proof for this. Does anyone have some thoughts about doing this or prove my intuition is wrong?

$\endgroup$
3
  • $\begingroup$ Can you prove it for $n=2$? $\endgroup$
    – D.W.
    Nov 11 '19 at 20:30
  • $\begingroup$ For $n = 2$, we need to prove $f(1,1) \geq f(0,1) + f(1,0)$. I can't think out a proof for it either... But from some examples like $f(x) = \sqrt{x \cdot y}$ which is a concave function, we can easily verify this is true. $\endgroup$
    – user54970
    Nov 12 '19 at 16:35
  • $\begingroup$ I think I forgot to mention one more constraint on the function $f(x)$, this concave function is constrained to be increasing. $\endgroup$
    – user54970
    Nov 13 '19 at 17:15
1
$\begingroup$

Consider the function $f(x, y) = 1 - e^{-(x + y)}$. Now $f(0, 0) = 0$, $f$ is increasing and concave, since $g(t) = -e^{-t}$ is concave.

But $f(1, 0) + f(0, 1) = 2(1 - e^{-1}) > 1 - e^{-2} = f(1, 1)$, hence the claim doesn't hold even when $n = 2$.

The claim doesn't hold for convex functions either. $f(x, y) = 2(x + y) + |x - y|$ is one counterexample: $f(0, 0) = 0$, $f$ is increasing and convex, since

$\alpha f(x_{1}, y_{1}) + \beta f(x_{2}, y_{2}) = \ldots + \alpha |x_{1} - y_{1}| + \beta |x_{2} - y_{2}| \geq \ldots + |\alpha(x_{1} - y_{1}) + \beta(x_{2} - y_{2})| = f(\alpha x_{1} + \beta x_{2}, \alpha y_{1} + \beta y_{2})$

By the triangle inequality, but $f(0, 1) + f(1, 0) = 6 > 4 = f(1, 1)$.

$\endgroup$

Your Answer

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