拉格朗日对偶

Lagrange优化问题：

标准形式的优化问题（原问题）：
$minimize$ $f_{0}(x)$
$subject$ $to$ $\left\{ \begin{array} ff_{i}(x) \leqslant 0, \quad i=1,...,m \\ h_{i}(x)=0,\quad i=1,...,p \end{array} \right.$
其中，自变量 $x \in R^{n}$ 。设问题的定义域 $D = \bigcap_{i=0}^{m}\,dom \, f_{i} \, \cap \bigcap_{i=1}^{p}\,dom\, h_{i}$ 是非空集合，优化问题的最优值为 $p^{*}$ 。则问题的Lagrange函数：
$L(x,\lambda,v)=f_{0}(x)+\sum_{i=1}^{m}\lambda_{i}f_{i}(x)+\sum_{i=1}^{p}v_{i}h_{i}(x)$
其中定义域为 $dom\,L=D\times R^{m} \times R^{p}$

Lagrange对偶函数：

定义Lagrange对偶函数：
$g(\lambda,v)={inf}_{x\in D} \; L(x,\lambda,v)$
$= {inf}_{x\in D} \; (f_{0}(x) + \sum_{i=1}^{m}\lambda_{i}f_{i}(x) + \sum_{i=1}^{p}v_{i}h_{i}(x) )$
对偶函数 $g(\lambda,v)$ 为Lagrange函数关于 $x$ 取得的最小值：即对 $\lambda \in R^{m}$ ， $v\in R^{p}$ ，可以理解成把 $\lambda,v$ 当作常量，关于 $x$ 取得的最小值。

最优值的下界：

对偶函数构成了原问题最优值 $p^{*}$ 的下界：即对任意 $\lambda \succeq 0$ 和 $v$ 都使下式成立
$g(\lambda,v) \leqslant p^{*}$
证明：
设 $\widetilde{x}$ 为满足原问题的任意可行点，即 $f_{i}(\widetilde{x}) \leqslant 0$ 且 $h_{i}(\widetilde{x})=0$ 。根据假设， $\lambda \succeq 0$ ，则 $\lambda_{i}f_{i}(\widetilde{x}) \leqslant 0$ ，即
$\sum_{i=1}^{m}\lambda_{i}f_{i}(\widetilde{x})+\sum_{i=1}^{p}v_{i}h_{i}(\widetilde{x}) \leqslant 0$
$L(\widetilde{x},\lambda,v)=f_{0}(\widetilde{x})+\sum_{i=1}^{m}\lambda_{i}f_{i}(\widetilde{x})+\sum_{i=1}^{p}v_{i}h_{i}(\widetilde{x}) \leqslant f_{0}(\widetilde{x})$
$g(\lambda,v) = {inf}_{x \in D} \, L(x,\lambda,v) \leqslant L(\widetilde{x},\lambda,v) \leqslant f_{0}(\widetilde{x})$
由于每一个可行点 $\widetilde{x}$ 都满足 $g(\lambda,v) \leqslant f_{0}(\widetilde{x})$ 。因此不等式 $g(\lambda,v) \leqslant p^{*}$ 成立。但是当 $g(\lambda,v)= -\infty$ 时没有意义，只有当 $\lambda \succeq 0$ 且 $(\lambda,v) \in dom \, g$ 即 $g(\lambda,v) > -\infty$ 时，对偶函数才能给出 $p^{*}$ 的一个非平凡下界。

Lagrange对偶问题：

对任意一组 $(\lambda,v)$ ，其中 $\lambda \succeq 0$ ，对偶函数给出了优化问题的最优值 $p^{*}$ 的一个下界，因此我们可以得到和参数 $\lambda,v$ 相关的一个下界，为得到最好的下界，表述为优化问题：
$maximize \quad g(\lambda,v)$
$subject \; to \quad \lambda \succeq 0$

弱对偶性：

Lagrange对偶问题的最优值，我们用 $p^{*}$ 表示，这是通过Lagrange函数得到的原问题的最优值 $p^{*}$ 的最好下界。特别的，
$d^{*} \leqslant p^{*}$
这个不等式成立，这个性质称为弱对偶性。

强对偶性

如果等式：
$d^{*}=p^{*}$
成立，即最优对偶间隙为零，那么强对偶性成立。这说明从Lagrange对偶函数得到的最好下界是紧的。
对于一般的优化问题，强对偶性通常不成立，但是若主问题为凸优化问题，即 $f_{i}(x)$ 为凸函数， $h_{i}(x)$ 为仿射函数，且其可行域中至少有一点使不等式约束严格成立，则此时强对偶性成立。

最后编辑于：2018.11.10 16:12:31

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