二分查找
 
概念
 
 
 
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
 
 
查找过程
 
 
 
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
 
 
算法要求
 
 
 
1.必须采用顺序存储结构。
 2.必须按关键字大小有序排列。
 
 
算法时间复杂度
 
 
 
二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
 时间复杂度无非就是while循环的次数！
 总共有n个元素，渐渐跟下去就是n,n/2,n/4,…n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。
 由于你n/2^k取整后>=1
 即令n/2^k=1
 可得k=log2n,（是以2为底，n的对数）
 所以时间复杂度可以表示O(h)=O(log2n)
 
 
代码实现
 
 
第一种：迭代法
 
int binarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            //中间位置计算,low+ 最高位置减去最低位置,右移一位,相当于除2.也可以用(high+low)/2
            int middle = low + ((high - low) >> 1);
            // int middle=(low+high)/2;
            //与最中间的数字进行判断,是否相等,相等的话就返回对应的数组下标.
            if (key == arr[middle]) {
                return middle;
                //如果小于的话则移动最高层的"指针"
            } else if (key < arr[middle]) {
                high = middle - 1;
                //移动最低的"指针"
            } else {
                low = middle + 1;
            }
        }
        return -1;
    }

 
第二种:递归
 
int BinarySearchRecursion(int arr[], int low, int high, int key) {
        if (low <= high) {
            int mid = (low + high) / 2;
            if (key == arr[mid])
                return mid;
            else if (key < arr[mid])
                //移动low和high
                return BinarySearchRecursion(arr, low, mid - 1, key);
            else if (key > arr[mid])
                return BinarySearchRecursion(arr, mid + 1, high, key);
        }
        return -1;
    }
 
顺序查找
 
二分查找顺序不一定是顺序存储，可以是无须的，对顺序没什么要求。
 
int SequentialSearch(int s[], int key) {
        int i;
        i = 0;
        int length = s.length;
        while (i < length && s[i] != key) i++;
        if (s[i] == key) return i;
        else return -1;
    }
 
算法时间复杂度：为O（n);

目录
 
 
 
广度优先搜索（BFS）
 
深度优先搜索（DFS）
 
爬山法（Hill Climbing）
 
最佳优先算法（Best-first search strategy） 
 
回溯法 （Backtracking）
 
分支限界算法（Branch-and-bound Search Algorithm）
 
A*算法
 

广度优先搜索（BFS）
 
这个不用我多说了吧……
 
深度优先搜索（DFS）
 
同上……
 
爬山法（Hill Climbing）
 
DFS的变形，不同的是每次选择的是最优的一个子结点，即局部最优解
 
例如，对于8数码问题，设置一个函数表示放错位置的数目，每次选择子结点中放错最少的结点
 
步骤：
 
 
 
1.建立一个栈，将根结点放入栈
 
 
2.判断栈顶元素是否是目标结点，如果是，算法结束，如果不是，进入第三步
 
 
3.栈顶元素出栈，根据评估函数计算的顺序将此结点的子结点入栈
 
 
4.如果栈空，则输出失败，否则，进入第二步
 
 
最佳优先算法（Best-first search strategy） 
 
是DFS和BFS的结合
 
每次找到的是所有结点中最好估计值的那个结点
 
找到的是全局最优解
 
步骤：
 
 
 
1.根据评估函数建立一个堆（或用优先队列），将根结点放入堆中
 
 
2.判断栈顶元素是否是目标结点，如果是，算法结束，如果不是，进入第三步
 
 
3.移出堆顶元素结点，将此结点的所有子结点加入堆
 
 
4.如果堆空，输出失败，否则，进入第二步
 
 
回溯法 （Backtracking）
 
找到所有选择，走不通则回溯
 
假定问题的解是一个向量(a1,a2,a3,...,an)，其中的每个元素ai都是问题的一个元素
 
步骤：
 
 
 
建立一个问题的部分解v=(a1,a2,...,ak)
 
 
若这个部分解是可行解，则继续，若不是可行解，删除ak，加入ak情况的另一种可能
 
 
若ak的可能已经遍历完，回溯并寻找ak-1的下一个可能
 
 
算法改进：搜索剪枝
 
 剪枝（pruning）可以帮助我们减少搜索空间，更快的找到解
 
剪枝的思想就是就是通过某种判断，避免一些不必要的遍历过程，就是如果发现此分支不可能找到最优解，就立刻回溯
 
剪枝的策略需要具体问题具体分析，这里不细讲
 
回溯法框架：
 
递归法
 
Backtrack(k,X[1...K-1])
    if(k>n) output(X[1...N])
    else
        for each element x in S(k):
               if(constraint(x,X[1...k-1]))
                    X[k]=x
                    backtrack(k+1,X[1...k])
 
迭代法
 
IterativeBacktrack()
    k=1
    while k>0
        while set S(k) is not empty
            get a new element x from set S(k)
            if(constraint(x,X[1,k-1]))
                X[k]=x
                if(solution(X)) output(X)
                else k++
        k--
 
分支限界算法（Branch-and-bound Search Algorithm）
 
 
 
分支限界法与回溯法的区别
 1.求解目标不同 
      1.回溯法的求解目标是找出解空间树中满足约束条件的所有解
      2.分支限界法的求解目标则是尽快找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解
      3.分支限界法通常用于解决离散值的最优化问题
 2.搜索方式不同 
      1.回溯法以深度优先的方式（遍历结点）搜索解空间树
      2.分支限界法以广度优先或最小耗费优先的方式搜索解空间树
 3.对扩展结点的扩展方式不同 
      1.分支限界法中，每一个活结点只有一次机会成为扩展结点
       2.活结点一旦成为扩展结点，就一次性产生其所有儿子结点
 4.存储空间的要求不同 
      1.分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大 
 
 
转载自最佳优先搜索（Best-First Search） 
 
分支限界算法可以用来寻找最优解，在平均情况下不必穷尽搜索
 
分支限界算法的搜索类似于最佳优先算法并做了一些改进（比如剪枝）
 
两个要点：
 
如何产生分支
 
如何产生界限
 
基本思想：
 
用一种方法分开解空间
 
用一种方法预测一系列解的最小界（lower bound），用一种方法预测最优解的最大界（upper bound）
 
如果一个解的最小界超出了整个解空间的最大界，那么这个解不可能是最优的，我们就可以提前终止此分支
 
分支界限适合最小化问题
 
平均情况下，许多分支能较早被终止，但许多NP难问题在最坏情况下仍是指数级的
 
A*算法
 
个人感觉类似最佳优先算法，都是维护一个优先队列或堆，将结点按照某个值优先的情况放进去，不同的是这次需要一个估计函数h(n)
 
算法思想：对于优先队列，每取出一个结点n，将他的所有儿子结点n'放入优先队列，优先级由函数f(n)计算出
 
 
 
g(n)：起点到结点n的代价
 
 
h(n)：结点n到终点的估计代价
 
 
f(n)=g(n)+h(n)
 
 
A*算法是一种启发式算法
 
设h*(n)为结点n到目标结点的实际最小代价
 
只要h(n)<=h*(n)，那么代价就不会被高估，这个算法就可以找出最优解
 
A*算法使用最佳优先策略，用来解决优化问题
 
步骤：
 
 
 
1.把起点放入优先队列
 
 
2.重复如下过程：
 
 
取出优先级最高的结点n，即f(n)最小的结点，作为当前要处理的结点
将这个结点放入一个close表中，这个表储存父结点子结点等信息
对于此结点可达的结点n'：
①若这个结点不在队列中，计算g(n'),h(n'),f(n')，将其加入队列，并将n设为n'的父亲
②若n'在队列中，计算由n到n'的g(n')值，更小的g(n')意味着这是更好的路径，如果g(n')更小，则将n设为n'的父亲，并重新计算g(n')和f(n')
停止，当：
①终点被找到
②队列为空，此时查找失败
 
3.保存路径，从终点开始，沿着父结点移动至起点，即为路径
 

 常见的几种最优化方法
 
 
 
 
 
 
 
 
 
 
 
 1. 梯度下降法（Gradient Descent）
 
 
 　　梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。梯度下降法的搜索迭代示意图如下图所示：
 
 
 
 
 
 
 　　牛顿法的缺点：
 
 
 　　（1）靠近极小值时收敛速度减慢，如下图所示；
 
 
 　　（2）直线搜索时可能会产生一些问题；
 
 
 　　（3）可能会“之字形”地下降。
 
 
 
 
 
 　　从上图可以看出，梯度下降法在接近最优解的区域收敛速度明显变慢，利用梯度下降法求解需要很多次的迭代。
 
 
 　　在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。
 
 
 　　比如对一个线性回归（Linear Logistics）模型，假设下面的h(x)是要拟合的函数，J(theta)为损失函数，theta是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数h(theta)就出来了。其中m是训练集的样本个数，n是特征的个数。
 
 
 
 
 
 
 
 
 　　1）批量梯度下降法（Batch Gradient Descent，BGD）
 
 
 　　（1）将J(theta)对theta求偏导，得到每个theta对应的的梯度：
 
 
 
 
 
 　　（2）由于是要最小化风险函数，所以按每个参数theta的梯度负方向，来更新每个theta：
 
 
 
 
 
 　　（3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度会相当的慢。所以，这就引入了另外一种方法——随机梯度下降。
 
 
 　　对于批量梯度下降法，样本个数m，x为n维向量，一次迭代需要把m个样本全部带入计算，迭代一次计算量为m*n2。
 
 
 
 　　2）随机梯度下降（Random Gradient Descent，RGD）
 
 
 　　（1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：
 
 
 
 
 
 　　（2）每个样本的损失函数，对theta求偏导得到对应梯度，来更新theta：
 
 
 
 
 
 　　（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。
 
 
 　　随机梯度下降每次迭代只使用一个样本，迭代一次计算量为n2，当样本个数m很大的时候，随机梯度下降迭代一次的速度要远高于批量梯度下降方法。两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。
 
 
 
 　　对批量梯度下降法和随机梯度下降法的总结：
 
 
 　　批量梯度下降---最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。
 
 
 　　随机梯度下降---最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。
 
 
 
 2. 牛顿法和拟牛顿法（Newton's method & Quasi-Newton Methods）
 
 
 
 　　1）牛顿法（Newton's method）
 
 
 　　牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数f (x)的泰勒级数的前面几项来寻找方程f (x) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。
 
 
 　　具体步骤：
 
 
 　　首先，选择一个接近函数 f (x)零点的 x0，计算相应的 f (x0) 和切线斜率f  ' (x0)（这里f ' 表示函数 f  的导数）。然后我们计算穿过点(x0,  f  (x0)) 并且斜率为f '(x0)的直线和 x 轴的交点的x坐标，也就是求如下方程的解：
 
 
 
 
 
 　　我们将新求得的点的 x 坐标命名为x1，通常x1会比x0更接近方程f  (x) = 0的解。因此我们现在可以利用x1开始下一轮迭代。迭代公式可化简为如下所示：
 
 
 
 
 
 　　已经证明，如果f  ' 是连续的，并且待求的零点x是孤立的，那么在零点x周围存在一个区域，只要初始值x0位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果f  ' (x)不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。
 
 
 　　由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：
 
 
 　　牛顿法搜索动态示例图：
 
 
 
 
 
 　　关于牛顿法和梯度下降法的效率对比：
 
 
 　　从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）
 
 
 　　根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
 
 
 
 
 
 注：红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。
 
 
 　　牛顿法的优缺点总结：
 
 
 　　优点：二阶收敛，收敛速度快；
 
 
 　　缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。
 
 
 　　2）拟牛顿法（Quasi-Newton Methods）
 
 
 　　拟牛顿法是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。
 
 
 　　拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。
 
 
 　　具体步骤：
 
 
 　　拟牛顿法的基本思想如下。首先构造目标函数在当前迭代xk的二次模型：
 
 
 
 
 
 　　这里Bk是一个对称正定矩阵，于是我们取这个二次模型的最优解作为搜索方向，并且得到新的迭代点：
 
 
 
 
 
 　　其中我们要求步长ak 
 
 
 满足Wolfe条件。这样的迭代与牛顿法类似，区别就在于用近似的Hesse矩阵Bk 
 
 
 代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵Bk
 
 
 的更新。现在假设得到一个新的迭代xk+1，并得到一个新的二次模型：
 
 
 
 
 
 　　我们尽可能地利用上一步的信息来选取Bk。具体地，我们要求
 
 
  
 
 
 
 
 
 　　从而得到
 
 
 
 
 
 　　这个公式被称为割线方程。常用的拟牛顿法有DFP算法和BFGS算法。
 
 
 3. 共轭梯度法（Conjugate Gradient）
 
 
 　　共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。
 
 
 　　下图为共轭梯度法和梯度下降法搜索最优解的路径对比示意图：
 
 
 
 
 
  
 
 
 注：绿色为梯度下降法，红色代表共轭梯度法
 
 
 　   
 
 
 4. 启发式优化方法
 
 
 　　启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。启发式优化方法种类繁多，包括经典的模拟退火方法、遗传算法、蚁群算法以及粒子群算法等等。
 
 
 　　还有一种特殊的优化算法被称之多目标优化算法，它主要针对同时优化多个目标（两个及两个以上）的优化问题，这方面比较经典的算法有NSGAII算法、MOEA/D算法以及人工免疫算法等。
 

机器学习中常见的几种优化方法
 

 声明：本文为转载，原文作者为：Poll的笔记，原文链接为：http://www.cnblogs.com/maybe2030/p/4751804.html#rd，尊重原创
 

 
 
 
 
 
 
  
 
   
 阅读目录
 
   
 1. 梯度下降法（Gradient Descent）
 2. 牛顿法和拟牛顿法（Newton's method & Quasi-Newton Methods）
 3. 共轭梯度法（Conjugate Gradient）
 4. 启发式优化方法
  5. 解决约束优化问题——拉格朗日乘数法
 
  
 
  
　　我们每个人都会在我们的生活或者工作中遇到各种各样的最优化问题，比如每个企业和个人都要考虑的一个问题“在一定成本下，如何使利润最大化”等。最优化方法是一种数学方法，它是研究在给定约束之下如何寻求某些因素(的量)，以使某一(或某些)指标达到最优的一些学科的总称。随着学习的深入，博主越来越发现最优化方法的重要性，学习和工作中遇到的大多问题都可以建模成一种最优化模型进行求解，比如我们现在学习的机器学习算法，大部分的机器学习算法的本质都是建立优化模型，通过最优化方法对目标函数（或损失函数）进行优化，从而训练出最好的模型。常见的最优化方法有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等。
 
  

   回到顶部
   
  
 
  
 1. 梯度下降法（Gradient Descent）
 
  
　　梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。梯度下降法的搜索迭代示意图如下图所示：
 
  
 
  
　　牛顿法的缺点：
 
  
　　（1）靠近极小值时收敛速度减慢，如下图所示；
 
  
　　（2）直线搜索时可能会产生一些问题；
 
  
　　（3）可能会“之字形”地下降。
 
  
 
  
　　从上图可以看出，梯度下降法在接近最优解的区域收敛速度明显变慢，利用梯度下降法求解需要很多次的迭代。
 
  
　　在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。
 
  
　　比如对一个线性回归（Linear Logistics）模型，假设下面的h(x)是要拟合的函数，J(theta)为损失函数，theta是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数h(theta)就出来了。其中m是训练集的样本个数，n是特征的个数。
 
  
 
  
 
  
　　1）批量梯度下降法（Batch Gradient Descent，BGD）
 
  
　　（1）将J(theta)对theta求偏导，得到每个theta对应的的梯度：
 
  
 
  
　　（2）由于是要最小化风险函数，所以按每个参数theta的梯度负方向，来更新每个theta：
 
  
 
  
　　（3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度会相当的慢。所以，这就引入了另外一种方法——随机梯度下降。
 
  
　　对于批量梯度下降法，样本个数m，x为n维向量，一次迭代需要把m个样本全部带入计算，迭代一次计算量为m*n2。
 
 
  
　　2）随机梯度下降（Random Gradient Descent，RGD）
 
  
　　（1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：
 
  
 
  
　　（2）每个样本的损失函数，对theta求偏导得到对应梯度，来更新theta：
 
  
 
  
　　（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。
 
  
　　随机梯度下降每次迭代只使用一个样本，迭代一次计算量为n2，当样本个数m很大的时候，随机梯度下降迭代一次的速度要远高于批量梯度下降方法。两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。
 
 
  
　　对批量梯度下降法和随机梯度下降法的总结：
 
  
　　批量梯度下降---最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。
 
  
　　随机梯度下降---最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。
 
 
  

   回到顶部
   
  
 
  
 2. 牛顿法和拟牛顿法（Newton's method & Quasi-Newton Methods）
 
 
  
　　1）牛顿法（Newton's method）
 
  
　　牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数f (x)的泰勒级数的前面几项来寻找方程f (x) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。
 
  
 　　具体步骤：
 
  
　　首先，选择一个接近函数 f (x)零点的 x0，计算相应的 f (x0) 和切线斜率f  ' (x0)（这里f ' 表示函数 f  的导数）。然后我们计算穿过点(x0,  f  (x0)) 并且斜率为f '(x0)的直线和 x 轴的交点的x坐标，也就是求如下方程的解：
 
  
 
 
  
　　我们将新求得的点的 x 坐标命名为x1，通常x1会比x0更接近方程f  (x) = 0的解。因此我们现在可以利用x1开始下一轮迭代。迭代公式可化简为如下所示：
 
  
 
 
  
　　已经证明，如果f  ' 是连续的，并且待求的零点x是孤立的，那么在零点x周围存在一个区域，只要初始值x0位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果f  ' (x)不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。下图为一个牛顿法执行过程的例子。
 
  
 
  
　　由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：
 
  
　　牛顿法搜索动态示例图：
 
  
 
  
　　关于牛顿法和梯度下降法的效率对比：
 
  
　　从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）
 
  
　　根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
 
  
 
 
  
 注：红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。
 
  
　　牛顿法的优缺点总结：
 
  
　　优点：二阶收敛，收敛速度快；
 
  
　　缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。
 
  
　　2）拟牛顿法（Quasi-Newton Methods）
 
  
　　拟牛顿法是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。
 
  
　　拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。
 
  
　　具体步骤：
 
  
　　拟牛顿法的基本思想如下。首先构造目标函数在当前迭代xk的二次模型：
 
  
 
   

    
   
 
   　　这里Bk是一个对称正定矩阵，于是我们取这个二次模型的最优解作为搜索方向，并且得到新的迭代点：
  
 
  
 
   

    
   
 
   　　
   其中我们要求步长ak  
   
 
    满足Wolfe条件。这样的迭代与牛顿法类似，区别就在于用近似的Hesse矩阵Bk 
    
 
     代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵Bk
    
  
   
 
   
 
    
 
     
 
      的更新。现在假设得到一个新的迭代xk+1，并得到一个新的二次模型：
     
   
     

        
     
   
     

        
     
   
     

        
     
   
     

        
     
 
    
 
   
 
  
 
  
 
   

    
   
 
  
 
  

   　　我们尽可能地利用上一步的信息来选取Bk。具体地，我们要求
  
 
  
 
   

     
   
 
   

    
   
 
   　　从而得到
  
 
  

   
  
 
  

   　　这个公式被称为割线方程。
   常用的拟牛顿法有DFP算法和BFGS算法。
  
 
  

   回到顶部
   
  
 
  
 3. 共轭梯度法（Conjugate Gradient）
 
  

   　　共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。
  
 
  

   　　具体的实现步骤请参加wiki百科共轭梯度法。
  
 
  

   　　下图为共轭梯度法和梯度下降法搜索最优解的路径对比示意图：
  
 
  

   
  
 
  

    
  
 
  

   注：绿色为梯度下降法，红色代表共轭梯度法
  
 
  

   　　MATLAB代码：
  
 
  
 
   
 
    

     
    
 
    
function [x] = conjgrad(A,b,x)
    r=b-A*x;
    p=r;
    rsold=r'*r;

    for i=1:length(b)
        Ap=A*p;
        alpha=rsold/(p'*Ap);
        x=x+alpha*p;
        r=r-alpha*Ap;
        rsnew=r'*r;
        if sqrt(rsnew)<1e-10
              break;
        end
        p=r+(rsnew/rsold)*p;
        rsold=rsnew;
    end
end
 
    

     
    
 
   
 
   

    回到顶部
    
   
 
   
 4. 启发式优化方法
 
   
　　启发式方法指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案。启发式优化方法种类繁多，包括经典的模拟退火方法、遗传算法、蚁群算法以及粒子群算法等等。
 
   
　　还有一种特殊的优化算法被称之多目标优化算法，它主要针对同时优化多个目标（两个及两个以上）的优化问题，这方面比较经典的算法有NSGAII算法、MOEA/D算法以及人工免疫算法等。
 
   
　　这部分的内容会在之后的博文中进行详细总结，敬请期待。这部分内容的介绍已经在博客《[Evolutionary Algorithm] 进化算法简介》进行了概要式的介绍，有兴趣的博友可以进行参考（2015.12.13）。
 
  
 
  

   回到顶部
   
  
 
  
  5. 解决约束优化问题——拉格朗日乘数法
 
  

   　　有关拉格朗日乘数法的介绍请见我的另一篇博客：《拉格朗日乘数法》