机械优化设计方法第四章一维搜索.ppt

第四章 一维搜索的最优化方法,4-1 概述,求解一元函数f()的极小点和极小值，如图4-1所示的*与f(*)问题，就是一维最优化问题，其数值迭代方法亦称为一维搜索方法。,一维最优化方法是优化方法中最简单、最基本的方法。它不仅可以用来解决一维目标函数的最优化问题 更重要的是在多维目标函数的求优过程中，常常需要通过一系列的一维优化来实现。由前述关于多维迭代寻优的讨论中，在任一次迭代计算中，当确定搜索方向S(k)之后，新设计点X(k+1)=X(k)+S(k)，总是位于过X(k)点的S(k)方向上，而不论步长因子数值如何。,图4-2表示二维优化问题的情况，S(k)应选择使在X(k)点邻域目标函数值下降的方向，同时希望选某一特定的=(k)，使产生的新点X(k+1)是在过X(k)点和S(k)方向上的目标函数的极小点。即有,这个特定的步长因子(k)称为最优步长因子。然后，把该X(k+1)点作为下次迭代的出发点，另选新的搜索方向S(k+1)，获得S(k+1)方向上的目标函数极小点，如此重复上述过程，直至把目标函数逼近理论极小值，实现多维目标函数寻优。,f(X(k)+(k)S(k)=min f(X(k)+S(k)（4-1）,式(4-1)表示过X(k)点沿S(k)方向搜索寻优，显然X(k)和S(k)已确定，即可认为是固定的量，所以求解步长(k)使函数f(X(k)+S(k)值为极小的问题，也就是求解一元函数f()=f(X(k)+S(k)的极小值问题。如图4-3所示，不论X属于几维向量，从定点X(k)出发，沿确定方向S(k)搜索，作为单变量寻优求满足式(4-1)的最优步长因子(k)的过程亦是一维搜索过程。一般来说，从X(k)点出发，沿方向S(k)求函数f()=f(X(k)+S(k)的极小点X(k+1)就构成某些多维最优化方法的一种基本过程。所以一维搜索的效率、稳定性等的索方法与之互相配合，否则将会带来占机时间长，或破坏算法稳定性等缺陷。,一维搜索最优化方法很多，有格点法、黄金分割法(0.618法)、分数法和插值法等。我们这里将介绍常用的0.618法和二次插值法。一维搜索过程总的可分为两大步骤：(1)确定函数f()的极小点(k)所在的初始搜索区间a，b；(2)在搜索区间a，b 中搜索寻优极小点(k)。,4-2 初始搜索区间的确定,要进行一维搜索，首先要确定极小点(k)所在的初始搜索区间a，b。用f()代表单变量函数，并假定是单峰函数，考虑的极值问题都是极小值问题。,如图4-4(a)所示，在极小点*左边，函数是严格减小的；而在*的右边，函数是严格增大的。设是(1)f(2)；若(1)*(图4-4(c)，则f(1)f(2)。由图4-4(d)所示，单蜂函数的函数值具有高一低一高的特征。,若找到(1)(2)(3)，且f(1)f(2)，f(2)f(3)，则*必在区间(1)，(3)之间。确定极小点的初始搜索区间就要利用这个函数值高一低一高，亦即函数值两头大中间小的特征。需要指出，对于预先有把握估计的区间值，可以直接给出。当事先难以估计区间的范围时初始区间可通过某种方法予以确定。下面介绍一种进退算法来确定初始搜索区间。,设函数f()为定义在区间a,b上的单变量函数，初始搜索区间a,b 单变量函数，*是f()在区间a,b上的全域极小点，若存在x1,x2a,b，并有x1 f(x2)，则x1,b是f()极小值点的一个搜索区间。,搜索区间,确定搜索区间的算法框图,某些情况下，目标函数的性态不明确，搜索区间无法人为地预先选定，因此需要采用一定的方法进行自动地寻找，以确定函数极小值点的搜索区间。下面介绍经常用的一种方法-进退法。基本思想：进退法也称成功-失败法。它是从事先给定的初始点(k)开始，沿搜索方向选定一步长h(k)，取得一个新点(k+1)=(k)+h(k)S(k)，计算目标函数值f(k+1)。若f(k+1)f(k)，即目标函数值下降，则称搜索成功，于是再加大步长前进搜索，直到目标函数值上升为止。如果从第一步(k)向前搜索目标函数值不下降，则称搜索失败，下一次就从初始点(k)开始，反方向以相同的步长h(k)后退，与前述方法相同，去寻找使目标函数值具有“大-小-大”特征的区间。,进退算法来确定初始搜索区间。,设给定某初始点(0)及初始步长h，求初始搜索区间的步骤(1)给定(0)、h,(0)值可任意选取,最好取(0)接近于极小点,或可取(0)=0。h为初始步长,h0，可取h=1。(2)令(0)(1),(1)+h(2)，得两个试点(1)、(2)。(1)(2)。计算其函数值f(1)和f(2)。令f(1)f1、f(2)f2。,(3)比较f1与f2。若f2f1,则作前进运算。以第二点(2)为起始点,以h为步长,前进搜索即可取得第三个试点(3)=(2)+h=(0)+2h，并计算f(3)f3。若f2f3，如图4-5(a)所示，则区间a，b(0),(0)+2h为初始搜索区间，即a=(0)，b(0)+2h；否则，即f2f3，则以(3)为起始点，按第二点(2)到第三点(3)的方向将步长再加倍，重复上述前进搜索运算，直到出现相继的三个试点，其两端试点的函数值大于中间试点的函数值为止。这时左端试点坐标即为a,端试点坐标即为b。如图4-5(b)所示，则区间a，b(0)+2h,(0)+8h为初始搜索区间，即a(0)+2h，b(0)+8h。,(4)如果在步骤(3)中的两个函数值有f3f1,则作后退运算。以第一点(1)为起始点,仍以h大小作为步长但反方向搜索取得第三个试点(3)=(1)h=(0)h,并计算f(3)f3。若f3f1如图4-6(a)所示,则区间a，b(0)-h，(0)+h为初始搜索区间，即a(0)-h,b(0)+h。否则,即f3 f1，则以(3)为起始点，按第一点(1)到第三点(3)的方向将步长再加倍,重复上述运算，直到出现相继的三个试点，其两端试点的函数值大于中间试点的函数值为止。这时左端试点坐标即为a，右端试点即为b。如图4-6(b)所示，则区间a，b(0)-7h，(0)-h为初始搜索区间，即a(0)-7h，b(0)-h。,上述计算步骤设计成如图4-7所示的计算程序框图，简称进退法算法框图。,例题4-1 用进退法确定函数f()=2-7+10的一维优化初始搜索区间a,b。设初始点(0)=0，初始步长h1。解：按图4-7所示算法框图进行计算(1)=(0)=0 f1=f(1)=10；(2)=(1)+h=1 f2=f(2)=4比较f2、f1，因f2f1，作前进运算(3)=(2)+h=2 f3=f(3)=0比较f2、f3，因f2f3，再作前进运算 h=21=2(1)=(2)=1 f1=f(1)=4；(2)=(3)=2 f2=f(2)=0；(3)=(2)+h=4 f3=f(3)=-2比较f2、f3，因f2f3，再作前进运算 h=22=4(1)=(2)=2 f1=f(1)=0(2)=(3)=4 f2=f(2)=-2(3)=(2)+h=8 f3=f(3)=18。此时f1f2、f2f3,故a=(1)=2，b=(3)=8,亦即初始搜索区间a，b2，8。,4-3 黄金分割法,一、消去法的基本原理 消去法的基本思路是：逐步缩小搜索区间，直至最小点存在的范围达到允许的误差范围为止。设一元函数f()如图4-8所示，起始搜索区间为a，b，*为所要寻求的函数的极小点。,在搜索区间a，b内任取两点(1)与(2)，且a(1)(2)b，计算函数f(1)与f(2)。当将f(1)与f(2)进行比较时，可能的猜况有下列三种：(1)f(1)f(2)：如图4-8(a)、(b)所示，这种情况下。可丢掉(2),b部分。而最小点*必在区间a,(2)内。(2)f(1)f(2)：如图4-8(c)、(d)所示，这种情况下，可丢掉a,(1)部分，而最小点*必在区间(1),b内。(3)f(1)f(2)：如图4-8(e)所示，这种情况下，不论丢掉a,(1)还是丢掉(2),b，最小点*必在留下的部分内。因此，只要在搜索区间内任取两点，计算它们的函数值并加以比较之后，总可以把搜索的区间缩小。这就是消去法的基本原理。,对于第(1)、(2)两种情况，经过缩小的区间内都保存了一个点的函数值,即f(1)或f(2)，只要再取一个点(3)，计算函数值f(3)并进行比较，就可以再次缩短区间进行序列消去。但对于第(3)情况，区间(1),(2)中没有已知点的函数值，若再次缩短区间必须计算两个点的函数值。为了简化迭代程序，可以把第(3)种情况合并到前面(1)、(2)两种情况之一中去，例如可以把上述三种情况合并为下述两种情况：(1)若f(1)f(2)，取区间a,(2)(2)若f(1)f(2)，取区间(1),b。这样做虽然对于原第(3)种情况所取的区间扩大了，但在进一步搜索时每次只要计算一个点，和第(1)、(2)种情况一致，简化了迭代程序。,二、“0.618”的由来,如图4-9所示，设区间a,b全长为L，在其内取两个对称计算点(1)和(2)，并令l/L=称为公比，无论如图(b)所示丢去(2),b，还是如图(c)所示丢去a,(1)、保留点在新区间a1,b1中相应线段比值仍为,由此得,解此方程得两个根，取其正根为,这种分割称为黄金分割、其比例系数为0.618只要第一个试点取在原始区间长的0.618处第二个试点在它的对称位置，就能保证无论经过多少次缩小区间，保留的点始终处在新区间的0.618处。再要进一步缩短区间，在其保留点的对称位置再取点作一次比较消去，这种分割每次消去时，区间的缩短率下变。均为0.618，此即0.618法名字的由来。,三、迭代过程及算法框图,0.618法的具体迭代过程如下：(1)在初始区间a，b内取两个计算点(1)与(2)，其值分别为(1)=b0.618(ba)(2)=a+0.618(ba)计算函数值f(1)、f(2)，且令f(1)f1、f(2)f2。（2)比较函数值，缩短搜索区间 1)若f1 f2，见图4-9(b)，则丢去区间(2)，b，取a,(2)为新区间a1，b1，在计算中作如下置换：(2)b,(1)(2),f1 f2,b0.618(ba)(1),f(1)f12)若f1f2，见图4-9(c)，则丢去区间a,(1)，取(1)，b 为新区间a1，b1，在计算中作如下置换：(1)a,(2)(1),f2 f1,a+0.618(ba)(2),f(2)f2(3)判断迭代终止条件 当缩短的新区间距离小于某一个预先规定的精度，即ba，终止迭代。此时，小区间内任一点均可作为f()极小值的近似点。例如可取区间的中点，即0.5(b+a)*。否则，返回第(2)步重新作进一步缩小区间的迭代计算。,0.618法的算法框图如图4-10所示。,例题4-2 用黄金分割法求一元函数f()=27+10的最优解。已知初始区间为2,8，取迭代精度=0.35。解：按图4-10所示算法框图进行计算(1)在初始区间a,b2，8中取计算点并计算函数值(1)=b0.618(ba)=4.292；f1=f(1)=1.622736(2)=a+0.618(ba)=5.70；f2=f(2)=2.625264(2)比较函数值，缩短搜索区间因有f1f2，则b=(2)=5.708，(2)=(1)=4.292，f2=f(2)=1.622736(1)=b0.618(ba)=3.416456，f1=f(1)=2.243020(3)判断迭代终止条件 ba=5.7082=3.708不满足迭代终止条件，比较函数值f1、f2继续缩短区间。将各次缩短区间的有关计算数据列于下表。,可见区间缩短6次后，区间长度为ba=3.697053.2863288=0.310722=0.35，迭代即可终止近似最优解为*=(a+b)/2=3.441689；f(*)=2.2466,4-4 二次插值法,一、基本原理 在求解一元函数f()的极小点时，常利用一个低次插值多项式p()来逼近原目标函数然后求该多项式的极小点(低次多项式的极小点比较容易计算)，并以此作为目标函数f()的近似极小点。如果其近似的程度尚未达到所要求的精度时，可以反复使用此法，逐次拟合，直到满足给定的精度时为止。常用的插值多项式p()为二次或三次多项式，分别称为二次插值法和三次插值法。由于二次插值法计算较简单且又有一定的精度，所以应用较广。下面介绍二次插值法的计算公式。,假定目标函数在初始搜索区间a，b 中有三点，(1)、(2)和(3)（a(1)(2)(3)b）,其函数值分别为f1、f2和f3(图4-11)，且满足f1f2，f2f3，即满足函数值为两头大中间小的性质。利用这三点及相应的函数值作一条二次曲线，其函数p()为一个二次多项式 p()=a0+a1+a22 式中，a0、a1、a2为待定系数。根据插值条件，插值函数p()与原函数f()在插值结点P1、P2、P3处函数值相等，得,为求插值多项式p()的极小点*；，可令其 p()=a0+a1+a22一阶导数为零，即,求得插值函数的极小点,要确定的系数a1，a2可在方程组中利用相邻两个方程消去a0得：,便得插值函数极小值点*p的计算公式：,把*p取作区间(1)，(3)内的另一个计算点，比较*p与(2)两点函数值的大小，在保持f()两头大中间小的前提下缩短搜索区间，从而构成新的三点搜索区间，再继续按上述方法进行三点二次插值运算，直到满足规定的精度要求为止，把得到的最后的*p作为f()的近似极小值点*。上述求极值点的方法称为三点二次插值法。为便于计算，可将上式改写为,式中,二、迭代过程及算法框图,(1)确定初始插值结点 通常取初始搜索区间a，b的两端点及中点为(1)=a,(3)=b,(2)=0.5(1)+(3)。计算函数值f1=f(1)、f2=f(2)和f3=f(3)。构成三个初始插值结点P1、P2、P3。(2)计算二次插值函数极小点*p 按式(4-10)计算*p，并将*p记作(4)点,计算f4=f(4)。若本步骤为对初始搜索区间的第一次插值或(2)点仍为初始给定点时，则进行下一步(3),否则转步骤(4)。(3)缩短搜索区间缩短搜索区间的原则是：比较函数值f2、f4取其小者所对应的点作为新的(2)点，并以此点左右两邻点分别取作新的(1)和(3)，构成缩短后的新搜索区(1),(3)。,其具体方法则如图4-12所示，根据原区间中(4)和(2)的相对位置以及函数值f2和f4比较有a、b、c、d四种情况，图中阴影线部分表示丢去的区间。在对新区间三个新点的代号作依次(1)、(2)、(3)的一般化处理后,计算其函数值,并令f1=f(1)、f2=f(2)和f3=f(3)，退回步骤（2）。,(4)判断迭代终止条件 在一般情况下，因(2)是前一次插值函数的极小值点，(4)是本次插值函数的极小值点，若(2)和(4)的距离足够小时，即满足|(4)(2)|或(4)和(2)两者原函数值已很接近，即满足|f4f2|，则停止迭代，这时，若f4f2，输出极小值点(4)*，极小值f4f(*)；否则,即f2f4时，输出极小值点(2)*,极小值f2f(*)。如不满足上述迭代终止条件、则返回步骤(3)，再次缩短搜索区间，直至最后满足终止条件。,二次插值法算法框图,算法框图中有几点需作些说明,1、判别框c2=0？若成立，按式(4-12)和式(4-11)则有说明三个插值结点P1(1),f1)、P2(2),f2)、P3(3),f3)在一条直线上；2、判别框(4)(1)(3)(4)0?若不成立，说明落(4)在区间(1)，(3)之外。上述两种情况只是在区间已缩得很小，由于三个插值结点已十分接近，计算机的舍入误差才可能使其发生。此时取(2)和f2作为最优解应是合理的。,3、在初始搜索区间第一次插值或(2)仍为初始给定点时，(2)和(4)并不代表前后二次插值函数极小点，因而判别式|(4)(2)|?并不能确切地反映该不该终止迭代，这时应进行步骤(3)缩短搜索区间，直至初始点(2)第一次由(4)代替，使用判别式|(4)(2)|?进行终止判别才具意义。为此，算法框图中设置开关k=0和k=1分别表示初始点(2)第一次由(4)代替前和后的状态。,例题43 用二次插值法求一元函数f()=27+10的最优解。已知初始区间为2，8，取终止迭代点距精度=0.01。解：按图413所示算法框图进行计算(1)确定初始插值结点(1)=a=2 f1=f(1)=0(3)=b=8 f3=f(3)=18(2)=(a+b)/2=5 f2=f(2)=0(2)计算插值函数极小点,(3)缩短搜索区间因(2)(4)，f2f2,故(3)=(2)=5 f3=0；(2)=(4)=3.5 f2=2.25；(1)=2 f1=0 开关k=1返回步骤(2)计算得c1=0，c2=10，(4)=3.5，f4=2.25(4)(1)(3)(4)=2.250(4)判断迭代终止条件|(4)(2)|=|3.53.5|=0满足迭代终止条件，得最优解*=(4)=3.5 f*=f(4)=2.25,