第八章数值优化课件

第第8 8章章 数数值值优优化化 8.1 8.1 单变量函数的极小值单变量函数的极小值8.2 8.2 内德内德-米德方法和鲍威尔方法米德方法和鲍威尔方法8.3 8.3 梯度和牛顿方法梯度和牛顿方法目录目录8.1 单变量函数的极单变量函数的极小值小值定义8.1 如果存在包含p的开区间I，使得对所有xI，有f(p)f(x)，则称函数f 在x=p处有局部极小值局部极小值。类似地，如果对所有xI，有f(p)f(x)，则称函数f 在x=p处有局部极大值局部极大值。如果f 在点x=p处有局部极大值或极小值，则称f 在点x=p处有局部极值局部极值。单调性的定义和判定单调性的定义和判定定义8.2 设f(x)定义在区间I上。若对所有x1x2，当x1,x2I时有f(x1)f(x2)，则称f 在区间I上递增递增。若对所有x1f(x2)，则称f 在区间I上递减递减。定理8.1 设f(x)在区间I=a,b上连续，并在(a,b)上可微。若对所有x(a,b)有f(x)0，则f(x)在 I上递增。若对所有x(a,b)有f(x)0，则f(x)在 I上递减。驻点和一阶导数测试驻点和一阶导数测试定理8.2 设f(x)定义在区间I=a,b上，并在内点p(a,b)处有局部极值。若f(x)在x=p处可微，则f(p)=0。定理8.3 设f(x)在I=a,b上连续，并设除x=p处外，f(x)对所有x(a,b)都有定义。若在(a,p)上f(x)0，则f(p)是局部极小值。若在(a,p)上f(x)0，而在(p,b)上f(x)0，则f(p)是f 的一个局部极小值。若f(p)0，则f(p)是f 的一个局部极大值。若f(p)=0，则结果不确定。8.1.1 分类搜索方法分类搜索方法直接法直接法是一种数值方法是一种数值方法这种方法的基本思想是这种方法的基本思想是迭代迭代，通过迭代产生一个点序列，通过迭代产生一个点序列 X(k)，使之逐步接近最优点，使之逐步接近最优点只用到只用到目标函数目标函数，通过对函数多次求值来求函数，通过对函数多次求值来求函数f(x)在给在给定区间上的一个局部极小值定区间上的一个局部极小值要尽量减少函数求值的次数，确定在哪里求要尽量减少函数求值的次数，确定在哪里求f(x)值的好策值的好策略非常重要略非常重要如如黄金分割搜索法、黄金分割搜索法、FibonacciFibonacci搜索法、随机搜索法搜索法、随机搜索法搜索法必须满足的条件搜索法必须满足的条件使用这些方法来求f(x)的极小值必须满足特定特定的条件，以保证在给定的区间内有合适的极小值这个特定条件就是函数f(x)在给定区间中是单峰单峰的定义8.3 如果存在唯一的pI，使得（1）f(x)在a,p上递减，（2）f(x)在p,b上递增，则函数f(x)在I=a,b上是（下下）单峰单峰的。黄金分割搜索法（黄金分割搜索法（0.618法）法）如果已知f(x)在a,b上是（下）单峰的，则有可能找到该区间的一个子区间，f(x)在该子区间上取得极小值选择两个内点cd，这样就有acdf(d)，则从左侧压缩，使用c,ba黄金分割法原理黄金分割法原理 设函数 f(x)在闭区间 a,b 上是（下）单峰函数，即在(a,b)内 f(x)有唯一的极小点p，在p的左边 f(x)严格单调下降，在p的右边f(x)严格单调上升。那么对于(a,b)内任意两点cd，如果 f(c)f(d)，则p a,d；否则p c,b黄金分割法黄金分割法选择内点c和d，使得区间a,c与d,b对称，即b-d=c-a，其中c=a+(1-r)(b-a)=ra+(1-r)bd=b-(1-r)(b-a)=(1-r)a+rb 并且1/2r1（保证cd）希望r在每个子区间上保持为常数，且旧的内点中有一个成为新子区间的一个内点，而另一个则成为新子区间的一个端点在每次迭代中只需要找一个新的点，则只需要一次新的函数求值计算比例因子的选择比例因子的选择设f(c0)f(d0)，则从右侧压缩，使用a0,d0，即取a1=a0，b1=d0和d1=c0，则需要再求一个新的点c1a1c1d1b1a0c0d0b001-rr1因为1/2r1（保证cd），故取斐波那契（斐波那契（Fibonacci）搜索法）搜索法黄金分割搜索法第一次迭代中进行了两次函数求值，而在后续的每次迭代中则只进行一次函数求值r的值对每个子区间相同，当|bk-ak|或|f(bk)-f(ak)|时，迭代结束，取ak,bk的中点为所求最小值点。其中是预定义的容差斐波那契（Fibonacci）搜索法中r的值不是常数，而且子区间数（迭代数）是由指定的容差决定的斐波那契（斐波那契（Fibonacci）搜索法）搜索法斐波那契（Fibonacci）序列基于公式：F0=0,F1=1,Fn=Fn-1+Fn-2 即Fk=0,1,1,2,3,5,8,13,21,设函数 f(x)在闭区间 a0,b0 上是单峰函数，选择1/2r01，使内点c0和d0可以在下一个子区间上使用，从而只需一次新的函数求值计算比例因子的确定比例因子的确定设f(c0)f(d0)，则从右侧压缩，使用a,d，即取a1=a0，b1=d0和d1=c0，则需要再求一个新的点c1为子区间a1,b1选择r1(1/2r11)，使得a1c1d1b1a0c0d0b01-r0r02r011-r0r11-r1因为有Fn=Fn-1+Fn-2，Fibonacci搜索从r0=Fn-1/Fn开始，对k=1,2,n-3，用rk=Fn-1-k/Fn-k。注意rn-3=F2/F3=1/2，因此这一步无需增加新的点。整个过程总共需要 (n-3)+1=n-2步。将第k个子区间的长度按因子 rk=Fn-1-k/Fn-k缩减，得到第(k+1)个子区间。最后一个子区间的长度为由Fibonacci数列，将r0=Fn-1/Fn，n4代入r1，得如果极小值横坐标的容差为，则需要找到最小的n，使得按要求，由如下公式可找到第k个子区间ak,bk的内点ck和dk其中的n由上面不等式求得区别常数的设置区别常数的设置每次迭代需要确定两个新的内点，一个来自前一次的迭代，另一个重新计算。当r0=F2/F3=1/2时，两个内点将在区间中点重合。为区分它们，引入一个小的区别常数e。当求ck和dk的时候，rk=1/2+e，则(1-rk)=1/2-e例8.3分类搜索法分类搜索法黄金分割搜索法与斐波那契搜索法都可用于f(x)不可微的情况。搜索法存在的问题：函数在极小值附近可能比较平缓，从而限制了精度，而且速度也较慢对于小的n值，斐波那契搜索法比黄金分割搜索法更为有效；对于大的n值，两者几乎相同8.1.2 利用导数求极小值利用导数求极小值设f(x)在区间a,b上是（下）单峰的，并在x=p处有唯一极小值。并设f(x)在(a,b)上所有的点处有定义。令初始点p0在(a,b)内。若f(p0)0，则极小值点p在p0左侧。ap0pby=f(x)ap0pby=f(x)1.对极小值分类对极小值分类首先求出三个测试值p0,p1=p0+h,p2=p0+2h,使得f(p0)f(p1),f(p1)f(p2)成立若f(p0)0,则p00若f(p0)0,则p0p，且应该选择步长h0容易找到h，使三点p0,p1=p0+h,p2=p0+2h满足要求。如有a+1b，则令h=(+/-)1，否则令h=(+/-)1/2，依此类推。寻找过程（设寻找过程（设f(p0)0）1.若满足f(p0)f(p1),f(p1)f(p1)且f(p1)f(p2)，则说明p2)p。则需检测更靠右(左)的点。步长加倍，并重复检测过程3.若f(p0)f(p1)，表明h太大，p1已经跳过了p。则需检测更靠近p0的点。步长减半，并重复检测过程2.求极小值求极小值p的二次逼近方法的二次逼近方法由p0,p1=p0+h,p2=p0+2h，可用二次插值来求p的近似值pmin。基于三点的拉格朗日多项式为其中yi=f(pi),i=0,1,2.Q(x)的导数为以Q(p0+hmin)的形式求解Q(x)=0，得将上式中的各项乘以2h2，并合并包含hmin的项，得由上式解得值pmin=p0+hmin比p0更逼近p，因此可用pmin代替p0，并重复上述计算过程，求出新的h和新的hmin。重复这一迭代过程，直到得到所需的精度。8.1 单变量函数的极小值8.2 内德-米德方法和鲍威尔方法8.3 梯度和牛顿方法目录目录多元函数求极值的问题多元函数求极值的问题设函数f(x1,x2,xN)定义在区域上。如果f(p1,p2,pN)f(x1,x2,xN)对所有的点(x1,x2,xN)R都成立，则函数f(x1,x2,xN)在点(p1,p2,pN)处有局部极小值；如果f(p1,p2,pN)f(x1,x2,xN)对所有的点(x1,x2,xN)R都成立，则函数f(x1,x2,xN)在点(p1,p2,pN)处有局部极大值。二元函数的极小值问题二元函数的极小值问题二元函数的图形是一个几何表面定理8.5（二阶偏导数测试）设f(x,y)及其一阶和二阶偏导数在区域R上连续。设点(p,q)R是一个临界点，即fx(p,q)=0且fy(p,q)=0。可用高阶偏导数来确定临界点的属性。I.若 且 fxx(p,q)0，则 f(p,q)是 f 的局部极小值。I.若 且 fxx(p,q)0，则 f(p,q)是 f 的局部极大值。I.若 ，则f(x,y)在(p,q)没有局部极值。I.若 ，则结果不确定。例8.5多元函数的直接搜索法多元函数的直接搜索法多变量目标函数f(x1,x2,xN)的极值直接搜索法对函数的可微性不作显性或隐性的假设对非光滑（不可微）目标函数而言，直接方法特别有用内德米德方法和鲍威尔方法单纯形方法的基本思想单纯形方法的基本思想内德和米德提出了单纯形法，可用于求解多变量函数的局部极小值从可行域中的一个基本可行解出发，判断它是否已是最优解，若不是，寻找下一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找出最优解或判定问题无解为止。从另一个角度说，就是从可行域的某一个极点出发，迭代到另一个极点，并使目标函数的值有所改善，直到找出有无最优解时为止。单纯形的概念单纯形的概念单纯形是指0维中的点，一维中的线段，二维中的三角形，三维中的四面体，n维空间中的有n+1个顶点的多面体。例如在三维空间中的四面体，其顶点分别为(0,0,0)，(1,0,0)，(0,1,0)，(0,0,1)。具有单位截距的单纯形的方程是xi1，并且xi0，i=1,2,n二元函数的单纯形方法二元函数的单纯形方法在二维平面空间中，单纯形就是三角形搜索过程：比较三角形3个顶点处的函数值，f(x,y)值最大的顶点为最差顶点(W)，用一个新的顶点代替最差顶点，形成新的三角形式继续这一过程，生成一系列三角形（它们可能具有不同的形状），函数在其顶点处的值越来越小随着三角形的减小就可以找到极小值点的坐标单纯形的寻找过程单纯形的寻找过程初始三角形BGW良边的中点反射点R开拓点E收缩点C向B方向收缩每一步的逻辑判断每一步的逻辑判断若f(B)f(R)，则以R代替W 否则计算E和f(E)若f(E)f(B)，则以E代替W 否则以R代替W若f(R)f(W)，则以R代替W否则计算C1=(M+R)/2和f(C1)计算C2=(W+M)/2和f(C2)取两者中函数值较小者为C 若f(C)f(W)，则以C代替W 否则计算S=(W+B)/2和f(S)以S代替W 以M代替Gn若f(R)f(P1).f(Pk).如果limkPk=P，则f(P)是f(X)的一个局部极小值梯度法搜索过程示意图梯度方法概要梯度方法概要设Pk已知求梯度向量f(Pk)计算搜索方向Sk=-f(Pk)/|-f(Pk)|在区间0,b上对()=f(Pk+Sk)进行单参数极小化，b为一个较大值。这一过程将产生值=hmin，它是()的一个局部极小值点。关系式(hmin)=f(Pk+hminSk)表明，它是f(X)沿搜索线X=Pk+hminSk的一个极小值构造下一个点Pk+1=Pk+hminSk进行极小化过程的终止判断，若函数值满足|f(Pk+1)-f(Pk)|或两点距离满足|Pk+1-Pk|，则迭代终止，否则转第步例8.9 用梯度法求函数 的P1和P2。初始点采用P0=(-3,-2)P0P1P2P梯度法小结梯度法小结梯度法是从梯度的几何含义自然延伸得到的，所以几何上比较直观梯度法的基本思想是从当前点xk出发寻找使得目标函数下降最快的方向，即负梯度方向负梯度方向。优点：迭代点列总是收敛的，而且计算过程简单梯度法的缺点梯度法的缺点梯度法相邻的两个搜索方向是相互垂直的，迭代点越靠近极小值点则函数下降的速度越慢对于N变量函数f(x1,x2,xN)而言，收敛到一个极小值的速度可能很慢一般地，函数f的极小值在几何上使得值hmin很小，这导致需要大量的极小化过程梯度法一般用于最优化过程开始的几步搜索例例 求目标函数的极小点。牛顿方法原理牛顿方法原理由单变量函数的二次逼近求极小值的方法推广而得，以有N个独立变量的二次多项式的极小值来近似代替目标函数f的极小值对有N个独立变量的函数z=f(x1,x2,xN)而言，从初始点P0开始，递归构造出一个含N个变量的二次多项式序列如果目标函数是良态的，并且初始点在实际极小值附近，则该二次多项式的极小值序列将收敛到目标函数f的极小值黑森（黑森（Hessian）矩阵）矩阵定义8.5 设z=f(X)是X的函数，对于i,j=1,2,.,N,存在。f 在X处的黑森矩阵是一个NN矩阵其中，i,j=1,2,.,N例8.10二阶泰勒多项式二阶泰勒多项式定义8.6 f(X)在中心A处的二阶泰勒多项式二阶泰勒多项式为n设z=f(x1,x2,xN)的一阶和二阶偏导数存在，并在包含P0的一个区间内连续，f 在点P处有极小值。则 f 在P0的泰勒展开为nQ(X)是一个N变量的二阶多项式，它可能在Q(X)=0有极小值由Q(X)=0得f(P0)+(X-P0)(H f(P0)T=0若P0在点P（f的极小值点）附近，则H f(P0)可逆，则可求得X=P0-f(P0)(H f(P0)-1)T用P1代替上式中的X，得P1=P0-f(P0)(H f(P0)-1)T上式中，用Pk-1代替P0，Pk代替P1，得Pk=Pk-1-f(Pk-1)(H f(Pk-1)-1)T上式建立了一个迭代关系式，由此迭代关系式可生成点序列Pk(k=0,1,2,.)但算法中涉及到矩阵求逆的运算，理论上虽然可行，实际上用它进行计算则效率很低改进的牛顿方法概要改进的牛顿方法概要设Pk已知计算搜索方向Sk=-f(Pk-1)(H f(Pk-1)-1)T在区间0,b上对()=f(Pk+Sk)进行单变量极小化，b为较大值。得到值=hmin它是()的极小值点。关系式(hmin)=f(Pk+hminSk)表明，它是f(X)沿搜索线X=Pk+hminSk的一个极小值构造下一点，Pk+1=Pk+hminSk进行终止条件测试，即函数值f(Pk)和f(Pk+1)是否足够相近，距离|Pk+1-Pk|是否足够小？重复上述过程无约束优化方法无约束优化方法直接法总结直接法总结1 Nelder-Mead法（单纯形法）思路清楚，收敛慢2 坐标轮换法计算效率较低适合维数较低，目标函数无导数或导数较难求得3 Powell法具有二次收敛性，收敛速度较快，可靠性高，被认为是直接法中最有效的方法之一写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits65 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End演讲人：XXXXXX 时 间：XX年XX月XX日