常用无约束最优化方法.ppt

第五章 常用无约束优化方法 5.8 单纯形法 单纯形法基本原理 以二元函数为例，说明单纯形法的原理． 设二元函数 在平面上取不在同一条直线上的三个点 ， 和 ，并以它们为顶点构成一单纯形——三角形．算出各顶点的函数值 ， ， ，比较其大小，不妨假定比较后有 这说明 点最差， 点最好， 点次差． 为了寻找极小点，一般来说应向最差点的反对称方向进行搜索．以 记为 的中点，在 的延长线上取点 ，使 称为 关于 的反射点． 第五章 常用无约束优化方法 计算函数值 ，可能出现以下几种情形： (1) 说明搜索方向正确，可进一步扩大效果，继续 沿向前搜索，也就是向前扩张．这时取 其中 为扩张因子，一般取 ． 如果 ，说明扩张有利，以点 代替点 构成新的单纯形 . 如果 ，说明扩张不利，舍去 ，仍以 代替点 构成新的单纯形 . 第五章 常用无约束优化方法 (2) 说明搜索方向正确，但无须扩张，以 代替 构成新的单纯形 (3) 表示 点走得太远，应缩回一些．若以 表示压缩因子，则有 常取为 0.5．以 代替 构成新的单纯 ． （5.35） (4) 说明应压缩更多一些，将新点压缩至 至 之间，令 （5.36） 如果 ，则以 代替 构成新的单纯形 。 第五章 常用无约束优化方法 如果 ，则认为 方向上所有点的函数值 都大于 ，不能沿此方向搜索．这时，可以以 为中心进行缩边．若使顶点 和 向 移近一半距离,得新单纯形 以此单纯形为基础再进行寻优． 以上说明，不管哪种情况，我们都可以得到一个新的单纯形，其中至少有一顶点的函数值比原单纯形为小．如此继续，直至满足收敛终止准则． 在n维情况下，一个单纯形含有n+1个顶点，计算工作量较大，但原理和上述二维情况相同． 下面具体看一下单纯形法迭代步骤。 第五章 常用无约束优化方法 单纯形法迭代步骤 已知 为n维变量，目标函数为 ，终止限为 ． (1) 构成初始单纯形 在n维空间中选初始点 （离最优点越近越好），从 出发，沿各坐标方向以步长 得 个顶点 ， ．这样选择顶点可保证向量组 线性无关．否则，就会使搜索范围局限在较低维的空间内，有可能找不到极小点．当然，在各坐标方向可以走不同的距离． 步长 的范围可取0.5~15.0，开始时常取 ，接近最优点时要减小，例如取0.5~1.0． (2) 计算各顶点的函数值 比较各函数值的大小，确定最好点 、最差点 和次差点 ，即 第五章 常用无约束优化方法 (3) 计算 之外各点的“重心” 求出反射点 (4) 当 时，需要扩张．令 如果 ，则以 代替 形成一新单纯形；否则，以 代替 构成新单纯形．然后转(8)． 第五章 常用无约束优化方法 (5) 当 时，以 代替 构成新单纯形，然后转(8) . (6) 当 时，则需要收缩．即令 以 代替 得新单纯形，并转(8)． (7)　当 时，令 如果 ，则将单纯形缩边，可将向量 的长度缩小一半，即 这样可得一新单纯形 ．否则就以 代替 得新单纯形．然后转(8)． 第五章 常用无约束优化方法