《维优化方法》PPT课件

第三章一维优化方法,3.1概述xk+1=xk+kdk(k=0,1,2,)式中dk为第k+1次迭代的搜索方向，k为沿dk搜索的最佳步长因子。当方向dk给定，求最佳步长k就是求一元函数f(xk+1)=f(xk+kdk)=(k)的极值问题。即在优化设计的迭代运算中，在搜索方向s(k)上寻求最优步长(k)的方法称一维搜索法。求多元函数极值点，需要进行一系列的一维搜索。,可利用一元函数的极值条件(*)=0求*。把f(xk+kdk)进行泰勒展开并取二阶项，即上式对进行微分并令其等于零求极值，得得此时需要计算函数梯度和海赛矩阵。,解析法的缺点是需要进行求导计算。在优化设计中，求解最佳步长因子主要采用数值解法，通过计算机的反复迭代计算求得最佳步长因子的近似值。数值解法的基本思路是：先确定*所在的搜索区间，然后根据区间消去法不断缩小此区间，从而获得*的数值近似解。,3.2搜索区间的确定与区间消去法原理,一、外推法在一维搜索时，需要确定一个搜索区间a,b，此区间必须包含函数的极小点x*，因此搜索区间必须是单谷区间，即该区间内的函数值呈现“高-低-高”的趋势。如图所示，通过将搜索区间a,b逐渐缩小，直至足够小，就可以得到近似最优点。,从=0开始，以初始步长h0向前试探。如果函数值上升，则步长变号，即改变试探方向。如果函数值下降，则维持原来的试探方向，并使步长加倍。区间的始点、中间点依次沿试探方向移动一步。此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。最后得到的三点即为搜索区间的始点、中间点和终点，形成函数值的“高-低-高”趋势。,上述确定搜索区间的外推法，其程序框图如图3-4所示。,二、区间消去法原理假设在搜索区间a,b内任取两点a1、b1,a1f(b1),如图3-5b所示。由于函数的单谷性，极小点在区间a1,b内。3)f(a1)=f(b1),极小点在区间a1,b1内。2)、3）可合并为一种情况，即f(a1)f(b1),极小点在区间a1,b内。,三、一维搜索方法的分类分为两类：一类称做试探法，按某种给定的规律来确定区间内插入点的位置，如黄金分割法等；一类称为插值法或函数逼近法，这类方法是根据某些点处的某些信息，如函数值、一阶导数、二阶导数等，构造一个插值函数来逼近原来函数，用插值函数的极小点作为区间的极小点，如二次插值法，三次插值法等。,3.3一维搜索的试探方法,黄金分割法适用于a,b区间上的任何单峰函数求极小值问题。对函数除要求单峰外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。黄金分割法也是建立在区间消去法原理基础上的试探方法。一、黄金分割法的原理在搜索区间a,b内适当插入两点1,2，12,且在区间内对称位置，1=b(b-a)2=a+(b-a)计算其函数值。y1=f(1)y2=f(2)1)若y1f(3)则新区间为a,1为保持相同的区间缩短率，应有（1-）/=故：1-=22+-1=0由此可得：=0.618黄金分割法可使相邻两次搜索区间都具有相同的缩短率0.618。1=b0.618(b-a)2=a+0.618(b-a),图3-6黄金分割法,黄金分割法的搜索过程1、给出初始搜索区间a,b及收敛精度,将赋值0.618。2、按坐标点计算公式1=b(b-a)2=a+(b-a)计算1，2，并计算相应的函数值f(1)，f(2)3、缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。4、检查区间是否缩短到足够小和函数值是否满足收敛条件，否则返回步骤2.5、若满足收敛条件，则取最后两点的平均值作为极小点的近似解。,三、黄金分割法流程图,3.4一维搜索的插值方法,一、插值法概念假定我们给定的问题是在某一确定区间内寻求函数的极小点的位置，但是没有函数表达式，只有若干试验点处的函数值。我们可以根据这些函数值，构成一个与原目标函数相接近的低次插值多项式，用该多项式的最优解作为原函数最优解的近似解，这种方法是用低次插值多项式逐步逼近原目标函数的极小点的近似求解方法，称为插值方法或函数逼近法。二、插值法与试探法的异同点相同点：都是利用区间消去法原理将初始搜索区间不断缩短，从而求得极小点的数值近似解。不同点：试验点位置的确定方法不同。,不同点：试验点位置的确定方法不同。在试探法中试验点的位置是由某种给定的规律确定的，并未考虑函数值的分布。例如：黄金分割法是按照等比例0.618缩短率确定的。插值法中，试验点的位置是按函数值近似分布的极小点确定的。试探法仅仅利用了试验点函数值进行大小的比较，而插值法还要利用函数值本身或其导数信息。插值法是利用函数在已知试验点的值（或导数值）来确定新试验点的位置。所以，当函数具有较好的解析性质时，插值方法比试探方法效果更好。,多项式是函数逼近的一种常用工具。在搜索区间内我们可以利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似。牛顿法、抛物线法,一、牛顿法（切线法）对于一维搜索函数y=f(),假定已给出极小点的一个较好的近似点0，因为一个连续可微的函数在极小点附近与一个二次函数很接近，所以可在0点附近用一个二次函数()来逼近f()，即在0点将f()进行泰勒展开并保留到二次项：f()()=f(0)+f(0)(0)+0.5f(0)(0)2然后以二次函数()的极小点作为f()极小点的一个新近似点1。于是(1)=0f(0)+f(0)(0)=01=0f(0)/f(0)依次计算下去，可得牛顿法迭代公式k+1=kf(k)/f(k)k=0,1,2,牛顿法的计算步骤：给定初始点0，控制误差，令k=0;1)计算f(k)、f(k)2）求k+1=kf(k)/f(k)3）若k+1-k则求得近似解*=k+1，停止结算，否则4）4）令kk+1转步骤1.,例3-2给定f()=4436216+4，使用牛顿法求其极小点*。解：f()=4(3323-4)f()=12(22-1)给定初始点0=3，控制误差=0.001，计算结果如下表所示。,牛顿法最大的优点是收敛速度快，但是在每一点处都需计算函数的二阶导数，工作量较大。特别是用数值微分代替二阶导数时，舍入误差会影响收敛速度，当f()很小时候这个问题跟严重。另外，该方法对于初始点要求选的比较好，否则有可能是极小化序列发散或收敛到非极小点。,二、二次插值法（抛物线法）利用原目标函数上的三个插值点，构成一个二次插值多项式，用该多项式的最优解作为原函数最优解的近似解，逐步逼近原目标函数的极小点，称为二次插值方法或抛物线法。设一维目标函数的搜索区间为a,b，取三点x1、x2、x3，其中x1、x3取区间的端点，即x1a，x