前言

参考与上一节相同

对偶理论

事物之间普遍存在某种对偶关系，从不同的角度（立场）出发观察事物时，有两种拟似对立的表述。如“平面上矩形的面积与周长的关系”可分别表述为：周长一定，面积最大的矩形是正方形。同样地，每个线性规划问题都有一个与之对应的另一个线性规划问题，我们称之为对偶问题（Dual Problem），在经济学中有时研究对偶解也称为研究影子价格（Shadow Price）

对偶线性问题

对偶性的引入

我们假设某个工厂A在计划期内要安排生产I,II两种产品，需要用到劳动力、设备和A，B两种原材料。已知生产单位产品的利润与所需各种资源的消耗量如下表所示

我们站在工厂资源配置的角度，需要确定两种产品的产量。设x_1,x_2分别为产品I和产品II的生产数量，我们优化产品的利润，方向为最大化，约束是资源配额，则该厂面临的优化模型为
::: align-center
\begin{aligned} &\max z=80x_100x_2\\ &s.t.\left\{\begin{matrix}8x_1+4x_2\le 360&\text{劳动力}\\ 4x_1+5x_2\le 200&\text{设备}\\ 3x_1+10x_2\le 250&\text{原材料A}\\ 4x_1+6x_2\le 200&\text{原材料B}\\ x_1,x_2\ge 0&\text{非负性}\end{matrix}\right . \end{aligned}

:::
该问题的最优决策为：产品I的产量为42.5，产品II的产量5单位，有最优利润3900元。在该生产安排下，劳动力和原材料B将刚好消耗完（是紧约束），而设备工时和原材料A将存在一定的剩余（是非紧约束）

现在假设有另外一家企业B需要完成某个项目，正好需要这家企业所具备的劳动力、设备和两种原材料资源（注意，这里我们不再从产品的角度考虑了，而是从劳动力、设备和材料的角度考虑），因此B的老板找到A的老板商量，A老板表示只要企业B支付的价格合适一切都好商量，但是B的老板肯定想尽可能少付钱，但又不能付的太少，因为如果钱太少A企业宁愿去接着生产产品I和II，所以我们现在优化劳动力/设备/原料的租金，方向为最小化，约束是A企业产品的利润，设各个资源的租金为y_1-y_4，现在目标函数变为
::: align-center
\min w=360y_1+200y_2

:::
为了让A企业放弃生产产品I,II，我们需要给“高于两种产品利润的价格”，因而约束变为
::: align-center
\left\{\begin{aligned}&8y_1+4y_2+3y_3+4y_4\ge 80\\ &4y_1+5y_2+10y_3+6y_4\ge 100\\ &y_1,y_2,y_3,y_4\ge 0\end{aligned}\right .

:::
求解上述问题得到的最优解w与原问题的最优解z是相同的

对比这两个问题，我们可以发现这两个线性规划模型所有的参数（目标函数、工艺矩阵、约束右边项）都是共同的，只是参数在不同模型中位置不同而已，我们称这两个模型为互为对偶的线性规划模型

（笔者）书上没有讲到的是，从另一种角度理解，在原问题和对偶问题中我们都在考虑优化同一个目标函数f(x_1,x_2,y_1,y_2,y_3,y_4)，只不过，在原问题中，我们考虑的是“在配额尽可能小的条件下令利润最大化”，即\max_{x_i\in\mathcal{X}}\min_{y_i\in\mathcal{Y}}f（只不过在我们显式的写出y_i关于x_i的约束不等式的情况下无需写出内层的最小化问题）而在对偶问题中我们考虑的是\min_{y_i\in\mathcal{Y}'}\max_{x_i\in\mathcal{X'}}f（只不过在我们显式的写出xi关于y_i的约束不等式的情况下无需写出内层的最大化问题），所以写对偶问题实际上是一种研究交换内外求最优化的问题，如果笔者阅读过李航的《统计学习方法》，一定会有更深的体会

一般地，我们考虑一个原问题（Primary Problem，简记为P）：
::: align-center
\begin{aligned}&\max z=c_1x_1+c_2x_2+\cdots+c_nx_n\\ &s.t.\left\{\begin{aligned}&a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n\le b_1\\&a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n\le b_2\\&\cdots\\&a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n\le b_m\\&x_1,x_2,\cdots,x_n\ge 0\end{aligned}\right .\end{aligned}

:::
那么，其对偶问题（Dual Problem，简记为D）为
::: align-center
\begin{aligned}&\min w=b_1y_1+b_2y_2+\cdots+b_my_m\\&s.t.\left\{\begin{aligned}&a_{11}y_1+a_{21}y_2+\cdots+a_{m1}y_m\ge c_1\\&a_{12}y_1+a_{22}y_2+\cdots+a_{m2}y_m\ge c_2\\&\cdots\\&a_{1n}y_1+a_{2n}y_2+\cdots+a_{mn}y_m\ge c_n\\&y_1,y_2,\cdots,y_m\ge 0\end{aligned}\right .\end{aligned}

:::
原问题和对偶问题之间的对称关系体现为：

• 原问题的每个约束对应对偶问题的一个决策变量
• 原问题为求极大（或极小），则对偶问题为求极小（或极大）
• 原问题的目标函数系数对应于对偶问题约束右边项
• 原问题的约束右边项对应于对偶问题的目标函数系数
• 原问题的系数矩阵和对偶问题的系数矩阵互为转置关系
• 原问题的约束条件方向为小于等于，其对偶问题的约束条件方向为大于等于

（笔者）其中，倒数第二条的在线性代数中也有类似的体现，比如，向量点积b^Tc中c的转置b^T就相当于向量b的对偶向量，而它还可以理解为一个n\times 1的矩阵，它将向量c转化为一个数，也就是c在b上的投影乘以b的长度（特别地，当b为单位向量时为c在b上的投影）

同时，如果用矩阵表示，上述原问题和对偶问题分别为：
::: align-center
(P)\begin{aligned}&\max z= CX\\&s.t.\left\{\begin{aligned}&AX\le b\\&X\ge 0\end{aligned}\right .\end{aligned}\space\space\space(D)\begin{aligned}&\min w=Yb\\&s.t.\left\{\begin{aligned}&YA\ge C\\&Y\ge 0\end{aligned}\right .\end{aligned}
:::
其中原问题中$X

接下来考虑带等式约束的原问题的对偶问题，原问题为：
::: align-center
\begin{aligned}&\max z=\sum_{j=1}^n c_jx_j\\&s.t.\left\{\begin{aligned}&\sum_{j=1}^na_{ij}x_j=b_i,i=1,2,\cdots,m\\&x_j\ge 0,j=1,2,\cdots,n\end{aligned}\right .\end{aligned}
:::
先考虑将等式约束条件分解为两个不等式约束条件，考虑构造约束：
::: align-center
b_i\le\sum_{j=1}^na_{ij}x_j\le b_i
:::
之后将其分解为：
::: align-center
\left\{\begin{aligned}&\sum_{j=1}^na_{ij}x_j\le b_i,i=1,\cdots m\\&-\sum_{j=1}^na_{ij}x_j\le-b_i,i=1,\cdots,m\end{aligned}\right .
:::
此时就可以按照已有的方法写出对偶问题：
::: align-center
\begin{aligned}&\min w=\sum_{i=1}^mb_iy_i'+\sum_{i=1}^m(-b_iy_i'')\\&s.t.\left\{\begin{aligned}&\sum_{i=1}^ma_{ij}y_i'+\sum_{i=1}^m(-a_{ij}y_{i}'')\ge c_j\\&y_i',y_i''\ge 0,i=1,2,\cdots,m\end{aligned}\right .\end{aligned}
:::
将其整理为：
::: align-center
\begin{aligned}&\min w=\sum_{i=1}^mb_iy_i'+\sum_{i=1}^m(-b_iy_i'')\\&s.t.\left\{\begin{aligned}&\sum_{i=1}^ma_{ij}(y_i'-y_i'')\ge c_j\\&y_i',y_i''\ge 0,i=1,2,\cdots,m\end{aligned}\right .\end{aligned}
:::
令y_i=y_i'-y_i'',y_i',y_i''\ge 0，由此可见y_i不受正负限制，它是自由（Unstricted） 的
::: align-center
\begin{aligned}&\min w=\sum_{i=1}^mb_iy_i'+\sum_{i=1}^m(-b_iy_i'')\\&s.t.\left\{\begin{aligned}&\sum_{i=1}^ma_{ij}y_i\ge c_j\\&y_i自由,i=1,2,\cdots,m\end{aligned}\right .\end{aligned}
:::

下面给出原问题和对偶问题的对应关系表：

以上的变换法则又称为标准法则

对偶问题的性质

考虑
::: align-center
(P)\begin{aligned}&\max z= CX\\&s.t.\left\{\begin{aligned}&AX\le b\\&X\ge 0\end{aligned}\right .\end{aligned}\space\space\space(D)\begin{aligned}&\min w=Yb\\&s.t.\left\{\begin{aligned}&YA\ge C\\&Y\ge 0\end{aligned}\right .\end{aligned}
:::

对称性

对偶问题的对偶问题即为原问题
证：将对偶问题进行等价变换
::: align-center
\begin{aligned}&\max(-w)=-Yb\\&s.t.\left\{\begin{aligned}&-YA\le -C\\&Y\ge 0\end{aligned}\right .\end{aligned}
:::
上述问题的对偶问题为
::: align-center
\begin{aligned}&\min z'=-CX\\&s.t.\left\{\begin{aligned}&-AX\ge -b\\&X\ge 0\end{aligned}\right .\end{aligned}
:::
在进行等价变换即可得到等价于原问题（P）的问题

弱对偶性（Weak Duality）

若\bar{X}是原问题的任一可行解。\bar{Y}是对偶问题的任一可行解，则有C\bar{X}\le \bar{Y}b
证：因\hat{X}是原问题的可行解，所以其满足约束条件
::: align-center
A\bar{X}\le b
:::
若\bar{Y}是给定的一组非负值，将其左乘上式，得到
::: align-center
\bar{Y}A\bar{X}\le \bar{Y}b
:::
因为\bar{Y}是对偶问题的可行解，所以满足
::: align-center
\bar{Y}A\ge C
:::
将\bar{X}右乘上式，得到
::: align-center
\bar{Y}A\bar{X}\ge C\bar{X}
:::
于是得
::: align-center
C\bar{X}\le\bar{Y}A\bar{X}\le\bar{Y}b
:::
证毕

弱对偶性表明，原问题中任一可行解所对应的目标函数值都构成对偶问题任一可行解对应函数值的下界，反之，对偶问题中任一可行解所对应的目标函数值都构成原问题任一可行解对应函数值的上界

弱对偶性好比任何时候你的存款（原问题目标值）均不可能超过你的信用额度（对偶问题目标值）

最优性&强对偶性（Strong Duality）

如果\hat{X},\hat{Y}分别是问题(P)和(D)的一个可行解，且满足C\hat{X}=\hat{Y}b，则它们分别是问题(P)和问题(D)的最优解
证：由弱对偶性知：对偶问题的任一可行解\bar{Y}都满足\bar{Y}b\ge C\hat{X}，因为C\hat{X}=\hat{Y}b，所以\bar{Y}b\ge\hat{Y}b，可见\hat{Y}是使对偶问题(D)目标函数取最小值的可行解，因而是最优解。同样地，可以证明对于原问题的任一可行解\bar{X}，有
::: align-center
C\hat{X}=\hat{Y}b\ge C\bar{X}
:::
所以\hat{X}是原问题(P)的最优解

强对偶性则指出如果原线性规划问题有最优解，那么其对偶问题也一定有最优解，并且两个最优解的目标函数值相等

强对偶性好比你在精心规划后财务状况达到最优状态，存款正好等于可用的信用额度，两者的资源价值被等价的衡量了出来，这就是影子价格概念的来源

松弛互补性（Complementary Slackness）

若\hat{X},\hat{Y}分别是如下标准化形式的原问题和对偶问题的可行解
::: align-center
(P)\begin{aligned}&\max z= CX\\&s.t.\left\{\begin{aligned}&AX+X_s=b\\&X,X_s\ge 0\end{aligned}\right .\end{aligned}\space\space\space(D)\begin{aligned}&\min w=Yb\\&s.t.\left\{\begin{aligned}&YA-Y_s=C\\&Y,Y_s\ge 0\end{aligned}\right .\end{aligned}
:::
那么\hat{X}和\hat{Y}是两个问题的最优解的充要条件是：
::: align-center
\hat{Y}X_s=0且Y_s\hat{X}=0
:::
证：将原问题中的C用对偶问题约束中的C=YA-Y_s代替后，得到
::: align-center
z=(YA-Y_s)X=YAX-Y_sX
:::
将对偶问题的目标函数中系数列向量，用b=AX+X_s代替后，得到
::: align-center
w=Y(AX+X_s)=YAX+YX_s
:::

• 若Y_s\hat{X}=0,\hat{Y}X_s=0，则有\hat{Y}b=\hat{Y}A\hat{X}=C\hat{X}，有弱对偶性可知\hat{X},\hat{Y}分别是原问题和对偶问题的最优解
• 若\hat{X}\hat{Y}分别是原问题和对偶问题的最优解，则由强对偶性可知C\hat{X}=\hat{Y}A\hat{X}=\hat{Y}b，因此，必有\hat{Y}X_s=0,Y_s\hat{X}=0

松弛互补性表明，在原问题中，如果某条不等式约束存在“剩余”时（即这条不等式约束代入最优解后的松弛/剩余变量\hat{x}_{n+i}>0），那么此条不等式对应的对偶问题中的决策变量在对偶问题的最优解中一定取0；反之，如果对偶问题中的某个决策变量在对偶问题最优解中取正，那么该决策变量对应的原问题中的不等式约束在代入原问题最优解后一定正好取等号（即此条不等式约束中的松弛/剩余变量取0）

换句话说你手里有两种资源：时间和金钱，你制定了最优的日程表以最大化的利用时间（原问题最优解），同时对偶地，市场有针对你在当前最优状态下每项活动进行后获得的最优物质回报（对偶问题最优解，“影子价格”），想象一下，如果你现在的日程中有一些安排是松弛的（比如说，你要求某个业务的时间应在4小时内完成，但是实际上你2小时就完成了，剩余了2小时），那么对应地，这剩余的2小时在“影子价格”中的价值就是0，因为你在最优的方案里这个业务的时间都没用完，那多加的业务时间对于你总收入的增加是没有帮助的，它是“闲置资产”；反之，如果你在最大化物质回报中看到了某项业务的“影子价格”大于0，那么你一定在日程安排中满打满算地安排了它，因为这个业务能让你获得回报，所以你当然会把它的档期安排满，在经济学上，这揭示了你在达到财务最优状态时，每一项具体资源的配置和其真实价值之间那套“严丝合缝，此消彼长”的关系，同时，它也暗含了，所谓“影子价格”是一种机会成本（Opportunity Cost），在后面我们会详细介绍它。

以上的强弱对偶性和松弛互补条件只是针对线性规划问题的，如果推广到二次规划，笔者的这篇文章对其做了简要的介绍

为什么？

标准法则

标准法则变换的根源是拉格朗日乘数法，我们考虑其中的一种情况，对于形如下方的原问题：
::: align-center
\begin{aligned}&\min c^Tx\\&s.t.\left\{\begin{aligned}&Ax\ge b\\&x\ge 0\end{aligned}\right .\end{aligned}
:::
我们引入拉格朗日乘子向量y\in\mathbb{R}^m，我们要求y\ge 0（因为此时我们要最小化拉格朗日函数，在这种问题上我们一般约定所有拉格朗日乘子非负，注意，标准法则中原问题的约束与对偶问题的对偶变量之间的同号变换就是从这里来的，如果原问题是最大化问题，我们一般约定所有拉格朗日乘子非正），同样地，对于约束x\ge 0，引入乘子向量s\ge 0,s\in\mathbb{R}^m

接下来构造拉格朗日函数：
::: align-center
L(x,y,s)=c^Tx-y^T(Ax-b)-s^Tx
:::
注意这里后面两个项（我们一般称之为罚项）的符号，因为原问题中Ax\ge b\Leftrightarrow Ax-b\ge 0，我们希望它为正，而同时我们对L的优化方向又是最小化，我们通过前面系数为-1的乘子来惩罚L（如果原问题是最大化问题，这里的系数应该为+1，当不等式条件违反时会造成一个令L减小的惩罚），这样当原约束Ax-b\ge 0被违反（即Ax-b< 0时）对应的罚项为正，导致L变大，我们就达到了“惩罚”的效果（更具体的，在我们最小化拉格朗日函数的过程中，我们的优化方向会强迫该不等式向着Ax-b\ge 0的方向移动），对于x\ge 0这个约束，亦然

此时我们就不再考虑Ax\ge b和x\ge 0这两个约束了，对于L这个函数，x,y,s取值任意，我们只需要保证y,s\ge 0即可

接下来我们定义对偶函数g(y,s)，对偶函数是拉格朗日函数关于原变量的下确界，取关于x的下确界后对偶函数是一个只与y,s有关的函数：
::: align-center
g(y,s)=\inf_{x\in\mathbb{R}^n}L(x,y,s)
:::
整理关于x的项：
::: align-center
L(x,y,s)=(c^T-y^TA-s^T)x+y^Tb
:::
对其取下确界时，为了避免让g不趋于负无穷（即为了让g有下确界），x的系数必须为零，否则存在x可以使得L无下确界，因此有：
::: align-center
c^T-y^TA-s^T=0\Rightarrow A^Ty+s=c
:::
此时我们得到：
::: align-center
g(y,s)=y^Tb
:::
同时，考虑之前我们得到的等式A^Ty+s=c，又有约束s\ge 0，所以我们可以得到有不等式A^Ty\le c

此时考虑原问题中最小化L就等于最大化其下确界g，于是对偶问题就变为了
::: align-center
\begin{aligned}&\max y^Tb\\&s.t.\left\{\begin{aligned}&A^Ty\le c\\&y\ge 0\end{aligned}\right .\end{aligned}
:::

阅读了以上问题后我们可以给出不同类型的原问题转化为对偶问题的标准法则：

这里“小”“大”指的是原问题的最优化方向

强弱对偶性和松弛互补性

考虑标准优化问题：
::: align-center
\begin{aligned}&\min_xf_0(x)\\&s.t.\left\{\begin{aligned}&f_i(x)\le 0,i=1,2,\cdots,m\\&h_j(x)=0,j=1,2,\cdots,p\end{aligned}\right .\end{aligned}
:::
原问题为最小化，第一条约束小于零，所以我们引入拉格朗日乘子\lambda_i>0，和\mu_j（自由），构造拉格朗日函数
::: align-center
L(x,\lambda,\mu)=f_0(x)+\sum_{i=1}^m\lambda_if_i(x)+\sum_{j=1}^p\mu_jh_j(x)
:::

我们对其取下确界获得对偶函数g(\lambda,\mu)=\inf_xL(x,\lambda,\mu)
对于任意可行点x（即满足f_i(x^*)\le 0,h_j(x^*)=0，任意\lambda_i\ge 0），总是有\lambda_if_i(x)\le 0,\mu_jh_j(x)=0，因此此时有L(x,\lambda,\mu)\le f_0(x)，而又因g(\lambda,\mu)是L的下确界，故有g(\lambda,\mu)\le f_0(x)，更不必说当x取最优点x^*时，一定有
::: align-center
g(\lambda,\mu)\le f_0(x^*)
:::
而这就是弱对偶性，即对偶函数值是原问题最优值的一个下界，对偶问题
::: align-center
\max_{\lambda\ge 0,\mu}g(\lambda,\mu)
:::
就是寻找这个下界中“最紧”的那个，记其最优值为d^*，原问题最优值为p^*，一定有d^*\le p^*

而如果又有强对偶性d^*=p^*，这意味着，存在一组乘子(\lambda^*,\mu^*)使得拉格朗日函数的下确界正好等于原问题的最优值，换句话说，在这个点处拉格朗日函数对原变量是最小化的，对对偶变量是最大化的，这等价于(x^*,\lambda^*,\mu^*)是拉格朗日函数的一个鞍点，所以说强对偶性的成立，等价于拉格朗日函数的鞍点存在，而一般情况下我们见到的满足Slater条件的凸问题中，这个鞍点是保证存在的，否则需要通过检查函数Hessian矩阵的行列式是否小于0或通过其他方法判断

在强对偶成立（即拉格朗日函数存在鞍点）的前提下，根据强对偶，有
::: align-center
\begin{aligned}&f_0(x^*)=g(\lambda^*,\mu^*)\\&=\inf_xL(x,\lambda^*,\mu^*)\\&\le L(x^*,\lambda^*,\mu^*)\\&=f_0(x^*)+\sum_{i=1}^m\lambda_i^*f_i(x^*)+\sum_{j=1}^p\mu_j^*h_j(x^*)\end{aligned}
:::
因为x^*是可行解，所以h_j(x^*)=0且f_i(x^*)\le 0，故有
::: align-center
f_0(x^*)\le f_0(x^*)+\sum_{i=1}^m\lambda_i^*f_i(x^*)
:::
因为\lambda_i^*\ge 0且f_i(x^*)\le 0，故求和项\sum_{i=1}^p\lambda_i^*f_i(x^*)\le 0，而要使上述不等式成立，只有可能是求和项\sum_{i=1}^m\lambda_i^*f_i(x^*)=0，又因为求和项中的每一项都是非正数，所以其为零只有可能是每一项均为零，即：
::: align-center
\lambda_i^* f_i(x^*)=0,\forall i
:::
这就是松弛互补条件，当对偶问题中的不等式约束的决策变量最优点\lambda_i^*\ne 0时，一定有原问题对于原问题最优点x^*的不等式约束一定是紧的，即f_i(x^*)=0，如果原问题约束不是紧的，那么一定有对偶问题对应的决策变量\lambda_i=0，同时因为对偶问题的对偶就是原问题，我们同样可以得到松弛互补条件对于对偶问题也是成立的

KKT条件？

读者可能会发现，我们先线性规划问题中一般不讨论KKT条件的前几条（除去松弛互补条件的剩余几条梯度为零的条件），这是因为在线性规划问题中，以上的几条条件直接推导并定义了问题本身，一旦我们写出了线性规划问题的对偶问题并承认了对偶可行性（即对偶变量非负），这几个梯度条件就已经隐式的蕴含在其中了，因此在讨论线性规划最优性时，我们通常直接从对偶理论本身出发（单纯形法，对偶理论），而不必再回到KKT条件

而对于非线性规划问题，优化往往十分困难，因为上一节已经证明线性规划问题的最优解一定在可行域的顶点，而在非线性规划问题中，最优解可以是可行域内部或边界上的任意一点，甚至不唯一，但在满足一定约束规格（比如Slater条件）的前提下，对于一个局部最优解它一定满足KKT条件，此时的KKT条件可以充当“解的过滤器”，任何不满足KKT条件的解均可以在优化任务中被直接排除，特别地，当被优化函数可保证为凸时，KKT变为充要条件，此时一个点为最优解当且仅当其满足KKT条件