SVM(1) 之 拉格朗日乘子法和KKT条件

其实我之前看过这个地方,但是当时感触不深(或者说根本没看懂,也可能是忘了),所以重新推导一下。《西瓜书》 、《统计学习方法》 还有网上讲的其实有点点的不一样,这里以《统计学习方法》为主,《西瓜书》中没有给出例题,所以不好说。

拉格朗日乘法谈起

拉格朗日乘法拉格朗日乘数法是用来求条件极值的,极值问题有两类,其一,求函数在给定区间上的极值,对自变量
没有其它要求,这种极值称为无条件极值。其二,对自变量有一些附加的约束条件限制下的极值,称为
条件极值。

求这个椭球的内接长方体的最大体积。

下,求


最大值。

通过拉格朗日乘数法将问题转化为

然后分别对x,y,z,兰姆达 求导,得到最值,带回原式即可

更多参考
https://zh.wikipedia.org/wiki/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%95%B0
https://blog.csdn.net/acdreamers/article/details/41413445

拉格朗日对偶法

《统计学习方法》 附录C

原始问题

假设f(x), c_{i}(x), h_{j}(x)是定义在R^n上的连续可微函数,考虑约束最优化问题

很多时候,现实问题可能跟上述结构不一样,那么把问题转化一下即可,比如 max->min

拉格朗日函数

其中,α_i β_i 是拉格朗日乘子,并且要求α_i ≥ 0

首先我们把L(x,α,β)看成是α,β的函数(把x看成常量),然后求该函数的最大值(含x的表达式),接着再把x看成变量,因此可以定义函数θ_p(x)如下:

下标P代表原始问题

这里或许可以看到一些拉格朗日乘法的影子,最值 求导 然后带回原式。至于为什么是max而不用min,一种说法是c_i(x)<=0α_i 没上限,所以式子可以一直小下去的,再所以用的是max

可以证明,如果 x满足原始问题中约束,那么 \theta(\boldsymbol{x})=f(\boldsymbol{x})

为什么 \theta(\boldsymbol{x})=f(\boldsymbol{x}) ,这里看一下L 里边的参数,c_i(x)小于0,a_i大于0,这两项乘积<=0h_j(x)又都是0,那么 L的最大值 其实 就只有一个 f(x) 了,毕竟别的都是负数。

如果 x不满足原始问题中的约束c_i(x)\le 0;h_j(x)=0,那么\theta(\boldsymbol{x})=+\infty,即:

所以如果考虑极小化问题:
\min_{\boldsymbol{x}}f(\boldsymbol{x})=\min_{\boldsymbol{x}}\theta_P(\boldsymbol{x})=\min_{\boldsymbol{x}}\max_{\boldsymbol{\alpha,\beta}:\alpha_i\ge0}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})
\min_{\boldsymbol{x}}\max_{\boldsymbol{\alpha,\beta}:\alpha_i\ge0}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta}) 称为广义勒格朗日函数的极小极大问题。此时原始最优化问题,转化为广义拉格朗日函数的极大极小问题。这样一来,就把原始最优化问题表示为广义拉格朗日函数的极小极大问题。我们定义原始问题最优解:
p^*=\min_{x}\theta_P(x)

  • 所以这一部分到底干了什么事?

从原始问题开始,通过拉格朗日函数重新定义一个无约束问题,这个无约束问题等价于原来的约束优化问题,从而将约束问题无约束化。也就是将d个变量和k个约束条件的最优化问题转换为d+k个变量的最优化问题。到此我们还是无法求解,我们需要将原始问题转换成对偶问题来求解。

对偶问题

我们再定义:
\theta_D(\alpha,\beta)=\min_x L(x,\alpha,\beta)
并极大化\theta_D,即:
\max_{\alpha,\beta}\theta_D(\alpha,\beta)=\max_{\boldsymbol{\alpha,\beta}}\min_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})
\max_{\boldsymbol{\alpha,\beta}}\min_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})为广义拉格朗日函数的极大极小问题(上一节的是极小极大问题)。这样可以将广义拉格朗日函数的极大极小问题进一步表示为约束最优化问题:
\max_{\alpha,\beta}\theta_D(\alpha,\beta)= \max_{\boldsymbol{\alpha,\beta}}\min_{\boldsymbol{x}}L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta}) \ \ \mathbb{s.t.}\quad\alpha_i\ge0,\quad i=1,2,\cdots,k
对比原始问题,对偶问题是先固定\alpha,\beta,求最优化x的解,在确定参数\alpha,\beta
原始问题是先固定x,求最优化\alpha,\beta的解,再确定x

原始问题和对偶问题的关系

这块我就不证明了,书上都有。

总之,当原始问题和对偶问题的最优值相等:d^*=p^* 时,可以用求解对偶问题来求解原始问题(当然是对偶问题求解比直接求解原始问题简单的情况下),但是到底满足什么样的条件才能使 d^*=p^* 呢,这就是下面要阐述的 KKT 条件。

KKT 条件

作为对比,把拉格朗日函数再拿出来对比一下
L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})=f(\boldsymbol{x})+\sum_{i=1}^k \alpha_ic_i(\boldsymbol{x}) + \sum_{j=1}^l\beta_jh_j(\boldsymbol{x})

KKT条件 说明
1 \nabla_\boldsymbol{x}L(\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*)=0
2 \nabla_\boldsymbol{\alpha}L(\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*)=0
3 \nabla_\boldsymbol{\beta}L(\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*)=0 极值部分,求导为0
4 c_i(\boldsymbol{x}^*)\le0,\quad i=1,2,\cdots,k C.2不等式约束
5 h_j(\boldsymbol{x}^*)=0,\quad j=1,2,\cdots,l C.3等式约束
6 \alpha_i^*\ge0,\quad i=1,2,\cdots,k 拉格朗日算子 法线方向相反的解释
7 \alpha_i^*c_i(\boldsymbol{x}^*)=0,\quad i=1,2,\cdots,k 1、\alpha_i^*=0 时, c_i(\boldsymbol{x}^*)\le0
7 2、\alpha_i^*>0 时, c_i(\boldsymbol{x}^*)=0

KKT条件可以分为三部分来考虑:

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

推荐阅读更多精彩内容

  • 一. 最优化问题求解 1. 等式约束的极值求法 目标函数: , 引入Lagrange算子: 2. 不等式约束的极值...
    婉妃阅读 12,597评论 3 9
  • 参考Jerrylead和july-支持向量机通俗导论 一、由逻辑回归,引申出SVM(线性可分的SVM) 1.1 逻...
    小碧小琳阅读 1,430评论 0 2
  • 今天又是周五,一个星期又到了我盼望的日子了,今晚我可以晚睡觉了,呵,下午放学后,孩子们回家吃完饭,就开始...
    夏雯敏阅读 85评论 0 0