持续填坑中。。。
假设多元目标函数是上具有一阶连续偏导的函数，要求解的无约束最优化如下：
一些经典的无约束优化问题，例如：
1、数据拟合，类似最小二乘法，但是我们想用一个指数来拟合：
2、假设数据为正态分布，使用正态分布来拟合：
正态分布模型：
代价函数：
要求估算出 来最大化概率分布
3、找到一堆数据的几何中心，几何中心满足跟所有多元数据的二范式最小：
一、分块松弛法
对于多元目标函数，可以反复地分别沿每个坐标轴方向进行一维搜索，称为坐标循环下降法；如果把x的多元分量分成若干组，每次针对某一组分量进行优化，然后轮换其他组进行优化，这样的方法叫做分块松弛法，这种方法一般比较简单易行，但其收敛速度不一定是最优的。
分块松弛法一般用在类似例3的k均值聚类问题中，作为初始中心，可以随机地选个k不同的点当作初始的聚类中心， 但是最好能让这k个初始中心相互距离远一些。 然后，轮流地，先把所有点按照到类中心的距离分配到k个类中， 再重新计算类中心， 如此重复直到结果不再变动。 这个算法简单有效。
二、梯度下降法
1、最速下降法 (steepest descent)
梯度下降法 (gradient descent)或最速下降法 (steepest descent)是求解无约束 最优化问题的一种最常用的方法，具有实现简单的优点。梯度下降法是迭代算法，每一步需要求解目标函数的梯度向量。
选取适当的初值 , 不断迭代，更新 的值，进行 目标函数的极小化，直到收敛。由于负梯度方向是使函数值下降最快的方向，在迭代的每一步，以负梯度方向更新 x 的值，从而达到减少函数值的目的。
具体方法：
由于具有一阶连续偏导数，若第 k 次迭代值为 , 则可将 在 附 近进行一阶泰勒展开:
是在处的梯度，等于所有维度的偏导数合成向量；
求出第k+1次迭代值:
其中，是搜索方向，取负梯度方向，是步长，由一维搜索确定，即使得
一般情况：如果其中不是通过一维搜索得到而是预先设定， 一般取为很小的正数， 称为学习速率，则该优化方法为一般的梯度法。 如果取为常数， 则较大的使得收敛较快， 但有可能跨越最小值点； 较小的收敛比较稳定但速度太慢。 也可以取，例如 (0<<1)， 这避免了两次搜索方向总是正交的问题， 在统计学习中可以减少过度拟合。
当目标函数是凸函数时，梯度下降法的解是全局最优解。一般情况下，其解不保证是全局最优解。梯度下降法的收敛速度也未必是很快的。
在算法中，“迭代收敛”可以用梯度向量长度小于某个预定值， 或者两次迭代间函数值变化小于某个预定值来判断。 在适当正则性条件下， 最速下降法可以收敛到局部极小值点并且具有线性收敛速度。 但是， 最速下降法连续两次的下降方向和是正交的， 这是因为在第k步沿搜索时找到点时已经使得函数值在该方向上不再变化， 下一个搜索方向如果与该方向不正交就不是下降最快的方向。 这样，最速下降法收敛速度比较慢。 所以， 在每次迭代的一维搜索时， 可以不要求找到一维搜索的极小值点， 而是函数值足够降低就结束一维搜索。 见沃尔夫准则。
一般大家最常用的就是最速梯度下降法，但是也存在各种方法变种，例如：
2、随机梯度法
例如之前提到的第二类问题，使用正态分布来拟合大量数据的分布情况，如果对代价函数使用梯度法求解极小值，当样本量特别巨大时，计算每一个会占用过多的计算资源使得算法不可行。
核心思想：在迭代的第k步， 可以从个样本点中随机抽取个样本, 记这些抽取的子样本下标集合为
， 用估计代价函数；每一次迭代计算梯度时，重新抽样并利用最速梯度下降法进行优化逼近， 称这种方法为随机梯度法。 当特别巨大时， 可以不随的增大而增大， 使得梯度法能适用于训练样本量过于巨大的训练数据集。
3、共轭梯度法
最速下降法收敛速度较慢， 而且越靠近最小值点步长越短， 速度越慢。 对于一个函数曲面为狭长的山谷形状的目标函数， 为了达到山谷的最低点， 会沿相互正交的梯度方向反复跳跃。
一种解决的方法是前面所说的不使用最优一维搜索而是使用预先确定的步长或步长序列， 还有一种方法是将两步之间的梯度正交， 推广到两步之间为“共轭”关系，即对某个矩阵使得
这种方法的来源是对目标函数用二次多项式近似：
而为了将一个d元的凸二次多项式达到最小值点， 只要从负梯度方向出发，沿着d个相互都关于共轭的方向进行一维搜索就保证达到最小值点。 连续可微函数在最小值点附近一般都很接近于一个凸二次多项式函数， 所以共轭梯度法能够克服最速下降法在靠近最小值点时收敛变慢的问题。
矩阵选取最好是Hissian阵， 但海色阵一般比梯度更难获得， 使用海色阵的方法见牛顿法和拟牛顿法。 共轭梯度法实际的算法并不去求， 而是从的负梯度出发， 然后每次用当前处的负梯度和上一步的共轭方向的线性组合作为t到t+1步的搜索方向。即：
对d元凸二次多项式，其中的系数可以用解出精确公式， 使得各个彼此共轭。 但是对一般目标函数， 只能使用一些近似的。方法例如：Fletcher-Reeves共轭梯度法和Polak-Ribiere法
4、动量法
loading
5、超梯度下降法
loading
三、牛顿法
1、概述
除了之前说的比较常用的各种梯度法，牛顿法也是机器学习中用的比较多的一种优化算法。如果希望迭代函数有一种固定格式的构造方法，就可以采用Newton迭代法。
牛顿法的基本思想是利用迭代点处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近似，然后把二次模型的极小点作为新的迭代点，并不断重复这一过程，直至求得满足精度的近似极小值。牛顿法的速度相当快，而且能高度逼近最优值。牛顿法分为基本的牛顿法和全局牛顿法。
2、原理
基本思想是：设法将一个非线性方程 转化为某种线性方程求解，其解决问题的基础是Taylor（泰勒）多项式展开！
（1）首先是一维情形：
对于一个需要求解的优化函数，求函数的极值的问题可以转化为求导函数。对函数进行泰勒展开到二阶，得到
对上式求导并令其为0，则为
即得到
几何解释：
Newton迭代法求解根的几何解释如下图所示：
方程的根为和（即x轴）的交点。设为某个初始近似值，过点作的切线交x轴于 ，即为所求得的近似值。继续过点，点,，作的切线，即可逐步逼近精确的根
因此，Newton法也叫切线法，因为它是沿着曲线上某一点作切线逐步外推逼近的。从点作切线与x轴的交点，由于不是直线，所以就不可能为零。因此必须以作为新的起点，从与之对应的点继续作切线，重复上述步骤，直至充分小，逼近零时为止。
Newton迭代法求解最优化的几何解释如下图所示：
设为某个初始近似值，过点进行多项式拟合（泰勒二阶展开），找到多项式的极值点（导数为0）作为下一个近似值继续进行迭代（因为只有泰勒二阶展开，拟合的多项式极值点不等于原始模型的极值点，要继续进行迭代），进而迭代得到当误差小于一定值或达到迭代上限，停止迭代，得到近似的最优极值点。
（2）推广到多维情形：
假设的自变量是多元变量，且具有二阶连续偏导数，若第k次迭代值为，则将在附近进行二阶泰勒展开：
是的梯度向量在点的值，也称作，是的黑塞矩阵（Hessian matrix）
在点的值。
若为正定矩阵，对泰勒展开的对求梯度导，令其为0：
所以的最小值点在
处达到。这一步需要用的Hessian矩阵的逆矩阵。所以牛顿法取初值后，用公式
进行迭代，直至收敛。 收敛的判断准则可以取为足够小， 或者取为足够小。
如果初值接近于最小值点并且目标函数满足一定正则性条件， 牛顿法有二阶收敛速度。但是问题是Hessian矩阵引入的复杂性，使得牛顿迭代求解的难度大大增加，但是已经有了解决这个问题的办法就是Quasi-Newton methond（拟牛顿法），不再直接计算hessian矩阵，而是每一步的时候使用梯度向量更新hessian矩阵的近似。
3、最速下降法和牛顿法的比较
牛顿法收敛更快，最速梯度法相邻两次迭代的方向互相垂直，这种锯齿现象会影响收敛速度！
从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。 如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。） 根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
四、拟牛顿法
在牛顿法的迭代中，需要计算黑塞矩阵的逆矩阵 ，这一计算比较复杂，考虑 用一个 n 阶矩阵 来近似代替 。这就是拟牛顿法的基本想法。
1、拟牛顿条件(Secant equation)
取 ，由泰勒二项展开的求梯度可得：
得
记 ，
或者，这称为拟牛顿条件(Secant equation)。
所以在拟牛顿法中，选择 作为 的近似，并且使得它们满足每次迭代是正定的，且满足上述拟牛顿条件，即s
为什么要满足正定条件？根据迭代公司和二项泰勒展开的可知
当正定时，恒成立，说明迭代方向是下降方向。
所以按照拟牛顿挑选选择的算法称为拟牛顿法，按照拟牛顿条件，在每次迭代中可以选择更新矩阵，这种选择有一定的灵活性，因此有多种具体实现方法。
2、DFP算法 (Davidon-Fletcher-Powell)
DFP算法用 作为 的近似，选择 的方法是，假设每一步迭代中矩阵 是由 加上两个附加项构成的，即
为使 满足拟牛顿条件，可使和 满足: ，
事实上，不难找出这样的和, 例如取
所以这里我们直接给出计算公式：
可以证明，如果初始矩阵 是正定对称的，则迭代过程中的每个矩阵 都是正定对称的，一般取
3、BFGS拟牛顿法
BFGS算法用 作为 的近似，与DFP相比，BFGS性能更佳。
这时，相应的拟牛顿条件是 ，可以用同样的方法得到另一迭代公式，首先令
考虑使和满足：
这里我们直接给出计算公式：
可以证明，如果初始矩阵 是正定对称的，则迭代过程中的每个矩阵 都是正定对称的，一般取 。
若记 ， ，那么应用Sherman-Morrison公式可以将上述迭代公式改写为：
这就是BFGS算法关于 Gk 的迭代公式。
参考
- 无约束优化方法-统计计算
- 统计学习方法（第二版)-李航
- Newton’s Method Optimization: Derivation and How It Works
- 【下降算法】最速下降法、Newton法、共轭梯度法
