---

拉格朗日乘子法

本节内容直接摘自约束优化方法之拉格朗日乘子法与KKT条件，这篇文章是我觉得阐述的最清晰的一篇关于KTT条件的，对着敲一遍不失为一个比较好的加深记忆的办法。
拉格朗日乘子法可以用解决带有约束条件的最优化问题，约束条件又分为等式约束和不等式约束。对于等式约束，可以直接应用拉格朗日乘子法求得最优解，对于含有不等式约束的最优化问题，可以转化为在满足KTT条件下的拉格朗日乘子法求解。拉格朗日乘子法求得的并不一定是最优解，只有在凸优化的情况下，才能保证得到的是最优解，所以本文称拉格朗日乘子法得到的为可行解，其实就是局部极小值。

无约束优化

首先考虑一个不带任何约束的优化问题，对于变量$x\in\mathbb{R}^N$的函数$f(x)$，无约束优化问题如下：

$$\underset{x}{min}f(x)$$

该问题很好解，根据Fermat定理，直接找到使目标函数得0的点即可即$\bigtriangledown_xf(x)=0$，如果没有解析解的话，可以使用梯度下降或牛顿方法等迭代的手段来使$x$沿负梯度方向逐步逼近极小值点。

等式约束优化

当目标函数加上约束条件之后，问题就变成如下形式：

$$\underset{x}{min}f(x)$$ $$s.t.\quad h_i(x)=0,i=1,2,...,m$$

约束条件会将解的范围限定在一个可行域，此时不一定能找到使得$\bigtriangledown_xf(x)=0$的点，只需找到在可行域内使得$f(x)$最小的值即可，常用的方法即为拉格朗日乘子法，该方法首先引入Lagrange Multiplier $\alpha\in\mathbb{R}^m$，构建拉格朗日等式如下：

$$L(x,\alpha)=f(x)+\sum^m_{i=1}\alpha_ih_i(x)$$

求解方法如下：首先基于等式对$\alpha$和$x$求：

$$\left\{\begin{matrix} \bigtriangledown_xL(x,\alpha)=0\\ \bigtriangledown_{\alpha}L(x,\alpha)=0 \end{matrix}\right.$$

令导数为0，求得$x$，$\alpha$的值后，将$x$带入$f(x)$即为在约束条件$h_i(x)$下的可行解。这样做的意义是什么呢? 接下来看一个直观的示例，对于二维情况下的目标函数是$f(x,y)$，平面中画出$f(x,y)$的等高线，如下图的虚线所示，并只给出一个约束等式$h(x,y)=0$，如下图的绿线所示，目标函数$f(x,y)$与约束$g(x,y)$只有三种情况，相交、相切或者没有交集，没交集肯定不是解，只有相交或者相切可能是解，但相交得到的一定不是最优值，因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与目标函数的交点的值更大或者更小，这就意味着只有等高线与目标函数的曲线相切的时候，才可能得到可行解。

因此给出结论：拉格朗日乘子法取得极值的必要条件是目标函数与约束函数相切，这时两者的法向量是平行的，即：

$$\bigtriangledown_{x}f(x)-\alpha\bigtriangledown_{x}h(x)=0$$

所以只要满足上述等式，且满足之前的约束$h_i(x)=0,i=1,2,…,m$，即可得到解，联立起来，正好得到就是拉格朗日乘子法。

不等式约束优化

当约束加上不等式之后，情况变得更加复杂，首先来看一个简单的情况，给定如下不等式约束问题：

$$\underset{x}{min}f(x)$$ $$s.t.\quad g(x)\leq 0$$

对应拉格朗日式子与图形分别如下所示：

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

这时的可行解必须落在约束区域$g(x)$之内，下图给出了目标函数的等高线与约束：

由图可见可行解$x$只能在$g(x)<0$或者$g(x)=0$的区域里取得：

• 当可行解$x$落在$g(x)<0$的区域内，此时直接极小化$f(x)$即可；
• 当可行解$x$落在$g(x)=0$即边界上，此时等价于等式约束优化问题.

当约束区域包含目标函数原有的可行解时，此时加上约束可行解扔落在约束区域内部，对应$g(x)<0$的情况，这时约束条件不起作用；当约束区域不包含目标函数原有的可行解时，此时加上约束后可行解落在边界$g(x)=0$上。下图分别描述了两种情况，右图表示加上约束可行解会落在约束区域的边界上。

以上两种情况就是说，要么可行解落在约束边界上即得$g(x)=0$，要么可行解落在约束区域内部，此时约束不起作用，另$\lambda=0$消去约束即可，所以无论哪种情况都会得到：

$$\lambda g(x)=0$$

还有一个问题是$\lambda$的取值，在等式约束优化中，约束函数与目标函数的梯度只要满足平行即可，而在不等式约束中则不然，若$\lambda\neq0$，这便说明可行解$x$是落在约束区域的边界上的，这时可行解应尽量靠近无约束时的解，所以在约束边界上，目标函数的负梯度方向应该远离约束区域朝向无约束时的解，此时正好可得约束函数的梯度方向与目标函数的负梯度方向应相同：

$$-\bigtriangledown_xf(x)=\lambda\bigtriangledown_xg(x)$$

上式需要满足的要求是拉格朗日乘子$\lambda>0$，这个问题可以举一个形象的例子，假设你去爬山，目标是山顶，但有一个障碍挡住了通向山顶的路，所以只能沿着障碍爬到尽可能靠近山顶的位置，然后望着山顶叹叹气，这里山顶便是目标函数的可行解，障碍便是约束函数的边界，此时的梯度方向一定是指向山顶的，与障碍的梯度同向，下图描述了这种情况:

可见对于不等式约束，只要满足一定的条件，依然可以使用拉格朗日乘子法解决，这里的条件便是KKT条件。接下来给出形式化的KKT条件首先给出形式化的不等式约束优化问题：

$$\underset{x}{min}f(x)$$ $$s.t.\quad h_i(x)=0,i=1,2,...,m$$ $$s.t.\quad g_j(x)\leq0,j=1,2,...,n$$

列出无约束优化问题的拉格朗日方程得到：

$$L(x,\alpha,\beta)=f(x)+\sum^m_{i=1}\alpha_ih_i(x)+\sum^n_{j=1}\beta_jg_j(x)$$

经过之前的分析，便得知加上不等式约束后可行解$x$需要满足的就是以下的KKT条件：

$$\begin{aligned} \bigtriangledown_xL(x,\alpha,\beta)&=0 &(1) \\ \beta_jg_j(x)&=0,j=1,2,...,n &(2) \\ h_i(x)&=0,i=1,2,...,m &(3) \\ g_j(x)&\leq0,j=1,2,...,n &(4) \\ \beta_j&\geq0,j=1,2,...,n &(5) \end{aligned}$$

满足KKT条件后极小化拉格朗日公式即可得到在不等式约束条件下的可行解。KKT条件看起来很多，其实很好理解:
(1):拉格朗日取得可行解的必要条件；
(2):这就是以上分析的一个比较有意思的约束，称作松弛互补条件；
(3)~(4):初始的约束条件；
(5):不等式约束的拉格朗日乘子需满足的条件。
主要的KKT条件便是(3)和(5)，只要满足这俩个条件便可直接用拉格朗日乘子法。

---

L1和L2正则

现在，我们用拉格朗日乘子法的解空间来理解L1和L2正则，有时候，相对于约束参数而言，L1又叫lasso回归，L2又叫岭回归(Ridge Regression)。
现在有一个损失函数$L(y,\hat{y})$，引入L1正则：

$$J(w)=L(y,\hat{y};w)+\lambda\sum^n_{i=1}|w_i| \tag{6}$$

引入L2正则：

$$J(w)=L(y,\hat{y};w)+\frac{1}{2}\lambda\sum^n_{i=1}w_i^2 \tag{7}$$

可以看到他们就是在求等式约束时拉格朗日公式的普通形式。观察两维，即取$w=1,2$，(6)式的正则项为$|w_1|+|w_2|$它和损失函数组成下右图，(7)式的正则项为$w_1^2+w_2^2$，它和损失函数组成下面左图。

现在我们讨论可行解落在约束边界上的情况，比较清晰的看出来，对于L1正则，受到约束的最优解$w^*$往往在棱形的顶点取到，而顶点在某一个维度上的投影为0(图中对应$w_1$这个轴，而$w_2$这个维度被选择了出来)，而对于L2正则，受到约束的最优解$w^*$可以在圆上的任意一点取到。
接下来就可以看图说说L1和L2的特点了，L1会趋向于产生少量的特征，而其他的特征都是0，故L1正则化导出的稀疏性质已被广泛用于特征选择，而L2会选择更多的特征，这些特征都会接近于0，更常见于做正则化。

---

Reference

• 约束优化方法之拉格朗日乘子法与KKT条件