An Application of Farkas’ Lemma

linear algebralinear programmingoptimization

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

Best Answer

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

Related Question