《华中农业大学现代设计方法第二章第三节推荐课件》由会员分享，可在线阅读，更多相关《华中农业大学现代设计方法第二章第三节推荐课件（49页珍藏版）》请在金锄头文库上搜索。
1、现代设计方法现代设计方法 第二章第二章 优化设计优化设计2.3 2.3 一维搜索方法一维搜索方法 一维搜索的数学形式一维搜索的数学形式 一维搜索的几何意义一维搜索的几何意义 常用一维搜索方法：常用一维搜索方法：进退法进退法 黄金分割法黄金分割法 二次插值法二次插值法2021/8/221现代设计方法现代设计方法 第二章第二章 优化设计优化设计一、概述一、概述 在数值迭代方法中，任一次迭代，总是从某个已知点在数值迭代方法中，任一次迭代，总是从某个已知点 出出发，沿着给定的方向发，沿着给定的方向 （用梯度法确定方向）搜索到目标函数（用梯度法确定方向）搜索到目标函数的极小值点的极小值点 ，这个过程称为
2、，这个过程称为一维搜索。一维搜索。 一维搜索法是构成非线性优化方法的基本算法，因为多元函一维搜索法是构成非线性优化方法的基本算法，因为多元函数的迭代解法都可归结为在一系列逐步产生的下降方向上的一维数的迭代解法都可归结为在一系列逐步产生的下降方向上的一维搜索搜索。 怎么理解怎么理解“一维一维”的含义的含义？2021/8/222现代设计方法现代设计方法 第二章第二章 优化设计优化设计对对“一维一维”的理的理解解寻找目标函数在指定方向上的极小点，在计算上就是从寻找目标函数在指定方向上的极小点，在计算上就是从 沿沿 前进多少的问题，即求步长因子前进多少的问题，即求步长因子 的问题。从这的问题。从这个意
3、义上讲，一维搜索是一个求解单元目标函数的过程。个意义上讲，一维搜索是一个求解单元目标函数的过程。一维搜索一维搜索寻找合适的寻找合适的 ，使，使 最小最小“一维一维”是指是指 “一个方向一个方向”（ ）；2021/8/223现代设计方法现代设计方法 第二章第二章 优化设计优化设计1.1.一维搜索的数学形式一维搜索的数学形式 在任一次迭代中，在任一次迭代中， 使得使得即即 也就是说，一维搜索的每一次迭代过程都是寻找合适的步长也就是说，一维搜索的每一次迭代过程都是寻找合适的步长因子因子 ，使得所得到的下一个点，使得所得到的下一个点 的函数值是该方向上所有的函数值是该方向上所有可能点中最小的。可能点中
4、最小的。 从从 出发，沿着方向出发，沿着方向 ，求步长因子，求步长因子 ，使，使 最小。此时的最小。此时的 记为记为 ，称为，称为最优步长因子最优步长因子。2021/8/224现代设计方法现代设计方法 第二章第二章 优化设计优化设计2.2.一维搜索的几何意义一维搜索的几何意义 从从 出发，沿方向出发，沿方向 一维搜索，就是求一维搜索，就是求方向方向 与与等值线的切点等值线的切点，此时的步长因，此时的步长因子即为最优步长因子。子即为最优步长因子。2021/8/225现代设计方法现代设计方法 第二章第二章 优化设计优化设计3.3.单峰区间单峰区间 对于所有的一维优化方法，对于所有的一维优化方法，首
5、先遇到的共同问题是：首先遇到的共同问题是： 如何确定一个初始搜索区间，如何确定一个初始搜索区间，使该区间内含有函数的极小点使该区间内含有函数的极小点x x* *，且在该区间内函数有唯一的极，且在该区间内函数有唯一的极小点，这个搜索区间就是小点，这个搜索区间就是单峰区单峰区间间。 2021/8/226现代设计方法现代设计方法 第二章第二章 优化设计优化设计 用解析方法给单峰区间下个定义：用解析方法给单峰区间下个定义：设函数设函数f(x)f(x)在区间在区间 内有定义，且内有定义，且 在区间在区间 内存在极小点内存在极小点 ，即有，即有 对区间对区间 上的任意自变量上的任意自变量x x，有，有 对
6、区间对区间 上的任意自变量上的任意自变量x x，有，有则称闭区间则称闭区间 为为函数函数f(x)f(x)的单峰区间的单峰区间。 2021/8/227现代设计方法现代设计方法 第二章第二章 优化设计优化设计单峰区间的特点：单峰区间的特点： q 在单峰区间内，在极小点在单峰区间内，在极小点 的左边，函数是严格减少的左边，函数是严格减少 的，在的，在 的右边，函数是严格增加的；的右边，函数是严格增加的；q 如果区间如果区间 是一个单峰区间，是一个单峰区间，x是区间内的一点，则是区间内的一点，则 两个不等式中必有一个成立；两个不等式中必有一个成立；q 函数的函数值在单峰区间具有函数的函数值在单峰区间具
7、有高高低低高高的特征，我们的特征，我们 用这一特征来确定初始的搜索区间。用这一特征来确定初始的搜索区间。2021/8/228现代设计方法现代设计方法 第二章第二章 优化设计优化设计讨论：讨论： 如果函数如果函数f f（x x）在区间）在区间a,ba,b上有多个极值点，则称为上有多个极值点，则称为多峰函数多峰函数。 对于多峰函数对于多峰函数f(x)f(x)，只要适当划分区间，也可以使该函，只要适当划分区间，也可以使该函数数f(x)f(x)在每一个子区间上是单峰的。在每一个子区间上是单峰的。 2021/8/229现代设计方法现代设计方法 第二章第二章 优化设计优化设计4.4.一维搜索的基本思想一维
8、搜索的基本思想 一一维维搜搜索索就就是是要要在在初初始始单单峰峰区区间间中中求求单单峰峰函函数数的的极极小小点点。所所以以找初始单峰区间是一维搜索的第一步找初始单峰区间是一维搜索的第一步。 然然后后将将初初始始单单峰峰区区间间逐逐步步缩缩小小，直直至至极极小小点点存存在在的的范范围围小小于于给给定定的的一一个个正正数数 ，此此 称称为为收收敛敛精精度度或或迭迭代代精精度度。此此时时，如如区间为区间为 ，即有，即有 可取该区间的中点作为极小点可取该区间的中点作为极小点 2021/8/2210现代设计方法现代设计方法 第二章第二章 优化设计优化设计(1)(1)如果如果 ，则缩小的区间为，则缩小的区
9、间为 要要使使区区间间缩缩小小可可采采用用区区间间消消去去法法，即即在在初初始始单单峰峰区区间间内内任任取取两两点点，计计算算和和比比较较它它们们函函数数值值的的大大小小，消消去去大大函函数数值值一一边边的的区区间间，剩剩下的区间中一定包含极小点。下的区间中一定包含极小点。 设设初初始始单单峰峰区区间间为为 ，取取两两点点 ，令令 2021/8/2211现代设计方法现代设计方法 第二章第二章 优化设计优化设计(3)(3)如果如果 ，则缩小的区间为，则缩小的区间为 (2)(2)如果如果 ，则缩小的区间为，则缩小的区间为 2021/8/2212现代设计方法现代设计方法 第二章第二章 优化设计优化设
10、计二、常用的一维搜索方法二、常用的一维搜索方法 最最优优步步长长 可可通通过过求求单单变变量量函函数数 的的极小点来获得，即极小点来获得，即 。这种在第。这种在第k k次迭代中求最优步长次迭代中求最优步长 的过程，就是的过程，就是一维搜索过程一维搜索过程，所用的方法就是，所用的方法就是一维优化方法。一维优化方法。 一一维维优优化化方方法法很很多多，介介绍绍确确定定初初始始区区间间的的进进退退法法、黄黄金金分分割法割法和和二次插值法二次插值法。2021/8/2213现代设计方法现代设计方法 第二章第二章 优化设计优化设计1.1.确定初始区间的进退法确定初始区间的进退法 (1) (1)确定单峰区间
11、的进退算法确定单峰区间的进退算法 进退算法的基本思路：进退算法的基本思路： 对对单单峰峰函函数数 任任选选一一个个初初始始点点 及及初初始始步步长长h h，由由此此可可确确定定两两点点。通通过过比比较较这这两两点点函函数数值值的的大大小小，来来决决定定第第三三点点的的位位置置，确确定定它它们们是是否否为为“高高低低高高”形形态态，如如是是，则则说说明明已已找找到到单单峰峰区区间间，否否则则向向前前或或向向后后继继续续寻寻求求下下一一点点，直到三点函数值形成直到三点函数值形成“高低高高低高”形态。形态。2021/8/2214现代设计方法现代设计方法 第二章第二章 优化设计优化设计 设有一维函数设
12、有一维函数f(x)f(x)，给定初始点，给定初始点x x0 0, ,初始步长初始步长h h ，求，求初始搜索区间初始搜索区间 的步骤如下：的步骤如下：第一步第一步 给定初始点给定初始点x x0 0，初始步长，初始步长h h，令，令 比较比较 ，此时有三种情况：，此时有三种情况： 如果如果 ，说明极小点，说明极小点 必在必在 的右方，应向右的右方，应向右( (前进前进) )搜索，加大步长，令搜索，加大步长，令 转步骤二；转步骤二； 如果如果 ，说明极小点，说明极小点 必在必在 的左边，的左边，应向左（后退）搜索，交换应向左（后退）搜索，交换 的值并令的值并令 ，转步骤二；转步骤二； （交换后仍然
13、是交换后仍然是 ） 2021/8/2215现代设计方法现代设计方法 第二章第二章 优化设计优化设计 如果如果 ，说明极小点，说明极小点 必在点必在点 和和 之之间，本身就是间，本身就是“高低高高低高”的形态，也就是说已经找到单峰区的形态，也就是说已经找到单峰区间间 。第二步第二步 取下一个计算点取下一个计算点 ，计算，计算 ；第三步第三步 比较比较 的大小，这个时候可能有二种情况：的大小，这个时候可能有二种情况： 如果如果 ，则，则 已经形成了已经形成了“高低高高低高”的形的形态，初始单峰区间已经找到，当态，初始单峰区间已经找到，当 时，输出初始单峰区间时，输出初始单峰区间 当当 时，输出初始
14、单峰区间为时，输出初始单峰区间为 。 如果如果 ，则说明应继续搜索。令，则说明应继续搜索。令转步骤二。转步骤二。2021/8/2216现代设计方法现代设计方法 第二章第二章 优化设计优化设计【例【例1 1】 试用进退算法确定函数试用进退算法确定函数 的初的初始搜索区间始搜索区间 ，设初始点，设初始点 ，初始步长，初始步长h=1h=1。2021/8/2217现代设计方法现代设计方法 第二章第二章 优化设计优化设计解：解： (1) (1) (2) (2)因为因为 ，说明极小点在右方，故作前，说明极小点在右方，故作前进运算，设步长加倍，进运算，设步长加倍， ，取第三试点为，取第三试点为2021/8/
15、2218现代设计方法现代设计方法 第二章第二章 优化设计优化设计(3)(3)因为因为 ，说明极小点在右方，故继续作前进运算，步，说明极小点在右方，故继续作前进运算，步长加倍。令长加倍。令取第三点取第三点(4)(4)此时因为此时因为 ，即，即 这个相邻三点的函数值为这个相邻三点的函数值为形成了形成了高高低低高高的特征，故寻得初始搜索区间为。的特征，故寻得初始搜索区间为。2021/8/2219现代设计方法现代设计方法 第二章第二章 优化设计优化设计 采用不同的初始点、不同的初始步长采用不同的初始点、不同的初始步长得到的初始单峰区间可能不一样，但只要这个得到的初始单峰区间可能不一样，但只要这个单峰区
16、间包含极小点，就是正确的。单峰区间包含极小点，就是正确的。2021/8/2220现代设计方法现代设计方法 第二章第二章 优化设计优化设计2.2.黄金分割法黄金分割法 (1) (1)基本原理基本原理 在区间在区间a,b内，适当插入两个内分点内，适当插入两个内分点x1和和x2 (x100；步骤二步骤二 计算内分点及其函数值计算内分点及其函数值步骤三步骤三 比较函数值比较函数值f1和和 f2的大小；的大小；2021/8/2225现代设计方法现代设计方法 第二章第二章 优化设计优化设计A.A.当当 f1 f2 时，极小点必在时，极小点必在a, x2中，则中，则2021/8/2226现代设计方法现代设计
17、方法 第二章第二章 优化设计优化设计B. B. 当当 f1 f2 时，极小点必在时，极小点必在x1, b中，则中，则2021/8/2227现代设计方法现代设计方法 第二章第二章 优化设计优化设计步骤四步骤四 根据比较结果缩短搜索区间根据比较结果缩短搜索区间步骤五步骤五 判断是否满足精度要求。若新区间已缩短至预定判断是否满足精度要求。若新区间已缩短至预定 精度要求，即精度要求，即 ，则转第六步；否则，则转第六步；否则 转第三步，进行下一次迭代计算。转第三步，进行下一次迭代计算。步骤六步骤六 输出最终区间的中点作为近似最优点，其对应的输出最终区间的中点作为近似最优点，其对应的 函数值即为最优值，他
18、们组成的最优解为：函数值即为最优值，他们组成的最优解为：2021/8/2228现代设计方法现代设计方法 第二章第二章 优化设计优化设计【例【例2 2】试用黄金分割法求解优化问题：试用黄金分割法求解优化问题：解：解：(1)(1)根据题意单峰区间为根据题意单峰区间为(2)(2)取内分点并计算函数值取内分点并计算函数值 2021/8/2229现代设计方法现代设计方法 第二章第二章 优化设计优化设计(3)(3)比较函数值大小：比较函数值大小： 因为因为 ，故可知新区间为，故可知新区间为 ，删去最右端，删去最右端，（在中再取内分点，把原来的（在中再取内分点，把原来的x x2 2变为新的变为新的b b，原
19、来的，原来的x x1 1变为变为新的新的x x2 2，原来的，原来的f f1 1变为新的变为新的f f2 2, ,找新的找新的x x1 1内分点。）内分点。）即：即： 比较函数值大小：因为比较函数值大小：因为(4)(4)判断是否满足精度要求：判断是否满足精度要求：b-a=1.944-(-3)=4.944 b-a=1.944-(-3)=4.944 2021/8/2230现代设计方法现代设计方法 第二章第二章 优化设计优化设计循环迭代历次结果循环迭代历次结果N Na ab bx x1 1x x2 2f f1 1f f2 20 0-3.000-3.0005.0005.0000.0560.0561.9
20、441.9440.1150.1157.6677.6671 1-3.000-3.0001.9441.944-1.111-1.1110.0560.056-0.986-0.9860.1150.1152 2-3.000-3.0000.0560.056-1.832-1.832-1.111-1.111-0.306-0.306-0.987-0.9873 3-1.832-1.8320.0560.056-1.111-1.111-0.665-0.665-0.987-0.987-0.888-0.8884 4-1.832-1.832-0.665-0.665-1.386-1.386-1.111-1.111-0.851-
21、0.851-0.987-0.9875 5-1.386-1.386-0.665-0.665-1.111-1.111-0.940-0.940-0.997-0.997-0.996-0.9966 6-1.111-1.111-0.665-0.665-0.940-0.940-0.835-0.835-0.966-0.966-0.973-0.9737 7-1.111-1.111-0.835-0.835-1.006-1.006-0.940-0.940-0.999-0.999-0.996-0.9968 8-1.111-1.111-0.940-0.940-1.046-1.046-1.006-1.006-0.996-
22、0.996-0.999-0.9992021/8/2231现代设计方法现代设计方法 第二章第二章 优化设计优化设计各次循环迭代的计算结果从表中可见，区间缩短各次循环迭代的计算结果从表中可见，区间缩短8 8次后，次后，最优解为：最优解为： 2021/8/2232现代设计方法现代设计方法 第二章第二章 优化设计优化设计3.3.二次插值法二次插值法 (1) (1)基本思想基本思想 二次插值法是一种近似法，其二次插值法是一种近似法，其基本思想基本思想是利用目标函数是利用目标函数值构成值构成“高低高高低高”形态的三点构造一个二次插值多项式，形态的三点构造一个二次插值多项式，并将这个多项式的极小点作为新的插
23、入点，根据插入点的目并将这个多项式的极小点作为新的插入点，根据插入点的目标函数值与这三点函数值的比较结果缩短搜索区间，直到区标函数值与这三点函数值的比较结果缩短搜索区间，直到区间长度满足精度要求。间长度满足精度要求。2021/8/2233现代设计方法现代设计方法 第二章第二章 优化设计优化设计 设设x1，x2，x3 是一维目标函数是一维目标函数f(x)在初始单峰区间中的在初始单峰区间中的三点，且三点，且x1 x2 x3，他们的函数值为：，他们的函数值为： 现把一维函数现把一维函数f(x)的的 作为二作为二次插值多项式次插值多项式 的插值点，的插值点，( (式中式中a，b，c是待定系数是待定系数
24、) )2021/8/2234现代设计方法现代设计方法 第二章第二章 优化设计优化设计 显然，在插值点处二次插值函数与目标函数应具有相同显然，在插值点处二次插值函数与目标函数应具有相同的函数值，即二次插值多项式满足如下公式：的函数值，即二次插值多项式满足如下公式：2021/8/2235现代设计方法现代设计方法 第二章第二章 优化设计优化设计 解此方程组得解此方程组得a，b，c的值分别为：的值分别为： 于是，插值函数于是，插值函数p(x)就成为一个确定的二次多项式，通就成为一个确定的二次多项式，通常称为常称为二次插值函数二次插值函数。2021/8/2236现代设计方法现代设计方法 第二章第二章 优
25、化设计优化设计 上述二次插值函数就是通过目标函数上述二次插值函数就是通过目标函数f(x)f(x)曲线上的三点曲线上的三点 画出，其方程为画出，其方程为 可以认为此曲线的极小点可以认为此曲线的极小点xp*就是原目标函数的近似极就是原目标函数的近似极小点小点x*，但是这种近似是否满足我们的精度要求则要用终止，但是这种近似是否满足我们的精度要求则要用终止准则来进行判断。在这里，判断准则是准则来进行判断。在这里，判断准则是2021/8/2237现代设计方法现代设计方法 第二章第二章 优化设计优化设计 按二次函数的性质按二次函数的性质 将上面求得的系数将上面求得的系数a a，b b代入上式，则得插值函数
26、的极小点代入上式，则得插值函数的极小点为：为：2021/8/2238现代设计方法现代设计方法 第二章第二章 优化设计优化设计 如果如果xp*不满足不满足 ，则以此点作为下单峰区间，则以此点作为下单峰区间的一个插入点，采用区间消去法缩短搜索区间，重复上述过的一个插入点，采用区间消去法缩短搜索区间，重复上述过程，直到程，直到xp*满足终止准则为止。满足终止准则为止。 二次插值法采用二次插值多项式的极小点作为插入点，二次插值法采用二次插值多项式的极小点作为插入点，由于该插入点包含了目标函数在三个已知点上的函数值信息，由于该插入点包含了目标函数在三个已知点上的函数值信息，无疑将使新的插入点向极小点逼近
27、的过程加快，从而提高优无疑将使新的插入点向极小点逼近的过程加快，从而提高优化工作的效率。化工作的效率。2021/8/2239现代设计方法现代设计方法 第二章第二章 优化设计优化设计(2)(2)二次插值法的迭代步骤二次插值法的迭代步骤 1) 1)确定初始区间确定初始区间a，b和精度和精度； 2) 2)在区间内选取三点在区间内选取三点x1，x2，x3。一般取。一般取x1，x3分别为初分别为初始区间的左右端点，始区间的左右端点， x2 为区间的一个内点，开始时可取为区间的一个内点，开始时可取 3) 3)计算计算x1，x2，x3 对应的目标函数值：对应的目标函数值：2021/8/2240现代设计方法现
28、代设计方法 第二章第二章 优化设计优化设计 4) 4)计算二次插值多项式的极小点计算二次插值多项式的极小点xp*和和 f p 5) 5)精度判断精度判断2021/8/2241现代设计方法现代设计方法 第二章第二章 优化设计优化设计 A. A.若若 ，说明搜索区间已经足够小，迭代结，说明搜索区间已经足够小，迭代结束，当束，当f p f2 时，输出目标函数的最优解为时，输出目标函数的最优解为 xp*和和f(xp*); ;当当f pf2 时，输出目标函数的最优解为时，输出目标函数的最优解为x2和和f2 B. B.若若 ，则需比较点，则需比较点xp*和和x2， fp和和f2的大的大小，并根据情况缩短搜
29、索区间，得到新的三点（新的三点小，并根据情况缩短搜索区间，得到新的三点（新的三点仍以仍以x1，x2，x3表示，它们应保持两端点表示，它们应保持两端点x1和和x3 的函数值大、的函数值大、中间点中间点x2的函数值小的特点），再转第的函数值小的特点），再转第4 4）步继续迭代）步继续迭代. .2021/8/2242现代设计方法现代设计方法 第二章第二章 优化设计优化设计xp*和和x2，f p和和 f2的大小比较可能出现四种情况的大小比较可能出现四种情况2021/8/2243现代设计方法现代设计方法 第二章第二章 优化设计优化设计【例【例3 3】用二次插值法求解优化问题：用二次插值法求解优化问题：【
30、分析】【分析】 题中没有给出初始单峰区间，因此首先要用进退法确题中没有给出初始单峰区间，因此首先要用进退法确定一个初始单峰区间定一个初始单峰区间 a a，b b 。寻找单峰区间过程中得到的。寻找单峰区间过程中得到的“高低高高低高”三点即可作为二次插值法需要的三点即可作为二次插值法需要的x1，x2，x3三点。三点。2021/8/2244现代设计方法现代设计方法 第二章第二章 优化设计优化设计解：解：(1)(1)确定初始单峰区间确定初始单峰区间 由于由于 ，因继续向前搜索，令，因继续向前搜索，令由于由于 ，所以初始单峰区间已经找到为，所以初始单峰区间已经找到为(2)(2)用二次插值法逼近极小点用二
31、次插值法逼近极小点 (a) (a)将第一步求出的将第一步求出的 代入二次插代入二次插值公式，求得插值点及其函数值：值公式，求得插值点及其函数值： 2021/8/2245现代设计方法现代设计方法 第二章第二章 优化设计优化设计 由于由于 ，故新区间为，故新区间为 作精度检作精度检: :由于由于 ，故应，故应继续作二次插值计算。继续作二次插值计算。 (b) (b)在新区间内，相邻的三点依次为在新区间内，相邻的三点依次为将它们代入二次插值公式计算，得将它们代入二次插值公式计算，得2021/8/2246现代设计方法现代设计方法 第二章第二章 优化设计优化设计由于由于 ，故新区间为，故新区间为作精度检验
32、：由于作精度检验：由于故结束一维搜索，极小点为故结束一维搜索，极小点为 2021/8/2247现代设计方法现代设计方法 第二章第二章 优化设计优化设计【本节思考题】【本节思考题】1.1.为什么一维搜索要以单峰区间为基础？为什么一维搜索要以单峰区间为基础？2.2.区间消去法是怎样缩短搜索区间的？区间消去法是怎样缩短搜索区间的？3.3.在黄金分割法中，如果出现了两个内分点函数值相在黄金分割法中，如果出现了两个内分点函数值相等的情况，应该怎样处理？等的情况，应该怎样处理？2021/8/2248现代设计方法现代设计方法 第二章第二章 优化设计优化设计【作【作 业】业】1.1.确定函数确定函数 的初始区间，的初始区间， 取取2.2.用黄金分割法求解以下问题用黄金分割法求解以下问题( (缩小区间缩小区间3 3次次) )2021/8/2249
