第二章一维搜素

优化设计一维搜索方法优化问题一维优化问题（1个设计变量）多维优化问题（多个设计变量）无约束多维问题单目标函数的优化问题多目标函数的优化问题有约束多维问题一维搜索，又称为线性搜索一维最优化方法是优化设计中最简单、最基本的方法一维问题是多维问题的基础，在数值方法迭代计算过程中，都要进行一维搜索，也可以把多维问题化为一些一维问题来处理。一维问题的算法好坏，直接影响到最优化问题的求解速度。一、概述数值迭代过程中，任何一次迭代，总是从某个已知点出发，沿着给定的方向（用某种优化方法确定）搜索到目标函数在该方向上的极小值点，这个过程称为一维搜索。一维搜索不仅可以求解一维优化问题，同时也是求解多维优化问题的基本步骤。)(kX)(kd)1(kX1.一维搜索的概念对“一维”的理解寻找目标函数在指定方向上的极小点，在计算上就是从沿前进多少的问题，即求步长因子的问题。从这个意义上讲，一维搜索是一个求解关于的单目标函数的过程。)(kX)(kd)(k一维搜索寻找合适的，使最小)(k)()()()(kkkdXf“一维”是指“一个方向”（）；)(kd任一次迭代，都是求使得其中：表示第k次迭代的搜索方向表示第k次迭代时最优步长因子表示待求的步长因子2.一维搜索的数学形式)()()()1(kkkkdXX)(min)(min)()()()1(kkkdXfXf)(k)(kd2x1x*X)(kX)(kd)1(kX3.一维搜索的几何意义从出发，沿方向一维搜索，就是求方向与等值线的切点，此时的步长因子即为最优步长因子。)(kX)(kd)(kd4.一维问题的解析算法0000000lim0cfcfxxfxxfxxfxxfcfxxfxxfcfcxfxxfxxfdxdfxfx　　　　　　　　证：点可微，则必有　取到极值，且函数在这点在定义区间上的一个内费马定律：如果函数一维函数求导：一元函数的极值点极小值点0xyy=f(x)x00xyy=f(x)x00yy=f(x)x0极大值点不存在极值点　，非极值，极大值，极小值，且一维函数极值条件：　又为极大值，则时，，当时，当为极小值，则时，，当时，当0000lim000000000000000xfxfxxxfxfxfxxfxxxfxxxxfxxxfxxxx解析方法的缺点是需要进行求导运算，有时非常不方便。在优化设计中通常采用数值计算方法，即通过计算机反复迭代求得近似值。数值方法的基本思路是：先确定搜索区间，然后根据区间消去原理不断缩小区间，从而获得近似解。5.单峰区间对于所有的一维搜索方法，首先遇到的共同问题是：如何确定一个初始搜索区间，使该区间内含有函数的极小点，且在该区间内函数有唯一的极小点，这个初始搜索区间就是单峰区间。*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,如果函数具有多个极小点，则表现为多峰函数。此时，需要对变量取值范围进行适当的划分，使每一个子空间只包含一个极小点，才能进行一维搜索。一维搜索时，同样需要在每个子空间内寻找单峰区间。注意：假设第k次得到的区间，若，则可取作为极小点。6.一维搜索的基本思想一维搜索就是要在初始单峰区间中求单峰函数的极小点。所以找初始单峰区间是一维搜索的第一步，然后将初始单峰区间逐步缩小，直至包括极小点的区间长度小于给定的一个正数，此称为收敛精度或迭代精度。)()(,kkba)()(kkab)(21*)()(kkbax][3][2][1)()(][][212112122122112121xxffbxffxaffxffxffxxbaxxba，，则留下的区间为）如果（，，则留下的区间为）如果（，，则留下的区间为）如果（，，令且，，，，取两点，设初始单峰区间为。的大小，消去部分区间计算和比较它们函数值过峰区间内任取两点，通区间消去法是在初始单缩小区间的区间消去法)a11fafb11)bfafb迭代迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。迭代•确定变量在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。•建立关系式所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。迭代•过程控制在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。迭代•%求第十个斐波那契数•a0=0•a1=1•fori=2:10•a2=a0+a1•a0=a1;a1=a2;•end••%求不大于100的最大斐波那契数•a0=0•a1=1•while(a2100)•a2=a0+a1•a0=a1;a1=a2;•end•二、搜索区间的确定确定搜索区间的原则：利用单峰函数值高-低-高的特征进退法：•已知搜索起点和初始步长•然后从起点开始以初始步长向前试探，如果函数值变大，则改变步长方向。•如果函数值下降，则维持原来的试探方向，并将步长加倍。()b()c【例】试用进退算法确定函数的初始搜索区间，设初始点，初始步长h=1。96)(2xxxf21,xx10x]7,1[],[1604731][321321bafffxxx输出初始单峰区间为，，，，最后的迭代结果为解采用不同的初始点、不同的初始步长得到的初始单峰区间可能不一样，但只要这个单峰区间包含极小点，就是正确的。（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[a3,a1]，函数最小值所在的区间为[a，b]。（1）选定初始点a1,初始步长h＝h0，计算y1＝f(a1)，y2＝f(a1＋h)。（2）比较y1和y2。（a）如y1y2,向右前进；转（3）向前；（b）如y1=y2,向左后退；h＝－h0，将a1与a2，y1与y2的值互换。转（3）向后探测；•function[a1,a3,a2,y1,y3,y2]=range_1(no,a0,h0)•h=h0;•a1=a0;y1=f_1(no,a1);•a2=a1+h;y2=f_1(no,a2);•ify2y1•h=-h;a3=a1;y3=y1;•a1=a2;y1=y2;a2=a3;y2=y3;•end•a3=a2+h;y3=f_1(no,a3);•whiley3y2•h=h*2;•a1=a2;y1=y2;a2=a3;y2=y3;•a3=a2+h;y3=f_1(no,a3);•end进退法计算机程序•functiony=f_1(no,x)••ifno==1•y=x*x;•elseifno==2•y=x(1)*x(1)+x(2)*x(2);•end•调用：y1=f(1,10)•y2=f(2,[10,10])求函数值的计算机程序•[a1,a3,a2,y1,y3,y2]=range(1,0,1);•[a1,a2,a3;y1,y2,y3]•[a1,a3,a2,y1,y3,y2]=range(1,-4,1);•[a1,a2,a3;y1,y2,y3]••[a1,a3,a2,y1,y3,y2]=range(2,[4;4],[1;1]);•[a1,a2,a3;y1,y2,y3]•[a1,a3,a2,y1,y3,y2]=range(2,[-4;-4],[1;1]);•[a1,a2,a3;y1,y2,y3]函数调用：三、一维搜索方法的分类从前面的分析可知，每次缩短区间，只需要在区间内在插入一点并计算其函数值。而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。一维搜索方法分类试探法插值法黄金分割法二次插值法1.黄金分割法最常用的一维搜索试探法是黄金分割法，又称0.618法。黄金分割法适用于确定区间上的任何单谷函数求极小值的问题。对函数除要求“单谷”之外没有任何其他要求。甚至可以不连续或者没有明确的函数表达式。黄金分割法是建立在区间消去法原理基础上的试探法。１、要求插入点a1、a2的位置相对于区间[a,b]两端点具有对称性。２、要求在保留下来的区间再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。22110510.61822黄金分割法的迭代步骤（1）给定初始单峰区间[a,b]及允许误差ε0；（2）计算内分点及其函数值)(),()(618.0)(618.0221121xffxffabaxabbx（3）比较函数值f1和f2的大小；根据比较结果缩短搜索区间)(),(618.0,,,11121212xffabbxffxxbxA.当f1≤f2时，极小点必在[a,x2]中，则B.当f1f2时，极小点必在[x1,b]中，则)(),(618.0,,,22212121xffabaxffxxax（4）判断是否满足精度要求。若新区间已缩短至预定精度要求，即，则转第5）步；否则转第3）步，进行下一次迭代计算。（5）输出最终区间的中点作为近似最优点，其对应的函数值即为最优值，他们组成的最优解为：ab)(,2***xffbax2.0532)(min2，允许误差，xxxxf【例】试用黄金分割法求解优化问题：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循环迭代历次结果2.Fibonacci法与黄金分割法的区别是：搜索区间的缩短率不采用黄金分割数0.618，而是采用Fibonacci数列：F(0)=F(1)=1F(k+1)=F(k)+F(k-1)计算流程：次后可以求得结果５、循环上轮循环中的值。　　另一个中间点保留计算一个中间点，及、４、根据