# Not a convex combination

Given vectors $a_1, a_2, \dots, a_m \in \mathbb{R}^m$, show that if $b$ is not a convex combination of $a_1, a_2, \dots, a_m$, then there exists $x \in \mathbb{R}^m$ such that $a_i \cdot x < b \cdot x$ for all $i=1,2,\dots,m$.

My attempt: try to formulate the problem as a LP: $$\max_{x} {\min_{1 \le i \le m} {(b-a_i) \cdot x}},$$ we need to show the optimal objective value is positive, but I don't know how to proceed. I guess I do not know how to deal with the convex combination condition.

UPD: I have written a solution below for the case $b$ is nonzero.

• This is a standard separation theorem in Functional Analysis. For example see the chapter on "Convexity" in Rudin's Functional Analysis. I do not know of any simpler proof in this case. – Kavi Rama Murthy May 4 '18 at 12:09
• @KaviRamaMurthy, thanks for that, I guess it is closely related to separation theorem in convex analysis, not functional analysis? – Kyle YIP May 4 '18 at 15:09
• Separation theorem are an essential part of Functional Analysis too. I consider convex analysis a part of Functional Analysis! – Kavi Rama Murthy May 5 '18 at 22:56

Now I know how to solve the problem when $b$ is nonzero.

I guess it is an application of Farka's lemma. Farkas' lemma states that exactly one of the following two statements is true:

There exist coefficients ${\displaystyle x_{1},\dots ,x_{m}\in \mathbb {R} ,x_{1},\dots ,x_{m}\geq 0}$ , such that ${\displaystyle \mathbf {b} =x_{1}\mathbf {a} _{1}+\dots +x_{m}\mathbf {a} _{m}}$.

OR

There exists a vector ${\displaystyle \mathbf {y} \in \mathbb {R} ^{m}}$ such that ${\displaystyle \mathbf {a} _{i}^{\mathsf {T}}\mathbf {y} \leq 0}$ for ${\displaystyle i=1,\dots ,m}$ and ${\displaystyle \mathbf {b} ^{\mathsf {T}}\mathbf {y} >0}$ .

Proof by contradiction. Suppose that: there exists $b$, such that $b$ is not a convex combination of $a_1, a_2, \dots, a_m$, and there does not exist $x \in \mathbb{R}^m, \lambda>0$ such that $a_i \cdot x < \lambda b \cdot x$ for all $i=1,2,\dots,m$.

OR equivlantly, there exists $b$, such that $b$ is not a non-negative combination of $a_1, a_2, \dots, a_m$, and there does not exist $x \in \mathbb{R}^m,$ such that $a_i \cdot x < b \cdot x$ for all $i=1,2,\dots,m$

This means the second case of Farka's lemma does not happen for given $a_i$'s and $b$, so the first case must happen.Thus, there exist coefficients ${\displaystyle x_{1},\dots ,x_{m}\in \mathbb {R} ,x_{1},\dots ,x_{m}\geq 0}$ , such that ${\displaystyle \mathbf {b} =x_{1}\mathbf {a} _{1}+\dots +x_{m}\mathbf {a} _{m}}$, a contradiction.