拉格朗日乘子法

作者: Paycation | 来源:发表于2019-03-11 23:29 被阅读0次

拉格朗日乘子法
拉格朗日乘子法
拉格朗日乘子法
拉格朗日乘子法
拉格朗日乘子法和KKT条件
拉格朗日乘数法
02 SVM - 拉格朗日乘子法
最优化--拉格朗日乘子法
拉格朗日乘子法、对偶、KTT
拉格朗日乘子法与KKT条件

学习背景：理解SVM时需要这部分背景知识。

对于条件最佳化constrained optimization，我们使用拉格朗日乘子法。
所谓constrained optimization就是求在特定条件下变量能输出的函数最大值或者最小值。
举个例子：函数 $f(x,y)=x^2+y^2$ ，其中两变量满足约束条件 $xy=3$ ，现在求 $f$ 的最值。不难看出， $f$ 的图像是无数个同心圆，原点是它的圆心。而约束条件是双曲线。

示意图
图中的圆是等高线，因为必须等于某个正数的时候才是圆的图像。而这个正数就是函数值。红色的圆正好和双曲线相切，再高就变成了相交。显然，随着等高线的升高，始终两者相交，因此这个问题没有最大值，只有最小值，且最小值就是两者相切的时候，等高线表达的值。
那么我们如何计算这个相切的位置？

法向量
根据上图可以想象，从一条等高线跨越到更高的一条等高线，必然是沿着垂直于切线的方向是最快的。而这个切线的方向就是梯度。这里不做数学上的证明，只需要有个直观的感受就够了。因此我们可以确定，梯度向量就是切线的法向量。两条曲线的法向量都和共同的切线垂直，那么它们也就共线，即两曲线的梯度共线。我们用来表示两者的长度关系，这也就是所谓的拉格朗日乘子：

即：和同时成立。这里的是，那么有：

$\begin{cases} f_x=2x \\ f_y=2y \\ g_x=y \\ g_y=x \\ \end{cases}\Rightarrow\begin{cases} 2x=\lambda y \\ 2y=\lambda x \\ xy=3 \end{cases}$

$\Rightarrow\begin{cases} x=\sqrt{3}\\ y=\sqrt{3}\\ \lambda=2 \end{cases}or\begin{cases} x=-\sqrt{3}\\ y=-\sqrt{3}\\ \lambda=2 \end{cases}$

因此函数 $f$ 在上述约束条件 $g(x,y)=3$ 下的最小值就是 $x^2+y^2=6$ 。（ $\lambda$ 不能等于-2，因为 $x,y$ 同号，而 $2x=\lambda y$ ）

拉格朗日函数 (Lagrangian)

公式：

$L(x,y,\lambda)=f(x,y)-\lambda(g(x,y)-c)$

或者

$L(x,y,\lambda)=f(x,y)+\lambda(c-g(x,y))$

具体到本例，也就是：

$L(x,y,\lambda)=x^2+y^2-\lambda (xy-3)$

使这个新构造的函数的梯度等于0，那么得到的方程组和上述相同：

$\nabla L=\begin{vmatrix}\dfrac{\partial{L}}{\partial{x}}\\\dfrac{\partial{L}}{\partial{y}}\\\dfrac{\partial{L}}{\partial{\lambda}}\end{vmatrix}=\begin{vmatrix}2x-\lambda y\\2y-\lambda x\\-xy+3\end{vmatrix}=\vec{0}$
在我看来，这个拉格朗日函数就是一个上述算法的紧凑版，本质无区别。