第二章一维搜素

1、优化问题优化问题一维优化问题一维优化问题（1个设计变量）个设计变量）多维优化问题多维优化问题（多个设计变量）（多个设计变量）无约束多维问题无约束多维问题单目标函数的优化问题单目标函数的优化问题多目标函数的优化问题多目标函数的优化问题有约束多维问题有约束多维问题 一维搜索，又称为线性搜索一维搜索，又称为线性搜索一维最优化方法是优化设计中最简单、最基本的方法一维最优化方法是优化设计中最简单、最基本的方法一维问题是多维问题的基础，在数值方法迭代计算过程一维问题是多维问题的基础，在数值方法迭代计算过程中，都要进行一维搜索，也可以把多维问题化为一些一中，都要进行一维搜索，也可以把多维问题化为一些一维问题

2、来处理。维问题来处理。一维问题的算法好坏，直接影响到最优化问题的求解速一维问题的算法好坏，直接影响到最优化问题的求解速度。度。一、概述一、概述 数值迭代过程中，任何一次迭代，总是从某个已数值迭代过程中，任何一次迭代，总是从某个已知点知点 出发，沿着给定的方向出发，沿着给定的方向 （用某种优化（用某种优化方法确定）搜索到目标函数在该方向上的极小值方法确定）搜索到目标函数在该方向上的极小值点点 ，这个过程称为一维搜索。，这个过程称为一维搜索。 一维搜索不仅可以求解一维优化问题，同时也是一维搜索不仅可以求解一维优化问题，同时也是求解多维优化问题的基本步骤。求解多维优化问题的基本步骤。)(kX)(kd

3、)1( kX1.1.一维搜索的概念一维搜索的概念 对对“一维一维”的理的理解解 寻找目标函数在指定方向上的极小点，在计算上寻找目标函数在指定方向上的极小点，在计算上就是从就是从 沿沿 前进多少的问题，即求步长因子前进多少的问题，即求步长因子 的问题。从这个意义上讲，一维搜索是一个求的问题。从这个意义上讲，一维搜索是一个求解关于解关于 的单目标函数的过程。的单目标函数的过程。)(kX)(kd)(k一维搜索一维搜索寻找合适的寻找合适的 ，使，使 最小最小)(k)()()()(kkkdXf “一维一维”是指是指 “一个方向一个方向”（ ）；)(kd任一次迭代，都是求任一次迭代，都是求使得使得其中：其

4、中： 表示第表示第k k次迭代的搜索方向次迭代的搜索方向 表示第表示第k k次次迭代时最优步长因子迭代时最优步长因子 表示待求的步长因子表示待求的步长因子2.2.一维搜索的数学形式一维搜索的数学形式 )()()()1(kkkkdXX)(min)(min)()()()1(kkkdXfXf)(k)(kd2x1x*X)(kX)(kd)1( kX3.3.一维搜索的几何意义一维搜索的几何意义 从从 出发，沿方向出发，沿方向 一一维搜索，就是求维搜索，就是求方向方向 与与等值线的切点等值线的切点，此时的步长，此时的步长因子即为最优步长因子。因子即为最优步长因子。 )(kX)(kd)(kd4.4.一维问题的

5、解析算法一维问题的解析算法 0000000lim0cfcfxxfxxfxxfxxfcfxxfxxfcfcxfxxfxxfdxdfxfx证：点可微，则必有取到极值，且函数在这点在定义区间上的一个内费马定律：如果函数一维函数求导：一元函数的极值点一元函数的极值点极小值点极小值点0 xyy=f(x)x00 xyy=f(x)x00yy=f(x)x0极大值点极大值点不存在极值点不存在极值点 ，非极值，极大值，极小值，且一维函数极值条件：又为极大值，则时，当时，当为极小值，则时，当时，当 0000lim000000000000000 xfxfxxxfxfxfxxfxxxfxxxxfxxxfxxxx 解析方

6、法的缺点是需要进行求导运算，解析方法的缺点是需要进行求导运算，有时非常不方便。有时非常不方便。 在优化设计中通常采用数值计算方法，在优化设计中通常采用数值计算方法，即通过计算机反复迭代求得近似值。即通过计算机反复迭代求得近似值。 数值方法的基本思路是：先确定数值方法的基本思路是：先确定搜索区搜索区间间，然后根据，然后根据区间消去区间消去原理不断缩小区间，原理不断缩小区间，从而获得近似解。从而获得近似解。5.5.单峰区间单峰区间 对于所有的一维搜索方法，对于所有的一维搜索方法，首先遇到的共同问题是：如何首先遇到的共同问题是：如何确定一个确定一个初始搜索区间初始搜索区间，使该，使该区间内区间内含有

7、函数的极小点含有函数的极小点，且，且在该区间内函数有在该区间内函数有唯一的极小唯一的极小点点 ，这个初始搜索区间就，这个初始搜索区间就是单峰区间。是单峰区间。 *xx)(xf2x*x1x 设函数设函数f(x)在区间在区间 内有定内有定义，且义，且(1)(1)在区间内存在极小点在区间内存在极小点 ，即有，即有 (2)(2)区间区间 上的任意上的任意x，均满足，均满足 ；区间；区间上的任意上的任意x，有，有 x)(xf2x*x1x21,xx用解析法给单峰区间下一个定义：用解析法给单峰区间下一个定义： *x21,*),()(minxxxxfxf*,1xx0),()(xxxfxf2*,xx0),()(

8、xxxfxf则称闭区间则称闭区间 为函数为函数f(x)的的单峰区间单峰区间。21,xx单峰区间的特点：单峰区间的特点： 单峰区间内，在极小点的左边，函数是严格减少单峰区间内，在极小点的左边，函数是严格减少的，在极小点的右边，函数是严格增加的；的，在极小点的右边，函数是严格增加的； 如果区间如果区间 是一个单峰区间，是一个单峰区间，x是区间内的一是区间内的一点，则点，则 两个不等式中必有两个不等式中必有一个成立；一个成立； 单峰区间内的函数图形表现为单峰区间内的函数图形表现为“高低高高低高”的的形态。形态。应用这一特征可以确定单峰区间。应用这一特征可以确定单峰区间。)()()()(bfxfafx

9、f和ba,如果函数具有多个极小点，则表现为多峰函数。此如果函数具有多个极小点，则表现为多峰函数。此时，需要对变量取值范围进行适当的划分，使每一时，需要对变量取值范围进行适当的划分，使每一个子空间只包含一个极小点，才能进行一维搜索。个子空间只包含一个极小点，才能进行一维搜索。一维搜索时，同样需要在每个子空间内寻找单峰区一维搜索时，同样需要在每个子空间内寻找单峰区间。间。注意注意： 假设第假设第k k次得到的区间次得到的区间 ，若，若 ， 则可取则可取 作为极小点。作为极小点。6.6.一维搜索的基本思想一维搜索的基本思想 一维搜索就是要在初始单峰区间中求单峰函数的一维搜索就是要在初始单峰区间中求单

10、峰函数的极小点。所以找初始单峰区间是一维搜索的第一极小点。所以找初始单峰区间是一维搜索的第一步，然后将初始单峰区间逐步缩小，直至包括极步，然后将初始单峰区间逐步缩小，直至包括极小点的区间长度小于给定的一个正数小点的区间长度小于给定的一个正数 ，此，此 称称为收敛精度或迭代精度。为收敛精度或迭代精度。 )()(,kkba)()(kkab)(21*)()(kkbax 3 2 1)()( 212112122122112121xxffbxffxaffxffxffxxbaxxba，则留下的区间为，则留下的区间为）如果）如果（，则留下的区间为，则留下的区间为）如果）如果（，则留下的区间为，则留下的区间为）

11、如果）如果（，令，令且且，取两点，取两点，设初始单峰区间为设初始单峰区间为。的大小，消去部分区间的大小，消去部分区间计算和比较它们函数值计算和比较它们函数值过过峰区间内任取两点，通峰区间内任取两点，通区间消去法是在初始单区间消去法是在初始单 缩小区间的区间消去法缩小区间的区间消去法 )a 11f af b 11)b f af b迭代迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。迭代 确定变量 在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

12、 建立关系式 所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。迭代 过程控制 在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。迭代%求第十个斐波那契数a0=0a1=1for i=2:10 a2=a0+a1 a0=a1;a1=

13、a2;end %求不大于100的最大斐波那契数a0=0a1=1while(a2yy3 3, , 加大步长加大步长 h h2h 2h ，a a1 1=a=a2 2,a,a2 2=a=a3 3, , 转（转（3 3）继续探测。）继续探测。 （b b）如）如y y2 2yyy2 2, ,向右前进；转（向右前进；转（3 3）向前；）向前； （b b）如）如y y1 1=y=y1 h=-h; a3=a1;y3=y1; a1=a2;y1=y2;a2=a3;y2=y3;enda3=a2+h;y3=f_1(no,a3);while y300；（2 2）计算内分点及其函数值）计算内分点及其函数值)(),()(6

14、18. 0)(618. 0221121xffxffabaxabbx（3 3）比较函数值）比较函数值 f1和和 f2的大小；的大小； 根据比较结果缩短搜索区间根据比较结果缩短搜索区间)(),(618. 0,11121212xffabbxffxxbxA. 当当 f1 f2 时，极小点必在时，极小点必在a, x2中，则中，则B. 当当 f1 f2 时，极小点必在时，极小点必在x1, b中，则中，则)(),(618. 0,22212121xffabaxffxxax（4）判断是否满足精度要求。若新区间已缩短至预）判断是否满足精度要求。若新区间已缩短至预定精度要求，即定精度要求，即 ，则转第，则转第5）步

15、；否则）步；否则转第转第3）步，进行下一次迭代计算。）步，进行下一次迭代计算。（5）输出最终区间的中点作为近似最优点，其对应）输出最终区间的中点作为近似最优点，其对应的函数值即为最优值，他们组成的最优解为的函数值即为最优值，他们组成的最优解为 ：ab)(,2*xffbax2 . 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.3

16、06-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，而是采用Fibon

17、acci数列：F(0)=F(1)=1F(k+1)=F(k)+F(k-1)计算流程：次后可以求得结果、循环上轮循环中的值。另一个中间点保留计算一个中间点，及、根据两端点、计算：根据：即为收敛次数。，确定出，即、根据及收敛精度、给出初始搜索区间nbaFFabFFFFFFabFFabnnabFabFbakkkknknknnnnnnnn1111322111211111111,(1)( )( )51lim0.6182nknkFF8569. 7.5040cossin)(min00nnFnabFxxxxf，查表得解：度度，允许误差度，【例】【例】试用试用Fibonacci法法求解优化问题：求解优化问题：Na

18、bF4/F5x1x2f1f2140505/843.7546.25-0.4995-0.4995243.75503/546.2547.5-0.4995 -0.4981343.7547.52/34546.25-0.5-0.4995443.7546.254545-0.5-0.5循环迭代历次结果循环迭代历次结果3.平分法 取具有极小点的单峰函数的搜索区间取具有极小点的单峰函数的搜索区间 的中点的中点 ，计算目标函数在该点的导数，计算目标函数在该点的导数来判断舍去的区间。（函数在极值点导数为零，来判断舍去的区间。（函数在极值点导数为零，在其左侧为负、右侧为正）在其左侧为负、右侧为正）,a b2ab步骤：步骤：1）计算）计算 c=(a+b)/2, 如如 ，则终止迭代，则终止迭代， 并取并取 *=c，否则转下一步；，否则转下一步；2）计算）计算 ，如，如 ，则终止迭代，则