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)$

It is

$\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.

  • 1
    $\begingroup$ 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. $\endgroup$ – joriki Aug 21 '11 at 16:37

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.