The Farkas' lemma I know is:

Exactly one of the following systems has a solution. \begin{equation} \left\{ \begin{array}{l} Ax=b,\ x\geq0 \\ A^Ty\geq0, \ y^Tb<0 \end{array} \right. \end{equation}

I want to find the alternative system for \begin{equation} c^Tx<0,Ax\geq0,Bx=0 \end{equation}

My solution is:

\begin{equation} \left( \begin{array}{c} A\\ B\\ -B \end{array} \right)x\geq0, x^Tc<0 \end{equation} By Farkas' Lemma, we have the corresponding alternative system \begin{equation} (A^T\ B^T\ -B^T) \left( \begin{array}{c} y_1\\ y_2\\ y_3 \end{array} \right)=c,\quad y_1,y_2,y_3\geq0 \end{equation}

Can anyone tell me whether my solution is correct? I'm not sure about $y_2$ and $y_3$, it seems there's some relation between $y_2$ and $y_3$ through $B^T$... Should I "rewrite" $y_2$ and $y_3$ into a vector $v$ such that $v=y_2-y_3$?


Your solution is correct. Your equation is $A^T y_1 + B^T y_2 - B^T y_3 = c$, which is equivalent to to $A^T y_1 + B^T( y_2 - y_3) = c$. You can indeed replace $y_2-y_3$ with $v$. What can you say about the sign of $v$?

  • $\begingroup$ I can not tell the sign of $v$... So it is correct to just left $y_1$, $y_2$ and $y_3$ over there? It is confused to me that at the beginning we have only $x$ but end up with three $y$s. $\endgroup$ – Huaixin Nov 17 '19 at 1:16
  • $\begingroup$ what do you mean that you cannot tell the sign of $v$? $\endgroup$ – LinAlg Nov 17 '19 at 13:54
  • $\begingroup$ Oh sorry, I mean I don't know the sign of $v$. $\endgroup$ – Huaixin Nov 17 '19 at 14:27
  • $\begingroup$ that's right, so you get $A^Ty_1 + B^T v = c$, with $y_1 \geq 0$ and $v \in \mathbb{R}^m$ $\endgroup$ – LinAlg Nov 17 '19 at 15:25
  • $\begingroup$ Got it, thanks for your replying and patience! $\endgroup$ – Huaixin Nov 17 '19 at 15:29

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.