拉格朗日乘子、KKT条件与对偶问题

1. 拉格朗日算子

1.1 基本流程

假设 $\boldsymbol{x}=[x_1,x_2,...,x_d]$ ，是一个 $d$ 维的向量， $f(x)$ 和 $g(x)$ 是定义在实数集上连续可微的函数，现在需要找一个 $x^*$ 使得 $f(x)$ 具有最小值，且 $g(x) \leq 0$ 。即有：
$\begin{align} \min _x f(x) \\ s.t. \ g(x) \leq 0 \tag{1.1} \end{align}$
那么，通过拉格朗日乘子法，可以构造出下面的式子：
$\begin{align} L(\boldsymbol{x}, w) = f(\boldsymbol{x}) + wg(\boldsymbol{x}) \tag{1.2} \end{align}$

令 $L(\boldsymbol{x},w)$ 的对 $\boldsymbol{x}$ 的导数为0，求解出 $x, w$ 的值，那么， $\boldsymbol{x}$ 就是函数 $f(\boldsymbol{x})$ 在附加条件 $g(\boldsymbol{x})$ 下可能的极值点。

会做题拿分就够了！！！

1.2 理解

第一层理解：

在学高数的时候，对拉格朗日的理解仅限于：构造了一个函数 $L(x,y,\lambda)$ ，对该函数 $L(x,y,\lambda)$ 求极导，令导数为0，可以算出极大值极小值。

第二层理解：

在进行第二层理解时，需要明白几个概念：

数学里面，梯度指的是函数变化最快的方向。
梯度跟函数约束曲线是垂直的，既然垂直于约束曲面，就一定垂直于等高线。

具体可以参考这篇文章拉格朗日乘子法。该文比较直观的介绍了拉格朗日的基本定理，并且从切线、梯度的角度分析了拉格朗日算子。

拉格朗日附体，我是最牛逼的！

2. KKT条件

2.1 一个限制条件的情况

看完这个例子之后，在公式(1.2)可能取到的所有点中，的的确确找到了一个 $\boldsymbol{x^*}$ ，使得 $f(\boldsymbol{x})$ 最小且满足 $g(\boldsymbol{x}) \leq 0$ ，在这样的情况下，必然有
$\begin{align} \bigtriangledown f(\boldsymbol{x^*}) + w \bigtriangledown g(\boldsymbol{x^*}) = 0 \tag{2.1} \end{align}$
而公式(2.1)在某些条件下刚好是公式(1.2)： $L(x, w) = f(\boldsymbol{x}) + wg(\boldsymbol{x})$ 对 $\boldsymbol{x}$ 的偏导数等于 $0$ 的情况。
$\begin{align} \frac{\partial{L(\boldsymbol{x}, w)}}{\partial{\boldsymbol{x}}} = \bigtriangledown f(\boldsymbol{x}) + w \bigtriangledown g(\boldsymbol{x}) \end{align}$
那么，某些条件是什么呢？

找到这些条件，就可以嘿嘿嘿

$g(\boldsymbol{x}) \leq 0$ ：这个没什么好说的，限制条件。
：要满足这个条件，考虑和两种情况：
- 当 $g(\boldsymbol{x^*})=0$ 时：说明这个点在 $g(\boldsymbol{x})=0$ 构成的边界上，此时必然有 $\bigtriangledown f(\boldsymbol{x^*})$ 和 $\bigtriangledown g(\boldsymbol{x^*})$ 平行，但是无法保证他们俩方向和大小相同，因此标量 $w>0$ ，使得等式(2.1)成立。
  
  g(x)=0, w>0的情况
- 当 $g(\boldsymbol{x^*})<0$ 时：说明这个点在 $g(\boldsymbol{x})=0$ 构成边界的内部，此时限制条件 $g(\boldsymbol{x}) \leq 0$ 就打酱油了，没卵用，可以直接通过条件 $\bigtriangledown f(\boldsymbol{x})=0$ 获得最优点，这个时候 $w=0$ 。
  
  g(x)<0, w=0的情况

$wg(\boldsymbol{x})=0$ ：要加上这个条件的原因是，为了满足条件2中的两种情况。
$\begin{align} \left\{\begin{matrix} g(\boldsymbol{x}) \leq 0 \\ w \geq 0 \\ wg(\boldsymbol{x})=0 \end{matrix}\right. \tag{2.2} \end{align}$
所以啊，公式(2.2)就被称为Karush-Kuhn-Tucker (KKT)条件。

2.2 多个限制条件的情况

一个限制条件说清楚了，那么多当有多个约束条件时，考虑 $l$ 个等式约束和 $k$ 个不等式约束。
$\begin{align} \min _x f(\boldsymbol{x}) & \\ s.t. \ c_i(\boldsymbol{x}) \leq 0 \ & (i=1,2,...,k)\\ \ h_j(\boldsymbol{x}) = 0 \ & (j=1,2,...,l) \tag{2.3} \end{align}$
这个时候，引入拉格朗日算子 $\boldsymbol{\alpha}=[\alpha_1,\alpha_2,...,\alpha_l]$ 和 $\boldsymbol{\beta}=[\beta_1,\beta_2,...,\beta_k]$ ，拉格朗日函数为
$\begin{align} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) = f(\boldsymbol{x}) + \sum_{i=1}^{k} \alpha_i c_i(\boldsymbol{x}) + \sum_{j=1}^{l} \beta_j h_j(\boldsymbol{x}) \tag{2.4} \end{align}$
则他们的KKT条件是：
$\begin{align} \left\{\begin{matrix} c_i(\boldsymbol{x}) \leq 0 \ & (i=1,2,...,k)\\ \alpha_i \geq 0 \ & (i=1,2,...,k)\\ \alpha_i c_i(\boldsymbol{x})=0\\ h_j(\boldsymbol{x})=0 \end{matrix}\right. \tag{2.5} \end{align}$

这有啥难的？瞎几把套就行

3. 对偶问题

KKT条件中提到，在公式(1.2)可能取到的所有点中，的的确确找到了一个 $\boldsymbol{x^*}$ ，使得 $f(\boldsymbol{x})$ 最小且满足 $g(\boldsymbol{x}) \leq 0$ 。

但是，如果找不到呢。。。

马德！！！

3.1 原始问题

3.1 一个限制条件的情况下

找不到 $\boldsymbol{x^*}$ ，公式(2.1)就不能成立了，
$\begin{align} \bigtriangledown f(\boldsymbol{x^*}) + w \bigtriangledown g(\boldsymbol{x^*}) = 0 \tag{2.1} \end{align}$
但是，我要怎么告诉公式(2.1)不能成立啊！！！

找不到 $\boldsymbol{x^*}$ ，说明存在一个 $\boldsymbol{x^{fake}}$ 违背了 $g(\boldsymbol{x}) \leq 0$ 的条件，有 $g(\boldsymbol{x^{fake}}) > 0$ ，既然这样的话，在
$\begin{align} L(\boldsymbol{x}, w) = f(\boldsymbol{x}) + wg(\boldsymbol{x}) \end{align}$
中，我们令 $w \rightarrow {+\infty}$ 。这样的话，

若 $\boldsymbol{x}$ 不违反 $g(\boldsymbol{x}) \leq 0$ 约束，则 $\max_w L(\boldsymbol{x}, w) =f(\boldsymbol{x})$
若 $\boldsymbol{x}$ 违反 $g(\boldsymbol{x}) \leq 0$ 约束，则 $\max_w L(\boldsymbol{x}, w) = {+\infty}$

所以就变成了
$\begin{align} \min _x \max_w L(\boldsymbol{x}, w)\tag{3.1} \end{align}$

3.2 多个限制条件的情况下

$\begin{align} \min _x \max_{\alpha_i, \beta_j; \alpha_i \geq0} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})\tag{3.2} \end{align}$

again？？？

3.2 转化者

换个心情，换个思路。。。（透。。。）
这个问题称为广义拉格朗日函数的极大极小问题。
$\begin{align} \max_{\alpha_i, \beta_j;\alpha_i \geq0} \min _x L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})\tag{3.3} \end{align}$
也就是求
$\begin{align} \max_{\alpha_i, \beta_j;}\min _x L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})\\ s.t. \ \alpha_i \geq0 \tag{3.4} \end{align}$

3.3 大小安排一波？？？

假设公式(3.2) 原始人 的最优解为 $p^*$ ，公式(3.4) 转化者 的最优解为 $d^*$ 。
因为
$\begin{align} \min _x L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \leq L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \leq \max_{\alpha_i, \beta_j; \alpha_i \geq0} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \tag{3.5} \end{align}$
因为原始人和转化者都有最优解，所以有
$\begin{align} d^*=\max_{\alpha_i, \beta_j;} \min _x L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \leq \min_x \max_{\alpha_i, \beta_j} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})=p^* \tag{3.5} \end{align}$
所以在KKT条件中，还要加上这几条，最后是：
$\begin{align} \left\{\begin{matrix} \bigtriangledown_{\boldsymbol{x}}L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})=0\\ \bigtriangledown_{\boldsymbol{\alpha}}L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})=0\\ \bigtriangledown_{\boldsymbol{\beta}}L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})=0\\ c_i(\boldsymbol{x}) \leq 0 \ & (i=1,2,...,k)\\ \alpha_i \geq 0 \ & (i=1,2,...,k)\\ \alpha_i c_i(\boldsymbol{x})=0\\ h_j(\boldsymbol{x})=0 \end{matrix}\right. \tag{3.6} \end{align}$

4. 小结

所以，要求一个连续可微函数的最小值，并且还有一堆限制条件，可以这么做：

引入拉格朗日乘子，构造拉格朗日函数；
计算拉格朗日函数对未知参数的偏导数，并令导数为0，求解参数。
将参数代入拉格朗日函数中，并转化成对偶问题后求解。（转换的时候注意其KKT条件）

疲惫。。。

5. 参考文献

《西瓜书》
《统计学习方法》
《拉格朗日乘子法》

最后编辑于：2019.09.16 23:33:59

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