机械优化设计_第三章一维搜索方法

机械优化设计第三章一维搜索方法一、一维搜索的概念二、搜索区间的确定与区间消去法原理三、一维搜索的试探方法——黄金分割法四、一维搜索的插值方法机械优化设计一、一维搜索的概念当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算：1(0,1,2)kkkkXXdkkdk当方向给定，求最佳步长就是求一元函数1kkkkkfxfxd的极值问题。这一过程被称为一维搜索。机械优化设计一维搜索是优化搜索方法的基础。f(x(k+1))=min.f(x(k)+αS(k))=f(x(k)+α(k)S(k))机械优化设计求解一元函数的极小点a*a，可用解析法。12TTfxadfxadfxadGad上式求α的极值，即求α导数为零。212TTfxdfxdGd*0TTdfxdGd则*TTdfxdGd机械优化设计数值解法基本思路：kk先确定所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得的数值近似解。解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。一维搜索也称直线搜索。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。一维搜索一般分为两大步骤：(1)确定初始搜索区间[a，b]，该区间应是包括一维函数极小点在内的单谷区间。(2)在单谷区间[a,b]内通过缩小区间寻找极小点。机械优化设计二、搜索区间的确定与区间消去法原理1、确定搜索区间的外推法（1）单谷（峰）区间在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，其区间称为单谷区间。函数值：“大—小—大”图形：“高—低—高”单谷区间中一定能求得一个极小点。机械优化设计f(x)0α1α3α0f(x)α3α1说明：单谷区间内，函数可以有不可微点，也可以是不连续函数；机械优化设计（2）外推方法基本思想：对任选一个初始点及初始步长，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高—低—高”形态。)(xf1ah步骤：1）选定初始点a1，初始步长h=h0，计算y1=f(a1)和y2=f(a1+h)2）比较y1和y2；a）如果y1y2，向右前进，加大步长h=2h0，转（3）向前；b）如果y1y2，向左后退，h=-2h0，将a1和a2,y1和y2的值互换。转（3）向后探测；c）如果y1=y2，极小点在a1和a1+h之间。3）产生新的探测点a3=a2+h，y3=f(a3)；机械优化设计4）比较函数值y2和y3：a）如果y2y3，加大步长h=2h，a1=a2,a2=a3,转（3）继续探测；b）如果y2y3，则初始区间得到：a=min[a1,a3],b=max[a1,a3]，函数最小值所在区间为[a,b]。机械优化设计khx1x2x30h0初始点初始点+h012h0初始点初始点+h0初始点+3h024h0初始点+h0初始点+3h0初始点+7h038h0初始点+3h0初始点+7h0初始点+15h0前进搜索步骤表khx1x2x30h0初始点初始点+h012h0初始点+h0初始点初始点-2h024h0初始点初始点-2h0初始点-6h038h0初始点-2h0初始点-6h0初始点-14h0后退搜索步骤表机械优化设计（3）搜索区间外推法程序框图是否是是否否初始进退距给定01,hx0hh)(,),(221211xfyhxxxfy21yyhh2)(,3323xfyhxx32yy0h31,xbxa结束13,xbxa1313yyxxhh32322121,,yyxxyyxx3xf2x1xx1x2x3x前进计算1x2x3xfx1x2x3x后退计算1x2x1y2y3y机械优化设计.1.0,0,983)(.1013hxxxxf初始进退距初始点给定的一维优化初始区间用外推法确定函数例题:解khx1y1x2y2x3y300.10.2090.18.2030.36.68110.40.18.2030.36.6810.74.42920.80.36.6810.74.4291.57.125.5.1,3.0,ba可得初始搜索区间机械优化设计.1.0,8.1,983)(.2013hxxxxf初始进退距初始点给定的一维优化初始区间用外推法确定函数例题:解khx1y1x2y2x3y300.1-0.21.812.0961.914.3771.914.3771.812.0961.68.4881-0.41.812.0961.68.4881.24.5842-0.81.68.4881.24.5840.45.992.6.1,4.0,ba可得初始搜索区间x0.9426最优点为机械优化设计练习确定的初始搜索区间。2)3()(xxfkhx1y1x2y2x3y3012091430141430716得区间]7,1[],[bakhx1y1x2y2x3y301-254696954301-45430-116得区间]5,1[],[ba1,501hx2）取1,001hx解：1）取机械优化设计2、区间消去法原理11()()fafb极小点必在区间内。1,ab11()()fafb则取为缩短后的搜索区间。1,ab基本思想：,ab11,ab11ab，搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。在搜索区间内任取两点且计算其函数值得如下结论：机械优化设计缩小的新区间为必在。11()()fafb缩小的新区间为必在；1,ab11()()fafb1,ab机械优化设计3、一维搜索方法分类根据插入点位置的确定方法，可以把一维搜索法分成两大类：试探法：即按照某种规律来确定区间内插入点的位置，如黄金分割法，裴波纳契法等。裴波纳契数列：1、1、2、3、5、8、13、21、34、55、89、144插值法（函数逼近法）：通过构造插值函数来逼近原函数，用插值函数的极小点作为区间的插入点，如二次插值法，三次插值法等。机械优化设计三、一维搜索的试探方法——黄金分割法1、前提函数在区间上是单谷函数。,ab2、点的插入原则（1）要求插入点的位置相对于区间,ab两端点具有对称性。1()bba2()aba（2）要求保留下来的区间内再插入一点所形成的新三段具有相同的比例分布。21,机械优化设计3、点位置的确定方法结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即。)1(::1)(618.0)()(618.0)(21abaabaabbabb两内分点值:机械优化设计4、黄金分割法的搜索过程（1）给出初始搜索区间及收敛精度，将赋以,ab0.618（2）按坐标点计算公式计算并计算其对应的函数值12和12,ff（3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。（4）检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足返回到步骤（2）。（5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。618.0ln)]/(ln[abk缩短区间的总次数（迭代次数）:机械优化设计5、黄金分割法程序框图给定,,ba)(),(618.0222xfyabax)(),(382.0111xfyabax21yy否否21211,,yyxxxa)(),(618.0222xfyabax是)(),(382.0111xfyabax12122,,yyxxxbab是)()(5.0xffbax止xfab1x2x1y2y1x2xbxfab1x2x1y2y1x2xa也可采用迭代次数是否大于或等于k作终止准则。机械优化设计6、举例22f35对函数，当给定搜索区间时，试用黄金分割法求极小点。表3-1黄金分割法的搜索过程迭代序号aa1a2by1比较y20-30.0561.94450.1157.6671-3-1.1110.0561.944-0.9870.1152-3-1.832-1.1110.056-0.306-0.9873-1.832-1.111-0.6650.056-0.987-0.8884-1.832-1.386-1.111-0.665-0.851-0.9875-1.386-1.111-0.940-0.665机械优化设计四、一维搜索的插值方法在某一确定的区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干点处的函数值。可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的最小值，这种方法称作插值方法，又叫函数逼近法。机械优化设计试探法（如黄金分割法）与插值法的比较：相同点：两种方法都是利用区间消去法原理将初始搜索区间不断缩短，求得极小值的数值近似解。试探法：试验点是按照某种个特定的规律确定；不考虑函数值的分布；不同点：表现在试验点（插入点）位置的确定方法不同。插值法：试验点是按照函数值近似分布的极小点确定；利用了函数值本身及其导数信息。机械优化设计1、牛顿法（切线法）对于一维搜索函数，假定已经给出极小点的一个较好的近似点，在点附近用一个二次函数来逼近函数yf00f20000012ffff然后以该二次函数的极小点作为极小点的一个新的近似点。根据极值必要条件：f100100ff1(0,1,2)kkkkfkf机械优化设计牛顿法的几何解释：在上图中，在处用一抛物线代替曲线，相当于用一斜线代替。这样各个近似点是通过对作切线求得与轴的交点找到，故牛顿法又称为切线法。)(f0)(')()('f)('f1(0,1,2)kkkkfkf机械优化设计牛顿法的计算步骤：1）给定初始点0，控制误差，并令0k2）计算,kkff3）求1kkkkff4）若1kk，则求得近似解，1k停止计算，否则作5）。5）令1kk转2）。机械优化设计例题：给定43246164f，试用牛顿法求其极小点。解：1）给定初始点03，控制误差0.001324(334)f212(21)f01001331366ff31133662）3）4）机械优化设计重复上边的过程，进行迭代，直到10.001kk为止。可得到计算结果如下表:表3-2牛顿法的搜索过程k01234值ak35.166674.334744.03964.00066f'(ak)-52153.3518332.301993.382990.00551f(ak)-24184.33332109.4458686.8699284.04720ak+15.166674.334744.039604.000664.00059机械优化设计优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。牛顿法的特点：机械优化设计２、二次插值法（抛物线法）基本思想：利用目标函数在不同3点的函数值构成一个与原函数相近似的二次多项式，以函数的极值点（即的根）作为目标函数的近似极值点。)