2024国赛数学建模备赛|30种常用的算法模型之最优算法-非线性规划
1.1 非线性规划的实例与界说如果目的函数或约束条件中包含非线性函数，就称这种规划题目为非线性规划题目。一般说来，解非线性规划要比解线性规划题目困难得多。而且，也不象线性规划有 单纯形法这一通用方法，非线性规划目前还没有适于各种题目的一般算法，各个方法都 有自己特定的实用范围。
下面通过实例归纳出非线性规划数学模型的一般情势，先容有关非线性规划的基本 概念。
https://i-blog.csdnimg.cn/direct/e76fca41edb644c3a0fbbd41f8be286d.png
最佳投资方案应是投资额最小而总收益最大的方案，以是这个最佳投资决策题目归 结为总资金以及决策变量（取 0 或 1）的限制条件下，极大化总收益和总投资之比。因 此，其数学模型为：
https://i-blog.csdnimg.cn/direct/3bba321f565e482881faa638b9f041b0.png
上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问 题，其中至少有一个非线性函数，这类题目称之为非线性规划题目。可概括为一般情势：
https://i-blog.csdnimg.cn/direct/df858ae20573411a8730fe47ff8ec5bf.png
https://i-blog.csdnimg.cn/direct/ad18bc53ebd74383b3b741155466a93e.png
对于一个现实题目，在把它归结成非线性规划题目时，一般要留意如下几点： （i）确定供选方案：起首要收集同题目有关的资料和数据，在全面熟悉题目的基 础上，确认什么是题目的可供选择的方案，并用一组变量来表示它们。 （ii）提出追求目的：经过资料分析，根据现实必要和可能，提出要追求极小化 或极大化的目的。而且，运用各种科学和技术原理，把它表示成数学关系式。 （iii）给出代价标准：在提出要追求的目的之后，要确立所考虑目的的“好”或 “坏”的代价标准，并用某种数目情势来描述它。 （iv）寻求限制条件：由于所追求的目的一般都要在肯定的条件下取得极小化或 极大化效果，因此还必要寻找出题目的所有限制条件，这些条件通常用变量之间的一些 不等式或等式来表示。
1.2 线性规划与非线性规划的区别
如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行 域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任 意一点达到。
1.3 非线性规划的 Matlab 解法
Matlab 中非线性规划的数学模型写成以下情势
https://i-blog.csdnimg.cn/direct/27ecc40f425e401aac8e8877bc5f2d8f.png
Matlab 中的命令是
X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS) https://i-blog.csdnimg.cn/direct/79b122b6af0e457085103fb0bf6bd6e6.png
https://i-blog.csdnimg.cn/direct/ce38f3b041004e7f9697319f60b84a97.png
https://i-blog.csdnimg.cn/direct/0004d3ff324346e89c19a8d7b02d7df3.png
https://i-blog.csdnimg.cn/direct/620d6c0a3dae4dcaa702178d2d9dbfe7.png
1.4 求解非线性规划的基本迭代格式
https://i-blog.csdnimg.cn/direct/3cac5e8582a14b738e37cd36ef00bc21.png
由于线性规划的目的函数为线性函数，可行域为凸集，因而求出的最优解就是整 个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一部分可行域上 的极值点，但却并不愿定是整个可行域上的全局最优解。
https://i-blog.csdnimg.cn/direct/d1050a0179794a3494cc021e5e2e75d1.png
https://i-blog.csdnimg.cn/direct/306f8b5a896048c88694b7fd7c58ac3d.png
1.5 凸函数、凸规划
https://i-blog.csdnimg.cn/direct/1a76f3425454432cbf6ca8352501e68e.png
可以证明，凸规划的可行域为凸集，其局部最优解即为全局最优解，而且其最优 解的聚集形成一个凸集。当凸规划的目的函数 f (x)为严格凸函数时，其最优解必定唯 一（假定最优解存在）。由此可见，凸规划是一类比较简单而又具有重要理论意义的非线性规划
2.1 一维搜刮方法
当用迭代法求函数的极小点时，常常用到一维搜刮，即沿某一已知方向求目的函数 的极小点。一维搜刮的方法很多，常用的有：（1）试探法（“成功—失败”，斐波那契法， 0.618 法等）；（2）插值法（抛物线插值法，三次插值法等）；（3）微积分中的求根法（切 线法，二分法等）。 考虑一维极小化题目
https://i-blog.csdnimg.cn/direct/4f0ca40126f843f7ba2f01b2e1ef1175.png
若 f (t) 是 区间上的下单峰函数，我们先容通过不停地收缩 的长度，来 搜刮得（2）的近似最优解的两个方法。
https://i-blog.csdnimg.cn/direct/5e9eec51f8c649878f0a8c168d3be908.png
2.1.1 Fibonacci 法
如用 Fn 表示盘算n 个函数值能收缩为单位长区间的最大原区间长度，可推出 Fn 满 足关系
https://i-blog.csdnimg.cn/direct/d2a43515babc4b0da83a4dcbf88a69f3.png
如果要求经过一系列探索点搜刮之后，使末了的探索点和最优解之间的距离不超 过精度δ > 0 ，这就要求末了区间的长度不超过δ ，即
https://i-blog.csdnimg.cn/direct/47eb2c04549a4dfbb2edd648fe7b341a.png
据此，我们应按照预先给定的精度δ ，确定使（4）成立的最小整数n 作为搜刮次数， 直到举行到第n 个探索点时停止。
用上述不停收缩函数 f (t) 的单峰区间 的办法，来求得题目（2）的近似解， 是 Kiefer(1953 年)提出的，叫做 Finbonacci 法，详细步骤如下
https://i-blog.csdnimg.cn/direct/b4077b9cf0534a37b10ca724c020279f.png
https://i-blog.csdnimg.cn/direct/d8dde8d883274bb392db538ab9aad9ed.png
其中ε 为恣意小的数。在 t1 和 t2 这两点中，以函数值较小者为近似极小点，相应的函数 值为近似极小值。并得终极区间[ a,t1 ] 或[ t2 b, ] 。
由上述分析可知，斐波那契法使用对称搜刮的方法，逐步收缩所观察的区间，它能 以只管少的函数求值次数，达到预定的某一收缩率。
https://i-blog.csdnimg.cn/direct/655a8cdb6cdd41ffa070601d0f88370f.png
https://i-blog.csdnimg.cn/direct/0a31be1f77dd40bb8273d38d1680cb57.png
现用稳固的区间收缩率 0.618，取代斐波那契法每次不同的收缩率，就得到了黄金 分割法（0.618 法）。这个方法可以看成是斐波那契法的近似，实现起来比较容易，效果 也相当好，因而易于为人们所接受。
用 0.618 法求解，从第 2 个探索点开始每增长一个探索点作一轮迭代以后，原单 峰区间要收缩 0.618 倍。盘算n 个探索点的函数值可以把原区间[ , ] a0 b0 一连收缩n −1 次，因为每次的收缩率均为 μ ，故末了的区间长度为
https://i-blog.csdnimg.cn/direct/903f2062c78e498fb88969e6c0e3a8c6.png
当然，也可以不预先盘算探索点的数目n ，而在盘算过程中逐次加以判定，看是否已满 足了提出的精度要求。 0.618 法是一种等速对称举行试探的方法，每次的探索点均取在区间长度的 0.618 倍和 0.382 倍处。
2.2 二次插值法
对极小化题目（2），当 f (t) 在 上一连时，可以考虑用多项式插值来举行一 维搜刮。它的基本思想是：在搜刮区间中，不停用低次（通常不超过三次）多项式来近 似目的函数，并逐步用插值多项式的极小点来逼近（2）的最优解。
2.3 无约束极值题目的解法
无约束极值题目可表述为
https://i-blog.csdnimg.cn/direct/5572a2fa44a14713bfd8a4acdbb2bd5d.png
求解题目（5）的迭代法大体上分为两点：一是用到函数的一阶导数或二阶导数， 称为解析法。另一是仅用到函数值，称为直接法。
2.3.1 解析法
2.3.1.1 梯度法（最速降落法）
对基本迭代格式
https://i-blog.csdnimg.cn/direct/4f1c55c82ea740dfb79695d4f19b4fca.png
https://i-blog.csdnimg.cn/direct/95ed48b642a847be8b0c1329351b5582.png
https://i-blog.csdnimg.cn/direct/683f2c37cf214ceb8e30a73d59e40ca2.png
2.3.1.2 Newton 法
https://i-blog.csdnimg.cn/direct/4a9959adb05245fa97e0369a28c9a847.png
https://i-blog.csdnimg.cn/direct/9abeaed837e94bab94d7e68c599d706b.png
https://i-blog.csdnimg.cn/direct/47db238d3bf34ecf8dc446178fad550f.png
https://i-blog.csdnimg.cn/direct/c063b98cab8e4383ad9692689a5af049.png
https://i-blog.csdnimg.cn/direct/c9d37a29b9cb4a5dac07b8a9cd9dc106.png
如果目的函数黑白二次函数，一般地说，用 Newton 法通过有限轮迭代并不能保证 可求得其最优解。 为了提高盘算精度，我们在迭代时可以采用变步长盘算上述题目，编写主步伐文件 example5_2 如下：
clc,clear
x=;
=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>f0
t=t/2;f=nwfun(x+t*p);
end
x=x+t*p;
=nwfun(x);
end
x,f0 Newton 法的优点是收敛速率快；缺点是有时不好用而需采取改进措施，此外，当 维数较高时，盘算https://i-blog.csdnimg.cn/direct/0197b82271d34db29bad56a45ef7ac9c.png的工作量很大。
2.3.1.3 变尺度法
变尺度法（Variable Metric Algorithm）是近 20 多年来发展起来的，它不仅是求解 无约束极值题目非常有效的算法，而且也已被推广用来求解约束极值题目。由于它既避 免了盘算二阶导数矩阵及其求逆过程，又比梯度法的收敛速率快，特别是对高维题目具 有显著的精良性，因而使变尺度法得到了很高的荣誉。下面我们就来扼要地先容一种变 尺度法—DFP 法的基本原理及其盘算过程。这一方法起首由 Davidon 在 1959 年提出， 后经 Fletcher 和 Powell 加以改进。
https://i-blog.csdnimg.cn/direct/0f4902f0fc324f7191763212f51cff88.png
这就是常说的拟 Newton 条件。
https://i-blog.csdnimg.cn/direct/c37a61a4f5c24b92bb2c57dde973493d.png
https://i-blog.csdnimg.cn/direct/988ea3d469934ac493210496a2e92e7d.png阵按式（18）逐步形成。可以证明： （i）当 k x 不是极小点且 (k ) H 正定时，式（17）右端两项的分母不为零，从而可 按式（18）产生下一个尺度矩阵 (k +1) H ； （ii）若 (k ) H 为对称正定阵，则由式（18）产生的 (k +1) H 也是对称正定阵； （iii）由此推出 DFP 法的搜刮方向为降落方向。 现将 DFP 变尺度法的盘算步骤总结如下。
https://i-blog.csdnimg.cn/direct/74ae114c37fc458c8132a1da627e5751.png
2.3.2 直接法
在无约束非线性规划方法中，遇到题目的目的函数不可导或导函数的解析式难以 表示时，人们一般必要使用直接搜刮方法。同时，由于这些方法一般都比较直观和易于 明白，因而在现实应用中常为人们所采用。下面我们先容 Powell 方法。 这个方法重要由所谓基本搜刮、加快搜刮和调整搜刮方向三部分构成，详细步骤 如下
https://i-blog.csdnimg.cn/direct/084181a14ee6463e80cb26445e5c7ce4.png
https://i-blog.csdnimg.cn/direct/0258361573324848a66cadd3f903cad1.png
2.4 Matlab 求无约束极值题目
Matlab 工具箱中，用于求解无约束极值题目的函数有 fminunc 和 fminsearch，用 法先容如下。 求函数的极小值
https://i-blog.csdnimg.cn/direct/e7ba4dd597d447deb3e18bad0c26023d.png
其中 x 可以为标量或向量。 Matlab 中 fminunc 的基本命令是
=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 的一些参数。
https://i-blog.csdnimg.cn/direct/31a9d9834dba497fa9e741c0524c5431.png
https://i-blog.csdnimg.cn/direct/748667217fae439ba8648a6114b70ce7.png
3约束极值题目
带有约束条件的极值题目称为约束极值题目，也叫规划题目。 求解约束极值题目要比求解无约束极值题目困难得多。为了简化其优化工作，可采 用以下方法：将约束题目化为无约束题目；将非线性规划题目化为线性规划题目，以及 能将复杂题目变换为较简单题目的别的方法。 库恩—塔克条件黑白线性规划领域中最重要的理论效果之一，是确定某点为最优点 的须要条件，但一般说它并不是充实条件（对于凸规划，它既是最优点存在的须要条件， 同时也是充实条件）。
3.1 二次规划
若某非线性规划的目的函数为自变量 x 的二次函数，约束条件又全是线性的，就称 这种规划为二次规划。 Matlab 中二次规划的数学模型可表述如下：
https://i-blog.csdnimg.cn/direct/afa5a78504cc4fd295669efaa5148d82.png
Matlab 中求解二次规划的命令是
= QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS) 返回值 X 是决策向量 x 的值，返回值 FVAL 是目的函数在 x 处的值。（详细细节可以参 看在 Matlab 指令中运行 help quadprog 后的帮助）。
https://i-blog.csdnimg.cn/direct/47aeda4b9d1343c7b33b17f5aeb72da2.png
h=;
f=[-6;-3];
a=;
b=;
=quadprog(h,f,a,b,[],[],zeros(2,1)) https://i-blog.csdnimg.cn/direct/ed29e1af14da48b18b63a69de2bc7346.png
3.2 罚函数法
利用罚函数法，可将非线性规划题目的求解，转化为求解一系列无约束极值题目， 因而也称这种方法为序列无约束最小化技术，简记为 SUMT (Sequential Unconstrained Minization Technique)。
罚函数法求解非线性规划题目的思想是，利用题目中的约束函数作出恰当的罚函 数，由此构造出带参数的增广目的函数，把题目转化为无约束非线性规划题目。重要有 两种情势，一种叫外罚函数法，另一种叫内罚函数法，下面先容外罚函数法
https://i-blog.csdnimg.cn/direct/e4fba00b5e5043b9b3ecab89f355bbf4.png
https://i-blog.csdnimg.cn/direct/836d9669856442efadaaeb93ada98e63.png
解 (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())-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 命令窗口输入 =fminunc('test',rand(2,1)) 即可求得题目的解
3.3 Matlab 求约束极值题目
在 Matlab 优化工具箱中，用于求解约束最优化题目的函数有：fminbnd、fmincon、 quadprog、fseminf、fminimax，上面我们已经先容了函数 fmincon 和 quadprog
3.3.1 fminbnd 函数
https://i-blog.csdnimg.cn/direct/de386a0333314f81b807065939b7c6ba.png
https://i-blog.csdnimg.cn/direct/f589912e76834736a637c4c498fc5db7.png
式约束Ceq(x) 和半无穷约束 PHI(x,w)的每一个分量函数，函数 SEMINFCON 有两个 输入参量 X 和 S，S 是推荐的取样步长，大概不被使用
https://i-blog.csdnimg.cn/direct/d36c5ba91c0040de80f17131c72eb68d.png
https://i-blog.csdnimg.cn/direct/4735ed26cf5e4909b37f6ecf831f83b2.png
（3）调用函数 fseminf 在 Matlab 的命令窗口输入
=fseminf(@fun6,rand(3,1),2,@fun7) 3.3.3 fminimax 函数
https://i-blog.csdnimg.cn/direct/aba8568786e44aa498deda50cfa0e84a.png
https://i-blog.csdnimg.cn/direct/614ada09532940b79b53d17e74cad93d.png
3.3.4 利用梯度求解约束优化题目
https://i-blog.csdnimg.cn/direct/5a9d264d5d364a03a67440e712700f4c.png
https://i-blog.csdnimg.cn/direct/8986cfd9032e4e86b1f79bc45d188a9f.png
3.4 Matlab 优化工具箱的用户图形界面解法
https://i-blog.csdnimg.cn/direct/44e24b831f6f40ceb0b7fb2f1709bf95.png
一、优化题目界说
在变量满足约束条件的前提下，使目的函数最小化的题目，即称为优化题目。优化题目的三要素：
[*]优化目的
min f(X)
[*]优化变量
X =
[*]约束条件
h1(x) ≤ 0h2(x) ≤ 0h3(x) ≤ 0
二、Matlab优化工具箱先容
Matlab的优化工具箱（Optimization Toolbox）中含有一系列的优化算法，用于求解不同的优化题目，包括：
无约束极小一元函数极小线性规划二次型规划非线性约束规划多目的优化极小极大题目。在处置惩罚优化题目时，起首根据相应的数学模型，设定合适的优化目的，然后输入优化变量的初值、约束条件、取值范围，通过调用相应优化函数或使用优化工具箱，即可求得相应的优化效果。
（1）求解无约束条件非线性极小值；
（2）求解约束条件下非线性极小值，包括目的逼近题目、极大-极小值题目和半无限极小值题目；
（3）求解二次规划和线性规划题目；
（4）非线性最小二乘逼近和曲线拟合；
（5）非线性系统的方程求解；
（6）约束条件下的线性最小二乘优化；
（7）求解复杂结构的大规模优化题目。
https://i-blog.csdnimg.cn/direct/3c520ca164094976ad8e6a23395d70ca.png
https://i-blog.csdnimg.cn/direct/d6d0d611454144b7bfc3329c8e300cd8.png
https://i-blog.csdnimg.cn/direct/14f85217195d46638592350db583c082.pnghttps://i-blog.csdnimg.cn/direct/de837606062540408c118cdc8a778e7c.png
指定题目类型：
根据目的函数的类型举行选择，本题目黑白线性题目
https://i-blog.csdnimg.cn/direct/642014eb56d54751b5048c0c5e32014e.png
指定约束类型：
本题目有参数的上下边界制和一个不等式约束，而且黑白线性的：
https://i-blog.csdnimg.cn/direct/3d96fa67e1f741aa8af54735a3163c26.png
选择优化方法，就用了默认的，点右边的问号可以看到关于求解器的更多信息
https://i-blog.csdnimg.cn/direct/112f4d3a6944473e846d56e4b36901a5.png
4. 编写目的函数
https://i-blog.csdnimg.cn/direct/9196c13a07b94f5896174220dc0a1c23.png
本实例目的函数是从局部函数选择，这种类型必要自己在脚本里编写目的函数，选择新建，下方就会出现一个目的函数模板：
这个模板已经把目的函数怎么写有了个实例，这个示例用的目的函数就是这个，以是不用改了
https://i-blog.csdnimg.cn/direct/51b00bfb7a6a4f7191dc9ec052499d6b.png
这个模板已经把目的函数怎么写有了个实例，这个示例用的目的函数就是这个，以是不用改了。
5. 选择初始点， 以同样的方法新建约束函数，并设置上下界。
https://i-blog.csdnimg.cn/direct/722b96ffd3084141a3d9b3c07e5443fb.png
https://i-blog.csdnimg.cn/direct/93e00b6ef52a42f9954f4127c989464d.png
再选择一下必要的效果就可以运行了：
https://i-blog.csdnimg.cn/direct/afdd57768452419fa6cdbe418c8480f8.png
效果图：
https://i-blog.csdnimg.cn/direct/2c5f5f33fe3946219cf49d7a1460985a.png
点击下方名片加入群聊获取更多免费数学建模的资料！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]