当前位置: 首页 > 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…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...