prove the linear combination of variables smaller than zero given the linear combination of their upper bound and lower bound smaller than zero

Question

I'd like to prove that

$a^Tx \leq 0$, where $x$ is a vector with all entries $x_i\geq 0$, given that

$a^Ty\leq 0$ and $a^Tz\leq 0$,

where $0\leq y_i\leq x_i\leq z_i$ for all $i$.

I can only show that $x\in \{x=c_1y+c_2z,\forall c_1,c_2\geq 0\}$ gives $a^Tx \leq 0$, which is trivial. It seems not all $x$ satisfying $y_i\leq x_i\leq z_i$ lead to the conclusion.

Many thanks!

Answer 1

I don't think you can prove what you want to prove.

Take $$ \begin{align} a&=\begin{bmatrix}1\\-1\end{bmatrix}\\ y&=\begin{bmatrix}1\\2\end{bmatrix}\\ z&=\begin{bmatrix}5\\6\end{bmatrix}\\ x&=\begin{bmatrix}4\\3\end{bmatrix} \end{align} $$

Then:

• $a^Ty=1-2=-1\leq 0$
• $a^Tz=5-6=-1\leq 0$
• $0\leq 1=y_1\leq 4=x_1\leq 5=z_1$ and $0\leq 2=y_2\leq3=x_2\leq6=z_2$

So all conditions are satisfied, however $a^Tx=4-3=1>0$, so $a,x,y,z$ form a counterexample.