# maximization over a simplex

Suppose I am given two sets of real numbers $\{a_i\}_{i=1}^N$ and $\{w_i\}_{i=1}^N$ with $w_i>0$. I am trying to find the maximum of the expression

$$\left\lvert \sum_i a_i \left(\frac{w_i s_i}{\sum_j w_j s_j}-s_i\right) \right\rvert$$

over a simplex $\Delta:= \{\{s_i\}: \sum_i s_i=1, s_i\ge 0\}\subset \mathbb{R}^N$. I suspect the answer is

$$\max_{i,j} \left\lvert(a_i-a_j) \frac{\sqrt{w_i}-\sqrt{w_j}}{\sqrt{w_i}+\sqrt{w_j}} \right\rvert\;,$$

which is obtained by having $s_i=\frac{\sqrt{w_j}}{\sqrt{w_i}+\sqrt{w_j}}$ and $s_j=\frac{\sqrt{w_i}}{\sqrt{w_i}+\sqrt{w_j}}$ for some $i$ and $j$ and having the remaining $s_k=0, k\ne i, k\ne j$. How can I show it is true, or if it is not true, how do I solve this problem? Thanks.

Start from any $\{s_i\}$, suppose none of $s_i$s is 0, consider the vector $p=[w_n-w_2, w_1-w_3, \cdots, w_{n-2}-w_n, w_{n-1}-w_1]$, and let $s_i'=s_i+\epsilon p_i$. We know that $\sum_i p_i=0$ and $\sum_i w_i p_i=0$. Therefore $\sum_i s_i'=1$ and $\sum_i w_i s_i'=\sum_i w_i s_i$. Now we should calculate the change
$\sum_i a_i (\frac{w_i s_i'}{\sum_j w_j s_j'}-s_i')-\sum_i a_i (\frac{w_i s_i}{\sum_j w_j s_j}-s_i)$
$\epsilon\{\frac{\sum_i a_i w_i (w_{i-1}-w_{i+1})}{\sum_i w_i s_i}-\sum_i a_i (w_{i-1}-w_{i+1})\}$
Notice the value within the bracket is constant when $\{s_i\}$ is moved to $\{s_i'\}$ along the direction $p$. Therefore one can always optimize the value along the direction of $p$ until at least one of $s_i'$ becomes 0. Then one can start over and define the new direction $p$ over the still strictly positive $s_i$s and further reduce the number of nonzero $s_i$s until only 2 of $s_i$ remain positive. Then one can apply simple optimization to get the local maximum point, which has at most 2 strictly positive $s_i$s.
• Very nice solution! You don't actually need the explicit $p$. The conditions $\sum_i p_i=0$ and $\sum_i w_ip_i=0$ are two linear conditions on $p$; they define a subspace of codimension $2$, so for $N>2$ there is necessarily some $p$ that fulfills them, and along such $p$ the objective function is linear. – joriki Aug 21 '11 at 16:37