当前位置: 首页 > news >正文

「最优化基础知识2」一维搜索,以及python代码

最优化基础知识(2)

无约束优化问题,一维搜索

一、一维搜索

一维搜索的意思是在一个方向上找到最小点。

用数学语言描述,X*=Xk +tPk,从Xk沿着Pk方向行走t到达最小点X*

1、收敛速度:

请添加图片描述

  1. 线性收敛:p=1,0<beta<1
  2. 超线性收敛: p>1或者beta=0
  3. 次线性收敛:p=1,beta=1
  4. p阶收敛:p>1
2、二次终止性:

能够在有限步内找到具有正定矩阵的二次函数的极小点。

f (X) = 1/2 XTAX + bTX + c

3、终止准则

什么时候停机,什么时候停止搜索。通常有以下五种:

请添加图片描述

1、黄金分割法

给定每次迭代区间缩小比例,如果做才能搜索次数最少?

黄金分割法的python代码:

import mathdef golden_section_search(f, a, b, tol=1e-6):golden_ratio = (math.sqrt(5) - 1) / 2length = b - ax1 = a + (1 - golden_ratio) * lengthx2 = a + golden_ratio * lengthwhile x2-x1>tol:print(x1,x2)if f(x1) < f(x2):b = x2x2 = x1x1 = a + (1 - golden_ratio) * (b - a)else:a = x1x1 = x2x2 = a + golden_ratio * (b - a)return (a + b) / 2# 示例用法
def f(x):# 定义函数 f(x)return x*math.log(x)# 在区间 [0, 5] 中寻找函数的极小值点
result = golden_section_search(f, 0, 5)
print(f"极小值点的位置为: {result}")
print(f"函数极小值为: {f(result)}")

2、fibonacci搜索

给定迭代次数,如何在迭代次数内达到最好的搜索效果(最后一次迭代完成,搜索区间最小)?

这个问题可以反过来理解,假设最后一次迭代完成,搜索区间长度为1,那么最开始的搜索区间最大为多少?

python代码:

import mathdef fibonacci_search(f, a, b, n):# 计算Fibonacci数列fibonacci = [0, 1]for i in range(n):fibonacci.append(fibonacci[-1] + fibonacci[-2])# 计算初始区间长度length = b - a# 计算初始比例ratio = (fibonacci[-3] / fibonacci[-1]) if len(fibonacci) > 2 else 0# 初始化区间端点x1 = a + ratio * lengthx2 = a + (1 - ratio) * length# 迭代搜索for _ in range(len(fibonacci) - 3):if f(x1) < f(x2):b = x2x2 = x1x1 = a + ratio * (b - a)else:a = x1x1 = x2x2 = a + (1 - ratio) * (b - a)fibonacci.pop()ratio = (fibonacci[-3] / fibonacci[-1])print(fibonacci[-3],fibonacci[-1],ration)# 返回最优解的位置return (a + b) / 2# 示例用法
def f(x):# 定义函数 f(x)return x*math.log(x)# 在区间 [-5, 5] 中寻找函数的极小值点
result = fibonacci_search(f, 0, 5, 30)
print(f"极小值点的位置为: {result}")
print(f"函数极小值为: {f(result)}")

在有的地方,直接给出的不是迭代次数,而是最终的区间长度的上界L,b1-a1是初始区间。
b n − a n = F n − 1 / F n ( b n − 1 − a n − 1 ) = F n − 1 F n F n − 2 F n − 1 ⋯ F 1 F 2 ( b 1 − a 1 ) b_n-a_n=F_{n-1}/F_{n}(b_{n-1}-a_{n-1}) = \frac{F_{n-1}}{F_{n}}\frac{F_{n-2}}{F_{n-1}}\cdots\frac{F_{1}}{F_{2}}(b_1-a_1) bnan=Fn1/Fn(bn1an1)=FnFn1Fn1Fn2F2F1(b1a1)
也就是说区间长度最小bn-an=(b1-a1)/F_n<=L,F_n是最大的fibonacci数。

关键:F[n-2]+F[n-1]=F[n],F[n-2]/F[n]+F[n-1]/F[n]=1,这样能保证每次删掉一侧的区间,比例是一样的。

当F[6]/F[7]=21/34=0.6176470588235294,和黄金分割法近似相同。

黄金分割法是fibonacci法的极限形式。

3、三点二次插值法

请添加图片描述

4、两点三次插值法

请添加图片描述

5、牛顿法

牛顿法就是在极小点附近选择一个初始点x0,在x0处二阶泰勒展开,并求其驻点。牛顿法不具有全局收敛性,因此初始点的选择很重要,它只是向初始点附近的驻点靠近。

请添加图片描述

牛顿法的python代码:

import sympy as sp
def newton_method(f, x0, tol=1e-6, max_iter=100):f_d1 = f.diff()f_d2 = f_d1.diff()# 迭代搜索for _ in range(max_iter):# 计算导数值fx = f_d1.subs({x:x0})fxx = f_d2.subs({x:x0})# 更新搜索位置x1 = x0 - fx / fxx# 检查是否满足终止条件if abs(x1 - x0) < tol:break# 更新当前点x0 = x1# 返回搜索结果return x1# 示例用法
x = sp.Symbol('x')
f=x**3-4*x+5# 选择初始点
x0 = -10# 使用牛顿法搜索函数的极小值点
result = newton_method(f, x0)
print(f"极小值点的位置为: {result.n()}")
print(f"函数极小值为: {f.subs({x:result}).n()}")

二、非精确一维搜索

1、Goldstein准则

请添加图片描述

2、Wolfe准则

请添加图片描述

3、Armijo准则

请添加图片描述

相关文章:

「最优化基础知识2」一维搜索,以及python代码

最优化基础知识&#xff08;2&#xff09; 无约束优化问题&#xff0c;一维搜索 一、一维搜索 一维搜索的意思是在一个方向上找到最小点。 用数学语言描述&#xff0c;X*Xk tPk&#xff0c;从Xk沿着Pk方向行走t到达最小点X*。 1、收敛速度&#xff1a; 线性收敛&#xff1…...

工厂模式之抽象工厂模式(常用)

抽象工厂模式 工厂方法模式中考虑的是一类产品的生产&#xff0c;如畜牧场只养动物、电视机厂只生产电视机、计算机软件学院只培养计算机软件专业的学生等。 同种类称为同等级&#xff0c;也就是说&#xff1a;工厂方法模式中只考虑生产同等级的产品&#xff0c;但是在现实生…...

Apache服务Rwrite功能使用

Rewrite也称为规则重写&#xff0c;主要功能是实现浏览器访问时&#xff0c;URL的跳转。其正则表达式是基于Perl语言。要使用rewrite功能&#xff0c;Apache服务器需要添加rewrite模块。如果使用源码编译安装&#xff0c;–enable-rewrite。有了rewrite模块后&#xff0c;需要在…...

【一起来学kubernetes】6、kubernetes基本概念区分

前言 前一篇文章我们对k8s中的一些常见概念进行了一个梳理&#xff0c;接下来我们将常见一些概念的区别和联系进行一个理解 service和deployment的区别和联系 在Kubernetes中&#xff0c;Service和Deployment是两个不同的概念&#xff0c;它们之间存在一定的关联。 Deployme…...

Python基础入门例程66-NP66 增加元组的长度(元组)

最近的博文: Python基础入门例程65-NP65 名单中出现过的人(元组)-CSDN博客 Python基础入门例程64-NP64 输出前三同学的成绩(元组)-CSDN博客 Python基础入门例程63-NP63 修改报名名单(元组)-CSDN博客 目录 最近的博文: 描述...

ubuntu22.04 安装 jupyterlab

JupyterLab Install JupyterLab with pip: pip install jupyterlabNote: If you install JupyterLab with conda or mamba, we recommend using the conda-forge channel. Once installed, launch JupyterLab with: jupyter lab...

探索移动端可能性:Capacitor5.5.1和vue2在Android studio中精细融合

介绍&#xff1a; 移动应用开发是日益复杂的任务&#xff0c;本文将带领您深入探索如何无缝集成Capacitor5.5.1、Vue2和Android Studio&#xff0c;以加速您的开发流程Capacitor 是一个用于构建跨平台移动应用程序的开源框架。Vue 是一个流行的 JavaScript 框架&#xff0c;用…...

【深度学习】Python快捷调用InsightFace人脸检测,纯ONNX推理

pypi资料&#xff1a; https://pypi.org/project/insightface/ 模型选择&#xff1a; https://github.com/deepinsight/insightface/tree/master/python-package#model-zoo onnxruntime的GPU对应CUDA &#xff1a; https://onnxruntime.ai/docs/reference/compatibility …...

JAVA序列化和反序列化

JAVA序列化和反序列化 文章目录 JAVA序列化和反序列化序列化什么是序列化&#xff1f;为什么要进行序列化?如何将对线进行序列化具体实现过程 完整代码 序列化 什么是序列化&#xff1f; 就是将对象转化为字节的过程 为什么要进行序列化? 让数据更高效的传输让数据更好的…...

基于浣熊算法优化概率神经网络PNN的分类预测 - 附代码

基于浣熊算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于浣熊算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于浣熊优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针对PNN神经网络的光滑…...

uni-app打包后,打开软件时使其横屏显示

找到page.json文件&#xff0c;在global加入以下代码&#xff1a; 这样就可以横屏显示了。...

MYSQL基础知识之【创建,删除,选择数据库】

文章目录 前言MySQL 创建数据库使用 mysqladmin 创建数据库使用 PHP脚本 创建数据库 MySQL 删除数据库使用 mysqladmin 删除数据库使用PHP脚本删除数据库 MySQL 选择数据库从命令提示窗口中选择MySQL数据库使用PHP脚本选择MySQL数据库 后言 前言 hello world欢迎来到前端的新世…...

关于 token 和证书

关于 token 和证书 在网络检测中&#xff0c;Token通常是指一种特殊的令牌&#xff0c;用于在分布式系统中进行资源控制和访问管理。Token可以用于验证客户端的身份、限制客户端的访问权限以及控制客户端对某些资源的使用。 在网络检测中&#xff0c;Token通常用于以下几个方…...

基于SSM和微信小程序的场地预约网站

文章目录 项目介绍主要功能截图:部分代码展示设计总结项目获取方式🍅 作者主页:超级无敌暴龙战士塔塔开 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 🍅文末获取源码联系🍅 项目介绍 基于SSM和微信小程序的场地预约网站,jav…...

Javascript每天一道算法题(十七)——缺失的第一个正整数_困难

文章目录 前言1、问题2、示例3、解决方法&#xff08;1&#xff09;方法1 总结 前言 提示&#xff1a; 1、问题 给你一个未排序的整数数组 nums &#xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 看了很久…...

【React】路径别名配置

路径解析配置&#xff08;webpack&#xff09;&#xff0c;把 / 解析为 src/路径联想配置&#xff08;VsCode&#xff09;&#xff0c;VSCode 在输入 / 时&#xff0c;自动联想出来对应的 src/下的子级目录 1. 路径解析配置 安装craco npm i -D craco/craco项目根目录下创建配…...

前缀和——238. 除自身以外数组的乘积

文章目录 &#x1f377;1. 题目&#x1f378;2. 算法原理&#x1f365;解法一&#xff1a;暴力求解&#x1f365;解法二&#xff1a;前缀和&#xff08;积&#xff09; &#x1f379;3. 代码实现 &#x1f377;1. 题目 题目链接&#xff1a;238. 除自身以外数组的乘积 - 力扣&a…...

MySql数据库常用指令(二)

MySql数据库常用指令&#xff08;二&#xff09; 一、WHERE 子句二、UPDATE 更新三、DELETE 语句四、LIKE 子句五、UNION 操作符 注&#xff1a;文中TEST为测试所用数据库&#xff0c;根据实际应用修改 一、WHERE 子句 SELECT 语句使用 WHERE 子句从数据表中读取数据&#xf…...

zookeeper 单机伪集群搭建简单记录

1、官方下载加压后&#xff0c;根目录下新建data和log目录&#xff0c;然后分别拷贝两份&#xff0c;分别放到D盘&#xff0c;E盘&#xff0c;F盘 2、data目录下面新建myid文件&#xff0c;文件内容分别为1&#xff0c;2&#xff0c;3.注意文件没有后缀&#xff0c;不能是txt文…...

【Linux】匿名管道与命名管道,进程池的简易实现

文章目录 前言一、匿名管道1.管道原理2.管道的四种情况3.管道的特点 二、命名管道1. 特点2.创建命名管道1.在命令行上2.在程序中 3.一个程序执行打开管道并不会真正打卡 三、进程池简易实现1.makefile2.Task.hpp3.ProcessPool.cpp 前言 一、匿名管道 #include <unistd.h&g…...

浏览器书签管理的革命性解决方案:Neat Bookmarks树状扩展深度解析

浏览器书签管理的革命性解决方案&#xff1a;Neat Bookmarks树状扩展深度解析 【免费下载链接】neat-bookmarks A neat bookmarks tree popup extension for Chrome [DISCONTINUED] 项目地址: https://gitcode.com/gh_mirrors/ne/neat-bookmarks 你是否曾在数百个杂乱书…...

Argo CD 实战:从零构建你的第一个 GitOps 应用

1. 为什么你需要Argo CD&#xff1f; 如果你正在管理Kubernetes应用&#xff0c;肯定遇到过这样的场景&#xff1a;每次代码变更后&#xff0c;都要手动执行kubectl apply来更新集群状态。这种操作不仅容易出错&#xff0c;还很难追踪谁在什么时候改了什么东西。我在实际项目中…...

7个秘诀快速掌握RPFM:全面战争模组编辑器的终极指南

7个秘诀快速掌握RPFM&#xff1a;全面战争模组编辑器的终极指南 【免费下载链接】rpfm Rusted PackFile Manager (RPFM) is a... reimplementation in Rust and Qt5 of PackFile Manager (PFM), one of the best modding tools for Total War Games. 项目地址: https://gitco…...

如何用code2prompt解决代码与AI协作的上下文难题

如何用code2prompt解决代码与AI协作的上下文难题 【免费下载链接】code2prompt A CLI tool to convert your codebase into a single LLM prompt with source tree, prompt templating, and token counting. 项目地址: https://gitcode.com/GitHub_Trending/co/code2prompt …...

PyTorch实战:nn.AvgPool2d参数详解与避坑指南(从padding到divisor_override)

PyTorch实战&#xff1a;nn.AvgPool2d参数详解与避坑指南 在深度学习模型的构建过程中&#xff0c;池化层扮演着至关重要的角色。作为特征降维和位置不变性的关键组件&#xff0c;二维平均池化&#xff08;AvgPool2d&#xff09;因其平滑特性和对噪声的鲁棒性&#xff0c;在图像…...

VCS仿真中用好断言debug选项,让你的验证效率翻倍(附避坑指南)

VCS仿真中高效断言调试的进阶技巧与实战指南 在复杂SoC验证环境中&#xff0c;断言&#xff08;Assertion&#xff09;作为设计意图的"活文档"&#xff0c;其调试效率直接影响项目周期。本文将从VCS仿真器的编译选项配置、断言控制文件编写技巧、波形分析策略三个维度…...

达芬奇剪辑效率翻倍秘籍:深入解读F9到F11(插入、覆盖、替换)的区别与实战应用场景

达芬奇剪辑效率翻倍秘籍&#xff1a;深入解读F9到F11&#xff08;插入、覆盖、替换&#xff09;的区别与实战应用场景 在专业视频剪辑领域&#xff0c;DaVinci Resolve凭借其强大的功能和流畅的工作流程&#xff0c;已成为众多剪辑师的首选工具。然而&#xff0c;许多中级用户在…...

别再死记硬背了!用C#手写一个位运算模拟器,彻底搞懂与、或、非、异或

从零构建C#位运算模拟器&#xff1a;用二进制视角彻底理解与、或、非、异或 当你第一次在代码中看到x & y或~z这样的表达式时&#xff0c;是否曾好奇计算机究竟在底层做了什么&#xff1f;位运算作为编程语言中最接近硬件的操作之一&#xff0c;理解它的本质能让你写出更高…...

Parsec VDD:Windows虚拟显示器终极解决方案,免费扩展你的数字工作空间

Parsec VDD&#xff1a;Windows虚拟显示器终极解决方案&#xff0c;免费扩展你的数字工作空间 【免费下载链接】parsec-vdd ✨ Perfect virtual display for game streaming 项目地址: https://gitcode.com/gh_mirrors/pa/parsec-vdd 在当今多任务处理日益普及的数字时代…...

用CH9329做个扫码枪?手把手教你串口转USB HID的完整开发流程(附代码)

用CH9329打造低成本扫码枪&#xff1a;从硬件连接到键码映射的全流程解析 在零售仓储、图书馆管理等场景中&#xff0c;扫码枪作为高效的数据录入工具早已普及&#xff0c;但商用设备动辄上千元的售价让个人开发者和小型项目望而却步。其实借助CH9329这款国产串口转USB HID芯片…...