一文理解拉格朗日对偶和KKT条件

一. 最优化问题求解

1. 等式约束的极值求法

$\begin{gather*} \underset{t}{min} f(t) \; s.t.\; h_i(t)=0,i=1,\cdots,p \end{gather*}$
目标函数: $f(t)$ , 引入Lagrange算子: $L(t,\beta) = f(t) + \sum_{i=1}^n\beta_ih_i(t)$

2. 不等式约束的极值求法

$\begin{gather*} \underset{t}{min}f(t) \; s.t. &g_i(t) \le 0, i=1,\cdots,p \\ &h_j(t) = 0, j=1, \cdots, q \end{gather*}$
目标函数: $f(t)$
约束条件:

$g_i(t) \le 0, i=1, \cdots, p$
$h_j(t) \le 0, j=1, \cdots, q$
很多情况, 不等式约束条件可引入新变量转化为等式约束条件, 故上述问题可简化为:
$\underset{t}{min}f(t)\;s.t.\; g_i(t) = 0, i=1, \cdots, n$

3. 最优化问题分类

根据约束条件和目标函数的类型分为3类:

线性规划: 目标函数和约束条件都为变量的线性函数

二次规划: 目标函数为变量的二次函数, 约束条件为线性函数

非线性规划: 目标函数或者约束条件是非线性函数

4. KKT条件广义定义

KKT条件指在满足某些规则条件下, 非线性规划问题能有最优解的充要条件, 是广义拉格朗日乘数的重要成果
一般优化问题(含等式和不等式约束约束):
$\begin{gather*} \underset{t}{min}f(t) \; s.t. &g_i(t) \le 0, i=1,\cdots,p \\ &h_j(t) = 0, j=1, \cdots, q \end{gather*}$
引入Lagrange算子 $\alpha, \beta$ :
$L(t, \alpha, \beta) = f(t) + \sum_{i=1}^p\alpha_i g_i(t) + \sum_{j=1}^q\beta_j h_j(t)$

可将 $\alpha和\beta$ 分别看做两个约束 $g_i(t) \le 0和g_j(t) \ 0$ 的限制条件

KKT条件指上述问题的最优点 $x^*$ 必须满足:
(1) 约束条件满足: $g_i(x^*) \le0, h_i(x^*)=0$
(2) $\nabla L(t,\alpha,\beta)|_{t=x^*} = \nabla f(x^*) + \sum_{i=1}^p\alpha_i\nabla g_i(x^*) + \sum_{j=1}^q \beta_j \nabla h_j(x^*) = 0$
即,
最优点 $x^*$ 处, $\nabla f$ 必须是 $\nabla g_i$ 和 $\nabla h_j$ 的线性组合
引入拉格朗日算子可以求出极值的原因:

由于 $f(t)$ 的 $dt$ 变化方向受其他不等式的约束, 且在极值 $x^*$ 处， $f(t$ )的梯度 $\nabla f(x^*)$ 与 $\nabla g(x^*)$ , $\nabla h(x^*)$ 之间存在线性关系, 故引入拉格朗日算子可以求出极值

(3) $\beta_j \ne 0$ 且 $\alpha_i \ge 0,\; \alpha_i g_i(x^*) = 0$

不等式 $g_i(t)\le0$ 的限制条件有方向性, 故 $\alpha_i \ge 0$ , 等式 $h_j(t)=0$ 的限制条件无方向性, 故 $\beta_j$ 无符号限制

5 为什么SVM用Lagrange duality来解决最大化间隔问题?

不等式约束一直是优化问题中的难题，求解对偶问题可以将支持向量机原问题约束中的不等式约束转化为等式约束；

支持向量机中用到了高维映射，但是映射函数的具体形式几乎完全不可确定，而求解对偶问题之后，可以使用核函数来解决这个问题。

并不一定要用拉格朗日对偶。要注意用拉格朗日对偶并没有改变最优解，而是改变了算法复杂度：
在原问题下，求解算法的复杂度与样本维度（等于权值w的维度）有关；
而在对偶问题下，求解算法的复杂度与样本数量（等于拉格朗日算子a的数量）有关。

因此，

如果你是做线性分类，且样本维度低于样本数量的话，在原问题下求解就好了，Liblinear之类的线性SVM默认都是这样做的；
如果你是做非线性分类，那就会涉及到升维（比如使用高斯核做核函数，其实是将样本升到无穷维），升维后的样本维度往往会远大于样本数量，此时显然在对偶问题下求解会更好。
这样：

就可以由求特征向量w转化为求比例系数a，
就可以导出含有内积形式的目标函数，
就可以实现对内积后的gram矩阵使用核函数，以达到非线性分类的目的。

支持向量机实现非线性的方法的数学本质是升维，升维升到无穷维则无法表达w, 所以还是使用拉格朗日对偶方法更好一点。准确的说，可以用一些优化算法直接求最小间距，但是，升维的时候核要是正定的，且升维可数，而且不是很大的时候可以用。

二. 拉格朗日对偶和KKT

1. 带约束的优化问题

任意一个带约束的优化均可写成:
$\begin{gather*} \underset{x}{min}{f_0(x)}\;s.t. &f_i(x) \le 0, i= 1,\cdots,m \\ &h_i(x)=0,i=1,\cdots,p \end{gather*}$

对于任意 $f_i(x) \le 0$ 均有 $h_i(x)=0$ .
一个 $maxf(x)$ 问题可以转化为 $1-maxf(x)$
假定 $f_0,f_1,\cdots,f_m$ 为凸函数, $h_1,h_2,\cdots,h_p$ 是仿射函数(形如 $Ax+b$ ),则上述问题为凸优化问题, 凸优化问题极值唯一

2. primal problem

将上述带约束的优化问题转化为无约束优化问题, 定义拉格朗日(Lagrangian)函数如下:
$L(x,\lambda,v) = f_0(x) + \sum_{i=1}^m\lambda_if_i(x) + \sum_{i=1}^pv_ih_i(x)$

最大化Lagrangian, 令
$z(x) = \underset{\lambda \ge 0,v}{max}L(x,\lambda,v)$

z(x)满足原始约束条件的x, 其值等于 $f_0(x)$ :
满足初始约束, 则 $h_i(x)=0$ , 拉格朗日函数第三项被消去:
$L(x,\lambda,v)=f_0(x) + \sum_{i=1}^m\lambda_if_i(x)$
又因为 $\lambda_if_i(x)\le0$ , 所以 $L(x,\lambda,v)$ 的最大值在 $f_0(x)$ 处取得.

所以原始带约束优化问题等价于以下无约束优化问题:
$\begin{gather*} min{f_0(x)}\;s.t. &f_i(x) \le 0, i= 1,\cdots,m \\ &h_i(x)=0,i=1,\cdots,p \end{gather*}$
等价于:
$\underset{x}{min}z(x) = \underset{x}{min} \;\underset{\lambda \ge0,v}{max}L(x,\lambda,v)$
上述问题称为primal problem
总结:

一个带约束的优化问题均可用 $minf_0(x)$ 表示

用拉格朗日函数将带约束优化转为无约束优化问题

初始约束条件总可写成 $f_i(x)\le0$ 的形式, 且拉格朗日算子 $\lambda_i\ge0$ , 所以 $maxL(x,\lambda,v)$ 可去掉约束条件:
去约束:
$f_0(x)\;\cdots s.t. \; f_i(x)\ge0 ,\;h_i(x)=0 \cong \underset{\lambda\ge0,v}{max}L(x,\lambda,v)$
最优化:
$\underset{x}{min}f_0(x) \cong \underset{x}{min} \; \underset{\lambda\ge0,v}{max}L(x,\lambda,v)$

3. dual problem

dual problem 只是将primal proble调换了min和max位置:
$\underset{\lambda \ge0,v}{max} \;\underset{x}{min}L(x,\lambda,v)$
注意上式和 $\underset{x}{min} \;\underset{\lambda \ge0,v}{max}L(x,\lambda,v)$ 并不等价.
令:
$g(\lambda,v) = \underset{x}{min}L(x,\lambda,v)$
上式中 $g(\lambda,v)$ 为拉格朗日对偶函数(Lagrange dual function), $g(\lambda,v)$ 是primal function的一个下界.
即, 若将primal proble的最小值记为 $p^*$ , 则对于所有的 $\lambda \ge 0和v$ , 有:
$g(\lambda,v) \le p^*$
证明:
对所有满足约束条件的x, 总有:
$\sum_{i=1}^m\lambda_i f_i(x) + \sum_{i=1}^pv_ih_i(x) \le 0$
因此
$L(x,\lambda,v) = f_0(x)+\sum_{i=1}^m\lambda_i f_i(x) + \sum_{i=1}^pv_ih_i(x) \le f_0(x)$
假设 $L(x,\lambda,v)$ 在 $x^*$ 处取得极值, 则
$minf_0(x) = f_0(x^*)$
代入上式:
$L(x^*,\lambda,v) = f_0(x^*)+\sum_{i=1}^m\lambda_i f_i(x^*) + \sum_{i=1}^pv_ih_i(x^*) \le f_0(x^*) = p^*$
于是
$g(\lambda,v) = \underset{x}{min}L(x,\lambda,v) \le L(x^*,\lambda,v) \le f_0(x^*) = p*$
这样, $g(\lambda,v)$ 的上界是 $p^*$ ,于是:
$\underset{\lambda \ge0,v}{max}g(\lambda,v)$
是primal problem的最大下界!
记dual problem 的最优值为 $d^*$ , 得到:
$d^* \le p^*$
该性质称为weak duality, 对所有的优化问题都成立.
此外,
$p^*-d^*$ 称为duality gap.

基于weak duality的重要结论:

无论 primal problem 是什么形式，dual problem 总是一个 convex optimization 的问题——它的极值是唯一的（如果存在的话）. 对于那些难以求解的 primal problem （甚至可以是 NP 问题），我们可以通过找出它的 dual problem ，通过优化这个 dual problem 来得到原始问题的一个下界估计。

当
$d^* = p^*$ 成立时,称为strong duality.

strong duality 成立的情况下，我们可以通过求解 dual problem 来优化 primal problem, 例如SVM 的时候我们直接假定了 strong duality 的成立.

4. KKT条件

4.1 slater条件

严格满足约束条件的点x, 指 $f_i(x)\le0$ 严格到 $f_i(x)<0$ , 即存在x满足:
$f_i(x) <0\;i=1,\cdots,m\\ h_i(x)=0\;i=1,\cdots,p$

4.2 strong duality

原始问题是convex且满足slater条件,则strong duality成立: $d^*=p^*$
特例: 对某些非convex optimization,strong duality也成立

4.3 SVM中的strong duality

SVM是一种convex optimization, SVM中通过QP(quadratic programming凸二次规划)求解, QP是凸优化问题的特殊情况
slater条件在SVM中等价于存在超平面能将数据分隔开来

4.4 strong duality成立时的性质

回顾primal problem和dual problem
primal problem: $\underset{x}{min}\;\underset{\lambda \ge 0,v}{max}L(x,\lambda,v)$
dual problem: $\underset{\lambda \ge 0,v}{max}\;\underset{x}{min}L(x,\lambda,v)$
dual problem极值 $d^*$ 在 $(\lambda^*,v^*)$ 处取得, primal problem极值 $p^*$ 在 $x^*$ 处取得
strong duality成立, 则 $d^*=p^*$ , duality gap为0
$f_0(x^*)\le f_0(x^*)$ 成立:
$\begin{align*} f_0(x^*) &=g(\lambda^*,v^*) \\ &=\underset{x}{min} \left( f_0(x)+\sum_{i=1}^m\lambda_i^*f_i(x)+\sum_{i=1}^pv_i^*h_i(x) \right) \\ &\le f_0(x^*)+\sum_{i=1}^m\lambda_i^*f_i(x^*)+\sum_{i=1}^pv_i^*h_i(x^*) \\ &\le f_0(x^*) \end{align*}$
由
$f_0(x^*) \le f_0(x) + \sum_{i=1}^m\lambda_if_i(x) + \sum_{i=1}^pv_ih_i(x)$
得:
$f_0(x^*) \le L(x^*,\lambda^*,v^*)$
所以 $x^*$ 是 $L(x,\lambda^*,v^*)$ 的一个极值点, 所以:
$\nabla f_0(x^*) + \sum_{i=1}^m\lambda_i^*\nabla f_i(x^*) + \sum_{i=1}^pv_i^*\nabla h_i(x^*)=0 \;(条件1)$
又由
$f_0(x^*) \le f_0(x^*)+\sum_{i=1}^m\lambda_i^*f_i(x^*)+\sum_{i=1}^pv_i^*h_i(x^*)$
得:
$\lambda_i^*f_i(x^*) \le 0$
故极值点 $x^*$ 处:
$\lambda_i^*f_i(x^*)=0,\;i=1,\cdots,m\;(条件2)$
条件(1)(2)合起来称为complementary slackness.

4.5 complementary slacknes条件分析

条件(2)中若 $\lambda_i^*>0$ 必有 $f_i(x^*)=0$ , 反之, 若 $f_i(x^*)<0$ 可得 $\lambda_i^*=0$ , 此条件在SVM中用来证明非支持向量 $f_i(x^*)<0$ 对应的系数 $\alpha_i$

4.6 引入KKT条件

complementary slacknes加上其他约束条件即为KKT条件:
$\begin{align*} \nabla f_0(x^*) + \sum_{i=1}^m\lambda_i^*\nabla f_i(x^*) + \sum_{i=1}^pv_i^*\nabla h_i(x^*)&=0 &(条件1) \\ \lambda_i^*f_i(x^*)&=0,\; i=1,\cdots,m&(条件2) \\ f_i(x^*) &\le 0,\; i=1,\cdots,m&(条件3) \\ \lambda_i^* &\ge0,\;i=1,\cdots,m&(条件4) \\ h_i(x^*) &= 0,\; i=1,\cdots,p&(条件5) \end{align*}$

任何满足strong duality的问题都满足KKT条件
primal problem是convex optimization problem是, KKT升级为充要条件, 通过KKT条件可求得$$, $(\lambda^*,v^*)$ 分别是primal problem和dual problem的极值点,且strong duality成立

总结

通过dual problem可求primal problem的解:

只有weak duality成立时, 至少可得到一个(primal problem的)下界
strong duality成立,则直接求解dual problem
dual problem可能比primal problem更易求解
dual problem可能有一些优良的结构(SVM通过dual problem将问题转化为内积以使用kernel trick)
迭代求解中, 会同事求解dual和primal problem, 通过duality gap来early stopping

最后编辑于：2019.05.10 15:59:38

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,240评论 6赞 498
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,328评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,182评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,121评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,135评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,093评论 1赞 295
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,013评论 3赞 417
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,854评论 0赞 273
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,295评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,513评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,678评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,398评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,989评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,636评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,801评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,657评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,558评论 2赞 352