牛顿法和拟牛顿法

@[toc]

1. 牛顿法

1.1 求解f' = 0的点，牛顿法推导

Newton method

NR法是寻找函数一阶导数为0（驻点）位置的方法。

这次为了求解f'=0的根，把f（x）的泰勒展开，展开到2阶形式：

image

这个式子是成立的，当且仅当 Δx 无线趋近于0。此时上式等价与：

image

1.2 Hessian矩阵

二阶偏导组成的矩阵, 如果有n个变量，一阶偏导为 $n \times 1$ , Hessian矩阵为 $n \times n$ 。

缺点

需要计算二阶导数
如果Hessian矩阵不是正定的话就会失效
多元函数判断是否为函数值下降方向的直观理解

1.3 阻尼牛顿法

从上面的推导中看出，牛顿方向 $−H^{−1}g$ 能使得更新后函数处于极值点，但是它不一定是极小点，也就是说牛顿方向可能是下降方向，也可能是上升方向，以至于当初始点远离极小点时，牛顿法有可能不收敛。因此提出阻尼牛顿法，在牛顿法的基础上，每次迭代除了计算更新方向（牛顿方向），还要对最优步长做一维搜索。
算法步骤
（1）给定给初始点 x(0)，允许误差 ϵ
（2）计算点 x(t)处梯度gt和Hesse矩阵H，若|gt|<ϵ则停止迭代
（3）计算点 x(t)处的牛顿方向作为搜索方向：
$d^{(t)}=-H_t^{-1}g_t \tag {1.1}$
（4）从点 x(t) 出发，沿着牛顿方向 d(t) 做一维搜索，获得最优步长：
$\lambda_t = \arg \min_{\lambda \in R} f(x^{(t)}+\lambda\cdot d^{(t)}) \tag {1.2}$
这个是在 $d^{(t)}$ 方向找使函数最小的值。
（5）更新参数：
$x^{(t+1)}=x^{(t)}+\lambda_t\cdot d^{(t)} \tag{1.3}$

阻尼牛顿法代码描述

$\delta$ 属于(0, 1), $\sigma$ 属于(0, 0.5)

在这里插入图片描述

step4: 记是满足下列不等式的最小非负整数m.

step 5: 令, 转step2

step4解释移项 $\frac {f(x_k + \sigma ^m d_k) - f(x_k)}{d_k} \leq \delta \sigma ^m g_k^T$ 即两点之间的梯度小于 $x_k$ 的梯度，证明梯度是在下降

def damp_newton(fun, gfun, hess, x0):
    # 用阻尼牛顿法求解无约束问题
    # x0是初始点，fun，gfun和hess分别是目标函数值，梯度，海森矩阵的函数
    maxk = 500  # 最大迭代次数
    sigma = 0.55  # 非线性搜索中的B因子
    delta = 0.4  # 非线性搜索中的δ因子
    k = 0  # 初始化迭代次数
    epsilon = 1e-5  # 设定迭代终止得的阈值
    x_store = [x0.copy()]

    while k < maxk:
        gk = gfun(x0)  # 计算梯度
        Gk = hess(x0)  # 计算海森矩阵
        dk = -1.0 * np.linalg.solve(Gk, gk)  # 相当于dk=-1.0*(Gk^-1)gk
        if np.linalg.norm(dk) < epsilon:
            break
        m = 0  # 初始化非线性搜索中的次数
        mk = 0  # 用于存放非线性搜索得到的最小非负整数
        while m < 20:
            if fun(x0 + sigma ** m * dk) < fun(x0) + delta * sigma ** m * np.dot(gk, dk):
                mk = m
                break
            m += 1
        x0 += sigma ** mk * dk  # 更新x的值
        k += 1  # 进入下一次循环

        x_store.append(x0.copy())
    x_store = np.array(x_store)
    return x0, x_store, k

2. 拟牛顿法

$g_t$ : 一阶偏导向量
$H_t$ : Hessian矩阵
$d_t$ : 牛顿方向
$\Delta X_t$ : X的改变量
$\Delta g_t$ : 一阶梯度的改变量

2.1 提出的初衷

牛顿法的优点是具有二阶收敛速度，缺点是：

但当海森矩阵 不正定时，不能保证所产生的方向是目标函数在处的下降方向。
特别地，当奇异时，算法就无法继续进行下去。尽管修正牛顿法可以克服这一缺陷，但修正参数的取值很难把握，过大或过小都会影响到收敛速度。
牛顿法的每一步迭代都需要目标函数的海森矩阵，对于大规模问题其计算量是惊人的。

拟牛顿法提出，用不含二阶导数的矩阵 $U_t$ 替代牛顿法中的 $H^{−1}_t$ ，然后沿搜索方向 $−U_tg_t$ 做一维搜索。根据不同的 Ut 构造方法有不同的拟牛顿法。
注意拟牛顿法的 关键词：

不用算二阶导数
不用求逆

2.2 拟牛顿条件

牛顿法的搜索方向是
$d^{(t)}=-H_t^{-1}g_t$
为了不算二阶导及其逆矩阵，设法构造一个矩阵 U，用它来逼近 $H^{−1}$

两点 x(t) 和 x(t+1) 之差是：
$x^{(t+1)}-x^{(t)} = H^{-1}\cdot [\bigtriangledown f(x^{(t+1)}) - \bigtriangledown f(x^{(t)})]$

因此要求近似矩阵U满足：
$x^{(t+1)}-x^{(t)}=U_{t+1}\cdot [\bigtriangledown f(x^{(t+1)})-\bigtriangledown f(x^{(t)})]$
即
$\Delta x_t=U_{t+1}\cdot \Delta g_t$
以上就是拟牛顿条件，不同的拟牛顿法，区别就在于如何确定 U。

2.3 DFP 法

为了方便区分，下面把U称作D（表示DFP）。

2.3.1 DFP推导

现在已知拟牛顿条件
$\Delta x_t=D_{t+1}\cdot \Delta g_t$
假设已知Dt，希望使用叠加的方法计算 $D_{t+1}$ , 即 $D_{t+1} = D_t + \Delta D_t$ ，带入得到：
$\Delta D_t \Delta g_t=\Delta x_t - D_t \Delta g_t$
现在我们来求 $\Delta D_{t}$ ，这个说起来比较tricky，主要运用了 $\Delta D$ 的对称性来分析，设参数 $q_t, w_t$ 。
$\Delta D_t=\Delta x_t \cdot q_t^T-D_t\Delta g_t\cdot w_t^T$

从形式上看，这种公式保证了 $\Delta D$ 的对称性:
首先，对照可以发现：
$q_t^T\cdot \Delta g_t=w_t^T \cdot \Delta g_t = I_n$
其次，要保证 ΔDt 是对称的，参照 ΔDt 的表达式，最简单就是令
$q_t=\alpha_t \Delta x_t\\ w_t=\beta_t D_t\Delta g_t$
第二个条件带入第一个可以得到
$\alpha_t=\frac{1}{\Delta g_t^T\Delta x_t} \\\beta_t=\frac{1}{\Delta g_t^TD_t\Delta g_t}$
带回 $\Delta D$ 的表达式：
$\Delta D_t = \frac{\Delta x_t\Delta x_t^T}{\Delta g_t^T\Delta x_t}-\frac{D_t\Delta g_t\Delta g_t^TD_t}{\Delta g_t^TD_t\Delta g_t}$

2.3.2 算法步骤

（1）给定初始点 x^(0)，允许误差 ϵ，令 $D_0 = I_n$ （n是x的维数），t=0
（2）计算搜索方向 $d^{(t)}=-D_t\cdot g_t$
（3）从点 x(t) 出发，沿着 d(t) 做一维搜索，获得最优步长并更新参数：
$\lambda_t = \arg \min_{\lambda \in R} f(x^{(t)}+\lambda\cdot d^{(t)})\\x^{(t+1)}=x^{(t)}+\lambda_t\cdot d^{(t)}$
（4）判断精度，若 $|g_{t+1}|<ϵ$ 则停止迭代，否则转（5）
（5）计算 $\Delta g=g_{t+1}-g_t, \Delta x=x^{(t+1)}-x^{(t)}$ ，更新D
$D_{t+1}=D_{t}+\frac{\Delta x\Delta x^T}{\Delta g^T\Delta x}-\frac{D_t\Delta g\Delta g^TD_t}{\Delta g^TD_t\Delta g}$
（6）t = t+1 转（2）

代码描述

step 1: 给定参数 $\delta \in (0, 1), \sigma \in (0, 0.5)$ , 终点误差 $\epsilon$ ，初始正定矩阵 $D_0$ (通常取 $I_0$ 或者 $H(X_0)^{-1}$ )，最大迭代次数maxk，令k=0.

step 2: Calculate $g_k= \bigtriangledown f(x_k)$ . if $|g_k| \leq \epsilon$ , break.

step 3: Calculate the search direction:
$d_k=-D_k\cdot g_k$

step4: $m_k$ is the smallest nonnegative integer m that satisfies the following inequality formula.
$f(x_k + \sigma ^m d_k) \leq f(x_k) + \delta \sigma ^m g_k^T d_k$
令 $\alpha_k = \sigma ^{m_k}, x_{k+1} = x_k + \alpha _k d_k, g_{k+1} = \bigtriangledown f(x_{k+1})$ .

step 5: Get the value of $D_{k+1}$ with this formula:
$D_{k+1}=D_{k}+\frac{\Delta x\Delta x^T}{\Delta g^T\Delta x}-\frac{D_k\Delta g\Delta g^TD_k}{\Delta g^TD_k\Delta g}$

参考链接

拟牛顿法（DFP、BFGS、L-BFGS）
牛顿法与拟牛顿法学习笔记
 牛顿法,拟牛顿法,DFP,BFGS,L-BFGS 原理及代码详解(2)

最后编辑于：2020.02.23 15:59:43

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,189评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,577评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,857评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,703评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,705评论 5赞 366
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,620评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,995评论 3赞 396
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,656评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,898评论 1赞 298
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,639评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,720评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,395评论 4赞 319
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,982评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,953评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,195评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,907评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,472评论 2赞 342