# Finding Farkas-type infeasibility certificate(s) for a simple problem in the standard primal conic form

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!

• Is there a typo in your question? A. and B. are exactly the same. Also, it would help to provide your definition of a "Farkas-type infeasibility certificate." – Math1000 Oct 24 '19 at 4:43
• Thank you I just fixed it! I found a note on Farkas certificate of feasibility, it is not as bad as previously thought: people.seas.harvard.edu/~yaron/AM221-S16/lecture_notes/… – mathnoob777 Oct 24 '19 at 5:55

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$$ **