When the convex combinations of two vectors are all non-negative?

53 Views Asked by At

Let $x=(x_1,\cdots,x_N),y=(y_1,\cdots,y_N)$ be two elements of the Euclidean space $\mathbb{R}^N$. What are the necessary and sufficient conditions on $x$ and $y$ for the following statement to be true:

For all $\lambda\in[0,1]$, $\lambda x+(1-\lambda)y\nleq0$ (i.e. it is not the case $\lambda x_i+(1-\lambda)y_i\leq0$ for all $i=1,\cdots,N$)

2

There are 2 best solutions below

3
On

For example a sufficient and necessary condition on $x$ and $y$ would be to not have both live in the negative quadrant, more formally...

... For all λ∈[0,1], λx+(1−λ)y≰0 iff $x,y \in \mathbb R^n$ and $\neg(x\le 0)$ and $\neg(y\le 0)$ ....

EDIT: as Kurt G and KBS have pointed out my answer is not correct.

0
On

I have the beginning of an answer, which is a necessary condition. Define the set

$$S(x,y):=\{\lambda x+(1-\lambda)y: \lambda\in[0,1]\}$$

and observe that it is convex.

The statement you want to prove can be be formulated as $$S(x,y)\cap \mathbb{R}_{\le0}^n=\emptyset.$$

Assume that this statement holds. Then, we can invoke the hyperplane separation theorem to state that there exists a vector $z\in\mathbb{R}^n$ such that $z^Tv>0$ for all $v\in S(x,y)$ and $z^Tw\le0$ for all $w\in\mathbb{R}^n_{\le0}$. This is equivalent to saying that $z>0$ and $z^Tv>0$ for all $v\in S(x,y)$.

We have that $z^Tv=\lambda z^Tx+(1-\lambda)z^Ty>0$ for all $\lambda\in[0,1]$. This is equivalent to say that $z>0$, $z^Tx>0$ and $z^Ty>0$. This provides a necessary condition.


I lack time now but it would be interesting to see whether it it also sufficient. Right now, my overall feeling is that it is not the case.