Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
Please do not deface your question by erasing all its content. I reverted the question to its previous-to-last Edit. –  Did Sep 9 '12 at 16:55
4  
Could you post your answer? There may be others interested in the same question... i.e. me! :) –  Paul Sep 9 '12 at 18:14
add comment

1 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.