AI算法工程师手册-五、拟牛顿法

五、拟牛顿法

5.1 原理

  1. 在牛顿法的迭代中,需要计算海森矩阵的逆矩阵 ![五、拟牛顿法 - 图1],这一计算比较复杂。 可以考虑用一个 ![五、拟牛顿法 - 图2]。

  2. 先看海森矩阵满足的条件:![五、拟牛顿法 - 图5] 。

  3. 五、拟牛顿法 - 图6 这称为拟牛顿条件。

  4. 根据牛顿法的迭代: 五、拟牛顿法 - 图9

五、拟牛顿法 - 图1

 当 ![五、拟牛顿法 - 图13],因此每次都是沿着函数递减的方向迭代。
  1. 如果选择 ![五、拟牛顿法 - 图15] 同样要满足两个条件:

  2. 五、拟牛顿法 - 图1

  3. 五、拟牛顿法 - 图1 因为 ![五、拟牛顿法 - 图21] 开始。 按照拟牛顿条件,在每次迭代中可以选择更新矩阵 ![五、拟牛顿法 - 图23] 。

  4. 正定矩阵定义:设 ![五、拟牛顿法 - 图24]正定矩阵。 正定矩阵判定:

  5. 判定定理1:对称阵 五、拟牛顿法 - 图2

  6. 判定定理2:对称阵 五、拟牛顿法 - 图3

  7. 判定定理3:任意阵 五、拟牛顿法 - 图3 正定矩阵的性质:

  8. 正定矩阵一定是非奇异的。奇异矩阵的定义:若 五、拟牛顿法 - 图3 正定矩阵的任一主子矩阵也是正定矩阵。

  9. 五、拟牛顿法 - 图3

  10. 五、拟牛顿法 - 图4 正定矩阵在某个合同变换下可化为标准型, 即对角矩阵。 所有特征值大于零的对称矩阵也是正定矩阵。

  11. 合同矩阵:两个实对称矩阵 五、拟牛顿法 - 图4

  12. 五、拟牛顿法 - 图5 5.2 DFP 算法

  13. DFP算法( Davidon-Fletcher-Powell) 选择 ![五、拟牛顿法 - 图54] 的方法是: 假设每一步迭代中 ![五、拟牛顿法 - 图55]。 为了满足拟牛顿条件,可以取:![五、拟牛顿法 - 图60]。 这样的![五、拟牛顿法 - 图61] 不止一个。例如取 :

五、拟牛顿法 - 图6 则迭代公式为:

五、拟牛顿法 - 图6 可以证明:如果初始矩阵 ![五、拟牛顿法 - 图64] 都是正定的。

  1. DFP算法: 输入:

  2. 目标函数 五、拟牛顿法 - 图6

  3. 梯度 五、拟牛顿法 - 图6

  4. 精度要求 五、拟牛顿法 - 图6

  5. 输出: 五、拟牛顿法 - 图6 算法步骤:

  6. 选取初始值 五、拟牛顿法 - 图7 迭代,停止条件为:梯度收敛。迭代步骤为:

  7. 计算 五、拟牛顿法 - 图7

  8. 五、拟牛顿法 - 图7

  9. 五、拟牛顿法 - 图7

  10. 计算 五、拟牛顿法 - 图7

  11. 一维搜索:求 五、拟牛顿法 - 图7

  12. 设置 五、拟牛顿法 - 图8

  13. 计算 五、拟牛顿法 - 图8

  14. 否则计算 五、拟牛顿法 - 图8

  15. DFP算法中,每一次 ![五、拟牛顿法 - 图87] 决定,若跨度过大容易引发震荡。

gradient_descent_newton_dfp 5.2 BFGS 算法

  1. BFGS是最流行的拟牛顿算法。 DFP算法中,用 ![五、拟牛顿法 - 图91]。
  2. 令: ![五、拟牛顿法 - 图98] 。 可以取 ![五、拟牛顿法 - 图100] 的迭代公式:

五、拟牛顿法 - 图1 可以证明,若 ![五、拟牛顿法 - 图104] 都是正定的。

  1. BFGS算法: 输入:

  2. 目标函数 五、拟牛顿法 - 图1

  3. 梯度 五、拟牛顿法 - 图1

  4. 精度要求 五、拟牛顿法 - 图1

  5. 输出: 五、拟牛顿法 - 图1 算法步骤:

  6. 选取初始值 五、拟牛顿法 - 图1 迭代,停止条件为:梯度收敛。迭代步骤为:

  7. 计算 五、拟牛顿法 - 图1

  8. 五、拟牛顿法 - 图1

  9. 五、拟牛顿法 - 图1

  10. 五、拟牛顿法 - 图1

    这里表面上看需要对矩阵求逆。但是实际上 ![五、拟牛顿法 - 图120] 的迭代公式。

  11. 一维搜索:求 五、拟牛顿法 - 图1

  12. 设置 五、拟牛顿法 - 图1

  13. 计算 五、拟牛顿法 - 图1

  14. 否则计算 五、拟牛顿法 - 图1

  15. BFPS 算法中,每一次 ![五、拟牛顿法 - 图131] 决定,若跨度过大容易引发震荡。

gradient_descent_newton_dfp 5.3 Broyden 类算法

  1. 若记 ![五、拟牛顿法 - 图135],则对式子:

五、拟牛顿法 - 图1 使用两次Sherman-Morrison公式可得:

五、拟牛顿法 - 图1

  1. DFP 算法获得的 ![五、拟牛顿法 - 图138] 的迭代公式记作:

五、拟牛顿法 - 图1BFGS 算法获得的 ![五、拟牛顿法 - 图140] 的迭代公式记作 :

五、拟牛顿法 - 图1 他们都满足拟牛顿条件,所以他们的线性组合:![五、拟牛顿法 - 图142] 。 这样获得了一族拟牛顿法,称为 Broyden 类算法。

  1. Sherman-Morrison公式:假设 ![五、拟牛顿法 - 图144] 也是可逆矩阵,则:

五、拟牛顿法 - 图1 .

文章列表

更多推荐

更多
  • Pharo敏捷人工智能-第一部分:神经网络
    Apache CN

  • Pharo敏捷人工智能-第二部分:遗传算法
    Apache CN

  • Pharo敏捷人工智能-# 第三部分:神经进化 第三部分:神经进化
    Apache CN

  • Azure数据工程指南-二十四、数据治理的权限 创建 azure 预览帐户,探索 azure 预览,探索词汇表,浏览资产,以编程方式使用预览,摘要,管理凭证和访问,创建扫描, 许多组织需要建立数据治理流程、标准和方法,并且已经能够使用内部 SQL Server 工具(如 Master
    Apache CN

  • Azure数据工程指南-二十二、Synapse 分析工作区 创建 Synapse 分析工作区,使用 Spark 探索样本数据,用 SQL 查询数据,用 SQL 创建外部表,摘要, 微软 Azure 数据平台的众多新增功能已经围绕许多类似的产品及其在现代 Azure 数据平台中的用途产生了兴奋和困
    Apache CN

  • Azure数据工程指南-二十三、数据块中的机器学习 创建 MLflow 实验,安装 MLflow 库,创建笔记本,选择性测井,自动记录,摘要, 寻求利用机器学习(ML)和人工智能能力的组织和开发人员花费大量时间构建 ML 模型,并寻求一种方法来简化他们的机器学习开发生命周期,以跟踪实验,
    Apache CN

  • Azure数据工程指南-二十一、将 Apache Spark 的 GraphFrame API 用于图形分析 安装 JAR 库,加载新数据表,将数据加载到数据块笔记本中,用顶点和边构建一个图,查询图表,寻找有图案的图案,用 PageRank 发现重要性,探索入度和出度度量,摘要,进行广度优先搜索,查找连接的组件, 图形技术使用户能够以图形的形式
    Apache CN

  • Azure数据工程指南-20 二十、部署 SQL 数据库先决条件,创建 Visual Studio SQL 数据库项目,安装 Visual Studio GitHub 扩展,导入 AdventureWorks 数据库,连接到 GitHub Repo 源代码控制,将
    Apache CN

  • Azure数据工程指南-十九、部署数据工厂更改 先决条件,创建 DevOps 持续集成构建管道,创建 DevOps 持续部署发布渠道,验证部署的数据工厂资源,摘要,Azure PowerShell 任务停止触发器,ARM 模板部署任务,Azure PowerShell 任务启动触发器
    Apache CN

  • Azure数据工程指南-十八、用于 Cosmos DB 的 Azure Synapse 链接 创建一个 Azure Cosmos DB 帐户,启用 Azure Synapse 链接,创建一个 Cosmos DB 容器和数据库,将数据导入 Azure Cosmos DB,在 Azure Synapse Analytics 中创建
    Apache CN

  • 近期文章

    更多
    文章目录

      推荐作者

      更多