机器学习深入与强化--数学基础(4)

一般优化问题：无约束和有约束

无约束：

综上，无约束忧化直接分析法的局限：

局限一：导数有可能求不出来

局限二：即便求出导数，导数=0的解可能就不出来，比如导数本身就是高维函数

局限三：即便是解出来了，对于有些高度非线性矩阵，解也有可能是一个集合的形式，找一个最小值的解也不容易

主要就看搜索方向dk的选择：

上式先忽略二次项，只看前两项，第二项和再做向量的内积，内积的定义为a和b的模的乘积再乘以cos夹角，所以要想下降，显然取负的梯度，就是在减一个数，即要比小，这就是在下降，下降的最快，就选择cos=-1。所以在图形上显示，深度下降法会走一个z字形的路径，最终逼近一个最优解。

但是这个算法通常比较慢，而且大概率求到的是局部最优解，尤其是函数极其复杂时，很难找到全局最优解。

上述深度下降法胡洛了二次项，而牛顿法重新考虑的二次项，考虑的数量更多，情况更全面。

但牛顿法也不是万能的，好的时候特别好，坏的时候也不咋地，有可能越走越坏。如果海森矩阵不可逆，就要做一定的修正。

相比深度下降法的z字形路径，牛顿法有效的时候，在选好步长的前提下，一步就可以到位。

因为牛顿法的搜索方向的式子中，需要求海森矩阵的逆矩阵。首先海森矩阵不一定可逆，其次即便可逆，求起来也可能很复杂。所以有了下面的Quasi牛顿法，利用估计对牛顿法的改进。

有约束：

无约束的时候求最优解：一阶导数等于零，判断二阶倒数的正负。

这么说KKT条件有一些抽象，下面简单说说他是如何推导出来的。

对于具有等式和不等式约束的一般优化问题：

KKT条件给出了判断是否为最优解的必要条件。

1、等式约束优化问题：

令，函数称为拉格朗日函数，参数称为拉格朗日乘子。

再联立方程组：

得到的解为可能极值点，由于我们用的是必要条件，具体是否为极值点需根据问题本身的具体情况检验。这个方程组称为等式约束的极值必要条件。

上式我们分别对n个和l个进行求偏导，相当于将优化变量个数增加到(n+l)个，与一视同仁，均为优化变量，均对它们求偏导.

2、不等式约束优化问题：

主要思想：将不等式约束条件变成等式约束条件。

具体做法：引入松弛变量。松弛变量也是优化变量，也需要一视同仁求偏导。

具体而言，我们先看一个一元函数的例子：

在这种优化问题中，我们必须求得一个确定的值，因此不妨令所有的不等式均取到等号，即<=的情况。

这里引入了两个松弛变量和，这两个变量直接就是非负数，避免了引入新的约束。

由此我们将不等式约束转化为了等式约束，并得到Lagrange函数：

我们再按照等式约束优化问题（极值必要条件）对其求解，联立方程

得出方程组后，便开始动手解它. 看到第3行的两式和比较简单，我们就从它们入手吧~

对于，我们有两种情况：

情形1：

因此g1与其相乘为零，可以理解为约束g1 不起作用，且有。

情形2：

此时，可以理解为约束g1起作用，且有g1(x)=0。

合并情形1和情形2得：，且在约束起作用时，约束不起作用时。

同理可分析，可得出约束g2起作用和不起作用的情形，并分析得到。

由此，方程组（极值必要条件）转化为：

这是一元一次的情形.类似地，对于多元多次不等式约束问题，

我们有：

上式便称为不等式约束优化问题的KKT（Karush-Kuhn-Tucker）条件称为KKT乘子。

总和上述两种约束情况：

KKT条件（是最优解的必要条件）为：

但是如果是凸优化，KKT条件就是该函数的充要条件。

一阶充要条件不好用，因为我们要将所有的点都带进去试一试，但很好解释。

二阶充要条件比较好用。

凸函数有一点非常重要：凸函数的局部最优解就是全局最优解（用凸函数定义，使用反证法可证之）。