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 优化工具箱的用户图形界面解法

一、优化问题定义

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

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

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