Hi there some classmates and I are trying to understand a review question for a class on convex optimization.
Consider the following programming instance: $\text {min} (x_3+x_4) s.t. -x_1-x_3+x_4=1,-x_2+x_3-x_4=1$, $\text{x}\ge1$.
Which of the following vectors provides a Farkas-type infeasibility certificate for the above problem:
A. $y=(1,1)$
B. $y=(-1,-1)$
C. $y=(2,2)$
D. All of the above
The answer is said to be "D", but would you please explain why it is the case? Thank you in advance and we wish you a wonderful day!
Note that if you find a vector $(y_1, y_2)$, the linear combination of your equations is
$$y_1(-x_1-x_3+x_4)+ y_2(-x_2+x_3-x_4)=y_1+y_2 \implies $$
$$ -y_1 x_1 -y_2 x_2 +(-y_1 +y_2)x_3 + (y_1 -y_2) x_4=y_1+y_2$$
Now, if the associated coefficients are nonpositive, but the right side of the equality is positive
$$-y_1\leq 0, -y_2\leq 0, -y_1 +y_2\leq 0, y_1 -y_2\leq 0 ~ and ~ y_1+y_2>0$$
your system of equations is infeasible due to $x_1\geq 1$ and $ x_2\geq 1$ [there is no way of a sum of nonpositive numbers to be positive]. Thus $y=y_1=y_2>0$ is a specific case where
$$-y x_1 -y x_2 =2y$$
is infeasible for all $y>0$
**It is the same to say $Ax=b$ is infeasible iff $\exists y, ~ yA\leq 0 ~ and ~ yb>0$ **