Maximum of concave function over probability simplex

702 Views Asked by At

Let $F:\mathcal{C}\subset\mathbb{R}^n\to\mathbb{R}$ be a continuous function defined over $$ \mathcal{C}=\left\{x\in\mathbb{R}^n:x_i\geq 0\,\forall i,\,\sum_{i=1}^nx_i=1\right\}. $$ In addition, $F$ is concave and permutation invariant, which means that $F(x)=F(\Pi(x))$, where $\Pi(x)$ is a copy of $x$ with permutated elements.

Is it true that $$ \left(\dfrac{1}{n},...,\dfrac{1}{n}\right)^{\top}=\text{argmax}_{x\in\mathcal{C}}\,F(x)\quad ? $$

If it is true, how can I show it? Is there a reference for this?

1

There are 1 best solutions below

2
On BEST ANSWER

Yes, this is always true.

Proof:

Assume $x^* \in \mathbb{R}^n$ is the point where $F(x)$ attains maxima, where each of its components $x^*(i)$ might be unequal. Since by definition of $F$ maxima will also be obtained at all permutations of $x^*$ $i.e.\ \Pi(x^*)$. Now you can prove that $F(x)$ attains maxima at all points in the convex hull of $\Pi(x^*)$. Let $y \in S$ where $S$ is the convex hull of $\Pi(x^*)$:

By concavity of $F$ $$ F(y) = F \bigg(\sum_{x_i \in \Pi(x^*)}\theta_i x_i \bigg) \geq \sum_{x_i \in \Pi(x^*)} \theta_i F(x_i) = F(x^*). $$ where $\theta_i \geq 0$ and $\sum_i \theta_i = 1$. But maxima is obtained at $x^*$. Hence $F(y) = F(x^*)$.

It is trivial to prove that the point $\left(\dfrac{1}{n},...,\dfrac{1}{n}\right)^{\top}$ always belongs to this convex hull of $\Pi(x^*)$ as it is the mean of all the elements of $\Pi(x)$. For eg: one can take $n$ points maintaining cyclic order of $x^*$ (cyclic permutations) and assign all $\theta_i = 1/n$. Since $x^*$ lies on simplex its co-ordinates sum to 1.