Loading [MathJax]/extensions/AssistiveMML.js
马同学

如何理解拉格朗日乘子法和KKT条件？

之前简单介绍了拉格朗日乘子法的基本思路：如何理解拉格朗日乘子法？
本文会继续介绍拉格朗日乘子法的细节，以及对其进行适当的推广（也就是所谓的KKT条件）。
1 无约束下的极值
1.1 直观
根据梯度的意义（参看如何理解梯度）可知，在函数f(x)的极值点梯度为0：
1.2 代数
要求（\text{minimize}的意思是求极小值）：
\text{minimize}\ f(x)
只需解如下方程：
\nabla f=0
2 单等式约束下的极值
关于这一节，更详细的请参看：如何理解拉格朗日乘子法？
2.1 直观
要求方程x^2y-3=0与原点的最小距离：
问题被转化为了同心圆与x^2y-3=0什么时候相切：
相切就是在极小值点有相同的切线：
只要能通过数学把相切这个条件表示出来，就可以得到解。
我们把同心圆可以看作凸函数f(x,y)=x^2+y^2的等高线：
把方程x^2y-3=0看作凸函数g(x,y)=x^2y的等高线中的一条：
这样f的等高线，同心圆，的法线就是\nabla f：
g的等高线的其中一条，方程x^2y-3=0，的法线就是\nabla g
两者相切就意味着，在切点，两者法线平行：
也就是：
\nabla f+\lambda\nabla g=0
2.2 代数
上面的问题形式化后，用代数表示为（\text{subject to}的意思是服从于，约束于的意思）：
\begin{aligned} & \text{minimize} & & f(x,y) \\ & \text{subject to} & & g(x,y) = 3 \end{aligned}
只需解如下方程组：
\begin{cases} \nabla f+\lambda\nabla g=0\\ \\ g(x,y)=3 \end{cases}
3 多等式约束下的极值
比如下图：
马同学高等数学
要求f被g_1=0,g_2=0约束后的极值，可以证明在极值点\nabla f必然在\nabla g_1,\nabla g_2张成的空间中。
那么上面的问题形式化后就是：
\begin{aligned} & \text{minimize} & & f \\ & \text{subject to} & & g1=0,g_2=0 \end{aligned}
只需解如下方程组：
\begin{cases} \nabla f+\lambda_1\nabla g_1+\lambda_2\nabla g_2=0\\ \\ g1=0,g_2=0 \end{cases}
更一般的，如果有n个约束等式：
\begin{aligned} & \text{minimize} & & f \\ & \text{subject to} & & g_i=0,i=1,2,\cdots,n \end{aligned}
只需解如下方程组：
\begin{cases} \displaystyle\nabla f+\sum_{i}^{n}\lambda_i\nabla g_i=0 \\ g_i=0,i=1,2,\cdots,n \end{cases}
4 不等式约束下的极值
比如，我们要求刚才同心圆的最小值：
那肯定就是原点啦，半径为0肯定就是最小值了。
从代数上看就是要求：
\text{minimize}\ f(x,y)=x^2+y^2
解：
\nabla f=0\implies (x,y)=(0,0)
4.1 情况一
我们给它添加一个不等式约束，也就是求：
\begin{aligned} & \text{minimize} & & f(x,y) \\ & \text{subject to} & & h(x,y)=x+y \le 1 \end{aligned}
可以看到，这个不等式约束实际上包含了原点：
所以这个约束等于没有，依然求解：
\nabla f=0\implies (x,y)=(0,0)
4.2 情况二
换一个不等式约束：
\begin{aligned} & \text{minimize} & & f(x,y) \\ & \text{subject to} & & h(x,y)=x+y \le -2 \end{aligned}
不等式约束看起来是这样的：
因为同心圆是凸函数的等高线，所以等高线的值是这么排列的：
所以，在不等式约束下，最小值是在边缘相切的地方取得：
和用等式h(x,y)=x+y=-2进行约束效果是一样的：
因此可以通过解方程组求出答案：
\begin{cases} \nabla f+\mu\nabla h=0 \\ h(x,y)=x+y=-2 \end{cases}
4.3 新增的条件
仔细研究，不等式实际上带来了新的条件。
同心圆是凸函数的等高线，等高线的值如下排列，所以在相切处，法线也就是\nabla f的方向如下（法线也就是梯度，指向增长最快的方向，也就是等高线的值变大的方向）：
而凸函数h(x,y)的法线\nabla h也一样指向h(x,y)增长的方向，这个方向正好和\nabla f相反：
因此：
\nabla f+\mu\nabla h=0,\mu \ge 0
其中，\mu \ge 0就表明\nabla f,\nabla h方向相反。
因此刚才的方程组可以再增加一个条件：
\begin{cases} \nabla f+\mu\nabla h=0 \\ h(x,y)=x+y=-2 \\ \mu \ge 0 \end{cases}
5 KKT条件
因此，综合上面的所有情况，可以把求如下的极值：
\begin{aligned} & \text{minimize} & & f \\ & \text{subject to} & & g_i=0,i=1,2,\cdots,n\\ & & & h_i\le 0,i=1,2,\cdots,n\\ \end{aligned}
通过解下面这个方程组来得到答案：
\begin{cases} \displaystyle\nabla f+\sum_{i}^{n}\lambda_i\nabla g_i+\sum_{j}^{m}\mu_j\nabla h_j=0 \\ g_i=0,i=1,2,\cdots,n\\ \\ h_j\le 0,j=1,2,\cdots,m\\ \\ \mu_j \ge 0\\ \\ \mu_j h_j = 0\\ \end{cases}
这个方程组也就是所谓的KKT条件。
进一步解释下方程组的各个项：
\begin{array}{c|c} \hline \\ \quad \displaystyle\nabla f+\sum_{i}^{n}\lambda_i\nabla g_i+\sum_{j}^{m}\mu_j\nabla h_j=0\quad&\quad 等式与不等式约束的梯度的线性组合\quad \\ \quad g_i=0,i=1,2,\cdots,n\quad&\quad等式约束\quad\\ \quad h_j\le 0,j=1,2,\cdots,m\quad&\quad不等式约束\quad\\ \quad \mu_j \ge 0\quad&\quad不等式约束下，法线方向相反\quad\\ \quad \mu_j h_j=0\quad&\quad不等式约束下\begin{cases}情况一：\mu=0,h_j\le 0\\\\情况二：\mu_j \ge 0,h_j=0\end{cases}\quad\\ \\ \hline \end{array}
关注马同学
马同学高等数学
微信公众号：matongxue314
马同学机器学习
马同学图解数学
马同学高等数学
微信公众号：matongxue314
©2021 成都十年灯教育科技有限公司 | 蜀ICP备16021378