1
$\begingroup$

I think there is a glitch in the proof by induction. The proof is still valid, but they add an unnecessary assumption:

In the induction step, they choose one of the $\lambda_i$'s that is strictly positive (I guess by that, they mean nonzero). Since the sum of the $\lambda_i$'s is 1, there must be at least one that is nonzero, that part is valid. And the argument that follows is also perfectly valid.

However, why do we need to pick a nonzero $\lambda_i$? Wouldn't the argument work regardless? If $\lambda_1 = 0$, the inequality still holds. In other words, the inequality holds regardless of the value of $\lambda_1$: $$ \varphi\left( \lambda_1 x_1 + (1 - \lambda_1) \sum_{i=2}^{n+1}\frac{\lambda_i}{1-\lambda_1} x_i \right) ~\leqslant~ \lambda_1 \varphi(x_1) + (1-\lambda_1)\varphi\left( \sum_{i=2}^{n+1} \frac{\lambda_i}{1-\lambda_1} x_i \right)$$

because $\varphi$ is convex, period. No requirement on the coefficient being nonzero: according to Wikipedia's definition of a convex function, it is $\forall x_1, x_2 \in X$, $\forall \lambda \in [0,1] ~ \cdots$

Since the $\lambda_i$'s are all nonnegative and their sum is 1, then every $\lambda_i \in [0,1]$, so the definition of convexity applies.

Am I missing something?

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

You are right that the case $\lambda_1 = 0$ is fine; the proof should be corrected to assume instead that $\lambda_1<1$. (If $\lambda_1=1$ the inequality is trivial but should be shown differently, since we can't divide by $1-\lambda_1$.)

$\endgroup$
1
  • $\begingroup$ D'oh!! Right! The selected $\lambda_i$ must be < 1, how could I miss that detail!! (when thinking that the argument was perfectly valid!!). Thanks for this! $\endgroup$
    – Cal-linux
    May 24, 2019 at 18:24
0
$\begingroup$

Of course, $\lambda_1=0$ is valid, but not so interesting: $$ \varphi\left(\sum_{i=2}^{n+1}\lambda_i x_i \right) ~\leqslant~ \varphi\left( \sum_{i=2}^{n+1} \lambda_i x_i \right)$$

$\endgroup$
6
  • $\begingroup$ I see that (I was going to add it as a remark in my post). But that does not negate the validity of the argument without that extra assumption. I think the assumption reduces the elegance of the argument (it does not invalidate it, though!). The point is, given the definition of convexity (which is the key property being applied), one should not even specifically think of the case $\lambda_1 = 0$; it should not matter whether that corresponds to the trivial case or not. For that matter, in the definition of a convex function, the case $\lambda = 0$ is completely non-interesting, right? $\endgroup$
    – Cal-linux
    May 24, 2019 at 15:46
  • $\begingroup$ @Cal-linux yes. The point is that we are assuming that (without the loss of generality) that $\lambda_1 \in (0,1)$. If $\lambda_1=0$, then we must have another $\lambda_i$ that is non-zero, and we can just swap them. And if one of the lambdas is $1$, then it's trivial. That's why we can assume that $\lambda_1 \in (0,1)$. $\endgroup$
    – Botond
    May 24, 2019 at 16:16
  • $\begingroup$ This is incorrect; we cannot assume that $\lambda_1 \in (0,1)$. We may have situations where neither of the lambdas $\in (0,1)$. You may claim that we may handle the cases separately, but that would also make for a "less-than-optimal" proof (in terms of elegance). The formula/derivation given in the proof works as long as you choose $\lambda_1 < 1$ — which you must do, as Misha Lavrov pointed out (and you can do, since there must be at least one of the lambdas that is < 1). $\endgroup$
    – Cal-linux
    May 24, 2019 at 18:55
  • $\begingroup$ @Cal-linux We can, because $\sum_i \lambda_i = 1$ and $\lambda_i \geqslant 0 \forall i$. So we can assume WLOG that either $\lambda_1=1$ or $\lambda_1 \in (0, 1)$. The $\lambda_1=1$ case is trivial, so we can assume that $\lambda_1 \in (0, 1)$. $\endgroup$
    – Botond
    May 24, 2019 at 19:04
  • $\begingroup$ Well, we seem to differ in terminology --- what you describe is not "we can assume"; what you're doing is treating the two cases separately; again: you cannot assume that $\lambda_1 \in (0,1)$, because it is not always the case that you can have that condition; you can, however (which is what you show above), treat the case of one of the lambdas = 1 separately, and in all remaining cases, it will necessarily be the case that at least one of the lambdas $\in (0,1)$ $\endgroup$
    – Cal-linux
    May 24, 2019 at 21:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .