《维优化方法》PPT课件.ppt

1,第三章 一维优化方法,济南大学 机械设计系 王桂从,2,第三章 一维优化方法,本章所解决的基本问题是对一维目标函数 F(x) 求最优点的问题，它虽然是求单变量极值问题，考虑到很多时候函数的求导比较困难，甚至根本不可导，所以在最优化技术中一般不用解析法而是采用直接探索方法求最优点，对单变量直接探索称为一维探索或一维搜索，这种求优的方法称为一维优化方法。 对于多维的优化问题，一般是转化为一维问题处理，所以一维优化方法是用于求解多维优化的基础。,3,二维优化问题中一维搜索,对于任意一次迭代计算，总是希望从已知的点 x(k) 出发，沿给定的方向 s(k) 搜索到目标函数极小值点 x(k+1)，即求参数 a 的一个最优步长因子a(k)，使：,F(x(k+1) ) = minF(x(k) +a(k) s(k) ),这种在给定方向上确定最优步长的过程，在多维优化过程中是多次反复进行的，所以说一维搜索是解多维优化问题的基础。,上述极小化问题实际上是以a为变量的一维优化问题，表示为：minf(a),4,第三章 一维优化方法,Fibonacci法/分数法 格点法 黄金分割法* 二次插值法*,3.1 初始搜索区间的确定*,3.2 一维搜索的最优化方法,试探搜索 前进搜索 后退搜索,一维搜索一般分两步进行。第一步是在s(k)方向上确定函数值最小点所在区间，第二步是求出该区间内的最优步长因子a(k),5,3.1 搜索区间的确定,在一维搜索时，需要确定一个搜索区间a，b，此区间必须包含函数的极小点 x*，因此搜索区间必须是单峰区间，即该区间内的函数值呈现“高-低-高”的趋势。如图所示，通过将搜索区间a，b逐渐缩小，直至足够小，就可以得到近似最优点。,6,确定初始搜索区间进退法,对于比较简单的一维优化问题，其搜索区间可以根据实际情况确定，但对于多维优化问题，在每一次一维搜索之前都用人为方法确定搜索区间是很困难的。所以必须建立一定的方法，使计算机在优化过程中自动地确定。,7,一、试探搜索,1、若 y2 y1 ， 则极小点位于x1点左方，应反向后退搜索,前进搜索,后退搜索,x1,x1,x2,x2,x3,x3,h0,2h0,h0,2h0,注意：x1x2互换后再取x3,y1,y3,y2,y2,y3,y1,设函数为 y =f(x) ,给定初始点为x1 ，选定的初始步长为h0。,由初始点 x1 沿 x 轴正向取 x2 点，x2=x1+h0，计算 x1 , x2 的函数值 y1 , y2 ，比较 y1 , y2 的大小，则极小点的位置有如图所示两种情况：,8,一、前进搜索,前进搜索,x1,x2,x3,h0,2h0,y1,y3,y2,令h h0，并使步长加倍 h2h，取得 x3点，,x3 x2+h=x2+2h0，,其函数值 y3与y2 比较有如下情况：,1、若y2 y2y3，令： a x1，b x3， 从而构成搜索区间a, b,9,二、前进搜索,然后步长加倍，取新点x3，重复上述比较y2与y3的大小，直至出现y1 y2y3时，令a x1，b x3，从而构成搜索区间a, b,前进搜索,x1,x2,x3,h0,2h0,y1,y3,y2,2、若y2y3，则继续前进搜索，各点变换如下：,x1 x2 ，y1 y2 x2 x3 ，y2 y3,10,三、后退搜索,x1,x2,h0,2h0,注意：x1x2互换后再取x3,y2,y3,y1,令 h -h0，并将 x1 与 x2 对调，使步长加倍 h2h，取得x3点， x3 x2+h， 其函数值 y3与 y2比较有如下情况：,1、若y2 y2y3，此时函数 f(x) 在x3, x1必有极小点，故令a x3，b x1，从而构成搜索区间a, b,x1,x2,x3,h0,2h0,注意：x1x2互换后再取x3,y2,y3,y1,11,三、后退搜索,然后步长加倍，取新点x3，重复上述比较y2与y3的大小，直至出现y1 y2y3时，令a x3，b x1，从而构成搜索区间a, b,2、若y2y3，则继续后退搜索，各点变换如下：,x1 x2 ，y1 y2 x2 x3 ，y2 y3,x1,x2,x3,h0,2h0,y1,y3,y2,x1,x2,x3,h0,2h0,y1,y3,y2,12,四、进退法确定搜索区间流程图,13,例题,例题3.1：试用进退法确定函数 f(x) = x2-6x+9 的一维优化搜索区间a，b，设初始点 x1=0，初始步长 h0=1,解：计算过程如下:,hh0=1 x2x1+h=1 y1=f(x1)=9, y2=f(x2)=4,由于y2y1，作前进搜索：,h2h=2 x3x2+h=3 y3=f(x3)=0,比较y2, y3有 y2y3，再做前进搜索,x1x2=1, y1y2=4 x2x3=3, y2y3 =0 h2h=4 x3x2+h=7, y3=F(x3)=16,14,再比较y2，y3有y2y3，则取,ax1=1，bx3=7 搜索区间a，b为1，7 搜索过程见下图,15,3.2 一维搜索的最优化方法,在确定了搜索区间以后，一维优化的任务是采用某种方法将此区间逐步缩小，在满足收敛精度或迭代精度的情况下，使其达到包含极小点的一个很小的邻域，以取得一个近似的最优点。 一维优化的方法有如下几种：,1. 分数法/Fibonacci法 2. 格点法 3. 黄金分割法 4. 二次插值法,16,Fibonacci数列,13世纪的意大利数学家斐波那契(Fibonacci)提出了这样一个问题：假定一对兔子在它们出生整整两个月以后可以生一对小兔子，其后每隔一个月又可以再生一对小兔子。假定现在在一个笼子里有一对刚生下来的小兔子，请问一年以后笼子里应该有几对兔子？,17,Fibonacci数列,斐波那契(Fibonacci)数列：0,1, 1, 2, 3, 5, 8, 13,18,Fibonacci数列的性质,数学定义：,F0 = 0 ； F1 = 1； Fn = F n - 1 + F n 2， n2,数列Fn 称为Fibonacci 数列，Fn称为第n 个Fibonacci 数，相邻两个Fibonacci 数之比Fn-1/Fn 称为称为Fibonacci 分数。,19,一维搜索算法试探法原理,试探法主要有： 斐波那契法（序贯实验法）； 黄金分割法 (0.618法),20,试探法原理,在区间 a , b内任取两点 a1 和 b1 ，a1 b1，并计算函数值 f(a1) 和 f(b1)，可能出现两种情况：,f(a1) f(b1)， b1一定在 t*的右端。,x,f(x),a,b,b1,a1,t*,a1,一定在 t 的右端,可在 t 的右端,也可在 t 的左端,极小点 t* 必在区间 a , b1 内。,21,试探法原理,f(a1) f(b1)， a1一定在 t*的左端 。,x,f(x),a,b,b1,b1,t*,a1,一定在 t 的左端,可在 t 的左端,也可在 t 的右端,极小点 t* 必在区间 a1 , b 内,22,试探法原理,只要在区间 a , b内任取两个不同点，并算出它们的函数值加以比较，就可以把搜索区间所小为 a1 , b 或 a , b1，因为缩小后的区间仍包含极小点,要进一步缩小搜索区间，只需在缩小后的区间内再取一点，并与 f(a1)或 f(b1)比较函数值大小。,按照上述方法，随着计算函数值次数的增加，区间变得越来越小，从而越接近极小点。,23,Fibonacci法算法步骤,第二步：k=1，计算最初的两个搜索点 t1 和 t2，,第一步： 选取初始数据，确定单峰区间a, b, 给出搜索精度 0，确定搜索次数 n 。,24,Fibonacci法算法步骤,斐波那契法寻优收敛快，计算次数少，然而每步取点繁琐，且各步缩短率不同。为此，引出黄金分割法。,第三步：k=n-1时，t1=t2=(a+b)/2，无法比较，此时取,25,黄金分割法,1)若y1 y2，则极小点必在区间a, x2内，令b=x2，新区间为a, x2 2)若y1y2，则极小点必在区间x1, b内，令a=x1，新区间为x1, b,黄金分割法适用于a,b区间上的任何单峰函数求极小值问题。对函数除要求单峰外不作其它要求，甚至可以不连续。因此适应面广,一、黄金分割法的原理,在搜索区间a, b内适当插入两点 x1, x2 ，x1x2, 且在区间内对称位置，计算其函数值：y1=f(x1) ，y2=f(x2),经过函数值比较，区间缩短一次。新区间只保留 x1，x2中的一个,26,黄金分割法区间缩短,27,黄金分割法区间缩短,28,黄金分割法的分点选取原则,黄金分割法内分点选取的原则：,对称且每次区间缩短率都相等。可证明0.618,设原区间长度为l。保留区间长度为1l，区间缩短率为 1。进行第二次缩短时，新点为x3 ,设y1f(x3)，则新区间为a, x1。设区间缩短率为2。为保持相同的区间缩短率，应有 ：,证明：,由此可得： =0.618。因而黄金分割法又称0.618法，是一种等比例缩短区间的直接搜索法,29,黄金分割法可使相邻两次搜索区间都具有相同的缩短率0.618。因而内分点的取点规则为： x1=a+ 0.382(b-a) x2=a+ 0.618(b-a),终止原则：,最优解：,k 为缩短区间的次数,30,黄金分割法的搜索过程,1、给出初始搜索区间a, b及收敛精度 ； 2、按坐标点计算公式计算，并计算相应的函数值； 3、缩短搜索区间； 4、检查是否满足收敛条件； 5、若满足收敛条件，则取最后两点的平均值作为极小点的近似解。,31,黄金分割法的流程图,32,例题,例题3.3 试用黄金分割法求目标函数 f(x)=x2-6x+9 的最优解。给定初始区间1，7，收敛精度=0.4。,解：第一次区间缩短计算过程：,计算两内点及对应函数值：,x1=a+0.382(b-a)=3.292 y1=f(x1)=0.085264 x2=a+0.618(b-a)=4.708 y2=f(x2)=2.917264,作数值比较，可见y1y2,再做置换：,用终止准则判断:,a(1) a=1 b(1) x2=4.708,33,为第二次区间缩短做准备，做置换：,x2x1=3.292 ， y2y1=0.085264,各次缩短区间的计算数据见下页表。第六次区间缩短的端点,满足精度要求，终止计算。取最优解为,34,黄金分割法例题计算数据,35,格点法,则最优解为：x* xm ， y* ym 若不能满足精度要求，把当前区间作为初始搜索区间，重复上述步骤直至满足精度为止,设一维函数为 f (x)，搜索区间为a, b，一维收敛精度为。在区间a, b的内部取 n 个等分点： x1 , x2 , , xn。区间被分为 n+1 等分，各分点坐标为:,对应各点的函数值为 y1 , y2 , , yn。比较其大小，取最小者：,格点法的原理,ym=min yk , k=1,2,n,则在区间xm-1 , xm+1内必包含极小点，取xm-1 , xm+1为缩短后新区间，若新区间满足收敛条件：,xm+1- x m-1 ,36,格点法的区间缩短,37,格点法流程图,38,例题,例题3.2：用格点法求一维目标函数 f(x) = 4x2-12x+10 的最优解。给定搜索区间a，b为1，2.2，迭代精度=0.2，内分点数 n = 4。,解：计算区间端点的函数值,f(a)=2 f(b)=2.96,由上式确定四个内分点的位置，并计算其函数值，计算结果如表所示。其中最小的函数值为：,对应的点：,39,40,新区间的端点为：,新区间的长度为： ，不满足精度要求。,再做第二次区间缩短后，得到区间端点为：,新区间长度 ，满足迭代精度。,最优解为：,41,二次插值法,假定我们给定的问题是在某一确定区间内寻求函数的极小点的位置，但是没有函数表达式，只有若干试验点处的函数值。我们可以根据这些函数值，构成一个与原目标函数相接近的低次插值多项式，用该多项式的最优解作为原函数最优解的近似解，这种方法是用低次插值多项式逐步逼近原目标函数的极小点的近似求解方法，称为插值方法或函数逼近法。,一、插值法概念,42,插值法与试探法的异同点,相同点：都是利用区间消去法原理将初始搜索区间不断缩短，从而求得极小点的数值近似解。,不同点：试验点位置的确定方法不同,试探法中试验点的位置是由某种给定的规律确定的，并未考虑函数值的分布。例如：黄金分割法是按照等比例0.618缩短率确定的。 插值法试验点的位置是按函数值近似分布的极小点确定的。,43,插值法与试探法的异同点,试探法仅仅利用了试验点函数值进行大小的比较，而插值法还要利用函数值本身或其导数信息。所以，当函数具有较好的解析性质时，插值方法比试探方法效果更好。,44,二次插值法,利用原目标函数上的三个插值点，构成一个二次插值多项式，用该多项式的最优解作为原函数最优解的近似解，逐步逼近原目标函数的极小点，称为二次插值方法或近似抛物线法。,45,二次插值函数的构成,设一维目标函数的搜索区间为a, b,第一步：取三点x1, x2, x3， x1 a，x3 b，x2=0.5 (x1+x3),第二步：计算三点函数值： f1=f (x1)，f2=f (x2)，f3=f (x3),第三步：过三点做一条二次曲线：p(x)=Ax2+Bx+C，则应满足：,p(x1)=Ax12+Bx1+C =f1 p(x2)=Ax22+Bx2+C = f2 p(x3)=Ax32+Bx3+C = f3 解线性方程组得：,46,于是函数 p(x) 就是一个确定的二次多项式，称二次插值函数 如图所示，虚线部分即为二次插值函数,47,二次插值函数的构成,第四步：计算二次曲线：p(x) = Ax2+Bx+C 的极小值,xp* = B / 2 A，带入A，B,令其一阶导数为零，即：p(x)=2Ax+B=0，得：,令,得,48,二次插值函数的构成,注意： 若c2=0， 则 即 说明三个插值点位于同一条直线上，因此说明区间已经很小，插值点非常接近，故可将 x2、f2 输出作为最优解。,49,二次插值法区间的缩短,第一次区间缩短的方法是，计算 xp* 点的函数值 fp*，比较 fp* 与 f2，取其中较小者所对应的点作为新的x2，以此点的左右两邻点作为新的x1和x3，得到缩短后的新区间 x1，x3，如图所示。,新区间,x1=a,x2,x3=b,x*,xP*,x1,x2,x3,为求得满足收敛精度要求的最优点，往往需要多次进行插值计算，搜索区间不断缩短，使 xp*不断逼近原函数的极小点 x*,50,根据 fp* 相对于 x2 的位置，并比较 fp*与 f2 ，区间的缩短可以分为以下：,51,二次插值法区间缩短框图,入口,xp*x2?,f2fP*?,f2fP*?,x1 xp* f1 fP*,x3 x2 f3 f2 x2 xp* f2 fP*,x1 x2 f1 f2 x2 xp* f2 fP*,x3 xp* f3 fP*,出口,Y,Y,Y,N,N,N,a,b,c,d,52,终止准则及最优解,x* xp* (k) f * f (x*),最优解：,终止准则：,53,二次插值算法的流程图,说明三点在一直线上,说明xp*落在区间x1, x3外,54,例题3.4,例题3.4 试用二次插值法求函数 f(x) = (x-3)2 的最优解，初始区间为1，7，精度=0.01,解：,(1)初始插值节点,x1=a=1, f1=f (x1)=4 x2=0.5(a+b)=4, f2=f (x2)=1 x3=b=7, f3=f (x3)=16,(2)计算插值函数的极小点与极小值,55,例题3.4,(3) 缩短区间,因有 ，故有,x1=1, f1=4 x2xp*(1) =3, f2=0 x3x2=4, f3=1,(4) 重复步骤(2),c1=-1 c2=1,(5) 检查终止条件,获得最优解,xp*(2) =3,fp*(2) =0,56,例题3.5,例题3.5 用二次差值法求非二次函数 的最优解。初始区间端点为a=-0.5, b=2.5。精度要求=0.005,(1) 初始插值节点,x1=a=-0.5, f1=f (x1)=-0.851279 x2=0.5(a+b)=1 f2=f (x2)=-2.610944 x3=b=2.5, f3=f (x3)=15.615452