精华内容
下载资源
问答
  • 二分查找也称折半查找(Binary Search),它是一效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 查找过程 首先,假设表中元素是按升序排列,将表...

    二分查找

    概念

    • 二分查找也称折半查找(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);

    展开全文
  • 种常见搜索算法

    万次阅读 多人点赞 2019-06-05 22:22:03
    广度优先搜索(BFS) 深度优先搜索(DFS) 爬山法(Hill Climbing) 最佳优先算法(Best-first search strategy) 回溯法(Backtracking) 分支限界算法(Branch-and-bound Search Algorithm) A*算法 广度...

    目录

     

    广度优先搜索(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.保存路径,从终点开始,沿着父结点移动至起点,即为路径

    展开全文
  • 常见的几优化方法

    千次阅读 2016-12-12 11:27:14
    常见的几最优化方法 1. 梯度下降法(Gradient Descent)  梯度下降法是最早最简单,也是最为常用的最优化方法。梯度下降法实现简单,当目标函数是凸函数时,梯度下降法的解是全局解。一般...

    常见的几种最优化方法



    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)

      牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数(x)的泰勒级数的前面几项来寻找方程(x) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。

      具体步骤:

      首先,选择一个接近函数 (x)零点的 x0,计算相应的 (x0) 和切线斜率f  ' (x0)(这里f ' 表示函数 f  的导数)。然后我们计算穿过点(x0,  f  (x0)) 并且斜率为'(x0)的直线和 轴的交点的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算法以及人工免疫算法等。

    展开全文
  • 机器学习中常见的几优化方法

    万次阅读 2016-06-08 15:11:36
    机器学习中常见的几优化方法 声明:本文为转载,原文作者为:Poll的笔记,原文链接为:http://www.cnblogs.com/maybe2030/p/4751804.html#rd,尊重原创 阅读目录 1. 梯度下降法(Gradient ...

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

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

      我们每个人都会在我们的生活或者工作中遇到各种各样的最优化问题,比如每个企业和个人都要考虑的一个问题“在一定成本下,如何使利润最大化”等。最优化方法是一种数学方法,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。随着学习的深入,博主越来越发现最优化方法的重要性,学习和工作中遇到的大多问题都可以建模成一种最优化模型进行求解,比如我们现在学习的机器学习算法,大部分的机器学习算法的本质都是建立优化模型,通过最优化方法对目标函数(或损失函数)进行优化,从而训练出最好的模型。常见的最优化方法有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等。

    1. 梯度下降法(Gradient Descent)

      梯度下降法是最早最简单,也是最为常用的最优化方法。梯度下降法实现简单,当目标函数是凸函数时,梯度下降法的解是全局解。一般情况下,其解不保证是全局最优解,梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向,因为该方向为当前位置的最快下降方向,所以也被称为是”最速下降法“。最速下降法越接近目标值,步长越小,前进越慢。梯度下降法的搜索迭代示意图如下图所示:

      牛顿法的缺点:

      (1)靠近极小值时收敛速度减慢,如下图所示;

      (2)直线搜索时可能会产生一些问题;

      (3)可能会“之字形”地下降。

    Banana-SteepDesc.gif

      从上图可以看出,梯度下降法在接近最优解的区域收敛速度明显变慢,利用梯度下降法求解需要很多次的迭代。

      在机器学习中,基于基本的梯度下降法发展了两种梯度下降方法,分别为随机梯度下降法和批量梯度下降法。

      比如对一个线性回归(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)

      牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数(x)的泰勒级数的前面几项来寻找方程(x) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。

      具体步骤:

      首先,选择一个接近函数 (x)零点的 x0,计算相应的 (x0和切线斜率f  ' (x0)(这里f ' 表示函数 f  的导数)。然后我们计算穿过点(x0,  f  (x0)) 并且斜率为'(x0)的直线和 轴的交点的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. 解决约束优化问题——拉格朗日乘数法

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


    展开全文
  • Python爬虫突破封禁的6种常见方法

    万次阅读 多人点赞 2016-08-17 22:36:59
    最常用的方法是写一个自动化程序向网络服务器请求数据(通常是用HTML表单或其他网页文件),然后对数据进行解析,提取需要的信息。本文假定读者已经了解如何用代码来抓取一个远程的URL,并具备表单如何提交及...
  • 常见的9大数据分析方法

    万次阅读 2019-01-23 16:01:30
    数据分析是从数据中提取有价值信息的过程,过程中需要对数据进行各种处理和归类,只有掌握了正确的数据分类方法和数据处理模式,才能起到事半功倍的效果,以下是数据分析员必备的9数据分析思维模式: 1. 分类 ...
  • 搜索两种高亮显示方式

    千次阅读 2013-01-23 14:15:30
    以下提供常见两种方式处理搜索时高亮显示。目前鉴于商麦系统中大量字段没有保存。solr返回ID。所以建议采用第一种方式处理。 处理方式为通过velocity模板工具注入工具类,提供静态方法。进行解析。达到高亮显示。 ...
  • 本博客将在win10+MySQL5.7的环境下,演示一些MySQL服务的两种开启方式。 MySQL服务的开启、关闭 这一步很有必要,有时当你打开一些数据库图形操作界面,会报错说无法连接,这一般都是MySQL服务没有开启的锅。 方法一...
  • SpringMVC实现文件下载的两种方法

    万次阅读 多人点赞 2018-05-28 20:31:20
    天玩spring的过程中遇到了一个很常见的问题——文件下载。以往很多时候都是直接给一个文件的静态链接,这种方法有很多局限性,其中一个很明显的局限性就是不易统计下次状态,还有就是需要http服务器来保存文件,...
  • 常见的几最优化方法

    千次阅读 2016-12-03 13:36:30
    阅读目录 1. 梯度下降法(Gradient Descent) ...2. 牛顿法和拟牛顿法(Newton's method...4. 启发式优化方法  我们每个人都会在我们的生活或者工作中遇到各种各样的最优化问题,比如每个企业和个人都
  • 以上方法若无效则建议带到手机售后服务中心检修。 二、设备出现系统或者程序错误 打开应用程序时提示无法打开或者强行关闭,一般是程序冲突造成的 将手机恢复出厂设置(恢复出厂设置会清空手机资料,请注意...
  • 你在互联网使用搜索的时候,关键词推荐可能是你经常使用到的一个辅助工具。如各种搜索引擎搜索框的下拉提示;google 结果页会有“XXX”的“相关搜索”;... 而这些常见的关键词推荐是怎么得到的呢?我总结了一下
  • 机器学习中常见的几最优化方法

    万次阅读 2016-06-07 10:02:17
    1. 梯度下降法(Gradient Descent) ...4. 启发式优化方法  5. 解决约束优化问题——拉格朗日乘数法 我们每个人都会在我们的生活或者工作中遇到各种各样的最优化问题,比如每个企业和个人都要考虑的一个问题
  • 数据结构——图的两种遍历方法

    万次阅读 2018-12-24 15:37:19
    /* 邻接矩阵存储,从顶点v出发,对图g进行深度优先搜索*/ int j; printf("%d ",g.vexs[v]); visited[v]=1; /*标识v被访问过*/ for(j=0;j;j++); /* */ { if( g.arcs[v][j]==1&&visited[j]==0)/*j为v的邻接点,...
  • 机器学习:几种常见的学习方法

    万次阅读 2017-05-14 00:00:45
    机器学习的几种方法,在理解和实践过程中持续更新。
  • 修复SQL注入漏洞的两种方法

    千次阅读 2011-03-16 15:17:00
    之前在网上找到一个在线的网站漏洞扫描工具,叫亿思平台,是一个免费的web安全扫描平台。...下面是网上的两种解决方法,其中第二方法有自己本身测试可以的。 <br />方法1: Replace过滤字符 解决方法
  • java中调用dll文件的两种方法

    万次阅读 2014-02-11 14:30:41
    一中是用JNA方法,另外是用JNative方法两种都是转载来的, JNA地址:http://blog.csdn.net/shendl/article/details/3589676 JNative地址:http://www.jb51.net/article/35232.htm JNA方法: 介绍 给大家介绍一...
  • 想象一下,程序员没有WIFI会怎样? 程序员没有网络肯定会...字典自己加精,你的字典有强大,你能破解的WIFI就越多,提供两种方法,一般人学到一种即可。 方法一 1.环境准备 python2.7 pywifi模块 字典 ...
  • 反反爬虫,爬虫突破封禁的6种常见方法

    万次阅读 多人点赞 2017-09-12 19:26:27
    ...HTTP 定义了十几古怪的请求头类型,不过大多数都不常用。只有下面的七个字段被大多数浏览器用来初始化所有网络请求(表中信息是我自己浏览器的数据)。     经典的 Python
  • 环境变量简单的说就是当前环境下的参数或者变量。如果说的专业一点就是指在操作系统中用来指定操作系统的...在Linux系统下配置环境变量最常用的两种方法: 1、修改家目录下的 .bashrc 文件 2、修改 /etc/profile 文件
  • IAR for MSP430 关于添加自定义头文件的两种方法 上次编写关于430的程序还是在一年半前,再次使用时新版本的IAR5.31时发现又不会添加头文件了,想想当时用的时候也遇到过类似问题,最后也不知是如何解决的,在利用...
  • 常见的7排序算法

    万次阅读 多人点赞 2018-06-10 11:37:21
    则冒泡排序的具体过程可以描述为:首先从数组的第一个元素开始到数组最后一个元素为止,对数组中相邻的个元素进行比较,如果位于数组左端的元素大于数组右端的元素,则交换这个元素在数组中的位置,此时数组最...
  • 搜索引擎的查询方法

    万次阅读 2010-11-18 22:03:00
    另一类是基于Web目录的分类查询方法,虽然功能略逊于前者,但是也有自己的优势,而且这两种方法还可以结合使用。本章对此分别予以介绍,并在最后讨论一些常见的查询策略和典型案例。 1.1 基于关键词的基本查询方法 ...
  • 常见的空间索引方法

    万次阅读 多人点赞 2018-05-21 15:51:17
    在谈论空间索引之前,我们必须了解索引的概念。...所以,索引是一“前人栽树,后人乘凉”的东西。 空间索引不同于书本“目录”,“目录”对应的书本内容是不变的,而我们讨论的空间索引是根据空间数据...
  • tensorflow NAN常见原因和解决方法

    千次阅读 多人点赞 2019-02-14 13:02:01
    最近遇到NAN的问题,花了很久才真正解决。...无论正反向,数值越界基本只有两种操作会导致: a) 节点/W/gradient数值逐渐变大直至越界 b) 有除零操作,包括0/0。 二、现象 两者的现象可能一样,绝大多...
  • 文献搜索方法概述

    万次阅读 2005-10-13 18:22:00
    文献搜索方法概述 一、文献密码搜索的方法概述 文献密码搜索的方法精要总结如下: 1.google是密码搜索的利器 2.标准检索表达式:杂志名(数据库名)+password+username 3.检索表达式的变异(pw, pwd等衍生词) 4.冗余信息...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 264,989
精华内容 105,995
关键字:

常见的两种搜索方法