《维优化方法》PPT课件

《《维优化方法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章一维优化方法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)进行泰勒展开并取二阶项，即上式对进行微分并令其等于零求极值，得得此时需要计算函数梯度和海赛矩阵。解析法的缺点是需要进行求导

2、计算。在优化设计中，求解最佳步长因子主要采用数值解法，通过计算机的反复迭代计算求得最佳步长因子的近似值。数值解法的基本思路是：先确定*所在的搜索区间，然后根据区间消去法不断缩小此区间，从而获得*的数值近似解。3.2搜索区间的确定与区间消去法原理一、外推法在一维搜索时，需要确定一个搜索区间[a,b]，此区间必须包含函数的极小点x*，因此搜索区间必须是单谷区间，即该区间内的函数值呈现“高-低-高”的趋势。如图所示，通过将搜索区间[a,b]逐渐缩小，直至足够小，就可以得到近似最优点。从=0开始，以初始步长h0向前试探。如果函数值上升，则步长变号，即改变试探方向。如

3、果函数值下降，则维持原来的试探方向，并使步长加倍。区间的始点、中间点依次沿试探方向移动一步。此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。最后得到的三点即为搜索区间的始点、中间点和终点，形成函数值的“高-低-高”趋势。上述确定搜索区间的外推法，其程序框图如图3-4所示。二、区间消去法原理假设在搜索区间[a,b]内任取两点a1、b1,a1f(b1),如图3-5b所示。由于函数的单谷性

4、，极小点在区间[a1,b]内。3)f(a1)=f(b1),极小点在区间[a1,b1]内。2)、3）可合并为一种情况，即f(a1)f(b1),极小点在区间[a1,b]内。三、一维搜索方法的分类分为两类：一类称做试探法，按某种给定的规律来确定区间内插入点的位置，如黄金分割法等；一类称为插值法或函数逼近法，这类方法是根据某些点处的某些信息，如函数值、一阶导数、二阶导数等，构造一个插值函数来逼近原来函数，用插值函数的极小点作为区间的极小点，如二次插值法，三次插值法等。3.3一维搜索的试探方法黄金分割法适用于[a,b]区间上的任何单峰函数求极小值问题。对函数除要求单峰外不

5、作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。黄金分割法也是建立在区间消去法原理基础上的试探方法。一、黄金分割法的原理在搜索区间[a,b]内适当插入两点1,2，1<2,且在区间内对称位置，1=b(b-a)2=a+(b-a)计算其函数值。y1=f(1)y2=f(2)1)若y1

6、要对称的、并采取每次区间缩短率都是相等的。设原区间长度为1如图3.6所示，保留区间长度为，区间缩短率为。进行第二次缩短时，新点为3,设y1>f(3)则新区间为[a,1]为保持相同的区间缩短率，应有（1-）/=故：1-=22+-1=0由此可得：=0.618黄金分割法可使相邻两次搜索区间都具有相同的缩短率0.618。1=b0.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)计

7、算1，2，并计算相应的函数值f(1)，f(2)3、缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。4、检查区间是否缩短到足够小和函数值是否满足收敛条件，否则返回步骤2.5、若满足收敛条件，则取最后两点的平均值作为极小点的近似解。三、黄金分割法流程图3.4一维搜索的插值方法一、插值法概念假定我们给定的问题是在某一确定区间内寻求函数的极小点的位置，但是没有函数表达式，只有若干试验点处的函数值。我们可以根据这些函数值，构成一个与原目标函数相接近的低次插值多项式，用该多项式的最优解作为原函数最优解的

8、近似解，这