SVM系列第七讲--KKT条件

上一讲我们介绍了最优化问题的两种形式,无约束的和等式约束条件下的,这一讲,我们主要介绍不等式约束条件下的最优化问题,并介绍一下我们的KKT条件。

1、不等式约束条件

设目标函数f(x),不等式约束为g(x),有的教程还会添加上等式约束条件h(x)。此时的约束优化问题描述如下:


不等式约束问题

则我们定义不等式约束下的拉格朗日函数L,则L表达式为:


屏幕快照 2017-07-20 下午10.46.37.png

求解上面的问题,我们同样可以使用等式约束条件的求解思路,对所有的参数进行求导,但是对于求解出的最优解,必须满足KKT条件(Karush-Kuhn-Tucker ):
1)L(a, b, x)对x求导为零;
2)h(x) =0;
3)a*g(x) = 0;

求取这些等式之后就能得到候选最优值。其中第三个式子非常有趣,因为g(x)<=0,如果要满足这个等式,必须a=0或者g(x)=0. 这是SVM的很多重要性质的来源,如支持向量的概念。

2、KKT条件推导

2.1 对偶问题转换

接下来我们介绍一下KKT条件的推导:首先让我们针对针对 λ 和 ν 最大化,令:



这里 λ⪰0 理解为向量 λ 的每一个元素都非负即可。这个函数 z(x) 对于满足原始问题约束条件的那些 x 来说,其值等于 f0(x) ,这很容易验证,因为满足约束条件的 x 会使得 hi(x)=0 ,因此最后一项消掉了,而 fi(x)≤0 ,并且我们要求了 λ⪰0 ,因此 λifi(x)≤0 ,所以最大值只能在它们都取零的时候得到,这个时候就只剩下 f0(x) 了。因此,对于满足约束条件的那些 x 来说,f0(x)=z(x) 。这样一来,原始的带约束的优化问题其实等价于如下的无约束优化问题:



到这里,我们成功把带约束问题转化为了无约束问题,不过这其实只是一个形式上的重写,并没有什么本质上的改变。我们只是把原来的问题通过 拉格朗日写作了如下形式:

我们把上面的形式称为原始问题,之前了解过SVM的同学肯定知道,如果我们把min和max对换一下位置,就得到这个问题的对偶问题:


对偶问题

2.2 对偶问题的最优解是原始问题最优解的下界

交换之后的对偶问题与原始问题的解并不相等,直观的可以这么理解,别墅中最便宜的房子的价格也要比普通楼房的最贵的价格高。当然这是很不严格的说法,我们需要严格的证明这一点,和刚才的z(x)类似,我们再定一个公式:


g 有一个很好的性质就是它是 primal problem 的一个下界。换句话说,如果 primal problem 的最小值记为 p∗ ,那么对于所有的 λ⪰0 和 ν ,我们有:



证明过程如下图:


证明

上面这个性质叫做弱对偶性,对于所有的优化问题都成立。既然有弱对偶性,那必然有强对偶性,前对偶性指的原始问题和对偶问题的最优解严格相等,即:
强对偶性

在强对偶性成立的情况下,我们就可以通过对原始问题的对偶问题的求解来得到最优解(SVM就是这么做的),但并不是所有情况下强对偶性都成立,它会有一定的前提。

2.3 Slater 条件

如果你不是专门研究规划问题的同学,咱们还是直接看结论吧。首先我们介绍一下Slater 条件,Slater 条件是指存在严格满足约束条件的点 x ,这里的“严格”是指 fi(x)≤0 中的“小于或等于号”要严格取到“小于号”,亦即,存在 x 满足:


Slater 条件

我们有:如果原始问题是凸优化问题(很庆幸,SVM的规划问题是一个凸优化问题)的并且满足 Slater 条件的话,那么 strong duality 成立。需要注意的是,这里只是指出了 strong duality 成立的一种情况,而并不是唯一情况,不过研究SVM的话 ,知道这种情况足够了。

2.4 KKT条件

让我们回到 duality 的话题。来看看 strong duality 成立的时候的一些性质。
假设 x∗ 和 (λ∗,ν∗) 分别是 primal problem 和 dual problem 的极值点,相应的极值为 p∗ 和 d∗ ,首先 p∗=d∗ ,此时我们可以得到:


因为左右两端其实是相等的,所以上面的小于等于号可以替换为等于号,我们一共替换了两次,这两次替换我们都能得到一个重要的性质:


再将其他一些显而易见的条件写到一起,就是传说中的 KKT (Karush-Kuhn-Tucker) 条件:


KKT条件

任何满足强对偶性(不一定要求是通过 Slater 条件得到,也不一定要求是凸优化问题)的问题都满足 KKT 条件,换句话说,这是 强对偶性 的一个必要条件。不过,当原始问题是凸优化问题的时候(当然还要求一应函数是可微的,否则 KKT 条件的最后一个式子就没有意义了),KKT 就可以升级为充要条件。换句话说,如果 原始问题是一个凸优化问题,且存在 x˜ 和 (λ˜,ν˜) 满足 KKT 条件,那么它们分别是 原始问题 和 对偶问题 的极值点并且强对偶性成立。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,362评论 5 477
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,330评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,247评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,560评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,580评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,569评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,929评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,587评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,840评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,596评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,678评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,366评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,945评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,929评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,165评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 43,271评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,403评论 2 342

推荐阅读更多精彩内容