Nevermind! I worked it out. This question seems really silly now.
I am working through the proof of the Kantorovich inequality on pages 6 and 7 of the following lecture notes: u.mich optimisation lecture notes
There's one step of it that I'm really struggling to understand. Could someone please explain to me how one gets from the RHS of the last identity on page 6 to the first LHS inequality on page 7.
I also have a little difficulty understanding the diagram. My interpretation of the diagram on page 7 is that: For any convex-hull type combination of the points $a_1, a_2,\dots , a_n,$ with weights $\lambda_1, \dots, \lambda_n,$ we can find a $\gamma$ such that $\gamma \frac{1}{a_1} + (1-\gamma)\frac{1}{a_n} > \sum_{i=1}^n \lambda_i\left(\frac{1}{a_i}\right)$.
However, in the problem, aren't we simultaneously trying to ensure that for those same weights $\lambda_i$, that our $\gamma$ is also maximising $\gamma a_1 + (1-\gamma) a_n > \frac{1}{\sum_{i=1}^n \lambda_i\left(\frac{1}{a_i}\right)} $, since, ultimately we're trying to find an upper bound for $\beta$ from the equation on the bottom of page 6?? How does the diagram deal with this latter aspect?
Much thanks in advance!
Best Answer
This question is bugging me since, as far as I can see, the diagram illustrates that if we define $\gamma$ by $$\sum_{i=1}^n \lambda_i a_i = \gamma {a_1}+(1-\gamma){a_n},$$ then $${1\over \sum_{i=1}^n \lambda_i a_i}\leq \gamma {1\over a_1}+(1-\gamma){1\over a_n},$$ which is true, but not at all useful. We want to show that $$\beta=\left(\sum_{i=1}^n \lambda_i a_i\right)\left(\sum_{i=1}^n \lambda_i/a_i\right)$$ is maximized when all the weight is on $a_1$ and $a_n$. We can prove this directly using induction, by finding a larger value of $\beta$ using fewer points.
If $n>2$, choose any $1<j<n$. Fix everything except $a_j$; all the weights $\lambda_i$ and all the other points $a_1, \dots, a_{j-1},a_{j+1}, \dots, a_n$. Let $x$ be a variable that can range freely between $a_{j-1}$ and $a_{j+1}$. Define $$\beta(x)=\left(\sum_{i\neq j} \lambda_i a_i+\lambda_j x\right)\left(\sum_{i\neq j} \lambda_i/a_i+\lambda_j/x\right).$$ Its second derivative is $$\beta^{\prime\prime}(x)=\left(\sum_{i\neq j} \lambda_i a_i\right) {2\lambda_j\over x^3}\geq 0.$$ This means that $\beta(x)$ is convex, and so its maximum occurs at one of the endpoints. In other words, $\beta\leq\max\{\beta(a_{j-1}),\beta(a_{j+1})\}$ so we can increase $\beta$ by moving $a_j$ to either $a_{j-1}$ or $a_{j+1}$. This completes the induction step, and gives the desired result.
I expect that there is a cleverer, more direct proof but I couldn't find it.