Weird Maximization Problem

Question

For $1 \leq i \leq 215$ let $a_i = \dfrac{1}{2^{i}}$ and $a_{216} = \dfrac{1}{2^{215}}$. Let $x_1, x_2, \dots, x_{216}$ be positive real numbers such that $\displaystyle\sum_{i=1}^{216} x_i=1$ and $$\sum_{1 \leq i < j \leq 216} x_ix_j = \dfrac{107}{215} + \sum_{i=1}^{216} \dfrac{a_i x_i^{2}}{2(1-a_i)}.$$Find the maximum possible value of $x_2.$

---

I simplified the condition to $\displaystyle\sum_{i=1}^{216}\dfrac{x_i^2}{1-a_i}=\dfrac{1}{215},$ but I'm not sure what to do next.

Answer 1

Given $ \sum \frac{ x_i ^2 } { 1 - a_i} = \frac{1}{215}$, apply Cauchy Schwarz / Titu's lemma to get

$$ \sum \frac{ x_i ^2 } { 1 - a_i} \geq \frac{ ( \sum x_i) ^ 2 } { \sum 1 - a_i } = \frac{ 1^2 } { 215 } . $$

Since equality holds throughout, we conclude that $ \frac{ x_i } { 1-a_i}$ is a constant, say $k$.
Since $ 1 = \sum x_i = \sum (1-a_i)k = 215 k$, so $ k = \frac{1}{215}$.

Hence, $ x_ i = \frac{ 1 - a_i } { 215 }$.

Answer 2

Very interesting, nice. My first reflex is

You should use Lagrange multipliers.

and it would have worked for other choices of the parameters. As it turns out, your problem is not an optimization problem: there is only one choice of the $x_i$ that satisfy your constraints, and the short proof is at the end. But I am including the work I have done with Lagrange multipliers that led me to the proof.

Let $A=\sum_i x_i$ and $B=\sum_i \frac{x_i^2}{1-a_i}$. Your goal is to maximize $x_2$ with some constraints on the values of $A$ and $B$.

What you do then is to maximize $$E = x_2 -\lambda A -\mu B=\sum_i\Big[(\delta_i^2-\lambda)x_i-\mu\frac{x_i^2}{1-a_i}\Big]$$ with no constraint on the $x_i$ other than $x_i≥0$. The parameters $\lambda$ and $\mu$ are your Lagrange multipliers.

Clearly, if $\mu<0$, $E$ can be made arbitrarily large by sending $x_i$ to infinity. This does not correspond to anything interesting in the original problem, so we restrict ourselves to $\mu>0$. (You can check that $\mu=0$ doesn't give anything interesting either.)

If $\lambda≥0$, then $E$ is maximized by taking $x_i=0$, except maybe for $x_2$ (depending on the sign of $1-\lambda$). Again, this does not lead to anything useful, so we restrict ourselves to $\lambda<0$.

With $\mu>0$ and $\lambda<0$, the maximum of $E$ is reached for $$ x_i=\frac{(1-a_i)(\delta_i^2-\lambda)}{2\mu}$$

We can now choose $\lambda$ and $\mu$ in such a way that the constraints are respected. Let us compute $A$ and $B$ when the $x_i$ maximize $E$: $$A=\frac{1}{2\mu}\bigg[1-a_2-\lambda\sum_i(1-a_i)\bigg]=\frac1{2\mu}\bigg[\frac34-215\lambda\bigg]$$ $$B=\frac1{4\mu^2}\bigg[(1-a_2)(1-2\lambda)+\lambda^2\sum_i(1-a_i)\bigg]=\frac1{4\mu^2}\bigg[\frac34(1-2\lambda)+215\lambda^2\bigg]$$

At this point, solving for $A=1$ and $B=\frac1{215}$ should give you values of $\lambda$ and $\mu$, and then the values of $x_i$ which maximize $x_2$ while repecting the constraints. But it turns out the equations don't have a solution! (Had your constraint been $B=\frac1{214}$, you would have found a solution in that way.)

In fact, trying to solve the stuff, you get the feeling that you should take $\lambda\to-\infty$ and $\mu\to\infty$. This leads you to guess that maybe in some sense $\lambda$ and $\mu$ are large , but their ratio is not, and that the solution should look like $$x_i= c(1-a_i)$$ with $c$ some constant. It turns out that by taking $$x_i=\frac{1-a_i}{215}$$ then your constraints are met. At this point, you can conjecture it is the right solution to the maximization problem. Let's prove it.

Write $$x_i= \frac{1-a_i}{215} + y_i$$ Then your constraints become $$\sum_i y_i=0,\qquad\sum_i \frac{y_i^2}{1-a_i}=0$$ so the only possible solution is $y_i=0$

So, it is not a matter of maximization: there is only one choice of the $x_i$ that satisfy your contraints.