2024国赛数学建模备赛|30种常用的算法模型之最优算法-非线性规划

 1.1   非线性规划的实例与定义

如果目标函数或约束条件中包含非线性函数,就称这种规划问题为非线性规划问题。一般说来,解非线性规划要比解线性规划问题困难得多。而且,也不象线性规划有 单纯形法这一通用方法,非线性规划目前还没有适于各种问题的一般算法,各个方法都 有自己特定的适用范围。

下面通过实例归纳出非线性规划数学模型的一般形式,介绍有关非线性规划的基本 概念。

最佳投资方案应是投资额最小而总收益最大的方案,所以这个最佳投资决策问题归 结为总资金以及决策变量(取 0 或 1)的限制条件下,极大化总收益和总投资之比。因 此,其数学模型为: 

 上面例题是在一组等式或不等式的约束下,求一个函数的最大值(或最小值)问 题,其中至少有一个非线性函数,这类问题称之为非线性规划问题。可概括为一般形式:

 

 对于一个实际问题,在把它归结成非线性规划问题时,一般要注意如下几点: (i)确定供选方案:首先要收集同问题有关的资料和数据,在全面熟悉问题的基 础上,确认什么是问题的可供选择的方案,并用一组变量来表示它们。 (ii)提出追求目标:经过资料分析,根据实际需要和可能,提出要追求极小化 或极大化的目标。并且,运用各种科学和技术原理,把它表示成数学关系式。 (iii)给出价值标准:在提出要追求的目标之后,要确立所考虑目标的“好”或 “坏”的价值标准,并用某种数量形式来描述它。 (iv)寻求限制条件:由于所追求的目标一般都要在一定的条件下取得极小化或 极大化效果,因此还需要寻找出问题的所有限制条件,这些条件通常用变量之间的一些 不等式或等式来表示。

1.2 线性规划与非线性规划的区别

如果线性规划的最优解存在,其最优解只能在其可行域的边界上达到(特别是可行 域的顶点上达到);而非线性规划的最优解(如果最优解存在)则可能在其可行域的任 意一点达到。

1.3 非线性规划的 Matlab 解法

Matlab 中非线性规划的数学模型写成以下形式

 Matlab 中的命令是

X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS) 

1.4 求解非线性规划的基本迭代格式

由于线性规划的目标函数为线性函数,可行域为凸集,因而求出的最优解就是整 个可行域上的全局最优解。非线性规划却不然,有时求出的某个解虽是一部分可行域上 的极值点,但却并不一定是整个可行域上的全局最优解。

 1.5 凸函数、凸规划

 可以证明,凸规划的可行域为凸集,其局部最优解即为全局最优解,而且其最优 解的集合形成一个凸集。当凸规划的目标函数 f (x)为严格凸函数时,其最优解必定唯 一(假定最优解存在)。由此可见,凸规划是一类比较简单而又具有重要理论意义的非线性规划

2.1 一维搜索方法

 当用迭代法求函数的极小点时,常常用到一维搜索,即沿某一已知方向求目标函数 的极小点。一维搜索的方法很多,常用的有:(1)试探法(“成功—失败”,斐波那契法, 0.618 法等);(2)插值法(抛物线插值法,三次插值法等);(3)微积分中的求根法(切 线法,二分法等)。 考虑一维极小化问题

若 f (t) 是[a,b] 区间上的下单峰函数,我们介绍通过不断地缩短[a,b] 的长度,来 搜索得(2)的近似最优解的两个方法。

2.1.1 Fibonacci 法

如用 Fn 表示计算n 个函数值能缩短为单位长区间的最大原区间长度,可推出 Fn 满 足关系

如果要求经过一系列探索点搜索之后,使最后的探索点和最优解之间的距离不超 过精度δ > 0 ,这就要求最后区间的长度不超过δ ,即

据此,我们应按照预先给定的精度δ ,确定使(4)成立的最小整数n 作为搜索次数, 直到进行到第n 个探索点时停止。

用上述不断缩短函数 f (t) 的单峰区间[a,b] 的办法,来求得问题(2)的近似解, 是 Kiefer(1953 年)提出的,叫做 Finbonacci 法,具体步骤如下

其中ε 为任意小的数。在 t1 和 t2 这两点中,以函数值较小者为近似极小点,相应的函数 值为近似极小值。并得最终区间[ a,t1 ] 或[ t2 b, ] 。

由上述分析可知,斐波那契法使用对称搜索的方法,逐步缩短所考察的区间,它能 以尽量少的函数求值次数,达到预定的某一缩短率。

 

现用不变的区间缩短率 0.618,代替斐波那契法每次不同的缩短率,就得到了黄金 分割法(0.618 法)。这个方法可以看成是斐波那契法的近似,实现起来比较容易,效果 也相当好,因而易于为人们所接受。

用 0.618 法求解,从第 2 个探索点开始每增加一个探索点作一轮迭代以后,原单 峰区间要缩短 0.618 倍。计算n 个探索点的函数值可以把原区间[ , ] a0 b0 连续缩短n −1 次,因为每次的缩短率均为 μ ,故最后的区间长度为

 当然,也可以不预先计算探索点的数目n ,而在计算过程中逐次加以判断,看是否已满 足了提出的精度要求。 0.618 法是一种等速对称进行试探的方法,每次的探索点均取在区间长度的 0.618 倍和 0.382 倍处。

2.2 二次插值法

对极小化问题(2),当 f (t) 在[a,b] 上连续时,可以考虑用多项式插值来进行一 维搜索。它的基本思想是:在搜索区间中,不断用低次(通常不超过三次)多项式来近 似目标函数,并逐步用插值多项式的极小点来逼近(2)的最优解。

2.3 无约束极值问题的解法

无约束极值问题可表述为

求解问题(5)的迭代法大体上分为两点:一是用到函数的一阶导数或二阶导数, 称为解析法。另一是仅用到函数值,称为直接法。

2.3.1 解析法

2.3.1.1 梯度法(最速下降法)

对基本迭代格式

2.3.1.2 Newton 法

如果目标函数是非二次函数,一般地说,用 Newton 法通过有限轮迭代并不能保证 可求得其最优解。 为了提高计算精度,我们在迭代时可以采用变步长计算上述问题,编写主程序文件 example5_2 如下:

clc,clear
x=[2;2];
[f0,g1,g2]=nwfun(x);
while norm(g1)>0.00001 p=-inv(g2)*g1;p=p/norm(p);t=1.0;f=nwfun(x+t*p);while f>f0t=t/2;f=nwfun(x+t*p);end
x=x+t*p;
[f0,g1,g2]=nwfun(x);
end
x,f0

Newton 法的优点是收敛速度快;缺点是有时不好用而需采取改进措施,此外,当 维数较高时,计算的工作量很大。

2.3.1.3 变尺度法

变尺度法(Variable Metric Algorithm)是近 20 多年来发展起来的,它不仅是求解 无约束极值问题非常有效的算法,而且也已被推广用来求解约束极值问题。由于它既避 免了计算二阶导数矩阵及其求逆过程,又比梯度法的收敛速度快,特别是对高维问题具 有显著的优越性,因而使变尺度法获得了很高的声誉。下面我们就来简要地介绍一种变 尺度法—DFP 法的基本原理及其计算过程。这一方法首先由 Davidon 在 1959 年提出, 后经 Fletcher 和 Powell 加以改进。

这就是常说的拟 Newton 条件。

阵按式(18)逐步形成。可以证明: (i)当 k x 不是极小点且 (k ) H 正定时,式(17)右端两项的分母不为零,从而可 按式(18)产生下一个尺度矩阵 (k +1) H ; (ii)若 (k ) H 为对称正定阵,则由式(18)产生的 (k +1) H 也是对称正定阵; (iii)由此推出 DFP 法的搜索方向为下降方向。 现将 DFP 变尺度法的计算步骤总结如下。

2.3.2 直接法

在无约束非线性规划方法中,遇到问题的目标函数不可导或导函数的解析式难以 表示时,人们一般需要使用直接搜索方法。同时,由于这些方法一般都比较直观和易于 理解,因而在实际应用中常为人们所采用。下面我们介绍 Powell 方法。 这个方法主要由所谓基本搜索、加速搜索和调整搜索方向三部分组成,具体步骤 如下

2.4 Matlab 求无约束极值问题

Matlab 工具箱中,用于求解无约束极值问题的函数有 fminunc 和 fminsearch,用 法介绍如下。 求函数的极小值

其中 x 可以为标量或向量。 Matlab 中 fminunc 的基本命令是

[X,FVAL]=FMINUNC(FUN,X0,OPTIONS,P1,P2, ...) 

 其中的返回值 X 是所求得的极小点,FVAL 是函数的极小值,其它返回值的含义参见相 关的帮助。FUN 是一个 M 文件,当 FUN 只有一个返回值时,它的返回值是函数 f (x); 当 FUN 有两个返回值时,它的第二个返回值是 f (x)的梯度向量;当 FUN 有三个返回 值时,它的第三个返回值是 f (x)的二阶导数阵(Hessian 阵)。X0 是向量 x 的初始值, OPTIONS 是优化参数,可以使用缺省参数。P1,P2 是可以传递给 FUN 的一些参数。

 

3约束极值问题

带有约束条件的极值问题称为约束极值问题,也叫规划问题。 求解约束极值问题要比求解无约束极值问题困难得多。为了简化其优化工作,可采 用以下方法:将约束问题化为无约束问题;将非线性规划问题化为线性规划问题,以及 能将复杂问题变换为较简单问题的其它方法。 库恩—塔克条件是非线性规划领域中最重要的理论成果之一,是确定某点为最优点 的必要条件,但一般说它并不是充分条件(对于凸规划,它既是最优点存在的必要条件, 同时也是充分条件)。

3.1 二次规划

若某非线性规划的目标函数为自变量 x 的二次函数,约束条件又全是线性的,就称 这种规划为二次规划。 Matlab 中二次规划的数学模型可表述如下:

Matlab 中求解二次规划的命令是

[X,FVAL]= QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)

返回值 X 是决策向量 x 的值,返回值 FVAL 是目标函数在 x 处的值。(具体细节可以参 看在 Matlab 指令中运行 help quadprog 后的帮助)。

h=[4,-4;-4,8]; 
f=[-6;-3]; 
a=[1,1;4,1]; 
b=[3;9]; 
[x,value]=quadprog(h,f,a,b,[],[],zeros(2,1))

3.2 罚函数法

利用罚函数法,可将非线性规划问题的求解,转化为求解一系列无约束极值问题, 因而也称这种方法为序列无约束最小化技术,简记为 SUMT (Sequential Unconstrained Minization Technique)。

罚函数法求解非线性规划问题的思想是,利用问题中的约束函数作出适当的罚函 数,由此构造出带参数的增广目标函数,把问题转化为无约束非线性规划问题。主要有 两种形式,一种叫外罚函数法,另一种叫内罚函数法,下面介绍外罚函数法

解 (i)编写 M 文件 test.m

function g=test(x);
M=50000;
f=x(1)^2+x(2)^2+8;
g=f-M*min(x(1),0)-M*min(x(2),0)-M*min(x(1)^2-x(2),0)+...
M*abs(-x(1)-x(2)^2+2);

或者是利用Matlab的求矩阵的极小值和极大值函数编写test.m如下:

function g=test(x); 
M=50000; 
f=x(1)^2+x(2)^2+8; 
g=f-M*sum(min([x';zeros(1,2)]))-M*min(x(1)^2-x(2),0)+... M*abs(-x(1)-x(2)^2+2);

我们也可以修改罚函数的定义,编写test.m如下:

function g=test(x);
M=50000;
f=x(1)^2+x(2)^2+8;
g=f-M*min(min(x),0)-M*min(x(1)^2-x(2),0)+M*(-x(1)-x(2)^2+2)^2;

(ii)在 Matlab 命令窗口输入 [x,y]=fminunc('test',rand(2,1)) 即可求得问题的解

3.3 Matlab 求约束极值问题

在 Matlab 优化工具箱中,用于求解约束最优化问题的函数有:fminbnd、fmincon、 quadprog、fseminf、fminimax,上面我们已经介绍了函数 fmincon 和 quadprog

3.3.1 fminbnd 函数

式约束Ceq(x) 和半无穷约束 PHI(x,w)的每一个分量函数,函数 SEMINFCON 有两个 输入参量 X 和 S,S 是推荐的取样步长,也许不被使用

(3)调用函数 fseminf 在 Matlab 的命令窗口输入

[x,y]=fseminf(@fun6,rand(3,1),2,@fun7)

3.3.3 fminimax 函数

3.3.4 利用梯度求解约束优化问题

3.4 Matlab 优化工具箱的用户图形界面解法

一、优化问题定义

在变量满足约束条件的前提下,使目标函数最小化的问题,即称为优化问题。优化问题的三要素:

  1. 优化目标
    min f(X)
  2. 优化变量
    X = [x1, x2, x3]
  3. 约束条件
    h1(x) ≤ 0h2(x) ≤ 0h3(x) ≤ 0

二、Matlab优化工具箱介绍
Matlab的优化工具箱(Optimization Toolbox)中含有一系列的优化算法,用于求解不同的优化问题,包括:
无约束极小一元函数极小线性规划二次型规划非线性约束规划多目标优化极小极大问题。在处理优化问题时,首先根据相应的数学模型,设定合适的优化目标,然后输入优化变量的初值、约束条件、取值范围,通过调用相应优化函数或使用优化工具箱,即可求得相应的优化结果。
(1)求解无约束条件非线性极小值;
(2)求解约束条件下非线性极小值,包括目标逼近问题、极大-极小值问题和半无限极小值问题;
(3)求解二次规划和线性规划问题;
(4)非线性最小二乘逼近和曲线拟合;
(5)非线性系统的方程求解;
(6)约束条件下的线性最小二乘优化;
(7)求解复杂结构的大规模优化问题。

 

指定问题类型:
根据目标函数的类型进行选择,本问题是非线性问题 

 指定约束类型:
本问题有参数的上下界限制和一个不等式约束,并且是非线性的:

选择优化方法,就用了默认的,点右边的问号可以看到关于求解器的更多信息

4. 编写目标函数

 本实例目标函数是从局部函数选择,这种类型需要自己在脚本里编写目标函数,选择新建,下方就会出现一个目标函数模板:

这个模板已经把目标函数怎么写有了个实例,这个示例用的目标函数就是这个,所以不用改了

这个模板已经把目标函数怎么写有了个实例,这个示例用的目标函数就是这个,所以不用改了。
5. 选择初始点, 以同样的方法新建约束函数,并设置上下界。

再选择一下需要的结果就可以运行了:

结果图:

 

点击下方名片加入群聊获取更多免费数学建模的资料!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/416965.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

并发工具类(一):CountDownLatch

1、CountDownLatch介绍 CountDownLatch 又称为“倒计数门阀”,但大多数称之为“计数器”,是juc包下的一个工具类; CountDownLatch 核心功能是:用于一个活多个线程等待其他线程执行完成的一组操作。 CountDownLatch 中有个全局的计…

【Blender】快捷键_ 学习日志_01

【Blender】快捷键_ 学习日志_01 学习了blender的快捷键的使用。 2024年8月30日 视角操控 围绕中心旋转:按住鼠标中建 平移视角:Shift鼠标中键 视角前进后退:滚动滚轮 视图切换 0 切换到摄像机视图 1 切换正试图 2,4&…

产值8111亿!从《中国地理信息产业发展报告2024》看产业链上的就业蓝海

中国地理信息产业协会28日发布《中国地理信息产业发展报告2024》,报告显示2023年我国地理信息产业总产值达到8111亿元,同比增长4.2%,初步形成了完整的地理信息产业链。 《中国地理信息产业发展报告2024》显示,2023年以来&#xf…

倍福EL6751快速配置CANopen伺服

EL6751快速配置CANopen伺服 使用倍福EL6751快速配置方法,不要求提供从站的eds文件,但是需要提供从站的使用手册和通讯手册,用来查阅从站的PDO配置信息,这些配置参数会使用如下方法通过EL6751写入到从站中。 建立通用CANopen节点…

开源通用验证码识别OCR —— DdddOcr 源码赏析(二)

文章目录 前言DdddOcr分类识别调用识别功能classification 函数源码classification 函数源码解读1. 分类功能不支持目标检测2. 转换为Image对象3. 根据模型配置调整图片尺寸和色彩模式4. 图像数据转换为浮点数据并归一化5. 图像数据预处理6. 运行模型,返回预测结果 …

使用seamless-scroll-v3 实现无缝滚动,自动轮播平滑的滚动效果

安装&#xff1a;npm地址&#xff1a;https://www.npmjs.com/package/seamless-scroll-v3 yarn add seamless-scroll-v3# 或者使用 npm npm install seamless-scroll-v3# 或者使用 pnpm pnpm add seamless-scroll-v3 实现效果&#xff1a; template中的代码&#xff1a; <…

陷抄袭风波 《黑神话:悟空》该如何应对

都说人红是非多&#xff0c;国产首部3A游戏《黑神话&#xff1a;悟空》在爆火的同时&#xff0c;一些问题也随之出现。一方面《黑神话&#xff1a;悟空》陷入抄袭风波&#xff1f;另一方面该游戏也被很多黑灰产盯上了。 8月23日&#xff0c;“塞上李云中”发布微博&#xff0c;…

做为一名研发人员,你是如何看待项目管理软件这种产品的?

我认为项目管理软件是现代软件开发和项目管理中不可或缺的工具。它能够提高项目管理的效率和准确性&#xff0c;降低项目失败的风险&#xff0c;并为团队带来显著的价值。然而&#xff0c;在选择和使用项目管理软件时&#xff0c;团队需要综合考虑多个因素&#xff0c;以确保选…

hiprint打印/jsPDF使用/html2canvas

最初我知道hiprint.print是可以打印双模板的&#xff0c;于是查看hiprint.print的源码发现底层实现是this.getHtml(t).hiwprint,于是断点查看getHtm的实现&#xff0c;得知它是遍历我们对print传参的list&#xff0c;利用list中模板对象的getHtml()方法得到模板的dom对象&#…

如何使用电商API接口?(淘宝|京东商品详情数据接口)

一、了解电商API接口&#xff1a; 如今&#xff0c;在电商市场中&#xff0c;电商API接口的广泛应用极大地提高了电商行业的工作效率&#xff0c;使得商家能够灵活集成多种服务&#xff0c;高效优化业务流程。 当前&#xff0c;电商平台中的多种业务都可以通过使用API接口来做…

OpenGL/GLUT实践:水面模拟——从单振源到 Gerstner Wave(电子科技大学信软图形与动画Ⅱ实验)

源码见GitHub&#xff1a;A-UESTCer-s-Code 文章目录 1 实现效果1 简单水面模拟——单振源1.1 水面高度函数1.2 水面建模1.3 openGL 渲染(1) renderSense(2) 其他 1.4 实现效果 2 添加鼠标控制3 添加纹理4 多个振源组合5 Gerstner Wave 模型5.1 原理5.2 具体实现5.2.1 全局变量…

光伏气象分析包含哪些数据?

1.海拔 海拔是影响太阳辐射强度和气温的重要因素之一。高海拔地区通常大气稀薄&#xff0c;太阳辐射衰减较少&#xff0c;因此太阳辐射强度相对较高。同时&#xff0c;随着海拔的升高&#xff0c;气温和气压也会发生变化&#xff0c;这些变化对光伏组件的性能和发电效率有直接…

深度学习5从0到1理解RNN(包括LTSM,GRU等):内容丰富(下)

续 5.4.4 LSTM 举例 网络里面只有一个 LSTM 的单元&#xff0c;输入都是三维的向量&#xff0c;输出都是一维的输出。这三维的向量跟输出还有记忆元的关系是这样的。假设 x2 的值是 1 时&#xff0c; x1 的值就会被写到记忆元里&#xff1b;假设 x2 的值是-1 时&#xff0c;就…

计算机,数学,AI在社会模拟中的应用

这些模型通常属于社会模拟的范畴&#xff0c;利用计算机技术和复杂系统理论来模拟和预测社会动态。以下是几种常见的社会模拟模型&#xff1a; 1. 系统动力学模型 系统动力学模型通过建立数学方程来描述社会系统中的各种变量及其相互关系。这种模型适用于宏观层面的社会变化分…

uniapp 封装uni.login 实现全局调用

封装utils app.vue中 使用globalData 注册 utils 页面中使用方法 定义app 调用方法

ICM20948 DMP代码详解(1)

序言 接触Invensense的芯片这已经是第三次了。2015年在第二空间的时候第一次接触它的芯片&#xff0c;那时候是MPU9250&#xff1b;2021年的时候在智橙动力再一次接触到了MPU6050&#xff0c;那个时候用到了其中的DMP&#xff1b;这次接触的是ICM20948&#xff0c;按目前笔者理…

外接串口板,通过串口打开adb模式

一、依赖库 import subprocess import serial from serial.tools import list_ports import logging import time 二、代码 import subprocessimport serial from serial.tools import list_ports import logging import timedef openAdb(com):# com []# for i in list_por…

1、.Net UI框架:Avalonia UI - .Net宣传系列文章

Avalonia UI是一个开源的跨平台UI框架&#xff0c;它允许开发者使用C#和XAML来创建应用程序&#xff0c;这些应用程序可以在多个平台上运行&#xff0c;包括Windows、macOS、Linux、Android和iOS。Avalonia UI的设计目标是提供一个现代化、可移植的UI框架&#xff0c;它具有类似…

如何通过日志或gv$sql_audit,分析OceanBase运行时的异常SQL

本文作者&#xff1a;郑增权&#xff0c;爱可生 DBA 团队成员&#xff0c;OceanBase 和 MySQL 数据库技术爱好者。本文约 2000 字&#xff0c;预计阅读需要 8 分钟。 简介 在 OCP 云平台的 Top SQL 界面中&#xff0c;能观察到异常SQL&#xff0c;但这些SQL并未明确显示具体的…

上手一个RGBD深度相机:从原理到实践--ROS noetic+Astra S(上):解读深度测距原理和内外参推导

前言 最近在做项目的时候&#xff0c;项目组丢给了我一个深度相机&#xff0c;今天我们来尝试上手一个实体深度相机。 本教程设计基础相机的原理&#xff0c;使用&#xff0c;标定&#xff0c;和读取。(注&#xff1a;本教程默认大家有ROS1基础&#xff0c;故不对程序进行详细…