机器学习的优化算法概述
机器学习的问题最终都会归结为对一个优化问题进行求解，而优化问题可以分为无约束优化问题和有约束优化问题。有约束的优化问题是指对于目标函数中的变量有显式约束条件的，比如0<=x<=100。无约束优化问题是指对于目标函数的变量没有显式约束的，或者说可以将约束转化成目标函数的惩罚项的，比如说正则化项。
大多数机器学习问题最终都要解一个无约束的优化问题，因此本文主要对无约束优化问题及其优化算法做一个概述。下文提到的优化问题都指无约束优化问题。
提到优化问题，自然就要知道优化算法。需要注意的是，没有一种通用的优化算法可以解决所有的优化问题，不同的算法适用于不同的问题。
一般来讲，优化算法采用的是迭代求解的方式。算法会设定一个初始值，然后不断迭代，直到找到一个最优解。关于如何迭代，不同的算法采取了不同的策略，有的算法利用了目标函数的值，有的算法利用了目标函数的一阶导数和二阶导数的信息，有的算法利用了前几轮迭代的信息，有的算法则利用了当前点的局部信息。
对于一个优化问题，如果我们能够求出它的全局最优，那么问题就一步到位了。而实际上，求解目标函数的全局最优解是很难的，原因在于我们对于目标函数的了解只能是它的局部信息，机器学习所使用的优化算法大都只能求出局部最优值。可能有人会有疑问，既然这些算法只能求出局部最优，那在机器学习中使用这些算法岂不是总也得不到全局最优？幸运的是，机器学习最后所要求解的目标函数大都是凸函数，我们知道，对于凸函数来讲，其局部最优就是全局最优，那么这样一来，那些求解局部最优解的算法就可以用了。
对于这些凸函数来讲，有的是可微的，有的则不是。对于后者的求解是相对困难的，但是如果函数只在个别点处不可微，比如f（x） = ||x||1。这样的函数求解还是相对容易的。
下面总体介绍一下求解无约束优化问题的算法。
所有求解无约束优化问题的算法都需要设定一个初始值x0，算法从x0开始进行迭代，直到取得最优值或者满足收敛条件为止。关于算法如何从xk迭代到xk+1，基本上有两种做法，这里主要讲讲直线搜索（line search）。
搜索方向
在直线搜索的方式中，算法首先选择一个搜索方向（不同的算法选择的搜索方向不同）pk，然后沿着这个方向从xk开始去搜索xk+1，使得目标函数在xk+1处的值要更优于在xk处的值。现在的问题是要沿着pk走多长，才能找到最优的xk+1，所以在直线搜索中，一旦搜索方向确定了之后，搜索的是这个步长t的值。这可以通过下面的公式获得：
（1）
通过求解式（1），我们可以得到最优的t值，但是在实践中，这样做的代价是十分大的，也没有必要，因此实践中只需要找到一个最小值的近似就可以了，也就是说f（xk+1）的值相对于f（xk）的值有足够的减小即可。在得到xk+1后，算法会重新计算新的迭代方向和步长。如此往复，直到最终问题求解。
对于直线搜索，我们已经提到了不同的算法会选择不同的搜索方向。这里我们介绍两个方向，一个是最速下降方向（steepest descent direction），另一个是牛顿方向（newtown direction）。前者对应的是目标函数的一阶导数，而后者对应的是目标函数的二阶导数。
最速下降方向
在直线搜索中，对于从xk出发的所有搜索方向，直觉上来讲，沿着梯度负方向是使得目标函数减小最多的方向，也就是我们的最速下降方向。表达式如下：
（2）
由（2）式可知：
（3）
基于最速下降法的优化算法在每一步迭代都沿着梯度的负方向进行直线搜索。它的优点是只需要计算目标函数的一阶导数；缺点就是算法呈线性收敛，在处理一些复杂问题时速度很慢，甚而至于慢到没有实用价值。
需要注意的是，最速下降方向仅仅是算法的局部性质。
牛顿方向
牛顿方向对应的优化算法称为牛顿法。牛顿方向的确定用到了目标函数的二阶导数，下式为在第k步迭代时确定的搜索方向。
（4）
这样一来，xk+1 = xk + pk。这里需要注意的是，我们假设步长t始终等于1。实践中是以1为初始值对步长进行直线搜索。
将目标函数在xk处作二阶泰勒展开，可得：
（5）
式（5）的右边为v的二次函数，要使得式子最小，那么对v求导并令结果式等于0可得：
（6）
求解式（6）可得：
（7）
由此可知，当搜索方向为牛顿方向时，目标函数减少最多。
对于多元函数，其二阶导数是一个矩阵，名叫海森矩阵（Hessian Matrix）。
牛顿法在接近局部最小值时为二次收敛，仅需5到6次就可以达到很高的精度，特别是在计算大规模问题时，无论是从收敛速度还是精度来讲，都有着最速下降法无法比拟的优势。牛顿法的缺点在于算法在执行过程中需要计算和存储海森矩阵以及海森矩阵的逆，当矩阵太大时，计算负荷太重。更为致命的是，目标函数的海森矩阵无法在算法执行期间保持正定，从而使得牛顿法失效。
拟牛顿方向
基于拟牛顿方向的优化算法称为拟牛顿法。拟牛顿法的思路实际上就是在迭代的每一步用一个矩阵Bk来替代海森矩阵，从而不必计算海森矩阵。Bk在迭代的每一步都会更新，只要B0为正定，那么任何一步迭代更新的Bk一定保证正定。通过Bk我们可以得到每一步向下一步迭代时的搜索方向。
需要注意的是，拟牛顿法的每一次迭代不能保证一定是最优的下降方向，但是一定是下降的，这样就保证了每一次迭代后，目标函数的值总会降低。
拟牛顿法的收敛速度没有牛顿法收敛得快，但是要好于最速下降法的线性收敛。
归一化
有时候优化算法的性能取决于问题的形式。这其中一个重要的方面就是模型参数（目标函数系数）的归一化。当目标函数的某一个变量发生变化时，它使得目标函数的值发生很大的变化，而在另外的变量上做相同的改变时，目标函数值的变化远远不及上述变化，那么这个问题被认为是没有归一化的。比如目标函数为：f(x) = 1010x1+ 0.1x2，那么很小的变化发生在x1上时，f的值会有很大的变化，但x2却不然。这个目标函数就没有做归一化。
基于一阶导数（梯度）的优化算法对于没有归一化的目标函数十分敏感，收敛很慢并且效果不好。但是基于二阶导数的牛顿法就不受此影响。
下图是两个凸二次函数的等值线，其中第一个表示没有归一化的目标函数，第二个表示归一化后的目标函数。对于第一个等值线，我们可以看出它的一边被拉得特别长，另一边又特别扁平，这种问题在工程上属于病态问题，基于梯度的方法无法快速的收敛到最优值。但是在两种情况下，基于二阶导数的牛顿法（或是拟牛顿法）都能很快收敛到很好的结果。由于实际工程中很多问题无法归一化，因此这些问题往往是病态的，因此我们在工程上一般都会选用基于二阶导数的拟牛顿法来求解无约束的最优化问题。
以上的讨论从大体上介绍了求解无约束优化问题的算法。在实际工程的应用中，还是会有些变化。比如说，解决超大规模的优化问题时，即便是拟牛顿法，比如BFGS，也无法很好地解决，原因在于拟牛顿法虽然不用计算和存储海森矩阵，但要计算和存储海森矩阵的近似矩阵B，当近似矩阵B很稠密时，算法的计算量和存储量也是巨大的。因此实践中一定会用到的方法是L-BFGS算法。该方法十分的重要，掌握了它不仅仅是掌握了一个算法，更重要的是掌握了求解大规模优化问题的一种思想。这个算法将会单独介绍。