02优化设计3

现代设计方法第二章优化设计§2.3一维搜索方法一维搜索的数学形式一维搜索的几何意义常用一维搜索方法：进退法黄金分割法二次插值法现代设计方法第二章优化设计一、概述在数值迭代方法中，任一次迭代，总是从某个已知点出发，沿着给定的方向（用梯度法确定方向）搜索到目标函数的极小值点，这个过程称为一维搜索。一维搜索法是构成非线性优化方法的基本算法，因为多元函数的迭代解法都可归结为在一系列逐步产生的下降方向上的一维搜索。)(kX)(kS)1(kX怎么理解“一维”的含义？现代设计方法第二章优化设计对“一维”的理解寻找目标函数在指定方向上的极小点，在计算上就是从沿前进多少的问题，即求步长因子的问题。从这个意义上讲，一维搜索是一个求解单元目标函数的过程。)(kX)(kS)(k一维搜索寻找合适的，使最小)(k)()()()(kkkSXf“一维”是指“一个方向”（）；)(kS现代设计方法第二章优化设计1.一维搜索的数学形式在任一次迭代中，使得即也就是说，一维搜索的每一次迭代过程都是寻找合适的步长因子，使得所得到的下一个点的函数值是该方向上所有可能点中最小的。)()()()1(kkkkSXX)(min)()()()1(kkkSXfXf)(min)()()()()()(kkkkkSXfSXf)1(kX从出发，沿着方向，求步长因子，使最小。此时的记为，称为最优步长因子。)(kX)(kS)()()(kkSXf)(k现代设计方法第二章优化设计2.一维搜索的几何意义从出发，沿方向一维搜索，就是求方向与等值线的切点，此时的步长因子即为最优步长因子。)(kX)(kS)(kS2x1x*X)(kX)(kS)1(kX现代设计方法第二章优化设计3.单峰区间对于所有的一维优化方法，首先遇到的共同问题是：如何确定一个初始搜索区间，使该区间内含有函数的极小点x*，且在该区间内函数有唯一的极小点，这个搜索区间就是单峰区间。x)(xf2x*x1x现代设计方法第二章优化设计用解析方法给单峰区间下个定义：设函数f(x)在区间内有定义，且①在区间内存在极小点，即有②对区间上的任意自变量x，有对区间上的任意自变量x，有则称闭区间为函数f(x)的单峰区间。21,xx21,xx21,*),()(minxxxxfxf*x*,1xx0),()(xxxfxf2*,xx0),()(xxxfxf21,xx现代设计方法第二章优化设计单峰区间的特点：在单峰区间内，在极小点的左边，函数是严格减少的，在的右边，函数是严格增加的；如果区间是一个单峰区间，x是区间内的一点，则两个不等式中必有一个成立；函数的函数值在单峰区间具有高—低—高的特征，我们用这一特征来确定初始的搜索区间。*x*xba,)()()()(bfxfafxf和现代设计方法第二章优化设计讨论：如果函数f（x）在区间[a,b]上有多个极值点，则称为多峰函数。对于多峰函数f(x)，只要适当划分区间，也可以使该函数f(x)在每一个子区间上是单峰的。现代设计方法第二章优化设计4.一维搜索的基本思想一维搜索就是要在初始单峰区间中求单峰函数的极小点。所以找初始单峰区间是一维搜索的第一步。然后将初始单峰区间逐步缩小，直至极小点存在的范围小于给定的一个正数，此称为收敛精度或迭代精度。此时，如区间为，即有可取该区间的中点作为极小点)()(,kkba)()(kkab)(21*)()(kkbax现代设计方法第二章优化设计(1)如果，则缩小的区间为要使区间缩小可采用区间消去法，即在初始单峰区间内任取两点，计算和比较它们函数值的大小，消去大函数值一边的区间，剩下的区间中一定包含极小点。设初始单峰区间为，取两点，令ba,2121,,,xxbaxx且)(),(2211xffxff21ff2,xaa2x1xb1f2f122,ffax现代设计方法第二章优化设计(3)如果，则缩小的区间为a2x1xb1f2f121,ffxbab1x2x1f2f1212,ffxx(2)如果，则缩小的区间为21ffbx,121ff21,xx现代设计方法第二章优化设计二、常用的一维搜索方法最优步长可通过求单变量函数的极小点来获得，即。这种在第k次迭代中求最优步长的过程，就是一维搜索过程，所用的方法就是一维优化方法。一维优化方法很多，介绍确定初始区间的进退法、黄金分割法和二次插值法。)(k)(minf)(k)()()()(kkSXff现代设计方法第二章优化设计1.确定初始区间的进退法(1)确定单峰区间的进退算法进退算法的基本思路：对单峰函数任选一个初始点及初始步长h，由此可确定两点。通过比较这两点函数值的大小，来决定第三点的位置，确定它们是否为“高－低－高”形态，如是，则说明已找到单峰区间，否则向前或向后继续寻求下一点，直到三点函数值形成“高－低－高”形态。)(xf1x现代设计方法第二章优化设计设有一维函数f(x)，给定初始点x0,初始步长h，求初始搜索区间的步骤如下：第一步给定初始点x0，初始步长h，令比较，此时有三种情况：①如果，说明极小点必在的右方，应向右(前进)搜索，加大步长，令转步骤二；②如果，说明极小点必在的左边，应向左（后退）搜索，交换的值并令，转步骤二；（交换后仍然是）)0(h21,xx)(,),(,22121101xffhxxxffxx21ff和21ff*x1x21ff*xhxx122121ffxx与、与hh21ffhh2现代设计方法第二章优化设计③如果，说明极小点必在点和之间，本身就是“高－低－高”的形态，也就是说已经找到单峰区间。第二步取下一个计算点，计算；第三步比较的大小，这个时候可能有二种情况：①如果，则已经形成了“高－低－高”的形态，初始单峰区间已经找到，当时，输出初始单峰区间当时，输出初始单峰区间为。②如果，则说明应继续搜索。令转步骤二。21ff*x1xhxx1221,xxhxx13)(33xff32ff和32ff321fff、、0h31,,xxba0h],[13xx32ff32322121;ffxxffxx、、hh2现代设计方法第二章优化设计【例1】试用进退算法确定函数的初始搜索区间，设初始点，初始步长h=1。96)(2xxxf21,xx00x现代设计方法第二章优化设计解：(1)(2)因为，说明极小点在右方，故作前进运算，设步长加倍，，取第三试点为4)1()(,9)0()(101,1,022110201fxfffxffhxxhxx21ffhh220)3()(,323323fxffhxx现代设计方法第二章优化设计(3)因为，说明极小点在右方，故继续作前进运算，步长加倍。令取第三点(4)此时因为，即这个相邻三点的函数值为形成了高—低—高的特征，故寻得初始搜索区间为。32ff4,12121ffxx0,33232ffxxhh4216)7()(,7433323fxffhxx32ff321fff、、]7,1[],[],[31xxba现代设计方法第二章优化设计采用不同的初始点、不同的初始步长得到的初始单峰区间可能不一样，但只要这个单峰区间包含极小点，就是正确的。现代设计方法第二章优化设计2.黄金分割法(1)基本原理在区间[a,b]内，适当插入两个内分点x1和x2(x1x2),它们把[a,b]分成三段。计算并比较x1和x2两点的函数值f(x1)和f(x2)，因为[a,b]是单峰区间，故当时，极小点必在[x1,b]中；当时，极小点必在[a,x2]中。12()()fxfx12()()fxfx现代设计方法第二章优化设计无论发生在那种情况，都将包含极小点的区间缩小，即可删去最左段或最右段，然后在保留下来的区间上做同样的处理，如此迭代下去，将使搜索区间逐步减小，直到满足预先给定的精度（终止准则）时，即获得一维优化问题的近似最优解。a2x1xb1f2fa2x1xb1f2fbaab21ff21ff现代设计方法第二章优化设计黄金分割法要求在区间[a,b]中插入的两点位置是对称的，如图所示，。设区间长为L，插入的每一点把区间分成较长的一段α和较短的一段(L–α)，如图所示，，，这样，无论删去那一段，保留的区间长度总是α，在每次迭代中，整个区间的长度L与较长一段长度α的比等于较长一段长度α与较短长度(L-α)的比。αLL－αaxxb2121xbaxLxbax21a1xb2x黄金分割法亦称0.618法。现代设计方法第二章优化设计比例系数—式中：LLLLLLLLLL382.0618.0618.02152150101012222αLL－αab1x2x120.382()0.618()xabaxaba现代设计方法第二章优化设计(2)黄金分割法的迭代步骤步骤一给定初始单峰区间[a,b]及允许误差ε0；步骤二计算内分点及其函数值步骤三比较函数值f1和f2的大小；)(),()(618.0)(382.0221121xffxffabaxabax现代设计方法第二章优化设计A.当f1≤f2时，极小点必在[a,x2]中，则)(),(382.0,,,11121212xffabaxffxxbx1f2f2fa1x2xba2xb1x现代设计方法第二章优化设计B.当f1f2时，极小点必在[x1,b]中，则)(),(618.0,,,22212121xffabaxffxxax2f1f1fab1x2xa1x2xb现代设计方法第二章优化设计步骤四根据比较结果缩短搜索区间步骤五判断是否满足精度要求。若新区间已缩短至预定精度要求，即，则转第六步；否则转第三步，进行下一次迭代计算。步骤六输出最终区间的中点作为近似最优点，其对应的函数值即为最优值，他们组成的最优解为：ab)(,2***xffbax现代设计方法第二章优化设计【例2】试用黄金分割法求解优化问题：2.0532)(min2，允许误差，xxxxf解：(1)根据题意单峰区间为(2)取内分点并计算函数值2.0,,5,3ba667.7)(944.1)35(618.03)(618.0115.0)(056.0)35(382.03)(382.0222111xffabaxxffabax现代设计方法第二章优化设计(3)比较函数值大小：因为，故可知新区间为，删去最右端，（在中再取内分点，把原来的x2变为新的b，原来的x1变为新的x2，原来的f1变为新的f2,找新的x1内分点。）即：比较函数值大小：因为(4)判断是否满足精度要求：b-a=1.944-(-3)=4.94421ff2,xa987.0)(111.1)3944.1(382.03)(382.0115.0056.0944.111121212xffabaxffxxbx115.0987.021ff2.0现代设计方法第二章优化设计循环迭代历次结果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.97