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!

  • $\begingroup$ 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." $\endgroup$ – Math1000 Oct 24 '19 at 4:43
  • $\begingroup$ 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/… $\endgroup$ – 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$ **


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.