第四讲_约束优化方法.ppt

随机方向法流程图 随机方向法搜索过程 §4.5 随机方向搜索法 六. 方法评价： 优点： 对目标函数无性态要求； 收敛快（当m足够大时）； 不受维数影响，维数愈高，愈体现优点。 缺点： 对于严重非线性函数，只能得近似解； 当m不够大时，解的近似程度大； 对于非凸函数，有可能收敛于局部解。 例4-4 二维约束优化问题 试用两个随机数 构成第K次搜索的随机方向 ， 由当前点 出发，按照该方向取步长 计算各个迭代 点，确定该方向的终点 解：随机方向和新点： 适用性检验： 新点函数值小于旧点函数值，该点适用 可行性检验： 该点可行。因此，新点 是成功点 令 ，按照原来的步长和方向继续迭代，得到新点： 适用性检验： 可行性检验： 该点不可行。因此，该方向的极小点是： 新点函数值小于旧点函数值，该点适用 其函数值： §4.6 复合形法 一. 单纯形法： 定义： 基本思想： 以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶点，组成新的单纯形，这样不断地迭代，单纯形逐渐逼近最优点。 以二维空间中的映射法为例： X(1)=X(H) X(2) X(3) X(S) X(R)=X(4) X(5) X(6) 在 n 维空间中，由n+1个点组成的图形称单纯形。 X* §4.6 复合形法 二. 复合形法： 定义： 在 n 维空间中，由 k≥n+1 个点组成的多面体称为复合形。 基本思想： 以一个较好的新点，代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。 说明： 单纯形是无约束优化方法，而复合形可用于约束优化的方法。 因为顶点数较多，所以比单纯形更灵活易变。 复合形只能解决不等式约束问题。 因为迭代过程始终在可行域内进行，运行结果可靠。 §4.6 复合形法 三. 迭代方法： 1. 映射法： 例：二维空间中，k=4，复合形是四面体 x(1)x(2)x(3)x(4)，计算得： f (x(1) ) f (x(2) ) f (x(3) ) f (x(4) ),确定最坏点 x(H)= x(4) ，次坏点 x(G) = x(3) ，最好点 x(L) = x(1) 。 x(S)为除x(H)以外，各点的几何中心。 搜索方向：沿 x(H)→ x(S) 的方向。 步长因子（映射系数）α： α1，建议先取1.3。 映射迭代公式： x(R) = x(S) + α(x(S) — x(H) ) 若求得的 x(R) 在可行域内，且 f (x(R) ) f (x(H) )，则以x(R)代替x(H)组成新复合形，再进行下以轮迭代。 ● X(S) X(R) §4.6 复合形法 2. 变形法一 —— 扩张法： 变形法二 —— 收缩法： §4.6 复合形法 四. 初始复合形的形成： 人工选择初始复合形： 随机产生初始复合形： 若可行域是非凸集，可能失败，需减小上、下界再进行。 §4.6 复合形法 五. 步骤： §4.6 复合形法 复合形法法流程图 §4.6 复合形法 六. 方法评价： 计算简单，不必求导，占内存小； 随着维数的增加，效率大大下降； 不能解含等式约束的问题； 收敛速度较慢，不能用于解决等式约束的优化问题。 建议： ①　初始α取1.3。 ②　n+1≤ k ≤ 2n ，当 n ≤ 5 时，k取值接近 2n ； 当 n 5 时，k 的取值可小些。 初始复合形的三个顶点为： 例4-5 用复合形法求二维约束优化问题的最优解 解：1.检验初始复合形各个顶点的可行性，经过检验（略），全部 顶点都在可行域内。 2.计算初始复合形各个顶点的目标函数值： 得到坏点： 好点： 3.去掉坏点的其他各顶点的几何中心： 取映射系数 ，计算映射点： 用映射点 取代坏点 ，构成一个新的复合形，它的三个顶点是： 满足约束条件，是可行点 4.计算： 5.第二个复合形的迭代计算（略） §4.7 可行方向法 一. 基本思想： 在第 k+1 次迭代时，从 x(k) 点出发，寻找一个可行的搜索方向和合适的步长因子，从而得到一个可行、目标函数值下降的新点 x(k+1) ，再以此点出发，寻找新点，直至满足收敛条件，得到最优点 x* 。 α(k) 的选择原则：