现代设计理论与方法(优化设计第三章)

致知力行明德任责KunmingUniversityofScienceandTechnologyFacultyofMechanicalandElectricalEngineering现代设计理论与方法（优化设计）第三章一维搜索方法机电学院刘孝保明德任责致知力行第一节一维搜索概述1第二节搜索区间与区间消去法原理2第四节一维搜索的插值方法4第三节一维搜索的试探方法3第三章一维搜索方法目录第五节本章小结5明德任责致知力行第一节一维搜索概述求解优化问题的基本解法有：解析法数值解法解析法：即利用数学分析(微分、变分等）的方法，根据函数（泛函）极值的必要条件和充分条件求出其最优解析解的求解方法。在目标函数比较简单时，求解还可以。局限性：工程优化问题的目标函数和约束条件往往比较复杂，有时甚至还无法用数学方程描述，在这种情况下应用数学分析方法就会带来麻烦。明德任责致知力行数值迭代法的基本思路：是进行反复的数值计算，寻求目标函数值不断下降的可行计算点，直到最后获得足够精度的最优点。这种方法的求优过程大致可归纳为以下步骤：1）首先初选一个尽可能靠近最小点的初始点X（0），从X（0）出发按照一定的原则寻找可行方向和初始步长，向前跨出一步达到X（1）点；2）得到新点X（1）后再选择一个新的使函数值迅速下降的方向及适当的步长，从X（1）点出发再跨出一步，达到X（2）点，并依此类推，一步一步地向前探索并重复数值计算，最终达到目标函数的最优点。数值解法求解步骤明德任责致知力行优化过程中每一步的迭代形式为：11()()kkkkkkSFFk=0,1,2,xxxx式中：X（k）——第k步迭代计算所得到的点，称第k步迭代点，亦为第k步设计方案；a（k）——第k步迭代计算的步长；S（k）——第k步迭代计算的探索方向。图1-8迭代计算机逐步逼近最优点过程示意图用迭代法逐步逼近最优点的探索过程如图1-8所示。明德任责致知力行运用迭代法，每次迭代所得新的点的目标函数都应满足函数值下降的要求，并且最终收敛1()()kkFFxx1kkkkSxx（1）选择搜索方向（2）确定步长因子（3）给定收敛准则迭代法要解决的问题：明德任责致知力行第一节一维搜索概述当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算:1(0,1,2,)kkkkskxx当方向给定，求最佳步长就是求一元函数:ksk1()()()kkkkkffsxx的极值问题，这一过程被称为一维搜索.明德任责致知力行1(0,1,2,)kkkkxxSk明德任责致知力行一维搜索方法解析法高等数学已学过，即利用一维函数的极值条件：一维搜索方法数值解法分类试探法插值法**()0kk，求一维搜索也称直线搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。明德任责致知力行1.解析法：步骤:①f(X(k)+αS(k))沿S(k)方向在x(k)点进行泰勒展开；②取二次近似：()()()()()2()()()1()[()][]()2kkkkTkkTkkfxSfxfxSSGxS1()()()kkkkkffsxx一维搜索的目标函数可表示为：明德任责致知力行()()()0kkdfxSd③对α求导，令其为零。()()()()()[()][]()0kTkkTkkfxSSGxS()()()()()()[()][]()kTkkkTkkfxSSGxS④求得最优步长明德任责致知力行从上式看出，用解析法求最优步长面临的问题：需要求导，对与复杂函数，求导困难和无法求导的情况，将不适用。因此工程中，通常采用数值解法求最优步长，以迭代的方式逐步逼近最优解。明德任责致知力行第二节搜索区间的确定与区间消去法原理1、单谷(峰）区间在给定区间内仅有一个谷值的函数称为单谷数，其区间称为单谷区间。一、一维搜索的基本思想Of(a)bx*xa函数值：“大－小－大”图形：“高—低—高”单谷区间中一定能求得一个极小点找初始单谷区间是一维搜索的第一步；第二步使区间缩小。明德任责致知力行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明德任责致知力行khx1y1x2y2x3y300.10.2090.18.2030.36.68110.40.18.2030.36.6810.74.42920.80.36.6810.74.4291.57.125解：明德任责致知力行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明德任责致知力行练习：确定在以下初始条件下的初始搜索区间。2)3()(xxfkhx1y1x2y2x3y3012091430141430716得区间]7,1[],[bakhx1y1x2y2x3y301-254696954301-45430-116得区间]5,1[],[ba1,501hx2）取1,001hx解：1）取明德任责致知力行编程演示Matlab编程实现外推法明德任责致知力行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)两内分点值:明德任责致知力行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止也可采用迭代次数是否大于或等于k作终止准则。明德任责致知力行例题：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明德任责致知力行实例编程利用matlab进行黄金分割法明德任责致知力行第四节一维搜索的插值方法在某一确定的区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干点处的函数值。可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的最小值，这种方法称作插值方法，又叫函数逼近法。明德任责致知力行试探法（如黄金分割法）与插值法的比较：相同点：两种方法都是利用区间消去法原理将初始搜索区间不断缩短，求得极小值的数值近似解。试探法：试验点是按照某种个特定的规律确定；不考虑函数值的分布；不同点：表现在试验点（插入点）位置的确定方法不同。插值法：试验点是按照函数值近似分布的极小点确定；利用了函数值本身及其导数信息。明德任责致知力行1、牛顿法（切线法）对于一维搜索函数，假定已经给出极小点的一个较好的近似点，在点附近用一个二次函数来逼近函数yf00f20000012ffff然后以该二次函数的极小点作为极小点的一个新的近似点。根据极值必要条件：f100100ff1(0,1,2)kkkkfkf明德任责致知力行牛顿法的几何解释：在上图中，在处用一抛物线代替曲线，相当于用一斜线代替。