2023年4月18日发(作者：汕头大学理学院)⾮线性规划（⼀）：定义与数值优化⽅法（梯度法、⽜顿法、
拟⽜顿法、变尺度法）
1 ⾮线性规划
⽬录
年终考核个人总结
1.1 ⾮线性规划的实例与定义
如果⽬标函数或约束条件中包含⾮线性函数，就称这种规划问题为⾮线性规划问 题。⼀般说来，解⾮线性规划要⽐解线性规划问题
困难得多。⽽且，也不象线性规划有 单纯形法这⼀通⽤⽅法，⾮线性规划⽬前还没有适于各种问题的⼀般算法，各个⽅法都 有⾃⼰特定的
适⽤范围。 下⾯通过实例归纳出⾮线性规划数学模型的⼀风的英语怎么读
般形式，介绍有关⾮线性规划的基本概念。
例⼀ 投资决策问题
⾮线性规划的构成要素
对于⼀个实际问题，在把它归结成⾮线性规划问题时，⼀般要注意如下⼏点：
（i）确定供选⽅案：⾸先要收集同问题有关的资料和数据，在全⾯熟悉问题的基 础上，确认什么是问题的可供选择的⽅案，并⽤⼀
组变量来表⽰它们。
（ii）提出追求⽬标：经过资料分析，根据实际需要和可能，提出要追求极⼩化 或极⼤化的⽬标。彼字开头的成语
并且，运⽤各种科学和技术原理，
把它表⽰成数学关系式。
（iii）给出价值标准：在提出要追求的⽬标之后，要确⽴所考虑⽬标的“好”或 “坏”的价值标准，并⽤某种数量形式来描述它。
（iv）寻求限制条件：由于所追求的⽬标⼀般都要在⼀定的条件下取得极⼩化或 极⼤化效果，因此还需要寻找出问题的所有限制条
件，这些条件通常⽤变量之间的⼀些 不等式或等式来表⽰。
1.2 线性规划与⾮线性规划的区别
如果线性规划的最优解存在，其最优解只能在其可⾏域的边界上达到（特别是可⾏ 域的顶点上达到）；⽽⾮线性规划的最优解（如
果最优解存在）则可能在其可⾏域的任 意⼀点达到。
1.3 ⾮线性规划的 Matlab 解法
Matlab 中⾮线性规划的数学模型写成以下形式
Matlab 中的命令是
X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)
解 （i）编写 M ⽂件 fun1.m 定义⽬三七粉每日用量
标函数
function f=fun1(x);
f=sum(x.^2)+8;
（ii）编写M⽂件fun2.m定义⾮线性约束条件
function [g,h]=fun2(x); 定冠词the的用法
g=[-x(1)^2+x(2)-x(3)^2
x(1)+x(2)^2+x(3)^3-20]; %⾮线性不等式约束
h=[-x(1)-x(2)^2+2
x(2)+2*x(3)^2-3]; %⾮线性等式约束
（iii）编写主程序⽂件 example2.m 如下：
options=optimt('largescale','off');
[x,y]=fmincon('fun1',rand(3,1),[],[],[],[],zeros(3,1),[], ...
'fun2', options)
1.4 求解⾮线性规划的基本迭代格式
局部最优、整体最优的定义
求解⾮线性规划模型(NP)的基本迭代格式
如何构造每⼀轮的搜索⽅向和确定适当的步长
⽤基本迭代格式（1）求解(NP)的⼀般步骤
1.5 凸函数、凸规划
可以证明，凸规划的可⾏域为凸集，其局部最优解即为全局最开在记忆深处的花朵作文
优解，⽽且其最优 解的集合形成⼀个凸集。当凸规划的⽬标函数 )
为严格凸函数时，其最优解必定唯 ⼀（假定最优解存在）。由此可见，凸规划是⼀类⽐较简单⽽⼜具有重要理论意义的
⾮线性规划.
2 ⽆约束问题
2.1 ⼀维搜索⽅法
当⽤迭代法求函数的极⼩点时，常常⽤到⼀维搜索，即沿某⼀已知⽅向求⽬标函数的极⼩点。⼀维搜索的⽅法很多，常⽤的有：中国银行查询余额
（1）试探法（“成功—失败”，斐波那契法， 0.618 法等） ；
（2）插值法（抛物线插值法，三次插值法等）；
（3）微积分中的求根法（切 线法，⼆分法等）。
试怎么写自我评价
探法
应该按照怎样的规则来选取探索点，使给定的单峰区间的长度能尽快地缩短？
2.1.1 Fibonacci 法
Finbonacci 法的具体步骤
由上述分析可知，斐波那契法使⽤对称搜索的⽅法，逐步缩短所考察的区间，它能 以尽量少的函数求值次数，达到预定的某⼀缩短
率。
2.1.2 0.618 法
黄⾦分割数
若 > 0 ，满⾜⽐例关系
黄⾦分割数和 Fibo中书令
nacci 分数的关系
现⽤不变的区间缩短率 0.618，代替斐波那契法每次不同的缩短率，就得到了黄⾦ 分割法（0.618 法）。这个⽅法可以看成是斐波
那契法的近似，实现起来⽐较容易，效果 也相当好，因⽽易于为⼈们所接受。
2.2 ⼆次插值法
对极⼩化问题（2），当 在[ a , b ]上连续时，可以考虑⽤多项式插值来进⾏⼀ 维搜索。它的基本思想是：在搜索
区间中，不断⽤低次（通常不超过三次）多项式来近 似⽬标函数，并逐步⽤插值多项式的极⼩点来逼近（2）的优解。
2.3 ⽆约束极值问题的解法
⽆约束极值问题可表述为
求解问题（5）的迭代法⼤体上分为两点：⼀是⽤到函数的⼀阶导数或⼆阶导数， 称为解析法。另⼀是仅⽤到函数值，称为直接法。
2.3.1 解析法
2.3.1.1 梯度法（最速下降法）
最速下降法的具体步骤
例 4 ⽤最速下降法求解⽆约束⾮线性规划问题
function [f,df]=detaf(x);
f=x(1)^2+25*x(2)^2;
df=[2*x(1) 50*x(2)];
（ii）编写主程序⽂件zuisu.m如下：
clc
x=[2;2];
[f0,g]=detaf(x);
while norm(g)>0.000001
p=-g/norm(g);
t=1.0;f=detaf(x+t*p);
while f>f0
t=t/2;
f=detaf(x+t*p);
end
x=x+t*p;
[f0,g]=detaf(x);
end
x,f0
2.3.1.2 Newton 法
Newton 法的具体步骤
例 5 ⽤ Newton 法求解，
（ii）编写 M ⽂件 nwfun.m 如下：
function [f,df,d2f]=nwfun(x);
f=x(1)^4+25*x(2)^4+x(1)^2*x(2)^2;
df=[4*x(1)^3+2*x(1)*x(2)^2;100*x(2)^3+2*x(1)^2*x(2)];
d2f=[2*x(1)^2+2*x(2)^2,4*x(1)*x(2)
4*x(1)*x(2),300*x(2)^2+2*x(1)^2];
（III）编写主程序⽂件 example5.m 如下：
clc
x=[2;2];
[f0,g1,g2]=nwfun(x);
while norm(g1)>0.00001
p=-inv(g2)*g1;
x=x+p;
[f0,g1,g2]=nwfun(x);
end
x, f0职工安置
如果⽬标函数是⾮⼆次函数，⼀般地说，⽤ 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>f0
t=t/2;f=nwfun(x+t*p);
end
x=x+t*p;
[f0,g1,g2]=nwfun(x);
end
x,f0
2.3.1.3 变尺度法
变尺度法（Variable Metric Algorithm）是近 20 多年来发展起来的，它不仅是求解 ⽆约束极值问题⾮常有效的算法，⽽且也已被
推⼴⽤来求解约束极值问题。由于它既避 免了计算⼆阶导数矩阵及其求逆过程，⼜⽐梯度法的收敛速度快，特别是对⾼维问题具 有显著的
优越性，因⽽使变尺度法获得了很⾼的声誉。下⾯我们就来简要地介绍⼀种变尺度法—DFP 法的基本原理及其计算过程。这⼀⽅法⾸先由
Davidon 在 1959 年提出， 后经 Fletcher 和 Powell 加以改进。
拟⽜顿法
如何构造Hes阵的近似矩阵---拟 Newton 条件
尺度矩阵的推导
DFP 变尺度法的计算步骤总结
2.3.2 直接法
在⽆约束⾮线性规划⽅法中，遇到问题的⽬标函数不可导或导函数的解析式难以 表⽰时，⼈们⼀般需要使⽤直接搜索⽅法。同时，
由于这些⽅法⼀般都⽐较直观和易于 理解，因⽽在实际应⽤中常为⼈们所采⽤。下⾯我们介绍 Powell ⽅法。 这个⽅法主要由所谓基本搜
索、加速搜索和调整搜索⽅向三部分组成，
Powell ⽅法的具体步骤
2.4 Matlab 求⽆约束极值问题
在 Matlab ⼯具箱中，⽤于求解⽆约束极值问题的函数有 fminunc 和 fminarch，⽤ 法介绍如下。
Matlab 中 fminunc 的基本命令是
[X,FVAL]=FMINUNC(FUN,X0,OPTIONS,P1,P2, ...)
解：编写 M ⽂件 fun2.m 如下：
function [f,g]=fun2(x);
f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;
g=[-400*x(1)*(x(2)-x(1)^2)-2*(1-x(1));200*(x(2)-x(1)^2)];
编写主函数⽂件example6.m如下：
options = optimt('GradObj','on');
[x,y]=fminunc('fun2',rand(1,2),options)
即可求得函数的极⼩值。 在求极值时，也可以利⽤⼆阶导数，编写 M ⽂件 fun3.m 如下：
function [f,df,d2f]=fun3(x);
f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;
df=[-400*x(1)*(x(2)-x(1)^2)-2*(1-x(1));200*(x(2)-x(1)^2)];
d2f=[-400*x(2)+1200*x(1)^2+2,-400*x(1)
-400*x(1),200];
编写主函数⽂件example62.m如下：
options = optimt('GradObj','on','Hessian','on');
[x,y]=fminunc('fun3',rand(1,2),options)
即可求得函数的极⼩值。
求多元函数的极值也可以使⽤ Matlab 的 fminarch 命令，其使⽤格式为：
[X,FVAL,EXITFLAG,OUTPUT]＝FMINSEARCH(FUN,X0,OPTIONS,P1,P2,...)
function f=fun4(x);
f=sin(x)+3;
编写主函数⽂件example7.m如下：
x0=2;
[x,y]=fminarch(@fun4,x0)
即求得在初值 2 附近的极⼩点及极⼩值。
