拉格朗日乘子

拉格朗日乘子在很多机器学习中都提到过，一般都会被一带而过，因为本身理论就比较复杂，这里会拉格朗日乘子的使用做一个简答的介绍，否则SVM这一类凸优化算法根本不可能理解其精髓。

在求解最优化问题中,经常用到就是拉格朗日乘子法。在有等式约束时使用拉格朗日乘子法，在有不等约束时使用KKT条件。当你遇到优化问题的时候，一般你会面临三种境遇。

无约束条件

这是最简单的情况，解决方法通常是函数对变量求导，令求导函数等于0的点可能是极值点。将结果带回原函数进行验证即可.

等式约束条件

设目标函数为$f(x)$，约束条件为$h_k(x)$，形如:

$$min f(x)$$

$$st.h_k(x)=0$$

$st.$表示受限于。

我们映射到一个具体的问题上，问题描述如下，给定椭球的表达式为：

$$\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}=1$$

求这个椭球的内接长方体的最大体积。这个问题实际上就是条件极值问题, 和上面的表达式是不是表达同一个意思？

条件$\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}=1$下。求 $f(x,y,z)=8xyz $的最大值。

首先定义拉格朗日函数

$$F(x,\lambda)=f(x)+\sum \lambda_k h_k(x)$$

然后解变量的偏导方程

$$\frac{\partial F}{\partial x_k}=0$$

$$\frac{\partial F}{\partial \lambda_k}=0$$

如果有$n$个约束条件，就应该有$n+1$个方程。求出的方程组的解就可能是最优化值，将结果带回原方程验证就可得到解。

$$F(x, y, z, \lambda)=f(x, y, z) + \lambda(x, y, z)$$

$$F(x, y, z, \lambda)=8xyz+ \lambda(\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1)$$

对$F(x, y, z, \lambda)$求偏导数

$$\frac{\partial F}{\partial x}=8yz+\frac{2\lambda x}{a^2}=0$$

$$\frac{\partial F}{\partial y}=8xz+\frac{2\lambda y}{b^2}$$

$$\frac{\partial F}{\partial z}=8xy+\frac{2\lambda z}{c^2}$$

$$\frac{\partial F}{\partial \lambda}=\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1=0$$

解四个方程

$$x=\frac{\sqrt{3}}{3}a$$

$$y=\frac{\sqrt{3}}{3}b$$

$$z=\frac{\sqrt{3}}{3}c$$

带入解得最大体积为：

$$V=\frac{8\sqrt{3}}{9} abc$$

不等式约束条件

目标函数$f(x)$, 不等式约束$g(x)$

$min f(x)$
$st. g_k(x)<=0$

则我们定义不等式约束下的拉格朗日函数L，则L表达式为：

$$L(X,\lambda,\mu)=f(x)+\sum\lambda_jh_j(X)+\sum\mu_kg_k(X)$$

其中$f(x)$是原目标函数，$h_j(x)$是第j个等式约束条件，$λ_j$是对应的约束系数，$g_k$是不等式约束，$u_k$是对应的约束系数

常用的方法是KKT条件，同样地，把所有的不等式约束、等式约束和目标函数全部写为一个式子

$$L(a, b, x)= f(x) + ag(x)+bh(x)$$

KKT条件是说最优值必须满足以下条件：
L(a, b, x)对x求导为零；
h(x) =0;
ag(x) = 0;

求取这些等式之后就能得到候选最优值。其中第三个式子非常有趣，因为g(x)<=0，如果要满足这个等式，必须a=0或者g(x)=0. 这是SVM的很多重要性质的来源，如支持向量的概念。

KKT推导

这里我就粘贴一个网上资源吧，实在太复杂，其实会用就可以，有机会可以推导一下。