4_约束最优化.ppt

第四章 约束问题的最优化方法 §4.1 引言 §4.1 引言 §4.1 引言 §4.1 引言 §4.2 内点惩罚函数法 §4.2 内点惩罚函数法 §4.2 内点惩罚函数法 §4.2 内点惩罚函数法 §4.2 内点惩罚函数法 §4.2 内点惩罚函数法 §4.2 内点惩罚函数法 §4.2 内点惩罚函数法 大作业布置 §4.3 外点惩罚函数法 (衰减函数法） §4.3 外点惩罚函数法 §4.3 外点惩罚函数法 §4.3 外点惩罚函数法 §4.3 外点惩罚函数法 §4.3 外点惩罚函数法 §4.3 外点惩罚函数法 §4.4 混合惩罚函数法 §4.4 混合惩罚函数法 §4.5 随机方向搜索法 §4.5 随机方向搜索法 §4.5 随机方向搜索法 §4.5 随机方向搜索法 §4.5 随机方向搜索法 §4.5 随机方向搜索法 §4.6 复合形法 §4.6 复合形法 §4.6 复合形法 §4.6 复合形法 §4.6 复合形法 §4.6 复合形法 §4.6 复合形法 §4.6 复合形法 §4.7 可行方向法 §4.7 可行方向法 §4.7 可行方向法 §4.7 可行方向法 §4.7 可行方向法 §4.7 可行方向法 §4.8 约束优化设计方法小结 一. 单纯形法： 定义： 基本思想： 以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶点，组成新的单纯形，这样不断地迭代，单纯形逐渐逼近最优点。 以二维空间中的映射法为例： X(1)=X(H) X(2) X(3) X(S) X(R)=X(4) X(5) X(6) 在 n 维空间中，由n+1个点组成的图形称单纯形。 X* 二. 复合形法： 定义： 在 n 维空间中，由 k≥n+1 个点组成的多面体称为复合形。 基本思想： 以一个较好的新点，代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。 说明： 单纯形是无约束优化方法，而复合形可用于约束优化的方法。 因为顶点数较多，所以比单纯形更灵活易变。 复合形只能解决不等式约束问题。 因为迭代过程始终在可行域内进行，运行结果可靠。 三. 迭代方法： 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) 2. 变形法一 —— 扩张法： 变形法二 —— 收缩法： 四. 初始复合形的形成： 人工选择初始复合形： 随机产生初始复合形： 若可行域是非凸集，可能失败，需减小上、下界再进行。 五. 步骤： 六. 方法评价： 计算简单，不必求导，占内存小； 随着维数的增加，效率大大下降； 不能解含等式约束的问题； 建议： ①　初始α取1.3。 ②　n+1≤ k ≤ 2n ，当 n ≤ 5 时，k取值接近 2n ； 当 n 5 时，k 的取值可小些。 一. 基本思想： 在第 k+1 次迭代时，从 x(k) 点出发，寻找一个可行的搜索方向和合适的步长因子，从而得到一个可行、目标函数值下降的新点 x(k+1) ，再以此点出发，寻找新点，直至满足收敛条件，得到最优点 x* 。 α(k) 的选择原则： 使新点 x(k+1) 在可行域内。 S (k) 的选择原则： ① 必须是可行方向，即必须与所有适时约束的梯度方向成钝角。 ② 必须是目标函数值下降的方向，即必须与目标函数的负梯度方向成锐角。 同时满足以上两个条件的方向，称为适用可行方向。 二. 搜索策略： 可根据目标函数和约束函数的不同性态，选择不同的搜索策略。 ① 边界反弹法： 第一次搜索为负梯度方向，终止于边界。以后各次搜索方向均为适用可行方向，以最大步长从一个边界反弹到另一个边界，直至满足 K-T