机器学习数学基础-拉格朗日对偶与KKT条件

本篇我们讨论一下一般的优化问题： $\min f(x)\\s.t.g_i(x)\leq 0，i=1,2,\dots,p\\h_j(x)=0,j=0,1,\dots,q\$ 这里我们对 $f,g,h$ 不做任何要求。
并记：

$x$ 的定义域 $\mathcal{D}$ 为 $dom f$ 和满足约束 $g,h$ 的 $x$ 的交集。
最优值： $p^*$

拉格朗日对偶问题

对偶问题的描述

为什么要引入拉格朗日对偶问题，首先我们注意到

原问题的目标函数的凹凸性未知，对此我们没有很好的办法去求得最优值。
且原问题的约束数量较多时，求解的难度很大。
那原问题的拉格朗日对偶有什么优势呢？
首先对偶问题的目标函数一定是凹函数，这在很大程度上带来了优化的便利。
对偶问题的约束只有一个。
为引入拉格朗日对偶问题，我们先给出原问题的拉格朗日函数：
$\mathcal{L}(x,\lambda,\mu)=f(x)+\sum_{i=1}^{p}\lambda _ig_i(x)+\sum_{j=i}^{q}\mu _j h_j(x)$
于是原问题的对偶问题为：
$\max g(\lambda,\mu)=\inf_{x\in \mathcal{D}}\mathcal{L}(x,\lambda,\mu)\\ =\inf_{x\in \mathcal{D}}(f(x)+\sum_{i=1}^{p}\lambda _ig_i(x)+\sum_{j=i}^{q}\mu _j h_j(x))\\\lambda _i \geq 0,i=1,2,\dots,p$
这里inf表示对 $x$ 取下界。
可以证明，对偶之后的函数 $g(\lambda,\mu)$ ，一定是一个凹函数。

对偶问题与原问题的关系

对偶函数的一个十分重要的性质是： $\forall \lambda \geq 0,g(\lambda,\mu) \leq p^*$ 。也就是说， $g$ 的值一定不会超过原问题的最优值。即对偶函数给出了原问题最优解 $p^*$ 的下界。于是，对于很多我们无法直接获取最优值的问题，我们可以用其最优下界去逼近原问题的最优值。那么最优下界是什么呢？很显然，在这里是 $\max g$ ，也就是对偶问题的最优值，我们记为 $d^*$ 。
现在我们找到了 $p^*$ 的逼近 $d^*$ ，满足 $d^*\leq p^*$ 。现在我们想知道，是否存在一种情况，使得 $d^*=p^*$ ，在这种十分理想的情况下，我们能够直接得到原问题的最优值。
为此我们引入另一个概念：强对偶。

强对偶

条件1：当原问题为凸优化问题，且满足（强或弱）Slater条件。为强对偶。这意味着：
1.1， $f,g_i$ 为凸函数。
1.2， $h_i$ 为仿射函数。
2.1， $\exists x\in \mathcal{D},s.t. g_i(x) < 0,i=1,2,\dots,p\\h_i(x)=0,i=1,2,\dots,q$
值得注意的是，2.1给出的是强Slater条件，弱Slater条件允许 $g_i(x) \leq 0$ ，前提是这个 $g_i$ 是个仿射函数。
当条件1被满足时，为强对偶，此时有 $d^*=p^*$ 。此时我们运用常规的凸优化问题的解法解对偶问题就可以得到 $p^*$ 了。

KKT条件

对于非凸优化问题：
假设

原问题的函数都可导
强对偶成立
$x^*,\lambda ^* ,\mu ^*$ ，为原问题和对偶问题的最优解。
那么 $x^*,\lambda ^* ,\mu ^*$ 满足KKT条件为： $g_i(x^*) \leq 0,i=1,2,\dots,p\\h_i(x)=0,i = 1,2,\dots,q\\ \lambda ^*_i \geq 0,i=1,2,\dots,p\\\lambda^*_ig_i(x)=0\\\nabla\mathcal{L(x^*,\lambda ^*,\mu ^*)}=\nabla f(x^*)+ \sum_{i=1}^{p}\nabla \lambda_i^* g_i(x)+\sum_{i=1}^{q}\nabla\mu ^*_i h_i(x)=0$
对于凸优化问题：
如果存在 $x^*,\lambda ^* ,\mu ^*$ ，满足KKT条件，那么 $x^*,\lambda ^* ,\mu ^*$ 为原始问题和对偶问题的最优解。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念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

机器学习数学基础-拉格朗日对偶与KKT条件

拉格朗日对偶问题

对偶问题的描述

对偶问题与原问题的关系

强对偶

KKT条件

推荐阅读更多精彩内容