Farka's Lemma and Linear Programming Duality

1. Farka's Lemma

Let $A \in \mathbb{R}^{m\times n}$ and $b \in \mathbb{R}^{m}.$ Then exactly one of the following two statements is true:
(1). There exists an $x\in \mathbb{R}^n$ such that $Ax=b$ and $x\geq 0.$
(2). There exists a $y\in \mathbb{R}^m$ such that $A^Ty\geq 0$ and $b^Ty<0$
Proof:

(1) feasible to show (2) infeasible is trivial.
(1) infeasible to show (2) feasible is by separation theorem.

Note
(2) can be written in the following way
There exists a $y\in \mathbb{R}^m$ such that $A^Ty\leq 0$ and $b^Ty>0$

2. Linear Programming Primal-Dual table

primal_dual_table.png

Example:
Primal:
$\begin{align*} \min_{x} \quad & c^Tx \\ Ax &\leq b \\ x &\geq 0 \\ \end{align*}$
Dual:
$\begin{align*} \max_{x} \quad & b^Ty \\ A^Ty &\leq c \\ y &\leq 0 \\ \end{align*}$

最后编辑于：2019.04.16 12:31:08

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

友情链接更多精彩内容

赞1赞

赞赏

手机看全文