1
$\begingroup$

I am given a set of coefficients such that the affine combination $\{x_1, x_2, ..., x_n \} \notin conv(x_1, x_2, ..., x_n)$. How do I prove that under such given conditions the Jensen's inequality direction is reversed? That is

$f(\sum_{i=0}^n \lambda_ix_i) \geq \sum_{i=0}^n \lambda_if(x_i) $

I know this result and I have verified this but I can't prove the statement.

$\endgroup$
2
  • $\begingroup$ I think you want to say that $\lambda_i$ are such that $\sum_{i} \lambda_i=1$ and at least one of them is not in $[0,1]$. $\endgroup$
    – P. Quinton
    Feb 10, 2023 at 6:48
  • $\begingroup$ Yes, that is true. $\endgroup$ Feb 10, 2023 at 6:54

1 Answer 1

1
$\begingroup$

This is false, let $f:\mathbb R^2\to\mathbb R$ be defined as $f(a,b)=a^2+b^2$, let $x_1=[0,0]^T$, $x_2=[1,0]^T$ and $x_3=[0,1]^T$ with $\lambda_1=-\varepsilon$, $\lambda_2=\lambda_3=\frac{1+\varepsilon}{2}$. For any $\varepsilon >0$, this is not in the convex hull of $x_1$, $x_2$ and $x_3$. We can compute explicitly
\begin{align*} f\left( \sum_{i} \lambda_i x_i \right)&=\frac{(1+\varepsilon)^2}{2}\\ \sum_{i=1}^n \lambda_i f(x_i) &= 1+\varepsilon \end{align*}

observe that $\frac{(1+\varepsilon)^2}{2}-1-\varepsilon=\frac{\varepsilon^2-1}{2}$, therefore for $\varepsilon\in ]0,1[$, $f\left( \sum_{i} \lambda_i x_i \right)<\sum_{i=1}^n \lambda_i f(x_i)$.


Observe however that your result is true for $n=2$, indeed if $x=\lambda x_1+(1-\lambda)x_2$ with $\lambda < 0$, then $x_2=\frac{1}{1-\lambda} x - \frac{\lambda}{1-\lambda} x_1$ where both coefficients are positive and sum to one, therefore by Jensen inequality we get \begin{align*} (1-\lambda)f(x_2)&\leq (1-\lambda)\frac{1}{1-\lambda} f(x) - (1-\lambda)\frac{\lambda}{1-\lambda}\\ &=f(x) - \lambda f(x_1) \end{align*} which proves your result. In the example above try drawing the points and the non-convex combination to see why we can break the condition, in particular it is clear when $\varepsilon \to 0$.

$\endgroup$
2
  • $\begingroup$ It was that simple? Thanks a lot. I was stuck with this in my head for hours. I am new here so can't upvote your answer. But thanks for the explanation. $\endgroup$ Feb 10, 2023 at 8:28
  • $\begingroup$ No worries and welcome ! If the answer is satisfying, you can validate it. $\endgroup$
    – P. Quinton
    Feb 10, 2023 at 8:35

You must log in to answer this question.

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