10.6 对偶性与KKT条件#
在第10.5节内容中，我们介绍了什么是拉格朗日乘数法及它的作用。同时还特意讲到，拉格朗日乘数法只能用来求解等式约束条件下的极值，但是当约束条件为不等式的时候又该如何进行求解呢？
10.6.1 广义拉格朗日乘数法#
由拉格朗日乘数法可知，对于如下等式条件的约束问题
$$ \begin{aligned} & \underset{w}{\mathop{\min }}\,\ \ f(w) \\ \text{s}.\text{t}. \ \ & {{h}_{i}}(w)=0,i=1,\cdots ,l. \\ \end{aligned}\tag{10-28} $$其中$w$是一个$n$维向量。
从式(10-28)可以明显看出这是一个含有等式约束条件下的条件极值问题，因此用拉格朗日乘数法就能解决。进一步可构造如下拉格朗日函数
$$ \mathcal{L}(w,\beta )=f(w)+\sum\limits_{i=1}^{l}{{{\beta }_{i}}}{{h}_{i}}(w)\tag{10-29} $$其中$\beta_i$是拉格朗日乘子。最后，通过对式子中所有的参数求偏导，令其为0便可求解所有未知变量。
此时，我们接着看如下优化问题
$$ \begin{aligned} & \underset{w}{\mathop{\min }}\ f(w) \\[2ex] \text{s}.\text{t}. \ & {{g}_{i}}(w)\le 0,i=1,\cdots ,k. \\[2ex] & {{h}_{i}}(w)=0,i=1,\cdots ,l. \\ \end{aligned}\tag{10-30} $$从式(10-30)可以看出，与式(10-28)明显不同的就是在式(10-30)中多了不等式约束条件，因此，为了解决这类问题需要定义如下所示的广义拉格朗日乘数法（Generalized Lagrangian）[2]，即
$$ \mathcal{L}(w,\alpha ,\beta )=f(w)+\sum\limits_{i=1}^{k}{{{\alpha }_{i}}}{{g}_{i}}(w)+\sum\limits_{i=1}^{l}{{{\beta }_{i}}}{{h}_{i}}(w)\tag{10-31} $$其中，$\alpha_i$和$\beta_i$都是拉格朗日乘子，但接下来的求解过程与之前就大相径庭了。
10.6.2 原始优化问题#
根据式(10-30)和式(10-31)考虑如下定义
$$ {{\theta }_{\mathcal{P}}}(w)=\underset{\alpha ,\beta :{{\alpha }_{i}}\ge 0}{\mathop{\max }}\,\mathcal{L}(w,\alpha ,\beta )\tag{10-32} $$式(10-32)表示的含义是求得最大化$\mathcal{L}(w,\alpha ,\beta )$时$\alpha$和$\beta$的取值，即$\alpha$和$\beta$作为自变量与$w$无关，最终求得的结果$\theta_{\mathcal{P}}$是关于$w$的函数。
因此，如果原约束条件$g_i(w)\leq0$和$h_i(w)=0$均成立，则式(10-32)等价为
$$ \underset{\alpha ,\beta :{{\alpha }_{i}}\ge 0}{\mathop{\max }}\,\left[ \sum\limits_{i=1}^{k}{{{\alpha }_{i}}}{{g}_{i}}(w)+\sum\limits_{i=1}^{l}{{{\beta }_{i}}}{{h}_{i}}(w) \right]\tag{10-33} $$则此时有$\theta_{\mathcal{P}}(w)=f(w)+0$。
同时，我们现在来做这样一个假设，如果存在$g_i$或$h_i$ 使原约束条件不成立，即${{g}_{i}}(w)>0$ 或者${{h}_{i}}(w)\ne 0$，则在这样的条件下$\theta_\mathcal{P}$会发生什么变化呢？如果${{g}_{i}}(w)>0$，为了最大化$\mathcal{L}$，只需取$\alpha_i$为无穷大，则此时$\mathcal{L}$为无穷大，但这样没有意义。同样，如果${{h}_{i}}(w)\ne 0$ ，取$\beta$为无穷大（${{h}_{i}}$与$\beta$同号），则最后结果同样会无穷大。于是在这两种情况下便可以得到$\theta_{\mathcal{P}}(w)=\infty$。
进一步，结合上述两种情况就可以得到下面这个式子
$$ {{\theta }_{\mathcal{P}}}(w)= \begin{cases} f(w), & \text{如果 }w\;\text{满足约束条件}\\ \infty , & \text{其它} \\ \end{cases}\tag{10-34} $$再进一步，在满足约束条件的情况下最小化$\theta_{\mathcal{P}}(w)$就等同于式(10-30)中所要求解的问题。于是便可以得到如下定义
$$ {{p}^{*}}=\underset{w}{\mathop{\min }}\,{{\theta }_{\mathcal{P}}}(w)=\underset{w}{\mathop{\min }}\,\underset{\alpha ,\beta :{{\alpha }_{i}}\ge 0}{\mathop{\max }}\,\mathcal{L}(w,\alpha ,\beta )\tag{10-35} $$同时，将式(10-35)称为原始优化问题（Primal Optimization Problem）。
10.6.3 对偶优化问题#
接下来继续定义
$$ {{\theta }_{\mathcal{D}}}(\alpha ,\beta )=\underset{w}{\mathop{\min }}\,\mathcal{L}(w,\alpha ,\beta )\tag{10-36} $$式(10-36)表示的含义是求得最小化$\mathcal{L}(w,\alpha ,\beta )$时$w$的取值，即$w$作为自变量（与$\alpha$和$\beta$无关），最终求得的结果$\theta_{\mathcal{D}}$是关于$\alpha$和$\beta$的函数。
此时便能定义出原问题的对偶问题
$$ {{d}^{*}}=\underset{\alpha ,\beta :{{\alpha }_{i}}\ge 0}{\mathop{\max }}\,{{\theta }_{\mathcal{D}}}(\alpha ,\beta )=\underset{\alpha ,\beta :{{\alpha }_{i}}\ge 0}{\mathop{\max }}\,\underset{w}{\mathop{\min }}\,\mathcal{L}(w,\alpha ,\beta )\tag{10-37} $$并将(10-37)称为对偶优化问题（Dual Optimization Problem）。
可以发现，式(10-35)和式(10-37)的唯一区别就是求解顺序发生了变化，前者是先最大化再最小化，而后者是先最小化然后最大化。
那么原始问题和对偶问题有什么关系呢？为什么又要用对偶问题？通常情况下两者满足以下关系
$$ {{d}^{*}}=\underset{\alpha ,\beta :{{\alpha }_{i}}\ge 0}{\mathop{\max }}\,\underset{w}{\mathop{\min }}\,\mathcal{L}(w,\alpha ,\beta )\le \underset{w}{\mathop{\min }}\,\underset{\alpha ,\beta :{{\alpha }_{i}}\ge 0}{\mathop{\max }}\,\mathcal{L}(w,\alpha ,\beta )={{p}^{*}}\tag{10-38} $$证明
由式(10-32)和式(10-36)可知，对于任意的$w$、$\alpha$、$\beta$有
$$ {{\theta }_{\mathcal{D}}}(\alpha ,\beta )=\underset{w}{\mathop{\min }}\,\mathcal{L}(w,\alpha ,\beta )\le \mathcal{L}(w,\alpha ,\beta )\le \underset{\alpha ,\beta :{{\alpha }_{i}}\ge 0}{\mathop{\max }}\,\mathcal{L}(w,\alpha ,\beta )={{\theta }_{\mathcal{P}}}(w)\tag{10-39} $$所以有
$$ {{\theta }_{\mathcal{D}}}(\alpha ,\beta )\le {{\theta }_{\mathcal{P}}}(w)\tag{10-40} $$进一步根据式(10-40)有
$$ \underset{\alpha ,\beta :{{\alpha }_{i}}\ge 0}{\mathop{\max }}\,{{\theta }_{\mathcal{D}}}(\alpha ,\beta )\le \underset{w}{\mathop{\min }}\,{{\theta }_{\mathcal{P}}}(w)\tag{10-41} $$由此便得到了式(10-38)中的不等式。
在上述过程中，之所以要用对偶问题是因为直接对原始问题进行求解异常困难，所以一般会通过将其转换为对偶问题进行求解，但就目前来看，两者并不完全等同，其解也就必然不会相同，所以下面就需要进一步介绍KKT条件。
10.6.4 KKT条件#
在10.6.3节中我们介绍过，要想用对偶问题的解来代替原始问题的解，就必须使两者等价。对于原始问题和对偶问题，假设函数$f(w)$和$g_i(w)$是凸函数，$h_i(w)$是仿射函数，并且存在一个$w$，使不等式$g_i(w)$严格可行（对于所有的$i$都有$g_i(w)<0$），则${{w}^{*}}$、${{\alpha }^{*}}$、${{\beta }^{*}}$同时原始问题和对偶问题解的充分必要条件是${{w}^{*}}$、${{\alpha }^{*}}$、${{\beta }^{*}}$满足（Karush-Kuhn-Tucker, KKT）条件[2]
$$ \frac{\partial }{\partial {{w}_{i}}}\mathcal{L}({{w}^{*}},{{\alpha }^{*}},{{\beta }^{*}})=0,\ i=1,\cdots ,n\tag{10-42} $$$$ \frac{\partial }{\partial {{\beta }_{i}}}\mathcal{L}({{w}^{*}},{{\alpha }^{*}},{{\beta }^{*}})=0,\ i=1,\cdots ,l\tag{10-43} $$$$ \alpha _{i}^{*}{{g}_{i}}({{w}^{*}})=0,i=1,\cdots ,k\tag{10-44} $$$$ {{g}_{i}}({{w}^{*}})\le 0,\ i=1,\cdots ,k\tag{10-45} $$$$ \alpha _{i}^{*}\ge 0,\ i=1,\cdots ,k\tag{10-46} $$其中式(10-44)称为KKT的对偶互补条件（Dual Complementarity Condition）。由此可以得到，如果$\alpha _{i}^{*}>0$，则必有$g_i(w)=0$，而这一点也将用来说明SVM仅仅只有少数的支持向量。同时，需要注意的是KKT条件中计算的是目标函数$\mathcal{L}(w,\alpha ,\beta )$中所有未知数及所有等式约束条件中拉格朗日乘子的偏导数。
因此，若存在${{w}^{*}}$、${{\alpha }^{*}}$、${{\beta }^{*}}$满足上述KKT条件，则${{w}^{*}}$、${{\alpha }^{*}}$、$\beta^{\ast}$既是对偶问题的解同样也是原始问题的解。
10.6.5 计算示例#
在介绍完对偶问题的相关求解原理后，下面再通过一个示例进行说明。试求解以下优化问题
$$ \begin{aligned} &\underset{x}{\mathop{\min}}\ f(x)=x_{1}^{2}+x_{2}^{2} \\[1ex] \text{s}.\text{t}. \ \ & h(x)={{x}_{1}}-{{x}_{2}}-3=0 \\[1ex] & g(x)={{({{x}_{1}}-3)}^{2}}+x_{2}^{2}-2\le 0 \\ \end{aligned}\tag{10-47} $$由于式(10-47)中的优化问题相对简单，所以可以先通过作图来直观地理解一下，如图10-12所示。
如图10-12所示，黑色虚线圆环为目标函数$f(x)$在水平面上的等高线， 黑色直线为等式约束条件$h(x)$的函数图形，整个灰色圆为不等式约束条件$g(x)$的函数图形。从图示中可以看出，由于目标函数$f(x)$存在约束条件$h(x)$，这就意味着最终求得的最优解必须位于直线$h(x)$上。同时，由于$f(x)$还要满足约束条件$g(x)$，所以解必定会在$h(x)$与$g(x)$相交的线段上。最后，由于是求解$f(x)$在约束条件下的最小值，所以最优解就是图10-12中的黑色圆点。
进一步，针对这一问题可以得到如下广义拉格朗日函数
$$ \mathcal{L}(x,\alpha ,\beta )=(x_{1}^{2}+x_{2}^{2})+\alpha \left[ {{({{x}_{1}}-3)}^{2}}+x_{2}^{2}-2 \right]+\beta ({{x}_{1}}-{{x}_{2}}-3)\tag{10-48} $$根据式(10-35)可知，式(10-48)对应的原始问题为
$$ {{p}^{*}}=\underset{x}{\mathop{\min }}\,\underset{\alpha ,\beta :\alpha \ge 0}{\mathop{\max }}\,\mathcal{L}(x,\alpha ,\beta )\tag{10-49} $$进一步，式(10-49)对应的对偶问题为
$$ {{d}^{*}}=\underset{\alpha ,\beta :\alpha \ge 0}{\mathop{\max }}\,\underset{x}{\mathop{\min }}\,\mathcal{L}(x,\alpha ,\beta )\tag{10-50} $$因此，接下来便可以通过式(10-50)中的顺序进行求解。
1. 最小化$\mathcal{L}(x,\alpha,\beta)$
此时将$\alpha$和$\beta$视为常数，那么这时$\mathcal{L}(x,\alpha,\beta)$就只是$x$的函数，因此可以通过令偏导数为0的方式来求得$\mathcal{L}(x,\alpha,\beta)$的最小值。故，此时有
$$ \begin{cases} \frac{\partial \mathcal{L}}{\partial {{x}_{1}}}=2{{x}_{1}}+\alpha (2{{x}_{1}}-6)+\beta =0 \\[2ex] \frac{\partial \mathcal{L}}{\partial {{x}_{2}}}=2{{x}_{2}}+2\alpha {{x}_{2}}-\beta =0 \\ \end{cases}\tag{10-51} $$