# A maximization problem within the simplex

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?

• If a maxima cannot lie in the (relative) interior, can you use induction on dimension? – copper.hat May 5 '15 at 20:13
• @copper.hat Yup. You're right. How didn't I think of that? You want to post an answer? – yohBS May 5 '15 at 20:23
• 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. – Michael Grant May 6 '15 at 11:39

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