程序员经验分享-hwhale

【下降算法】最速下降法、Newton法、共轭梯度法

2023-11-19

1. 一维搜索

最优化问题一般选择某一组变量，然后在满足一定的限制条件下，求出使目标值达到最优（最大或最小）的变量值。大部分时候，最优化问题都采用迭代计算的方式来求解。而大多数迭代下降算法都具有的共同点是在得到某次迭代点 x k x^k xk后，需要按照一定规则来确定一个方向 d k d^k dk，沿着该方向在直线上求函数的极小点得到下一个迭代点 x x xk+1 。
这样不断在一维的目标函数上，求其在各迭代点的直线方向上的极小点，直到求出问题最优解的方式就被称为一维搜索，或者线搜索。其一般过程可用如下公式表示：
在这里插入图片描述

其中 d k d^k dk 表示在这一步的搜索方向，步长因子 λ λ λ 决定了沿着该方向前进多远，这两者共同决定了该搜索算法的好坏。一维搜索的算法有好多种，以下介绍几种常见的。

2. 最速下降法

上文中的一维搜索（ x x xk+1 = x k x^k xk + λ d k λd^k λdk）可归结为单变量函数的最优化问题，也是最速下降法的基础。其迭代过程中最重要的就是为下次迭代选择一个合适的方向 d k d^k dk。
人们利用了梯度方向是函数值增长最快的方向的思想，来让迭代点沿着负梯度方向前进，保证函数的“最速”下降。
以下直接给出公式：
在这里插入图片描述
在最速下降法中，步长 λ λ λ 由式子求出，是一种精确步长的搜索方式。其与梯度下降法的区别也在于此，梯度下降中的步长往往是由工程师自己预先设置好的一个固定值，因此梯度下降法只是最速下降法中的一种特殊形式。
在这里插入图片描述
补充：梯度下降法容易陷入局部极小值（如下图所示）。
在这里插入图片描述

形象点地说，假设有一小球要从山顶滚到山脚，那么每次沿最陡峭（梯度）的方向向下滚是最快的。
在确定了每次下降的方向的同时也需要小心地选择一个合适的步长。若是过大，可能导致迭代点发散，过小则导致收敛太慢。

最速下降法在极小化目标函数时的相邻两个搜索方向是正交的。
在这里插入图片描述
【例】利用最速下降法求 m i n f ( x ) = x 1 2 + 2 x 2 2 − 2 x 1 x 2 − 4 x 1 minf(x) = x_1^2 + 2x_2^2 - 2x_1x_2 - 4x_1 minf(x)=x12​+2x22​−2x1​x2​−4x1​ ，取初始向量 x 0 = ( 1 , 1 ) T x_0 = (1,1)^T x0​=(1,1)T。
在这里插入图片描述
在这里插入图片描述

最速下降法特征

相邻两次迭代的方向互相垂直。
在这里插入图片描述

  • 最速下降法在两个相邻点之间的搜索方向是正交的。
  • 最速下降法向极小点逼近是曲折前进的，这种现象称为锯齿现象，锯齿现象会影响收敛速度！
    在这里插入图片描述
    缺点：最速下降法收敛速度慢！
  • 在最速下降法中，利用精确一维搜索求最佳步长，使得相邻两次迭代的搜索方向总是垂直的，使得逼近极小点过程是“之”字形。
    在这里插入图片描述
    这样从任何一个初始点开始，都可以很快达到极小点附近，但是越靠近极小点步长越小，移动越慢，导致最速下降法的收敛速度很慢。实际运用中，在可行的计算时间内可能得不到需要的结果。
最速下降法的优缺点
  • 优点：理论明确，程序简单，每次的计算量小，所需的存储量小，对初始点要求不合格。
  • 缺点：收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。

【补充】一些有效算法是通过对它的改进或利用它与其他收敛快的算法结合而得到的，因此它是无约束优化的方法之一。在计算的前中期使用梯度下降，而在接近极小点时使用其他算法进行迭代会是更理想的方案。

3. Newton法

此处介绍的牛顿法是其在一维搜索中的推广形式。与最速下降法一样可用于求解一般无约束的多元优化问题。其基本思想还是采用泰勒二阶展开来拟合极小点附近的函数来进行迭代：
在这里插入图片描述

算法基本思想

考虑从 x k x^k xk 到 x x x k+1 的迭代过程，在 x k x^k xk 点处对函数 f ( x ) f(x) f(x) 泰勒展开：
在这里插入图片描述
略去高阶项，得到
在这里插入图片描述
对 f ( x ) f(x) f(x) 求梯度得（第三项求导后是高阶可以省略）：
在这里插入图片描述
移项得：
在这里插入图片描述
两边同时乘二阶导数项的逆矩阵，然后移项可得极小点：
在这里插入图片描述
Newton法的计算步骤如下：
在这里插入图片描述
【例】用Newton方法求 f ( x 1 , x 2 ) = x 1 2 + 25 x 2 2 f(x_1,x_2) = x_1^2 + 25x_2^2 f(x1​,x2​)=x12​+25x22​ 的极小点。
在这里插入图片描述
由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：

在这里插入图片描述

牛顿法和梯度下降法的效率对比

从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。
如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）
根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
在这里插入图片描述
图中红色的是牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。

4. 共轭梯度法

共轭梯度法是基于共轭方向的一种算法。针对目标函数为二次函数的问题，其搜索方向是与二次函数系数矩阵相关的共轭方向。 用这类方法求解n元二次正定函数的极小问题，最多进行n次一维搜索。
在这里插入图片描述
几何意义：
假设 f ( x ) f(x) f(x) 是 n n n 元正定二次函数：
在这里插入图片描述
对于二维情况 n = 2 n=2 n=2，任任取初始点 x 0 x^0 x0 沿某个下降方向 d 0 d^0 d0 作精确一维搜索，得 x 1 = x 0 + l a m d a 0 d 0 x^1 = x^0 + lamda_0d^0 x1=x0+lamda0​d0 。
由精确一维搜索的性质，可知：
在这里插入图片描述
在这里插入图片描述
这里参考了西北工业大学的PPT：最优化方法第二章：线搜索算法

【参考资料】CSDN博客：@https://blog.csdn.net/zxxxxxxy/article/details/103850557

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Machine Learning

算法

机器学习

人工智能

【下降算法】最速下降法、Newton法、共轭梯度法 的相关文章

随机推荐

  • python request第三方库介绍

    python request第三方库介绍 快速上手 迫不及待了吗 本页内容为如何入门Requests提供了很好的指引 其假设你已经安装了Requests 如果还没有 去 安装 一节看看吧 首先 确认一下 Requests 已安装 Reque

  • mybatis查询mysql时间格式化 DATE_FORMAT

    在数据库中对应的是DateTime 查询参数为String类型 缺少时分秒的情况下使用 select from order where isDelete 0

  • 笔记 —— ByteArrayOutputStream

    内存输出流 ByteArrayOutputStream 此类实现了一个输出流 其中的数据被写入一个 byte 数组 缓冲区会随着数据的不断写入而自动增长 可使用 toByteArray 和 toString 获取数据 两个构造函数 1 By

  • Linux系统编程makefile制作动态库和静态库

    目录 制作动态库 制作静态库 首先准备简单的add c sub c main c head h 具体代码如下 head h文件 int Add int a int b int Sub int a int b add c文件 include

  • 山洪灾害监测预警系统解决方案

    一 方案概述 山洪灾害是指山丘地区由降雨引起的洪水 泥石流和滑坡灾害 近年来 我国突发性 局部性极端强降雨引发的山洪灾害导致大量人员伤亡 占洪涝灾害死亡总人数的比例趋上升趋势 群死群伤事件时有发生 山洪灾害严重制约山区和丘陵地区经济发展 人

  • SVM支持向量机学习——使用MATLAB实现基于SVM的数据二分类

    SVM支持向量机学习 使用MATLAB实现基于SVM的数据二分类 支持向量机 Support Vector Machine SVM 是一种广泛应用于分类 回归和异常检测等领域的算法 它的优点在于具有较高的准确性 鲁棒性和可扩展性 在本文中

  • Hyper-v 虚拟机挂载物理硬盘的方法-Windows Server 2022/2025

    起因 之前我写过一篇介绍在KVM虚拟机体系下 如何直接挂载物理硬盘和物理分区的方法 KVM虚拟机直接挂栽物理硬盘分区的方法 给libvirt虚机挂载磁盘 lggirls的博客 CSDN博客 近期帮助一个朋友搭建局域网 其中有OA系统要用到w

  • Get to know yosys & yosys-abc

    In this blog I m going to give some instructions about yosys yosys abc in Linux Environment yosys 0 7 gcc 5 4 0 ubuntu 1

  • verilog 基本语法 ｛｝大括号的使用

    的基本使用是两个 一个是拼接 一个是复制 下面列举了几种常见用法 基本用法 表示拼接 第一位 第二位 表示复制 4 a 等同于 a a a a 所以 13 1 b1 就表示将13个1拼接起来 即13 b1111111111111 拼接语法详

  • 学习总结——按下按键灯亮，再次按下按键，灯灭

    按键控制灯的亮灭 1 主要实现按键控制灯的亮灭 按键按下 灯亮 再次按下 灯灭 主要对实现的逻辑进行控制 逻辑清晰 很简单 实现的方法有两种 方法1 将按键按下的值赋值给一个变量 变量除以2的值的是基数或者偶数来确定灯亮还是灯灭 程序中设置

  • 堆栈 对比

    https www cnblogs com guoxiaoyan p 8664150 html

  • STL — Set/Multiset容器

    1 1 Set容器基本概念 Set的特性是 所有元素都会根据元素的键值自动被排序 Set的元素不像map那样可以同时拥有实值和键值 set的元素即是键值又是实值 set不允许两个元素有相同的键值 我们可以通过set的迭代器改变set元素的值

  • POI解析word\pdf中表格

  • Windows10下SlowFast环境安装和运行

    SlowFast安装详解 第一步 下载官方源码 第二步 我搭建的环境配置 第二步 安装其他包以及出现的问题 第三步 构建SlowFast 第四部 下载权重和标签 第五步 更改参数 第六步 当然是运行啦 第一步 下载官方源码 github代码

  • Retrofit2.0使用详解

    简介 Retrofit是由Square公司提供的开源产品 为Android平台的应用提供一个类型安全的REST客户端 其实质上是对OkHttp的封装 使用面向接口的方式进行网络请求 利用动态生成的代理类封装了网络接口请求的底层 将REST

  • Windows程序员必须掌握的计算机编码问题——海明码（通俗易懂）

    我是荔园微风 作为一名在IT界整整25年的老兵 今天总结一下计算机中的编码问题 来看第二部分 海明码 很多初学者一看到海明码就郁闷 因为课本上关于海明码的描述实在是太难懂了 那就跟随我一起来搞懂海明码 我用最简单最好懂的方式描述 我不会使用

  • 基于STM32F4单片机对步进电机的控制（有代码）

    步进电机简介 步进电机是将电脉冲控制信号转变为角位移或线位移的一种常用的数字控制执行元件 又称为脉冲电机 在驱动电源的作用下 步进电机受到脉冲的控制 其转子的角位移量和速度严格地与输入脉冲的数量和脉冲频率成正比 步进电机每接收一个电脉冲 转

  • R语言 write.xlsx() 写入同一excel，及同一sheet注意

    write xlsx x file sheetName Sheet1 col names TRUE row names TRUE append FALSE showNA TRUE 1 想要将data1写da xlsx的sheet1 data

  • spring boot 配合element ui vue实现表格的批量删除（前后端详细教学，简单易懂，有手就行）

    目录 一 前言 二 前端代码 2 1 element ui组件代码 2 2删除按钮 2 3 data 2 4 methods 三 后端代码 一 前言 研究了其他人的博客 找到了一篇有含金量的 进行了部分改写实现前后端分离 参考博主为小白Ra

  • 【下降算法】最速下降法、Newton法、共轭梯度法

    文章目录 1 一维搜索 2 最速下降法 最速下降法特征 最速下降法的优缺点 3 Newton法 算法基本思想 牛顿法和梯度下降法的效率对比 4 共轭梯度法 1 一维搜索 最优化问题一般选择某一组变量 然后在满足一定的限制条件下 求出使目标值

热门标签