3第三章-一维优化方法new

第三章 一维优化方法,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, a1 f(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)若y1y2则极小点必在区间a,2内， 令b =2，新区间为a，2 2)若y1y2则极小点必在区间1,b内， 令a = 1，新区间为1，b 经过函数值比较，区间缩短一次。 新区间只保留1，2中的一个。,图3-6 黄金分割法,黄金分割法内分点选区的原则之一是要对称的、并采取每次区间缩短率都是相等的。 设原区间长度为1如图3.6所示，保留区间长度为，区间缩短率为 。进行第二次缩短时，新点为3 ,设y1f(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) 计算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)=0 f (0)+f (0)( 0) =0 1 = 0 f (0)/ f (0) 依次计算下去， 可得牛顿法迭代公式 k+1 = k f (k)/ f (k) k = 0, 1, 2, ,牛顿法的计算步骤： 给定初始点0，控制误差，令k = 0; 1) 计算f (k)、 f (k) 2）求k+1 = k f (k)/ f (k) 3）若k+1 - k 则求得近似解*= k+1 ， 停止结算， 否则4） 4）令kk+1转步骤1.,例3-2 给定f ()= 4 43 62 16+4，使用牛顿法求其极小点*。 解： f () = 4(3 32 3-4) f () = 12(2 2-1) 给定初始点0 = 3， 控制误差 = 0.001，计算结果如下表所示。,牛顿法最大的优点是收敛速度快， 但是在每一点处都需计算函数的二阶导数， 工作量较大。特别是用数值微分代替二阶导数时，舍入误差会影响收敛速度，当f ()很小时候这个问题跟严重。另外， 该方法对于初始点要求选的比较好， 否则有可能是极小化序列发散或收敛到非极小点。,二、二次插值法（抛物线法） 利用原目标函数上的三个插值点，构成一个二次插值多项式，用该多项式的最优解作为原函数最优解的近似解，逐步逼近原目标函数的极小点，称为二次插值方法或抛物线法。 设一维目标函数的搜索区间为a,b，取三点x1、x2、x3，其中x1、x3取区间的端点，即 x1a ， x3 b 而x2为区间内的一个点，开始可以取区间的中点，即 x2=0.5 ( x1 + x3 ) 利用函数y = f() 在单谷区间中的三点1 f(2) f(3), 作二次插值多项式 p()=a0 + a1 + a22 它应满足 p(1)=a0 + a11 + a212 p(2)=a0 + a12 + a222 p(3)=a0 + a13 + a232 解方程组，得待定系数a0 、 a1、 a2分别为,于是函数p()就是一个确定的二次多项式，称二次插值函数 如图所示，虚线部分即为二次插值函数,令插值函数p()的一阶导数为0，即 p´() = 2a2p + a1= 0 得 p() 极小点为 p* = a1 / 2a2 代入a1、2a2得,令,得,注意： 若c2=0， 则 即 说明三个插值点位于同一条直线上，因此说明区间已经很小，插值点非常接近，故可将2、y2输出作为最优解。,五、区间的缩短 为求得满足收敛精度要求的最优点，往往需要多次进行插值计算，搜索区间不断缩短，使p*不断逼近原函数的极小点*。 第一次区间缩短的方法是，计算p*点的函数值yp*，比较yp*与y2，取其中较小者所对应的点作为新的2，以此点的左右两邻点作为新的1和3，得到缩短后的新区间1，3，如图所示。,新区间,1=a,2,3=b,*,P*,1,2,3,为了在每次计算插入点的坐标时能应用同一计算公式， 新区间端点的坐标及函数值名称需换成原区间端点的坐标和函数值名称。根据p 与2的相对位置， yp与y2的大小以及正向搜索（h0)或反向搜索（h0)的不同，具体换名有如表3-3所示的8种情况。如果成绩（ p - 2)h的符号相同， 则正向搜索和反向搜索将采取同样的换名方式。因此八种情况合并为4种。,