0
$\begingroup$

Let $\lambda_i$ be an ordered list of $N$ positive numbers, $\lambda_1<\lambda_2<\dots<\lambda_N$. I'm looking for the extrema of the function

$$ f=\left(\sum_{i=1}^N p_i \lambda_i \right)\left(\sum_{i=1}^N\frac{p_i}{\lambda_i}\right) $$

where $0\le p_i \le 1$ and $\sum_i p_i=1$, or in other words, $\vec p$ is in the $N$-simplex.

Jensen's inequality says that $f\ge1$, and this happens when $p_{i_0}=1$ for any $i_0$. So we got the minima.

For the maxima, it's a little more involved. Using Lagrange multipliers, it's straightforward to show that the extrema cannot lie in the interior of the simplex. Sadly, this is the farthest I could go analytically.

After some experimentation, I'm pretty sure that the maximum is unique and is located at $\vec p=\left(\frac{1}{2},0,\dots,0,\frac{1}{2}\right)$, i.e. a $\vec p$ that gives equal weights to the highest and lowest $\lambda$, and zero to the rest. How can I prove this?

$\endgroup$
  • 1
    $\begingroup$ If a maxima cannot lie in the (relative) interior, can you use induction on dimension? $\endgroup$ – copper.hat May 5 '15 at 20:13
  • $\begingroup$ @copper.hat Yup. You're right. How didn't I think of that? You want to post an answer? $\endgroup$ – yohBS May 5 '15 at 20:23
  • 1
    $\begingroup$ Take the square root of f and you have a concave function, so the problem becomes a convex optimization problem, with all the machinery that goes with that. $\endgroup$ – Michael Grant May 6 '15 at 11:39
1
$\begingroup$

Here is a rather tedious solution, I suspect a cleaner solution could be obtained using Michael's remark above, but it doesn't leap out at me at present.

Let $f(x) = (\sum_k \lambda_k x_k )(\sum_k {1 \over \lambda_k} x_k)$, and $\Sigma = \{ x | x_k \ge 0, \sum_k x_k = 1 \}$. Since $\Sigma$ is compact and $f$ is continuous, we know the various extrema exist.

Suppose $x$ is an extreme point and $x \in \operatorname{ri} \Sigma$ (that is, $x >0$), then $x$ is an extreme point of $f$ subject to the constraint $\sum_k x_k = 1$. Using Lagrange multipliers (or projected gradients, which amounts to the same thing here, since $\Sigma$ is convex), we have ${\partial f(x) \over \partial x_k} +\mu = 0$ for some $\mu$ and for all $k$. This gives $ \lambda_k(\sum_i {1 \over \lambda_i} x_i) + { 1\over \lambda_k }(\sum_i \lambda_i x_i) + \mu = 0$.

Now note that at most two values of $t$ can satisfy the equation $at+ {b \over t} = c$ (with $a,b,t>0$). Since the $\lambda_k$ are distinct, the Lagrange condition can only be satisfied if $\dim \operatorname{ri} \Sigma \le 2$.

Hence if $x$ is an extreme point, then either $\dim \operatorname{ri} \Sigma \le 2$ or $x \in \operatorname{rb} \Sigma$. In the latter case, at least one component of $x$ will be zero and we then note that $x$ is an extreme point for $f$ on a simplex of smaller dimension. Consequently, we may assume that $\dim \operatorname{ri} \Sigma \le 2$.

Now consider $f$ on a simplex of dimension $2$. Let $\phi(t) = f(t e_i + (1-t) e_j)$, where $e_i,e_j$ are unit vectors with $1$ in the $i,j$ places respectively. Then \begin{eqnarray} \phi(t) &=& (\lambda_j + t (\lambda_i - \lambda_j)) ({ 1\over \lambda_j} + t ({1 \over \lambda_i} - {1 \over \lambda_j})) \\ &=& 1+ ({ \lambda_i \over \lambda_j} + { \lambda_j \over \lambda_i}-2) (t-t^2) \end{eqnarray} Noting that $y+ {1 \over y} > 2$ for all positive $y \neq 1$, we see that $\phi$ has a minimum value of $1$ (for $t \in \{0,1\}$) and a maximum value of $\phi({1 \over 2}) = {1 \over 2} + {1 \over 4} ({ \lambda_i \over \lambda_j} + { \lambda_j \over \lambda_i})$ (at $t={1 \over 2}$).

It follows from this that the maximum value of $f$ is ${1 \over 2} + {1 \over 4} ({ \lambda_1 \over \lambda_n} + { \lambda_n \over \lambda_1})$ and that this is attained at the (unique) minimiser ${1 \over 2} (e_1+e_n)$.

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