第三讲一维优化方法精选PPT.ppt

《第三讲一维优化方法精选PPT.ppt》由会员分享，可在线阅读，更多相关《第三讲一维优化方法精选PPT.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第1页，本讲稿共62页第三章第三章 一维优化方法一维优化方法n本章所解决的基本问题是对一维目标函数本章所解决的基本问题是对一维目标函数 F(x)求最优点求最优点的问题，它虽然是求单变量极值问题，考虑到很多时候的问题，它虽然是求单变量极值问题，考虑到很多时候函数的求导比较困难，甚至根本不可导，所以在最优化函数的求导比较困难，甚至根本不可导，所以在最优化技术中一般不用解析法而是采用直接探索方法求最优点，技术中一般不用解析法而是采用直接探索方法求最优点，对单变量直接探索称为一维探索或一维搜索，这种求优的对单变量直接探索称为一维探索或一维搜索，这种求优的方法称为一维优化方法方法称为一维优化方法。n对

2、于多维的优化问题，一般是转化为一维问题处理，所以对于多维的优化问题，一般是转化为一维问题处理，所以一维优化方法是用于求解多维优化的基础。一维优化方法是用于求解多维优化的基础。第2页，本讲稿共62页二维优化问题中一维搜索二维优化问题中一维搜索对于任意一次迭代计算，总是希望对于任意一次迭代计算，总是希望从已知的点从已知的点 x(k)出发，沿给定的方向出发，沿给定的方向 s(k)搜索到目标函数极小值点搜索到目标函数极小值点 x(k+1)，即求参数，即求参数 a 的一个的一个最优步长最优步长因子因子a(k)，使：，使：F(x(k+1)=minF(x(k)+a(k)s(k)这种在给定方向上确定最优步长的

3、过程，在多维优化过程中是多次反复进这种在给定方向上确定最优步长的过程，在多维优化过程中是多次反复进行的，所以说一维搜索是解多维优化问题的基础。行的，所以说一维搜索是解多维优化问题的基础。上述极小化问题实际上是以上述极小化问题实际上是以a为变量为变量的一维优化问题，表示为：的一维优化问题，表示为：minf(a)第3页，本讲稿共62页第三章第三章 一维优化方法一维优化方法ppFibonacciFibonacci法法法法/分数法分数法分数法分数法pp格点法格点法格点法格点法pp黄金分割法黄金分割法黄金分割法黄金分割法*pp二次插值法二次插值法二次插值法二次插值法*3.1 3.1 初始搜索区间的确定初

4、始搜索区间的确定*3.2 一维搜索的最优化方法一维搜索的最优化方法p p试探搜索试探搜索试探搜索试探搜索p p前进搜索前进搜索前进搜索前进搜索p p后退搜索后退搜索后退搜索后退搜索u一维搜索一般分两一维搜索一般分两步进行。第一步是步进行。第一步是在在s s(k k)方向上确定函方向上确定函数值最小点所在区数值最小点所在区间，第二步是求出间，第二步是求出该区间内的最优步该区间内的最优步长因子长因子a a(k k)第4页，本讲稿共62页3.1 搜索区间的确定搜索区间的确定 在一维搜索时，需要确定一个搜索区间在一维搜索时，需要确定一个搜索区间 a a，b b，此区间必须包含函数的极小点，此区间必须包

5、含函数的极小点 x x*，因此搜索区间必须是因此搜索区间必须是单峰区间单峰区间，即该区间内的函数值呈现，即该区间内的函数值呈现“高高-低低-高高”的的趋势。如图所示，通过将搜索区间趋势。如图所示，通过将搜索区间 a a，b b 逐渐缩小，直至足够小，就可以得到近似逐渐缩小，直至足够小，就可以得到近似最优点。最优点。第5页，本讲稿共62页确定初始搜索区间确定初始搜索区间进退法进退法对于比较简单的一维优化问题，其搜索区间可以根据实对于比较简单的一维优化问题，其搜索区间可以根据实际情况确定，但对于多维优化问题，在每一次一维搜索际情况确定，但对于多维优化问题，在每一次一维搜索之前都用人为方法确定搜索区

6、间是很困难的。所以必须之前都用人为方法确定搜索区间是很困难的。所以必须建立一定的方法，使计算机在优化过程中自动地确定。建立一定的方法，使计算机在优化过程中自动地确定。第6页，本讲稿共62页一、试探搜索一、试探搜索1、若、若 y2 y1，则极小点位于则极小点位于x1点左方，应反向后退搜索点左方，应反向后退搜索前进前进搜索搜索后后退退搜搜索索x1x1x2x2x3x3h02h0h02h0注意：注意：x1x2互换后再互换后再取取x3y1y3y2y2y3y1设函数为设函数为 y=f(x),给定初始点为给定初始点为x1，选定的初始步长为，选定的初始步长为h0。由初始点由初始点 x1 沿沿 x 轴正向取轴正

7、向取 x2 点，点，x2=x1+h0，计算，计算 x1,x2 的函数值的函数值 y1,y2，比较比较 y1,y2 的大小，则极小点的位置有如图所示两种情况：的大小，则极小点的位置有如图所示两种情况：第7页，本讲稿共62页一、前进搜索一、前进搜索前进前进搜索搜索x1x2x3h02h0y1y3y2令令h h0，并使步长加倍，并使步长加倍 h2h，取得取得 x3点，点，x3 x2+h=x2+2h0，其函数值其函数值 y3与与y2 比较比较有如下情况：有如下情况：1、若、若y2 y2 y2y3，则继续前进搜索，各点，则继续前进搜索，各点变换如下：变换如下：x1 x2，y1 y2 x2 x3，y2 y3

8、第9页，本讲稿共62页三、后退搜索三、后退搜索x1x2h02h0注意：注意：x1x2互换后再互换后再取取x3y2y3y1令令 h -h0，并将，并将 x1 与与 x2 对调，对调，使使步长加倍步长加倍 h2h，取得，取得x3点，点，x3 x2+h，其函数值其函数值 y3与与 y2比较比较有如下情况：有如下情况：1、若、若y2 y2 y2y3，则继续后退搜索，各点变换，则继续后退搜索，各点变换如下：如下：x1 x2，y1 y2x2 x3，y2 y3x1x2x3h02h0y1y3y2x1x2x3h02h0y1y3y2第11页，本讲稿共62页四、进退法确定搜索区间流程图四、进退法确定搜索区间流程图第

9、12页，本讲稿共62页例题例题例题例题3.1：试用进退法确定函数：试用进退法确定函数 f(x)=x2-6x+9 的一维优化搜索区间的一维优化搜索区间a，b，设初始点，设初始点 x1=0，初始步长，初始步长 h0=1解：解：计算过程如下计算过程如下:hh0=1x2x1+h=1y1=f(x1)=9,y2=f(x2)=4 由于由于y2y1，作前进搜索：，作前进搜索：h2h=2 x3x2+h=3 y3=f(x3)=0 比较比较y2,y3有有 y2y3，再做前进搜索，再做前进搜索x1x2=1,y1y2=4x2x3=3,y2y3=0h2h=4x3x2+h=7,y3=F(x3)=16第13页，本讲稿共62页

10、再比较再比较y2，y3有有y2y3，则取，则取ax1=1，bx3=7搜索区间搜索区间a，b为为1，7搜索过程见下图搜索过程见下图第14页，本讲稿共62页3.2 一维搜索的最优化方法一维搜索的最优化方法 在确定了搜索区间以后，一维优化的任务是采用某种方法将此在确定了搜索区间以后，一维优化的任务是采用某种方法将此区间逐步缩小，在满足收敛精度或迭代精度的情况下，使其达区间逐步缩小，在满足收敛精度或迭代精度的情况下，使其达到包含极小点的一个很小的邻域，以取得一个近似的最优点。到包含极小点的一个很小的邻域，以取得一个近似的最优点。一维优化的方法有如下几种：一维优化的方法有如下几种：1.1.分数法分数法/

11、Fibonacci/Fibonacci法法2.2.格点法格点法3.3.黄金分割法黄金分割法 4.4.二次插值法二次插值法第15页，本讲稿共62页Fibonacci数列数列13世纪的意大利数学家斐波那契世纪的意大利数学家斐波那契(Fibonacci)提出提出了这样一个问题：假定一对兔子在它们出生整整了这样一个问题：假定一对兔子在它们出生整整两个月以后可以生一对小兔子，其后每隔一个月两个月以后可以生一对小兔子，其后每隔一个月又可以再生一对小兔子。假定现在在一个笼子里又可以再生一对小兔子。假定现在在一个笼子里有一对刚生下来的小兔子，请问一年以后笼子里有一对刚生下来的小兔子，请问一年以后笼子里应该有几

12、对兔子？应该有几对兔子？第16页，本讲稿共62页Fibonacci数列数列斐波那契斐波那契(Fibonacci)数列：数列：0,1,1,2,3,5,8,13.第17页，本讲稿共62页Fibonacci数列的性质数列的性质n数学定义：数学定义：F0=0；F1=1；Fn=F n-1+F n 2，n22 数列数列Fn 称为称为Fibonacci 数列，数列，Fn称为第称为第n 个个Fibonacci 数，数，相邻两个相邻两个Fibonacci 数之比数之比Fn-1/Fn 称为称为称为称为Fibonacci 分数。分数。第18页，本讲稿共62页一维搜索算法一维搜索算法试探法原理试探法原理试探法主要有：

13、n 斐波那契法（序贯实验法）；n 黄金分割法(0.618法)第19页，本讲稿共62页试探法原理试探法原理 在区间在区间 a,b内任取两点内任取两点 a1 和和 b1，a1 b1，并计算函数，并计算函数值值 f(a1)和和 f(b1)，可能出现两种情况：，可能出现两种情况：f(a1)0 0，确定搜索次数，确定搜索次数 n。第23页，本讲稿共62页Fibonacci法算法步骤法算法步骤 斐波那契法寻优收敛快，计算次数少，然而每步取斐波那契法寻优收敛快，计算次数少，然而每步取点繁琐，且各步点繁琐，且各步缩短率缩短率不同。为此，引出黄金分割不同。为此，引出黄金分割法。法。第三步：第三步：k=n-1时，

14、时，t1=t2=(a+b)/2，无法比较，此时取，无法比较，此时取第24页，本讲稿共62页黄金分割法黄金分割法1)若若y1 y2，则极小点必在区间，则极小点必在区间a,x2内，令内，令b=x2，新区间为，新区间为a,x22)若若y1y2，则极小点必在区间，则极小点必在区间x1,b内，令内，令a=x1，新区间为，新区间为x1,b黄金分割法适用于黄金分割法适用于a,b区间上的任何单峰函数求极小值问题。对函区间上的任何单峰函数求极小值问题。对函数除要求单峰外不作其它要求，甚至可以不连续。因此适应面广数除要求单峰外不作其它要求，甚至可以不连续。因此适应面广一、黄金分割法的原理一、黄金分割法的原理在搜索

15、区间在搜索区间a,b内适当插入两点内适当插入两点 x1,x2，x1f(x3)，则新区间为，则新区间为a,x1。设区。设区间缩短率为间缩短率为 2。为保持相同的区间缩短率，应有为保持相同的区间缩短率，应有：证明：证明：由此可得：由此可得：=0.618=0.618。因而黄金分割法又称。因而黄金分割法又称0.6180.618法，是一种法，是一种等比例缩短区间的直接搜索法等比例缩短区间的直接搜索法第28页，本讲稿共62页黄金分割法可使相邻两次搜索区间都具有相同的缩短率黄金分割法可使相邻两次搜索区间都具有相同的缩短率0.618。因而。因而内分点的取点规则为：内分点的取点规则为：x1=a+0.382(b-

16、a)x2=a+0.618(b-a)终止原则：终止原则：最优解：最优解：k 为缩短区间的次数为缩短区间的次数第29页，本讲稿共62页黄金分割法的搜索过程黄金分割法的搜索过程1、给出初始搜索区间、给出初始搜索区间a,b及收敛精度及收敛精度 ；2、按坐标点计算公式计算，并计算相应的函数值；、按坐标点计算公式计算，并计算相应的函数值；3、缩短搜索区间；、缩短搜索区间；4、检查是否满足收敛条件；、检查是否满足收敛条件；5、若满足收敛条件，则取最后两点的平均值作为极小点的、若满足收敛条件，则取最后两点的平均值作为极小点的近似解。近似解。第30页，本讲稿共62页黄黄金金分分割割法法的的流流程程图图第31页，

17、本讲稿共62页例题例题例题例题3.3 试用黄金分割法求目标函数试用黄金分割法求目标函数 f(x)=x2-6x+9 的最优解。给定初始的最优解。给定初始区间区间1，7，收敛精度，收敛精度=0.4。解解：第一次区间缩短计算过程：第一次区间缩短计算过程：计算两内点及对应函数值：计算两内点及对应函数值：x1=a+0.382(b-a)=3.292 y1=f(x1)=0.085264x2=a+0.618(b-a)=4.708 y2=f(x2)=2.917264 作数值比较，可见作数值比较，可见y1x2?f2fP*?f2fP*?x1 xp*f1 fP*x3 x2 f3 f2x2 xp*f2 fP*x1 x2

18、 f1 f2x2 xp*f2 fP*x3 xp*f3 fP*出口出口YYYNNNabcd第51页，本讲稿共62页终止准则及最优解终止准则及最优解x*xp*(k)f*f(x*)最优解：最优解：终止准则：终止准则：第52页，本讲稿共62页二二次次插插值值算算法法的的流流程程图图说明三点在一说明三点在一直线上直线上说明说明xp*落在区间落在区间x1,x3外外第53页，本讲稿共62页例题例题3.4例题例题3.4 试用二次插值法求函数试用二次插值法求函数 f(x)=(x-3)2 的最优解，初始区间为的最优解，初始区间为1，7，精度，精度=0.01解解：(1)初始插值节点初始插值节点x1=a=1,f1=f

19、(x1)=4x2=0.5(a+b)=4,f2=f(x2)=1x3=b=7,f3=f(x3)=16(2)计算插值函数的极小点与极小值计算插值函数的极小点与极小值第54页，本讲稿共62页例题例题3.4(3)缩短区间缩短区间因有因有 ，故有，故有x1=1,f1=4x2xp*(1)=3,f2=0 x3x2=4,f3=1(4)重复步骤重复步骤(2)c1=-1 c2=1 (5)检查终止条件检查终止条件获得最优解获得最优解xp*(2)=3fp*(2)=0第55页，本讲稿共62页例题例题3.5例题例题3.5 用二次差值法求非二次函数用二次差值法求非二次函数 的最优解。初始的最优解。初始区间端点为区间端点为a=

20、-0.5,b=2.5。精度要求。精度要求=0.005(1)初始插值节点初始插值节点x1=a=-0.5,f1=f(x1)=-0.851279x2=0.5(a+b)=1 f2=f(x2)=-2.610944x3=b=2.5,f3=f(x3)=15.615452(2)(2)计算计算 与与 c1=5.488910,c2=4.441347解：解：解：解：第56页，本讲稿共62页例题例题3.5(3)(3)缩短区间缩短区间因有因有 ，故取故取x1=-0.5,f1=-0.851279x2=0.382067,f2=-20927209x3=1,f3=-2.610944(4)(4)对新区间重复步骤二对新区间重复步骤

21、二c1=-1.17311,c2=1.910196(5)(5)检查终止条件检查终止条件未满足终止条件，返回步骤（未满足终止条件，返回步骤（未满足终止条件，返回步骤（未满足终止条件，返回步骤（3 3）第57页，本讲稿共62页计算次数12345x1x2x3f1f2f3c1c2xp*fp*-0.51.02.5-0.851279-2.61094415.6154525.4889104.4413470.382067-2.927209-0.50.3820671.0-0.851279-2.927209-2.610944-1.173111.9101960.557065-3.0404500.1749980.3820

22、670.5570651.0-2.927209-3.040450-2.6109440.5118112.6164330.593226-3.0465340.0361610.5570650.5932261.0-3.040450-3.046534-2.6109440.9696822.7974490.605217-3.0471450.0119910.5932260.6052171.0-3.046534-3.047145-2.6109441.0708402.8415480.608188-3.0471880.002971计算结果表计算结果表第58页，本讲稿共62页经五次差值计算后，得得最优解第59页，本讲稿共

23、62页一维优化方法的比较一维优化方法的比较6格点法格点法的结构及程序很简单的结构及程序很简单,但效率偏低；但效率偏低；6黄金分割法黄金分割法的结构简单，使用可靠，但效率也不高；的结构简单，使用可靠，但效率也不高；6格点法格点法和和黄金分割法黄金分割法适于低维优化问题中的一维搜索；适于低维优化问题中的一维搜索；6二次插值法二次插值法在同样搜索次数下，其计算精度更高，但程序略在同样搜索次数下，其计算精度更高，但程序略复杂，可靠性差些，对高维数的优化问题更适宜，经过某些复杂，可靠性差些，对高维数的优化问题更适宜，经过某些技术处理，方法的可靠度可大为提高。技术处理，方法的可靠度可大为提高。第60页，本

24、讲稿共62页作业作业1.用用进退法进退法确定函数确定函数 f(x)=3x3-8x+9 的一维优化初始区间，的一维优化初始区间，给定初始点给定初始点 x1=0，初始进退距，初始进退距 h0=0.12.用用黄金分割法黄金分割法求函数求函数 f(x)=x(x+2)经过两次区间缩短后经过两次区间缩短后的区间范围、区间长度和近似优化解。设定初始区间的区间范围、区间长度和近似优化解。设定初始区间端点端点a=-3，b=5。3.用用二次插值法二次插值法求函数求函数 f(x)=8x3-2x2-7x+3的最优解，给定初始的最优解，给定初始区间端点区间端点a=0,b=2，终止迭代的点距精度取，终止迭代的点距精度取=0.01=0.01第61页，本讲稿共62页作业作业4.在一维优化问题中，设初始区间长度为在一维优化问题中，设初始区间长度为l，现规定，只通，现规定，只通过计算六个点的函数值作比较来确定最后缩短的区间：试回答过计算六个点的函数值作比较来确定最后缩短的区间：试回答下面的问题：下面的问题：用格点法求解时，每一次区间缩短时的内分点 n 取多大才能使最后的区间缩得最小？最终的区间长度l为多少？若用上面格点法区间缩得最小的方案所得之结果，与同样进行六次 函数值计算的黄金分割法结果相比较，哪种方法的最后区间更小些？第62页，本讲稿共62页