论坛 › 数学中国数学建模网络挑战赛(TZMCM) › 数值优化方法

浅夏110 发表于 2020-5-21 10:10

数值优化方法

如果目标函数或约束条件中包含非线性函数的规划问题为非线性规划，求解非线性规划可用梯度法、牛顿法、拟牛顿法、高斯·塞德尔迭代法，BFGS等一系列方法。

非线性规划的实例与定义
如果目标函数或约束条件中包含非线性函数，就称这种规划问题为非线性规划问 题。一般说来，解非线性规划要比解线性规划问题困难得多。而且，也不象线性规划有 单纯形法这一通用方法，非线性规划目前还没有适于各种问题的一般算法，各个方法都 有自己特定的适用范围。 下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。

例一  投资决策问题

https://img-blog.csdnimg.cn/20190423235931251.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70

https://img-blog.csdnimg.cn/20190424000009458.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70

非线性规划的构成要素

https://img-blog.csdnimg.cn/20190424000036514.png

对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：

（i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基 础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。

（ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化 或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。

（iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或 “坏”的价值标准，并用某种数量形式来描述它。

（iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或 极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些 不等式或等式来表示。

1.2  线性规划与非线性规划的区别
如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行 域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任 意一点达到。

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

https://img-blog.csdnimg.cn/20190424000154729.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70

Matlab 中的命令是

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

https://img-blog.csdnimg.cn/20190424000211596.png

https://img-blog.csdnimg.cn/20190424000225724.png

解  （i）编写 M 文件 fun1.m 定义目标函数

function f=fun1(x);
f=sum(x.^2)+8;

（ii）编写M文件fun2.m定义非线性约束条件

function =fun2(x);
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=optimset('largescale','off');
=fmincon('fun1',rand(3,1),[],[],[],[],zeros(3,1),[], ...
'fun2', options)

https://img-blog.csdnimg.cn/20190424000453649.png

1.4  求解非线性规划的基本迭代格式
局部最优、整体最优的定义

https://img-blog.csdnimg.cn/20190424000511219.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70


求解非线性规划模型(NP)的基本迭代格式

https://img-blog.csdnimg.cn/20190424000528102.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70


如何构造每一轮的搜索方向和确定适当的步长

https://img-blog.csdnimg.cn/20190424000621861.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70


用基本迭代格式（1）求解(NP)的一般步骤

https://img-blog.csdnimg.cn/20190424001015313.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70

1.5  凸函数、凸规划

https://img-blog.csdnimg.cn/20190424001058238.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70


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

2  无约束问题
2.1  一维搜索方法
当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有： （1）试探法（“成功—失败”，斐波那契法， 0.618 法等） ；

（2）插值法（抛物线插值法，三次插值法等）；

（3）微积分中的求根法（切 线法，二分法等）。

试探法

https://img-blog.csdnimg.cn/20190424001559955.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70



应该按照怎样的规则来选取探索点，使给定的单峰区间的长度能尽快地缩短？

2.1.1 Fibonacci 法

https://img-blog.csdnimg.cn/20190424001633512.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70

https://img-blog.csdnimg.cn/20190424001719260.png


Finbonacci 法的具体步骤

https://img-blog.csdnimg.cn/20190424001758834.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70


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

https://img-blog.csdnimg.cn/20190424001823638.png

2.1.2     0.618 法
黄金分割数
若  ω > 0 ，满足比例关系

https://img-blog.csdnimg.cn/20190424002002392.png

黄金分割数和 Fibonacci 分数的关系

https://img-blog.csdnimg.cn/20190424002023126.png


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

https://img-blog.csdnimg.cn/2019042400210391.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70

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


2.3  无约束极值问题的解法
   无约束极值问题可表述为

https://img-blog.csdnimg.cn/20190424002333166.png

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

2.3.1  解析法
2.3.1.1  梯度法（最速下降法）

https://img-blog.csdnimg.cn/20190424002358900.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70


最速下降法的具体步骤


https://img-blog.csdnimg.cn/20190424002512972.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70

例 4  用最速下降法求解无约束非线性规划问题

https://img-blog.csdnimg.cn/20190424002548639.png


function =detaf(x);
f=x(1)^2+25*x(2)^2;
df=;

（ii）编写主程序文件zuisu.m如下：

clc
x=;
=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;
=detaf(x);
end
x,f0

2.3.1.2    Newton 法 https://img-blog.csdnimg.cn/20190424002830360.pnghttps://img-blog.csdnimg.cn/2019042400294532.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70Newton 法的具体步骤https://img-blog.csdnimg.cn/20190424003010195.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70例 5  用 Newton 法求解， https://img-blog.csdnimg.cn/20190424003037230.png（ii）编写 M 文件 nwfun.m 如下：
function =nwfun(x);
f=x(1)^4+25*x(2)^4+x(1)^2*x(2)^2;
df=;
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=;
=nwfun(x);
while norm(g1)>0.00001           
    p=-inv(g2)*g1;   
    x=x+p;
    =nwfun(x);
end
x, f0

如果目标函数是非二次函数，一般地说，用 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


https://img-blog.csdnimg.cn/20190424003359674.png.

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

拟牛顿法

https://img-blog.csdnimg.cn/20190424003433212.png

如何构造Hesse阵的近似矩阵---拟 Newton 条件

https://img-blog.csdnimg.cn/2019042400355479.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70

尺度矩阵的推导


https://img-blog.csdnimg.cn/20190424003715880.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70


https://img-blog.csdnimg.cn/20190424003735185.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70

https://img-blog.csdnimg.cn/20190424003808356.png

DFP 变尺度法的计算步骤总结

https://img-blog.csdnimg.cn/20190424003839854.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70

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

Powell 方法的具体步骤

https://img-blog.csdnimg.cn/20190424003946812.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70

https://img-blog.csdnimg.cn/2019042400400498.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70



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

https://img-blog.csdnimg.cn/20190424004122815.png

Matlab 中 fminunc 的基本命令是

=FMINUNC(FUN,X0,OPTIONS,P1,P2, ...)

https://img-blog.csdnimg.cn/20190424004150534.png

https://img-blog.csdnimg.cn/20190424004204278.png

解：编写 M 文件 fun2.m 如下：

function =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 = optimset('GradObj','on');
=fminunc('fun2',rand(1,2),options)




即可求得函数的极小值。 在求极值时，也可以利用二阶导数，编写 M 文件 fun3.m 如下：

function =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 = optimset('GradObj','on','Hessian','on');
=fminunc('fun3',rand(1,2),options)

options = optimset('GradObj','on','Hessian','on');
=fminunc('fun3',rand(1,2),options)


即可求得函数的极小值。
求多元函数的极值也可以使用 Matlab 的 fminsearch 命令，其使用格式为：

＝FMINSEARCH(FUN,X0,OPTIONS,P1,P2,...)


https://img-blog.csdnimg.cn/201904240044369.png

function f=fun4(x);
f=sin(x)+3;

编写主函数文件example7.m如下：

x0=2;
=fminsearch(@fun4,x0)


即求得在初值 2 附近的极小点及极小值。
————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89483975

查看完整版本: 数值优化方法