29-4 Farkas'ss lemma

Let \(A\) be an \(m \times n\) matrix and \(c\) be an \(n\)-vector. Then Farkas's lemma states that exactly one of the systems

\[ \begin{aligned} Ax & \le 0, \\\\ c^Tx & > 0 \end{aligned} \]

and

\[ \begin{aligned} A^Ty & = c, \\\\ y & \le 0 \end{aligned} \]

is solvable, where \(x\) is an \(n\)-vector and \(y\) is an \(m\)-vector. Prove Farkas's lemma.

Suppose that both systems are solvable, let \(x\) denote a solution to the first system, and \(y\) denote a solution to the second. Taking transposes we have \(x^{\text T}A^{\text T} \le 0^{\text T}\). Right multiplying by \(y\) gives \(x^{\text T}c = x^{\text T}A^{\text T}y \le 0^{\text T}\), which is a contradiction to the fact that \(c^{\text T}x > 0\). Thus, both systems cannot be simultaneously solved. Now suppose that the second system fails. Consider the following linear program:

and its corresponding dual program

Since the second system fails, the primal is infeasible. However, the dual is always feasible by taking \(x = 0\). If there were a finite solution to the dual, then duality says there would also be a finite solution to the primal. Thus, the dual must be unbounded. Thus, there must exist a vector \(x\) which makes \(−c^{\text T}x\) arbitrarily small, implying that there exist vectors \(x\) for which \(c^{\text T}x\) is strictly greater than \(0\). Thus, there is always at least one solution.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用