牛顿法、拟牛顿法

2024-05-18 08:07

1. 牛顿法、拟牛顿法

根据二阶泰勒展开，用一阶和二阶倒数确定参数迭代步长和方向
  
 设初始向量  ，它在  处的泰勒展开如下：
  
   ，当  时
  
 注：矩阵求导公式：
  
      
  
 对上式相对于  求导：
  
   ①
  
 因此可以得到  处的迭代方程：
  
   
  
 对应  这种形式，步长  ，方向  
  
 从上述公式可以知道，牛顿法的每一次迭代都需要计算二阶海塞矩阵，当特征和数据非常多时，时间和空间开销都会比较大。
  
 拟牛顿法只是一种方法的统称，即用一个近似矩阵B去替代逆海塞矩阵  ，然后在每一轮迭代中更新B
  
  怎样找到逆海塞矩阵的替代矩阵？ 
  
 对上一节中的①式做一下变换：
  
   
  
 令  ,  ，上式变成：
  
   
  
 再令  ，  ，得到：
  
   ①
  
 也就是说，第k步迭代的海塞矩阵可以通过第k步的迭代步长和一阶导数差值拟合。
  
  BFGS( Broyden–Fletcher–Goldfarb–Shanno ): 
  https://blog.csdn.net/itplus/article/details/21897443
                                          
 用  表示  的近似，  表示  的近似：
  
 那么  的迭代公式为  
  
 设  ②，再根据①式得到的  :
  
   
  
 交换  和  的位置：  
  
 令：  ，以及  
  
 解出：  
  
 再带入到②中：
  
   
  
  L-BFGS: 
  
 BFGS中B矩阵的每次更新都需要nXn的空间开销，L-BFGS不会直接存储B，而是①只存取需要用到的n个向量，并且②只保存了最近的m次迭代的结果，所以L-BFGS算法又做了近似。

牛顿法、拟牛顿法

2. 拟牛顿法的介绍

拟牛顿法(Quasi-Newton Methods)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W. C. Davidon所提出来。

3. 牛顿法推导

    本文记录的目的是方便自己学习和复习，有误之处请谅解，欢迎指出。
  
     除了梯度下降法，现在介绍下牛顿法的推导。牛顿法也是通过泰勒展开推导出来的。泰勒公式如下：
                                          
     与梯度下降一样，取前两项：
                                          
     两边相等，等式两边同时求导：
                                                                                  
     当下一阶段损失最小时，  的值最小，其导数为0，即：
                                                                                  
     由于  =  ,所以参数更新公式为：
                                          
     另一种推到，保留泰勒公式前三项，化简对  求导也可计算出相同公式

牛顿法推导

4. 牛顿法问题的提出谢谢了，大神帮忙啊

牛頓法  維基百科，自由的百科全書  跳轉到:  導航 ,  搜尋   牛頓法 （ Newton's method ）又稱為 牛頓-拉夫遜方法 （ Newton- Raphson method ）， 它是一種在實數域和複數域上近似求解方程的方法。方法使用函數 f ( x )的 泰勒級數 的前面幾項來尋找方程 f ( x ) = 0 的根。        目錄  [ 隱藏 ]  1  起源 2  方法說明 3  例子 4  參見    [ 編輯 ]  起源  牛頓法最初由 艾薩克·牛頓 于 1736 年在 Method of Fluxions 中公開提出。而事實上方法此時已經由 Joseph Raphson 于 1690 年在 Analysis Aequationum 中提出，與牛頓法相關的章節 Method of Fluxions 在更早的 1671 年已經完成了。   [ 編輯 ]  方法說明  首先，選擇一個接近函數 f ( x ) 零點的 x 0 ，計算相應的 f ( x 0 ) 和切線斜率 f '( x 0 ) （這裡 f ' 表示函數 f 的 導數 ）。 然後我們計算穿過點 ( x 0 , f ( x 0 )) 並且斜率為 f '( x 0 ) 的直線和 x 軸的交點的 x 坐標，也就是求如下方程的解：   我們將新求得的點的 x 坐標命名為 x 1 ，通常 x 1 會比 x 0 更接近方 程 f ( x ) = 0 的解。因此我們現在可以利用 x 1 開始下一輪迭代。 迭代公式可化簡為如下所示：   已經證明，如果 f ' 是 連續 的，並且待求的零點 x 是孤立的， 那麼在零點 x 周圍存在一個區域，只要初始值 x 0 位於這個鄰近區域 內，那麼牛頓法必定收斂。 並且, 如果 f '( x ) 不為0, 那麼牛頓法將具有平方收斂的性能. 粗略的說, 這意味著每迭代一次, 牛頓法結果的有效數字將增加一倍。 下圖為一個牛頓法執行過程的例子。   [ 編輯 ]  例子  求方程 f ( x ) = cos( x )   x 3 的根。兩邊求導，得 f '( x ) = sin( x )  3 x 2 。由於cos( x )≤ 1（對於所有 x ），以及 x 3 > 1（對於 x >1），可知方程的根位於0和1之間。我們從 x 0 = 0.5開始。

满意请采纳