2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Kavi Rama Murthy May 4 '18 at 12:09
  • $\begingroup$ @KaviRamaMurthy, thanks for that, I guess it is closely related to separation theorem in convex analysis, not functional analysis? $\endgroup$ – Kyle YIP May 4 '18 at 15:09
  • $\begingroup$ Separation theorem are an essential part of Functional Analysis too. I consider convex analysis a part of Functional Analysis! $\endgroup$ – Kavi Rama Murthy May 5 '18 at 22:56
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.