4
$\begingroup$

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.

1 Answers 1

2

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
    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.2011-08-21