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.

• 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]$. Feb 10, 2023 at 6:48
• Yes, that is true. Feb 10, 2023 at 6:54

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