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