当求解一个线性规划问题时，如何确定线性不等式约束是否存在可行解呢？这一部分使用对偶理论找到另一组线性不等式，使得这个问题与原问题的可行性等价。而这个新问题的思路是去寻找原问题不可行的条件。
比如，考虑标准型问题，约束为\(Ax=b\)以及\(x\geq 0\)。假设存在向量\(p\)使得\(p^TA\geq 0^T\)以及\(p^Tb<0\)成立。那么对于任意\(x\geq 0\)，有\(p^TAx\geq 0\)。由于\(p^Tb<0\)，因此\(p^TAx\not = p^Tb\)，这也就是说对于所有\(x\geq 0\)都有\(Ax\not = b\)。上述的思路说明若我们可以找到一个向量\(p\)满足\(p^TA\geq 0^T\)以及\(p^Tb<0\)，那么这个标准型问题的约束就不存在可行解。下面的定理将说明只要标准型问题是不可行的，那么\(p\)(称为 certificate of infeasibility) 就一定存在。
定理：（Farkas 引理） 已知\(A\)是一个\(m\times n\)的矩阵以及\(b\in\mathbb{R}^m\)。下面两种情形中的一种成立：
- 存在一些\(x\geq 0\)使得\(Ax=b\)。
- 存在一些 \(p\) 使得\(p^TA\geq 0^T\)以及\(p^Tb<0\)成立。
证：
先证1成立时，2不可能成立。若存在一些\(x\geq 0\)使得\(Ax=b\)成立，并且有\(p^TA\geq 0^T\)，那么\(p^Tb=p^TAx\geq 0\)。
下来证1不成立时，2成立。假设不存在\(x\geq 0\)使得\(Ax=b\)。考虑下面的两个问题：
注意左边的问题是右边的对偶问题。由假设可知左边的问题不可行，那么这表示右边的问题要么是无界的（最优值为\(-\infty\)）要么是不可行的。由于\(p=0\)是右边问题的一个可行解，说明这个问题是无界的。因此，存在满足\(p^TA\geq 0^T\)，使得\(p^Tb<0\)(因为最优解为\(-\infty\))。证毕。
下面我们从几何的角度重新审视一下 Farkas 引理。记矩阵\(A\)的列分别为\(A_1,\cdots,A_n\)，则有\(Ax=\sum_{i=1}^nA_ix_i\)。那么若存在\(x\geq 0\)使得\(Ax=b\)将等价于\(b\)可以表示为列\(A_1,\cdots,A_n\)的非负线性表出（如下图的阴影部分）。如果\(b\)没有落在阴影部分（Farkas引理的1就不成立），我们想要找到一个向量\(p\)使得\(b\)落在超平面\(\{z\mid p^Tz=0\}\)的一侧，而阴影面积在另一侧。那么我们就有了\(p^Tb<0\)而\(p^TA_i\geq 0,\,\forall i\)，这也就是说引理中的2成立。
结论： 已知向量\(A_1,\cdots,A_n\)以及\(b\)，假设对于任意向量\(p\)都有\(p^TA_i\geq 0,\,\)\(i=1,\cdots,n\)且 \(p^Tb\geq 0\)。那么\(b\)可以表示为向量\(A_1,\cdots,A_n\)的非负线性组合。
定理： 假设线性不等式\(Ax\leq b\)存在至少一个解，且有\(d\in\mathbb{R}\)，那么下面的描述等价：
- \(Ax\leq b\)的每个可行解都满足\(c^Tx\leq d\)。
- 存在\(p\geq 0\)使得\(p^TA=c^T\)以及\(p^Tb\leq d\)成立。
证：
考虑如下的问题（左边的是右边的对偶问题）：
若\(Ax\leq b\)存在可行解并且每个可行解都满足\(c^Tx\leq d\)，这说明左边的问题有最优解并且最优值是有界的。根据强对偶可知，右边的问题存在最优解\(p\)且\(p^Tb\leq d\)。
相反的，若存在 \(p\) 满足\(p^TA=c^T,\,p \geq 0\)以及\(p^Tb\leq d\)，那么由弱对偶定理可知左边问题的每一个可行解都满足\(c^Tx\leq p^Tb\leq d\)。证毕。
考虑一个单期市场，假设有n个不同的可交易的资产。并且在期末时，每种资产都有m种可能的状态。如果我们在期初对资产\(i\)投资\(1\)元，期末时资产变到达状态\(s\)，我们记得到的支付 （payoff） 为\(r_{si}\)。因此，每一个资产\(i\)可由一个支付向量\((r_{1i},\cdots,r_{mi})\)描述。下面的\(m\times n\)的支付矩阵描述了n个资产的m种状态：
记\(x_i\)为持有资产\(i\)的数量。\(x=(x_1,\cdots,x_n)\)描述了一个资产组合。其中\(x_i\)可正可负，正值代表买入\(x_i\)的资产\(i\)（多头），期末时若状态为\(s\)，则资产变为\(r_{si}x_i\);负值代表空头，它可以理解为在期初"借"了\(|x_i|\)的资产\(i\)然后卖出，在期末时在市场中买入\(|x_i|\)的资产\(i\)还给被“借”方，这说明在期末时若状态为\(s\)，那么将需要支出\(r_{si}|x_i|\)（注：当资产价值升高时，多头赚钱；当资产价值下降时，空头赚钱。）
因此期末状态为\(s\)时，投资组合\(x\)的总资产变为:
记向量\(w=(w_1,\cdots,w_m)\)，然后有
若期初时资产\(i\)的价格为\(p_i\)，基资产价格向量\(p=(p_1,\cdots,p_n)\)，那么获得资产组合\(x\)需要花费\(p^Tx\)。现在的问题就是资产\(i\)的期初价格\(p_i\)如何确定呢？
我们先引入一个经济学的原理：无套利原理，在这里可描述为：若\(Rx\geq 0\)，那么必然有\(p^Tx\geq 0\)。可是满足无套利原理的\(p_i\)应该如何确定呢？
定理： 无套利原理满足当且仅当存在非负向量\(q=(q_1,\cdots,q_m)\)使得资产i的价格为
\[p_i=\sum_{s=1}^mq_sr_{si}. \]
证：
无套利原理说明了不存在\(x\)使得\(x^TR^T\geq 0^T\)以及\(x^Tp<0\)成立（这恰好就是Farkas引理的第2个描述）。由Farkas引理可知，存在非负向量\(q\)使得\(R^Tq=p\)。证毕。
这个定理说明了，在市场运作很好时，状态价格\(q_s\)可以用来计算当前资产价格。
在之前，我们是通过单纯形法引出对偶理论的。这里我们换个方式，先介绍分离超平面，然后引入Farkas引理，之后叙述对偶理论。
称集合\(S\subset \mathbb{R}^n\)为闭集是指满足：若\(x^1,x^2,\cdots\)是\(S\)中的一列收敛到\(x\in\mathbb{R}^n\)的元素，有\(x\in S\)。换句话说，\(S\)是闭集是指\(S\)包含任意点列的极限。
定理： 多面体是闭集。
证：
考虑多面体\(P=\{x\in\mathbb{R}^n\mid Ax\geq b\}\)。若\(P\)中序列\(^1,x^2,\cdots\)收敛到\(x^*\)，我们需要证明\(x^*\in P\)。对于任意\(k\)，有\(x^k\in P\)说明\(Ax^k\geq b\)。给两边取极限则有
这说明\(x^*\in P\)。证毕。
下面给出的定理来自于实分析，它为证明优化问题存在优化解提供了很重要的结论。但证明在这里略去了。
定理：（Weierstrass 定理） 若\(f:\mathbb{R}^n\mapsto \mathbb{R}\)是一个连续函数，\(S\)是\(\mathbb{R}^n\)的一个非空有界的闭子集。那么存在\(x^*\in S\)使得\(f(x^*)\leq f(x),\) \(\forall x\in S\)。类似的，存在\(y^*\in S\)使得\(f(y^*)\geq f(x),\) \(\forall x\in S\)。
若集合\(S\)不是闭集的话Weierstrass 定理也就失效了。比如集合\(S=\{x\in\mathbb{R}\mid x>0\}\)不是闭集（可以找到一个收敛到0的点列），对于\(f(x)=x\)上述的结果就不存在（总可以找到另一个更小的值）。这个例子中\(S\)不是闭集是因为定义\(S\)的不等式是严格不等的，而多面体的定义就避免了这种情形。
这一部分介绍的定理几何上看很直观，对于凸集的学习很重要。它描述了若存在一个非空闭集\(S\)以及一个点\(x^*\notin S\)，那么我们可以找到一个超平面（称为分离超平面 （separating hyperplane）），使得\(S\)和\(x^*\)位于不同的半空间（如下图）。
定理：（分离超平面定理） \(S\)是\(\mathbb{R}^n\)种的一个非空闭的凸集，\(x^*\in\mathbb{R}^n\)是一个不属于\(S\)的向量。那么存在向量\(c\in\mathbb{R}^n\)使得 \(c^T x^* < c^Tx,\,\forall x\in S\)。
证：
记\(\parallel\cdot\parallel\)为欧几里得范数，定义为\(\parallel x\parallel=(x^Tx)^{1/2}\)。假设现在固定一个点\(w\in S\)，然后定义
以及\(D=S\cap B\) （下图中的图\((a)\)）。集合\(D\)是非空的，因为\(w\in D\)。另外由于\(D\)是两个闭集的交，因此\(D\)也是闭的。同时由于\(B\)是有界的，\(D\)也是有界的。考虑\(\parallel x-x^*\parallel\) \(x\in D\)是关于\(x\)的连续函数。
由于\(D\)是非空闭的有界集合，根据Weierstrass 定理可知存在\(y\in D\)使得
对于任意属于\(S\)但不属于\(D\)的元素\(x\)，都有
因此，我们可知
这说明了\(S\)中存在 \(y\) 使得 \(y\) 离\(x^*\)最近。下面说明向量\(c=y-x^*\)就是满足定理要求的（上图中图\((b)\)）。
若\(x\in S\)，对于任意\(\lambda\in (0,1]\)，由于\(S\)是一个凸集，因此有\(y+\lambda(x-y)\in S\)。又由于\(y\)是离\(x^*\)最近的，因此
这表明
给上式两边同时除以\(\lambda\)，然后取关于\(\lambda \to 0\)的极限，可得
(这个不等式说明了图\((b)\)中的角\(\theta\)不能超过90度)。因此
令\(c=y-x^*\)。证毕。
这里，我们使用分离超平面定理再重新审视 Farkas 引理。仅考虑证明较难的那部分，也就是若\(Ax=b,\,\)\(x\geq 0\)不存在解，则存在向量\(p\)使得\(p^TA\geq 0^T\)以及\(p^Tb<0\)成立。
令
并且假设\(b\notin S\)。显然\(S\)是一个非空闭凸集（非空是有\(0\in S\)，凸集是由于约束是线性的，闭集是因为\(S\)是多面体\(\{(x,y)\mid y=Ax,\, x\geq 0\}\)在\(y\)轴上的投影（参考线性规划中的几何（五）））。
使用分离超平面定理分离\(S\)和\(b\)，存在向量\(p\)使得\(p^Tb < p^Ty,\) \(\forall y\in S\)。由于\(0\in S\)，因此\(p^Tb<0\)。另外，对于\(A\)的任意列\(A_i\)以及\(\lambda >0\)，都有\(\lambda A_i\in S\)及
式子两边同时除以\(\lambda\)，然后取关于\(\lambda\to\infty\)的极限，可得
（等于0是因为\(p^Tb<0\)）。由于上式对于任意\(i\)都成立，因此有\(p^TA\geq 0^T\)。
这里我们描述通过 Farksa 引理得到对偶理论，仅证明原问题的约束是\(Ax\geq b\)的情形。
考虑如下的原问题（左）和对偶问题（右）：
假设原问题存在最优解\(x^*\)。然后我们证明对偶问题也存在一个可行解使得对偶问题目标函数值与原问题的最优值相同，那么由上上节的推论可得到强对偶定理的结果。
记\(I=\{i\mid a_i^Tx^*=b_i\}\)为原问题约束有效的下标的集合。我们先证对于满足\(a_i^Td\geq 0,\) \(i\in I\)的任意向量\(d\)都有\(c^Td\geq 0\)。考虑满足\(a_i^Td\geq 0,\) \(i\in I\)的向量\(d\)以及极小值\(\epsilon\)，有
另外对于\(i\notin I\)以及\(\epsilon\)足够小，有\(a_i^T(x^*+\epsilon d) > b_i\)。因此\(x^*+\epsilon d\)是原问题的一个可行解。又由于\(x^*\)是最优解，那么\(c^Td\geq 0\)。由 Farkas 引理（参考Farkas几何中的结论）可知\(c\)可以表示为向量\(a_i,\, i\in I\)的非负线性组合，也即存在非负的\(p_i,\,i\in I\)使得
而对于\(i\notin I\),我们定义\(p_i=0\)。那么有\(p\geq 0\)，结合上式可知\(p^TA=c^T\)。另外
至此，证明完毕。
参考文献: Introduction to Linear Optimization by Dimitris Bertsimas & John N. Tsitsiklis.
原文：https://www.cnblogs.com/yhxm/p/13047489.html