简单易懂的拉格朗日对偶法和KKT条件

问题描述

假设要解决的优化问题为:
min f_{0}(x) \tag{1}
约束条件为 f_{i}(x) <= 0 \quad {\forall}i \in 1,2,3...,m\tag{2}

问题的简单改写

我们现在需要用一个函数来写出上面问题的等价问题。也就是要把约束条件跟目标函数写进一个函数中,把这个函数记作J(x),那么J(x)可以写作:

\begin{aligned} J(x) =& \begin{cases} f_{0}(x), \quad & if \quad f_{i}(x) \leq 0 \quad \forall i \\ +\infty, & otherwise \\ \end{cases} \\ =& f_{0}(x) + \sum_{i} I[f_{i}(x)] \\ \end{aligned}

这里的I[u]是个无穷阶跃函数,其表达式为:
\begin{align} I(u) =& \begin{cases} 0, \quad &if \quad u \leq 0 \tag{5} \\ +\infty, & otherwise\ \end{cases} \end{align}

如果f_{i}(x) 大于0, 由于阶跃函数I[f_{i}(x)]取值为正无穷, 那么函数不可能在这时取到极小值. 如果f_{i}(x)小于等于0, 那么 I[f_{i}(x)]值为0,求J(x)最小值就是求f_{0}(x)的最小值.注意到此时的f_{i}(x)小于等于0,因此完全和原问题等价.

至此已经把求原问题最小值成功写成求该函数最小值了.

改写成连续可导形式

不难发现, 这个函数不是连续可导的函数, 因此不好进行极值的求解 (连续可导函数可通过让导数值为0来求极值).我们需要进一步把函数转化成一个连续函数的等价形式.

不连续的原因是函数I(u)造成的,如何去改写I(u)呢?

一个最简单的方法把I(u)给松弛成\lambda u, \lambda \geq 0\.假设\lambda = 0.6如下图所示:

无穷阶跃函数I(u)和线性松弛λu

显然, \lambda uI(u)的一个下界,这个结论对于任意\lambda \geq 0\都是成立的.

现在可以把J(x)中的I(u)替换为\lambda u,新的函数由于引入的新的参数\lambda,因此不能用一个字母来表示,于是记作:
L(x,\lambda) = f_{0}(x) + \sum_{i} \lambda_{i}f_{i}(x) \tag{6}
那么这个函数该如何跟之前的J(x)等价呢?
我们注意到如果f_{i}(x)>0\lambda_{i}f_{i}(x)取值为+\infty,f_{i}(x)\leq0\lambda_{i}f_{i}(x)取值为0, 那么\lambda_{i}f_{i}(x)的效果将跟I[f_{i}(x)]完全相同. 要实现这一步,只需要把L(x,\lambda)写成\underset{\lambda}{max} L(x,\lambda)即可.也就是把(6)式中的\lambda看作变量,x看作常量求(6)式的最大值. 如果f_{i}(x)>0那么\lambda取值为+\inftyL(\lambda)最大,如果f_{i}(x)\leq0, 那么\lambda_{i}f_{i}(x)的值\leq 0, 当且仅当\lambda = 0时取到0,才能使L(\lambda)最大.因此, J(x)的等价函数为\underset{\lambda}{max} L(x,\lambda). 原问题等价为min J(x)也就是\underset{x}{min}{\,} \underset{\lambda}{max} L(x,\lambda). 其中\underset{x}{min}表示把x看作变量求函数的最小值.

对偶问题

注意到求\underset{x}{min}{\,}\underset{\lambda}{max} L(x,\lambda)与求原问题等价, 都不好进行求解. 但是,如果我们考虑调换求极值的顺序, 也就是先把x看作变量求函数的最小值, 再把\lambda看作变量求函数的最大值. 那么问题就变成:
\underset{\lambda}{max}{\,}\underset{x}{min} L(x,\lambda) = \underset{\lambda}{max} {\,}g(\lambda) \tag{7}
这个问题跟原问题是不等价的,它被称为原问题的对偶问题. 虽然不等价, 但是对偶问题的最优值是原问题最优值的一个下界,证明如下:

L(x, \lambda) \leq J(x) \forall \lambda \geq 0

\Rightarrow \min _{x} L(x, \lambda) = g(\lambda) \leq \min _{x} J(x)=: p^{\star}

\Rightarrow d^{\star} =\max _{\lambda} g(\lambda) \leq p^{\star} \tag{8}

第一项是因为\lambda u \leq I[u], 第二项就是把x看作变量同时取极小值, p^{\star}是原问题的最优值. 第三项是因为由第二项可知g(\lambda)的所有值都小于等于p^{\star},因此, g(\lambda)的最大值, 也就是对偶问题的最优值d^{\star}是小于等于p^{\star}的.所以对偶问题的最优值是原问题最优值的一个下界.
g(\lambda)根据凸优化的相关理论是一个凹函数, 因此容易求解.具体证明可参考:https://github.com/ShiqinHuo/Numerical-Optimization-Books/blob/master/Convex%20Optimization%20Boyd.pdf.

当问题具有强对偶性时, d^{\star} = p^{\star}. 若d^{\star} < p^{\star}则问题具有弱对偶性.一般来说,几乎所有的凸优化问题都满足强对偶性.比如SVM中, 它的损失函数就是凸函数, 我们几乎就能断定它是一个强对偶的问题.

KKT条件

对于一个没有约束的凸优化问题, 只需要对函数的梯度求导并令其为0即可. 对于由约束的凸优化问题而言, 它的最优解一定满足KKT条件. 第一个条件如下所示:
\nabla_{x} L\left(x^{\star}, \lambda^{\star}\right)=\nabla_{x} f_{0}\left(x^{\star}\right)+\sum \lambda_{i}^{\star} \nabla_{x} f_{i}\left(x^{\star}\right)=0 \tag{9}
这个条件可以解释为目标函数和约束函数的梯度必须平行且相反, 如下图所示:


假设目标函数为f_{0}(x)=(x_1-1.1)^{2}+(x_2+1.1)^{2} ,不等值约束为f_{1}(x)=x_{1}^2+x_{2}^{2}−1,如图所示, 最小值点取在f_{0}(x)梯度的反方向和约束条件f_{1}(x)梯度的方向上. 值得注意的是,如果f_{0}(x)最小值落在可行域内,约束将不起作用,\lambda取值为0,上面的等式依然成立,求极小值的方法就是直接令f_{0}(x)梯度为0.

根据(8)式我们有:
f_{0}\left(x^{\star}\right)=g\left(\lambda^{\star}\right)=\min _{x} L\left(x, \lambda^{\star}\right) = f_{0}\left(x^{\star}\right)+\sum \lambda_{i}^{\star} f_{i}\left(x^{\star}\right) \leq f_{0}\left(x^{\star}\right) \tag{10}

最右边的不等式成立的原因为\lambda_{i} \geq 0,f_{i}(x^{\star}) \leq 0.(10)式成立的条件只有取等号, 因此我们得到了第二个KKT条件:
\sum_{i}\lambda_{i}^{\star}f_{i}(x^{\star}) = 0 \qquad \forall i\tag{11}
综上, 在不等式约束下凸优化问题的所有KKT条件包括:
\lambda_{i} \geq 0

f_{i}(x^{\star}) \leq 0

\nabla_{x} L\left(x^{\star}, \lambda^{\star}\right)=\nabla_{x} f_{0}\left(x^{\star}\right)+\sum \lambda_{i}^{\star} \nabla_{x}f_{i}\left(x^{\star}\right) =0

\sum_{i}\lambda_{i}^{\star}f_{i}(x^{\star}) = 0 \qquad \forall i

参考资料

[1] David Knowles,Lagrangian Duality for Dummies,November 13, 2010
[2] 瑞典皇家理工学院(KTH)“统计学习基础”课程的KKT课件:http://www.csc.kth.se/utbildning/kth/kurser/DD3364/Lectures/KKT.pdf

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

推荐阅读更多精彩内容