# 牛顿法

f(x)f(x)f(x)有极值的必要条件是在极值点处一阶导数为0，即梯度向量为0. 当H(x(k))H(x^{(k)})H(x(k))为正定矩阵时，f(x)f(x)f(x)的极值为极小值.

## 算法过程

1. 取初始点x(0)x^{(0)}x(0)，令k=0k=0k=0.
2. 计算gkg_kgk​.
3. 若∣∣gk∣∣&lt;ϵ||g_k||&lt;\epsilon∣∣gk​∣∣<ϵ，则停止计算，得近似解x∗=x(k)x^* = x^{(k)}x∗=x(k).
4. 计算HkH_kHk​，并求pkp_kpk​
5. x(k+1)=x(k)+pkx^{(k+1)} = x^{(k)} + p_kx(k+1)=x(k)+pk​
6. k=k+1k=k+1k=k+1，转2

# 拟牛顿法

## DFP(Davidon-Fletcher-Powell)算法

DFP选择Gk+1G_{k+1}Gk+1​的方法是，假设每一次迭代Gk+1G_{k+1}Gk+1​都是由GkG_kGk​加上两个附加项构成，我们假设这两个附加项分别为Qk、PkQ_k、P_kQk​、Pk​，则有 Gk+1=Gk+Qk+PkGk+1yk=Gkyk+Qkyk+Pkyk G_{k+1} = G_k + Q_k + P_k\\ G_{k+1}y_k = G_ky_k + Q_ky_k + P_ky_k Gk+1​=Gk​+Qk​+Pk​Gk+1​yk​=Gk​yk​+Qk​yk​+Pk​yk​

1. 选取初始点x(0)x^{(0)}x(0)，取G0G_0G0​为正定对称矩阵，令k=0k=0k=0
2. 计算gkg_kgk​，若∣∣gk∣∣&lt;ϵ||g_k||&lt;\epsilon∣∣gk​∣∣<ϵ，则停止计算，得到近似解x∗=x(k)x^* = x^{(k)}x∗=x(k)
3. 令pk=−Gkgkp_k = - G_kg_kpk​=−Gk​gk​
4. 一维搜索： 求λk\lambda_kλk​使得f(x(k)+λkpk)=min⁡λ≥0f(x(k)+λpk)f(x^{(k)} + \lambda_kp_k) = \min_{\lambda\geq 0}f(x^{(k)}+\lambda p_k)f(x(k)+λk​pk​)=minλ≥0​f(x(k)+λpk​)
5. 令x(k+1)=x(k)+λkpkx^{(k+1)} = x^{(k)} + \lambda_k p_kx(k+1)=x(k)+λk​pk​
6. 计算gk+1g_{k+1}gk+1​，若∣∣gk+1∣∣&lt;ϵ||g_{k+1}||&lt;\epsilon∣∣gk+1​∣∣<ϵ，则停止计算，得近似解x∗=x(k)x^* = x^{(k)}x∗=x(k)，否则按式(2.2)(2.2)(2.2)计算Gk+1G_{k+1}Gk+1​.
7. k=k+1k=k+1k=k+1

## BFGS(Boyden-Fletcher-Goldfarb-Shanno)算法

BFGS是最流行得拟牛顿算法.

Bk+1δk=ykB_{k+1}\delta_k = y_kBk+1​δk​=yk​ 令 Bk+1=Bk+Pk+QkBk+1δk=Bkδk+Pkδk+Qkδk B_{k+1} = B_k + P_k + Q_k\\ B_{k+1}\delta_k = B_k\delta_k + P_k\delta_k + Q_k\delta_k Bk+1​=Bk​+Pk​+Qk​Bk+1​δk​=Bk​δk​+Pk​δk​+Qk​δk​

1. 选取初始点x(0)x^{(0)}x(0)，取B0B_0B0​为正定对称矩阵，令k=0k=0k=0
2. 计算gkg_kgk​，若∣∣gk∣∣&lt;ϵ||g_k||&lt;\epsilon∣∣gk​∣∣<ϵ，则停止计算，得到近似解x∗=x(k)x^* = x^{(k)}x∗=x(k)
3. 令pk=−Bkgkp_k = - B_kg_kpk​=−Bk​gk​
4. 一维搜索： 求λk\lambda_kλk​使得f(x(k)+λkpk)=min⁡λ≥0f(x(k)+λpk)f(x^{(k)} + \lambda_kp_k) = \min_{\lambda\geq 0}f(x^{(k)}+\lambda p_k)f(x(k)+λk​pk​)=minλ≥0​f(x(k)+λpk​)
5. 令x(k+1)=x(k)+λkpkx^{(k+1)} = x^{(k)} + \lambda_k p_kx(k+1)=x(k)+λk​pk​
6. 计算gk+1g_{k+1}gk+1​，若∣∣gk+1∣∣&lt;ϵ||g_{k+1}||&lt;\epsilon∣∣gk+1​∣∣<ϵ，则停止计算，得近似解x∗=x(k)x^* = x^{(k)}x∗=x(k)，否则按式(2.3)(2.3)(2.3)计算Bk+1B_{k+1}Bk+1​.
7. k=k+1k=k+1k=k+1

## Broden类算法

Gk+1=(I−δkykTδkTyk)Gk(I−δkykTδkTyk)T+δkykTδkTyk G_{k+1} = \Big(I - \frac{\delta_ky_k^T}{\delta^T_ky_k}\Big)G_k\Big(I - \frac{\delta_ky_k^T}{\delta^T_ky_k}\Big)^T + \frac{\delta_ky_k^T}{\delta^T_ky_k} Gk+1​=(I−δkT​yk​δk​ykT​​)Gk​(I−δkT​yk​δk​ykT​​)T+δkT​yk​δk​ykT​​

# 参考文献

0 条评论

• ### 数据结构与算法 - 时间复杂度与空间复杂度

时间复杂度：时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的最大次数。 空间复杂度：类似于时间复杂度的讨论，一个算法的空间复杂度为该算法所耗费...

• ### Core官方DI解析(3)-ServiceCallSite.md

上一篇说过在整个DI框架中IServiceProviderEngine是核心,但是如果直接看IServiceProviderEngine派生类其实看不出也没什么...

• ### SSH免密远程登录的配置与实现

操作系统：CentOS Linux release 7.4.1708 (Core)

• ### 多达 95% 的 HTTPS 链接能被黑客劫持

HSTS 是一个被当前大多数 Web 浏览器所支持的 Web 安全策略，它可以帮助 Web 管理员保护他们的服务器和用户避免遭到 HTTPS 降级、中间人攻击和...

• ### 用JWT技术解决IM系统Socket长连接的身份认证痛点1、引言2、原作者3、系列文章5、完全搞懂什么是JWT技术6、我们是怎样使用JWT技术的？7、JWT技术的缺点8、点评附录：更多即时通讯方面的文

本文引用了封宇《JWT技术解决IM系统的认证痛点》一文的部分内容，即时通讯网重新整理、增补和修订，感谢原作者的无私分享。

• ### 电脑小白学习软件开发（9）-C#基础数组最大值，最小值及排序

上次说了枚举字符串以及数组的一部分知识点，其实这些东西枯燥的很。小编在以前学习的时候也是如此。虽然枯燥，但这是做所有项目的基础。今天主要讲解点数组的基础知识，这...

• ### Debian升级内核开启TCP_BBR 实现网络单边加速

自从锐速发布以来，这款牛逼的单边加速神器的确为一些线路不太优秀的服务器带来了更优秀的体验。但是呢，过高的价格和不再低端售卖。导致了我们并无法实现一个免费好用的单...

• ### React Native APP签名打包release版本APK

首先React Native开发的APP是无法通过Android Studio进行打包的，因为AS打包的APK，也是和debug版本一样，需要进行依托local...

• ### 巧用OpenSSL完成md2、md4、md5、rmd160、sha、sha1等的验证

版权声明：本文为耕耘实录原创文章，各大自媒体平台同步更新。欢迎转载，转载请注明出处，谢谢