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

1第一页，本课件共有62页第三章第三章 一维优化方法一维优化方法n本章所解决的基本问题是对一维目标函数本章所解决的基本问题是对一维目标函数 F(x)求最求最优点的问题，它虽然是求单变量极值问题，考虑到优点的问题，它虽然是求单变量极值问题，考虑到很多时候函数的求导比较困难，甚至根本不可导，很多时候函数的求导比较困难，甚至根本不可导，所以在最优化技术中一般不用解析法而是采用直接所以在最优化技术中一般不用解析法而是采用直接探索方法求最优点，探索方法求最优点，对单变量直接探索称为一维探索对单变量直接探索称为一维探索或一维搜索，这种求优的方法称为一维优化方法或一维搜索，这种求优的方法称为一维优化方法。n对于多维的优化问题，一般是转化为一维问题处理，所对于多维的优化问题，一般是转化为一维问题处理，所以一维优化方法是用于求解多维优化的基础。以一维优化方法是用于求解多维优化的基础。第二页，本课件共有62页二维优化问题中一维搜索二维优化问题中一维搜索对于任意一次迭代计算，总是希对于任意一次迭代计算，总是希望从已知的点望从已知的点 x(k)出发，沿给定出发，沿给定的方向的方向 s(k)搜索到目标函数极小值搜索到目标函数极小值点点 x(k+1)，即求参数，即求参数 a 的一个的一个最优最优步长因子步长因子a(k)，使：，使：F(x(k+1)=minF(x(k)+a(k)s(k)这种在给定方向上确定最优步长的过程，在多维优化过程中是多次这种在给定方向上确定最优步长的过程，在多维优化过程中是多次反复进行的，所以说一维搜索是解多维优化问题的基础。反复进行的，所以说一维搜索是解多维优化问题的基础。上述极小化问题实际上是以上述极小化问题实际上是以a为变为变量的一维优化问题，表示为：量的一维优化问题，表示为：minf(a)第三页，本课件共有62页第三章第三章 一维优化方法一维优化方法ppFibonacciFibonacci法法法法/分数法分数法分数法分数法pp格点法格点法格点法格点法pp黄金分割法黄金分割法黄金分割法黄金分割法*pp二次插值法二次插值法二次插值法二次插值法*3.1 初始搜索区间的确定初始搜索区间的确定*3.2 一维搜索的最优化方法一维搜索的最优化方法p p试探搜索试探搜索试探搜索试探搜索p p前进搜索前进搜索前进搜索前进搜索p p后退搜索后退搜索后退搜索后退搜索u一维搜索一般分两一维搜索一般分两步进行。第一步是步进行。第一步是在在s s(k k)方向上确定方向上确定函数值最小点所在函数值最小点所在区间，第二步是求区间，第二步是求出该区间内的最优出该区间内的最优步长因子步长因子a a(k k)第四页，本课件共有62页3.1 搜索区间的确定搜索区间的确定 在一维搜索时，需要确定一个搜索区间在一维搜索时，需要确定一个搜索区间 a a，b b，此区间必须包含函数的极，此区间必须包含函数的极小点小点 x x*，因此搜索区间必须是因此搜索区间必须是单峰区间单峰区间，即该区间内的函数值呈现，即该区间内的函数值呈现“高高-低低-高高”的趋势。如图所示，通过将搜索区间的趋势。如图所示，通过将搜索区间 a a，b b 逐渐缩小，直至足够小，逐渐缩小，直至足够小，就可以得到近似最优点。就可以得到近似最优点。第五页，本课件共有62页确定初始搜索区间确定初始搜索区间进退法进退法对于比较简单的一维优化问题，其搜索区间可以对于比较简单的一维优化问题，其搜索区间可以根据实际情况确定，但对于多维优化问题，在每根据实际情况确定，但对于多维优化问题，在每一次一维搜索之前都用人为方法确定搜索区间是一次一维搜索之前都用人为方法确定搜索区间是很困难的。所以必须建立一定的方法，使计算机很困难的。所以必须建立一定的方法，使计算机在优化过程中自动地确定。在优化过程中自动地确定。第六页，本课件共有62页一、试探搜索一、试探搜索1、若、若 y2 y1，则极小点位于则极小点位于x1点左方，应反向后退搜索点左方，应反向后退搜索前前进进搜搜索索后后退退搜搜索索x1x1x2x2x3x3h02h0h02h0注意：注意：x1x2互换后再互换后再取取x3y1y3y2y2y3y1设函数为设函数为 y=f(x),给定初始点为给定初始点为x1，选定的初始步长为，选定的初始步长为h0。由初始点由初始点 x1 沿沿 x 轴正向取轴正向取 x2 点，点，x2=x1+h0，计算，计算 x1,x2 的函数值的函数值 y1,y2，比较，比较 y1,y2 的大小，则极小点的位置有如图所示两种情况：的大小，则极小点的位置有如图所示两种情况：第七页，本课件共有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第九页，本课件共有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第十一页，本课件共有62页四、进退法确定搜索区间流程图四、进退法确定搜索区间流程图第十二页，本课件共有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第十三页，本课件共有62页再比较再比较y2，y3有有y2y3，则取，则取ax1=1，bx3=7搜索区间搜索区间a，b为为1，7搜索过程见下图搜索过程见下图第十四页，本课件共有62页3.2 一维搜索的最优化方法一维搜索的最优化方法 在确定了搜索区间以后，一维优化的任务是采用某种方法将此在确定了搜索区间以后，一维优化的任务是采用某种方法将此区间逐步缩小，在满足收敛精度或迭代精度的情况下，使其达区间逐步缩小，在满足收敛精度或迭代精度的情况下，使其达到包含极小点的一个很小的邻域，以取得一个近似的最优点。到包含极小点的一个很小的邻域，以取得一个近似的最优点。一维优化的方法有如下几种：一维优化的方法有如下几种：1.1.分数法分数法/Fibonacci/Fibonacci法法2.2.格点法格点法3.3.黄金分割法黄金分割法 4.4.二次插值法二次插值法第十五页，本课件共有62页Fibonacci数列数列13世纪的意大利数学家斐波那契世纪的意大利数学家斐波那契(Fibonacci)提提出了这样一个问题：假定一对兔子在它们出生出了这样一个问题：假定一对兔子在它们出生整整两个月以后可以生一对小兔子，其后每隔整整两个月以后可以生一对小兔子，其后每隔一个月又可以再生一对小兔子。假定现在在一一个月又可以再生一对小兔子。假定现在在一个笼子里有一对刚生下来的小兔子，请问一年个笼子里有一对刚生下来的小兔子，请问一年以后笼子里应该有几对兔子？以后笼子里应该有几对兔子？第十六页，本课件共有62页Fibonacci数列数列斐波那契斐波那契(Fibonacci)数列：数列：0,1,1,2,3,5,8,13.第十七页，本课件共有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 分数。分数。第十八页，本课件共有62页一维搜索算法一维搜索算法试探法原理试探法原理试探法主要有：n 斐波那契法（序贯实验法）；n 黄金分割法(0.618法)第十九页，本课件共有62页试探法原理试探法原理 在区间在区间 a,b内任取两点内任取两点 a1 和和 b1，a1 b1，并计算函，并计算函数值数值 f(a1)和和 f(b1)，可能出现两种情况：，可能出现两种情况：f(a1)0 0，确定搜索次数，确定搜索次数 n。第二十三页，本课件共有62页Fibonacci法算法步骤法算法步骤 斐波那契法寻优收敛快，计算次数少，然而每步斐波那契法寻优收敛快，计算次数少，然而每步取点繁琐，且各步取点繁琐，且各步缩短率缩短率不同。为此，引出黄金不同。为此，引出黄金分割法。分割法。第三步：第三步：k=n-1时，时，t1=t2=(a+b)/2，无法比较，此时取，无法比较，此时取第二十四页，本课件共有62页黄金分割法黄金分割法1)若若y1 y2，则极小点必在区间，则极小点必在区间a,x2内，令内，令b=x2，新区间为，新区间为a,x22)若若y1y2，则极小点必在区间，则极小点必在区间x1,b内，令内，令a=x1，新区间为，新区间为x1,b黄金分割法适用于黄金分割法适用于a,ba,b区间上的任何单峰函数求极小值问题。对函数除要区间上的任何单峰函数求极小值问题。对函数除要求单峰外不作其它要求，甚至可以不连续。因此适应面广求单峰外不作其它要求，甚至可以不连续。因此适应面广一、黄金分割法的原理一、黄金分割法的原理在搜索区间在搜索区间a,b内适当插入两点内适当插入两点 x1,x2，x1f(x3)，则新区间为，则新区间为a,x1。设区间缩短率为。设区间缩短率为 2 2。为保持相同的区间缩短率，应有为保持相同的区间缩短率，应有：证明：证明：由此可得：由此可得：=0.618=0.618。因而黄金分割法又称。因而黄金分割法又称0.6180.618法，是一种等法，是一种等比例缩短区间的直接搜索法比例缩短区间的直接搜索法第二十八页，本课件共有62页黄金分割法可使相邻两次搜索区间都具有相同的缩短率黄金分割法可使相邻两次搜索区间都具有相同的缩短率0.618。因而内分点。因而内分点的取点规则为：的取点规则为：x1=a+0.382(b-a)x2=a+0.618(b-a)终止原则：终止原则：最优解：最优解：k 为缩短区间的次数为缩短区间的次数第二十九页，本课件共有62页黄金分割法的搜索过程黄金分割法的搜索过程1、给出初始搜索区间、给出初始搜索区间a,b及收敛精度及收敛精度 ；2、按坐标点计算公式计算，并计算相应的函数值；、按坐标点计算公式计算，并计算相应的函数值；3、缩短搜索区间；、缩短搜索区间；4、检查是否满足收敛条件；、检查是否满足收敛条件；5、若满足收敛条件，则取最后两点的平均值作为极小点、若满足收敛条件，则取最后两点的平均值作为极小点的近似解。的近似解。第三十页，本课件共有62页黄黄金金分分割割法法的的流流程程图图第三十一页，本课件共有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 f1 f2x2 xp*f2 fP*x3 xp*f3 fP*出口出口YYYNNNabcd第五十一页，本课件共有62页终止准则及最优解终止准则及最优解x*xp*(k)f*f(x*)最优解：最优解：终止准则：终止准则：第五十二页，本课件共有62页二二次次插插值值算算法法的的流流程程图图说明三点在一说明三点在一直线上直线上说明说明xp*落在区间落在区间x1,x3外外第五十三页，本课件共有62页例题例题3.4例题例题3.4 试用二次插值法求函数试用二次插值法求函数 f(x)=(x-3)2 的最优解，初始区间为的最优解，初始区间为1，7，精度，精度=0.01解解：(1)初始插值节点初始插值节点x1=a=1,f1=f(x1)=4x2=0.5(a+b)=4,f2=f(x2)=1x3=b=7,f3=f(x3)=16(2)计算插值函数的极小点与极小值计算插值函数的极小点与极小值第五十四页，本课件共有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第五十五页，本课件共有62页例题例题3.5例题例题3.5 用二次差值法求非二次函数用二次差值法求非二次函数 的最优解。初始区间的最优解。初始区间端点为端点为a=-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解：解：解：解：第五十六页，本课件共有62页例题例题3.5(3)(3)缩短区间缩短区间因有因有 ，故取故取x1=-0.5,f1=-0.851279x2=0.382067,f2=-20927209x3=1,f3=-2.610944(4)(4)对新区间重复步骤二对新区间重复步骤二c1=-1.17311,c2=1.910196(5)(5)检查终止条件检查终止条件未满足终止条件，返回步骤（未满足终止条件，返回步骤（未满足终止条件，返回步骤（未满足终止条件，返回步骤（3 3）第五十七页，本课件共有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.3820670.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计算结果表计算结果表第五十八页，本课件共有62页经五次差值计算后，得得最优解第五十九页，本课件共有62页一维优化方法的比较一维优化方法的比较6格点法格点法的结构及程序很简单的结构及程序很简单,但效率偏低；但效率偏低；6黄金分割法黄金分割法的结构简单，使用可靠，但效率也不高；的结构简单，使用可靠，但效率也不高；6格点法格点法和和黄金分割法黄金分割法适于低维优化问题中的一维搜索；适于低维优化问题中的一维搜索；6二次插值法二次插值法在同样搜索次数下，其计算精度更高，但程序在同样搜索次数下，其计算精度更高，但程序略复杂，可靠性差些，对高维数的优化问题更适宜，经过某略复杂，可靠性差些，对高维数的优化问题更适宜，经过某些技术处理，方法的可靠度可大为提高。些技术处理，方法的可靠度可大为提高。第六十页，本课件共有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第六十一页，本课件共有62页作业作业4.在一维优化问题中，设初始区间长度为在一维优化问题中，设初始区间长度为l，现规定，只，现规定，只通过计算六个点的函数值作比较来确定最后缩短的区间：通过计算六个点的函数值作比较来确定最后缩短的区间：试回答下面的问题：试回答下面的问题：用格点法求解时，每一次区间缩短时的内分点 n 取多大才能使最后的区间缩得最小？最终的区间长度l为多少？若用上面格点法区间缩得最小的方案所得之结果，与同样进行六次 函数值计算的黄金分割法结果相比较，哪种方法的最后区间更小些？第六十二页，本课件共有62页