-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$
  • $\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$ – Minbiao 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$ – Minbiao 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

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