现代设计方法-优化设计-一维搜索

现代设计方法优化设计部分黄正东二0一三年一月本章主要内容优化设计概述优化设计的数学基础一维探索优化方法无约束优化方法约束问题优化方法优化设计若干问题优化设计概述优化设计的数学基础一维探索优化方法无约束优化方法约束问题优化方法优化设计若干问题一维搜索的概念单峰区间进退法黄金分割法平分法切线法二次插值法一维搜索优化方法数值迭代过程中，任何一次迭代，总是从某个已知点出发，沿着给定的方向（用某种优化方法确定）搜索到目标函数在该方向上的极小值点，这个过程称为一维搜索。一维搜索不仅可以求解一维优化问题，同时也是求解多维优化问题的基本步骤。)(kX)(kS)1(kX怎么理解“一维”的含义？一维搜索的概念对“一维”的理解寻找目标函数在指定方向上的极小点，在计算上就是从沿前进多少的问题，即求步长因子的问题。从这个意义上讲，一维搜索是一个求解关于的单元目标函数的过程。)(kX)(kS)(k一维搜索寻找合适的，使最小)(k)()()()(kkkSXf“一维”是指“一个方向”（）；)(kS任一次迭代，都是求使得即其中：表示步长因子表示最优步长因子一维搜索的数学形式)()()()1(kkkkSXX)(min)()()()1(kkkSXfXf)(min)()()()()()(kkkkkSXfSXf)(k2x1x*X)(kX)(kS)1(kX一维搜索的几何意义从出发，沿方向一维搜索，就是求方向与等值线的切点，此时的步长因子即为最优步长因子。)(kX)(kS)(kS子优化问题:FindMinimize()=f(x(k)+s(k))fs(k)X(k)子优化问题的一阶必要条件:’()=0[f(x(k)+s(k))]Ts(k)=0一维搜索的几何意义假设第k次得到的区间，若，则可取作为极小点。一维搜索的基本思想一维搜索就是要在初始单峰区间中求单峰函数的极小点。所以找初始单峰区间是一维搜索的第一步，然后将初始单峰区间逐步缩小，直至包括极小点的区间长度小于给定的一个正数，此称为收敛精度或迭代精度。)()(,kkba)()(kkab)(21*)()(kkbax][3][2][1)()(][][212112122122112121xxffbxffxaffxffxffxxbaxxba，，则留下的区间为）如果（，，则留下的区间为）如果（，，则留下的区间为）如果（，，令且，，，，取两点，设初始单峰区间为。的大小，消去部分区间计算和比较它们函数值过峰区间内任取两点，通区间消去法是在初始单缩小区间的区间消去法对于所有的一维搜索方法，首先遇到的共同问题是：如何确定一个初始搜索区间，使该区间内含有函数的极小点，且在该区间内函数有唯一的极小点，这个初始搜索区间就是单峰区间。*xx)(xf2x*x1x单峰区间设函数f(x)在区间内有定义，且(1)在区间内存在极小点，即有(2)区间上的任意x，均满足；区间上的任意x，有x)(xf2x*x1x21,xx用解析法给单峰区间下一个定义：*x21,*),()(minxxxxfxf*,1xx0),()(xxxfxf2*,xx0),()(xxxfxf则称闭区间为函数f(x)的单峰区间。21,xx单峰区间的特点：单峰区间内，在极小点的左边，函数是严格减少的，在极小点的右边，函数是严格增加的；如果区间是一个单峰区间，x是区间内的一点，则两个不等式中必有一个成立；单峰区间内的函数图形表现为“高－低－高”的形态。应用这一特征可以确定单峰区间。)()()()(bfxfafxf和ba,如果函数具有多个极小点，则表现为多峰函数。此时，需要对变量取值范围进行适当的划分，使每一个子空间只包含一个极小点，才能进行一维搜索。一维搜索时，同样需要在每个子空间内寻找单峰区间。注意：确定单峰区间的进退法区间搜索的终止条件:找到三点a,c,b,满足(a)(c)(b),输出[a,b].acb算法思想先在初始点的左右方向中确定一个下降方向.沿着下降方向向前搜索,直到遇到上升点.搜索的前一点与上升点构成所求区间.另外,用到步长加倍,提高搜索效率.进退法算法1.初始化.k=0,k=0,hk=h0,t=t01.计算0=(0).2.比较目标值.k+1=k+hk,计算k+1=(k+1).若k+1k,转步3;否则,转步4.3.加大步长.hk+1=thk,=k,k=k+1,k=k+1,k=k+1,转步2.4.反向搜索.若k=0,转换搜索方向,hk=-hk,=k+1,转步2;否则,停止.输出a=min{,k+1},b=max{,k+1}.k-迭代变量;k-当前点;-前一点;k+1-后一点;hk-步长t-步长加倍系数进退法举例k-迭代变量;k-当前点;-前一点;k+1-后一点;hk-步长t-步长加倍系数()014235t=1.5a=3b=5例：试用进退算法确定函数的初始搜索区间，设初始点，初始步长h=1。96)(2xxxf21,xx00x]7,1[],[1604731][321321bafffxxx输出初始单峰区间为，，，，最后的迭代结果为解采用不同的初始点、不同的初始步长得到的初始单峰区间可能不一样，但只要这个单峰区间包含极小点，就是正确的。基本原理对于目标函数f(x)，在区间[a,b]内，适当插入两个内分点x1和x2(x1x2),它们把[a,b]分成三段。计算并比较x1和x2两点的函数值f(x1)和f(x2)，因为[a,b]是单峰区间，故当f(x1)f(x2)时，极小点必在[x1,b]中；当f(x1)≤f(x2)时，极小点必在[a,x2]中。黄金分割法无论发生在那种情况，都将包含极小点的区间缩小，即可删去最左段或最右段，然后在保留下来的区间上做同样的处理，如此迭代下去，将使搜索区间逐步减小，直到满足预先给定的精度（终止准则）时，即获得一维优化问题的近似最优解。a2x1xb1f2fa2x1xb1f2fbaab消去函数值大的内分点到同一侧端点之间的区间黄金分割法要求在区间[a,b]中插入的两点位置是对称的，如图所示，ax1=x2b。设区间长为L，插入的两个点把区间分成较长的一段α和较短的一段(L–α)。这样，无论删去那一段，保留区间长度总是α。21axbxLbxax21αLL－αa2x1xb比例系数—式中：LLLLLLLLLL382.0618.0618.02152150101012222αLL－αa2x1xb黄金分割法的迭代步骤（1）给定初始单峰区间[a,b]及允许误差ε0；（2）计算内分点及其函数值)(),()(618.0)(382.0221121xffxffabaxabax（3）比较函数值f1和f2的大小；根据比较结果缩短搜索区间)(),(382.0,,,11121212xffabaxffxxbxA.当f1≤f2时，极小点必在[a,x2]中，则B.当f1f2时，极小点必在[x1,b]中，则)(),(618.0,,,22212121xffabaxffxxax（4）判断是否满足精度要求。若新区间已缩短至预定精度要求，即，则转第5）步；否则转第3）步，进行下一次迭代计算。（5）输出最终区间的中点作为近似最优点，其对应的函数值即为最优值，他们组成的最优解为：ab)(,2***xffbaxa1µ1b11a2µ2b22只计算一个新点就能将区间缩小倍.bk+1-ak+1=(bk-ak)另外,设,µ在[a,b]中对称bk-µk=k-ak1=a1+(1-)(b1-a1)µ1=a1+(b1-a1)µ2=a2+(b2-a2)=a1+(µ1-a1)=a1+(a1+(b1-a1)-a1)=a1+2(b1-a1)由1=µ2,1-=2,=(5-1)/2=0.618算法特点：(2)算法1.初始化.a1,b1,1=a1+0.382(b1-a1),µ1=a1+0.618(b1-a1),k=1.计算(1),(µ1).取0.2.比较目标值.若(k)(µk)转步3;否则,转步4.3.若bk-k,停止,输出µk.否则,ak+1=k,bk+1=bk,k+1=µk.µk+1=ak+1+0.618(bk+1-ak+1),计算(µk+1),转步2.4.若µk-ak,停止,输出k.否则,ak+1=ak,bk+1=µk,µk+1=k.k+1=ak+1+0.382(bk+1-ak+1),计算(k+1),转步2.2.0532)(min2，允许误差，xxxxf【例8】试用黄金分割法求解优化问题：Nabx1x2f1f20-3.0005.0000.0561.9440.1157.6671-3.0001.944-1.1110.056-0.9860.1152-3.0000.056-1.832-1.111-0.306-0.9873-1.8320.056-1.111-0.665-0.987-0.8884-1.832-0.665-1.386-1.111-0.851-0.9875-1.386-0.665-1.111-0.940-0.997-0.9966-1.111-0.665-0.940-0.835-0.966-0.9737-1.111-0.835-1.006-0.940-0.999-0.9968-1.111-0.940-1.046-1.006-0.996-0.999循环迭代历次结果教材P100例3-5,自己对照学习适于目标函数易求一阶或二阶导数的情形。平分法是取具有极小点的单峰函数的探索区间[s,e]的中点m作为计算点，并根据函数在m处的一阶导数来判断应该消去m点左右哪一半探索区间，收缩探索区间。平分法的收缩率约为0.5。给定k=0,s(0),e(0),1,2时，平分法的迭代步骤如下：平分法1）计算m(k)=(s(k)+e(k))/2,如，则终止迭代，并取*=s(k)，否则转下一步；2）计算，如，则终止迭代，并取*=s(k)，否则转下一步；3）如0，则取新区间为[s(k),m(k)],否则为[m(k),e(k)]，当k=k+1后转1）。1)()(kske2)()(kmf)()(kmf)()(kmf适于目标函数f(x)的二阶导数均大于0的情形。方法：采用目标函数的曲线上某点x(k)的切线代替该点附近的导函数弧来逼近一阶导函数根*。)(xf切线法切线法的原理图ya(1)(0)b(2)*y=f'(x(k)+(k)s)0)('')(')('')(')()()()()()1()0()0()0()0()1()0(SxfSxfSxfSxfkkkkkk经过有限次迭代，当k足够大时，总可以满足：此时可近似认为*=(k))(')('')(')()()()()()()()1(sxfsxfsxfkkkkkkkk或例：采用切线法求一元函数f(x)=x2-7x+10在初始区间[1,7]内，迭代精度=0.35下的最优解。解：（1）则f(x)为区间[1,7]内的凸函数，存在最小值。（2）取x(0)=1,得存在（3）取x*=x(1)=3.5，则f(x*)=-2.25。5)(')0(xf5.3)('')(')0()0()0()1(xfxfxx0)(')1(xf02)('',07)7(',05)1(',72)('xfffxxf适于目标函数易求一阶或二阶导数的情形。插值法：当目标函数比较复杂，不易通过limf(x(k