第16讲约束优化计算方法

1、机械现代设计第16讲 约束优化设计方法 外点法 随机搜索法 复合型法等约束优化设计的最优解条件1 约束优化设计的最优点在可行域 D 中 最优点是一个内点，其最优解条件与无约束优化设计的最优解条件相同：2 约束优化设计的最优点在可行域 D 的边界上 设 X (k) 点有适时约束 则，在 X (k) 点的可行方向 S 应满足 若在所有满足式(1) 的可行方向 S 中，有可行下降方向 Si 存在，则 Si 还应满足约束优化设计的最优解条件 若在所有满足式(1) 的可行方向 S 中，找不到满足式(2)的可行下降方向，即：因此，目标函数 f (X) 在 X (k) 点的邻域中，再也不可能下降了，即 f

2、( X (k) ) 是目标函数 f (X) 在 X (k) 附近邻域中的极小值，X (k) 是其邻域的极小点。 约束优化设计的最优解条件 3 Kuhn-Tucker 最优性条件（K-T条件） 设 gj (X (k) ) ， j = 1、2、 、 l ，是 X (k) 点的适时约束，即有则 X (k) 点是约束优化问题的一个极小点的必要条件是注意：式(4) 中， 必须线 性无关，该条件才成立。约束优化设计的最优解条件不是极小点是极小点概述 惩罚函数法是一种约束优化问题的间接解法。 约束优化问题的间接解法的基本思想是把一个约束优化问题转化为无约束优化问题。一、外点法的惩罚函数 对于约束优化问题外点

3、法的惩罚函数为 Z0,一般Z=2.惩罚因子 r(k) 二、外点法的基本原理 对于式(1) 表示的约束优化问题，外点法定义惩罚函数如式(2)，把式(1) 表示的约束优化问题，转化一系列的无约束优化问题 外点法求解约束优化问题式(1) 的过程：i. 选取初始点 X(k) ，k = 0；ii. 选择合适的惩罚因子 r(0) iii. 从 X(0) 出发，求解无约束优化问题 得到 X*(r(0) ) ；iv. k = k +1 ，调整惩罚因子 r(k) ，从 X*(r(k-1) ) 出发，求解无约束优化问题 得到 X*(r(k) )，k = 1，2， 二、外点法的基本原理1) 当 X*(r(k) )

4、在可行域内，2) 当 X*(r(k) ) 在可行域外，则二、外点法的基本原理三、 惩罚因子 r(k) 的选择1 r(0) 的选取 2 r(k) ( k = 1、2、) 的选取 递增系数四、收敛条件 及 在外点法中，还必须判断 X*(r(k) ) 是否到达约束面，即 为减少迭代次数 k ，通常规定一个精度判据 0 = 103 105 ，要求五、外点法的计算步骤1 选择初始点 X(0) ，惩罚因子 r(0) 、递增系数 、1、2、0、k = 02 构造惩罚函数3 调用无约束优化方法，求解无约束优化问题 得到 X*(r(k) ) ；4 计算 X*(r(k) ) 违反约束条件的情况：5 判别 Q 0

5、?i. 是，输出 X* = X*(r(k) ) 及 f (X*) ，结束；ii. 否，6 判断收敛条件 及i. 否，ii. 是，输出 X* = X*(r(k) ) 及 f (X*) ，结束。7 五、外点法的计算步骤例: 用外点法求解下列有约束优化问题解: 惩罚函数为：用解析法求函数的极小值，运用极值条件：注意：应舍去在可行域的点。则无约束极值点为当惩罚因子渐增时，由下表可看出收敛情况。六、外点法的优缺点1 优点：i. 外点法可用于含有等式约束的约束优化问题；ii. 初始点 X(0) 可以是可行点，也可以是非可行点。2 缺点： 外点法求得的最优点，通常不是严格的可行点。 六、外点法的优缺点为了获

6、得严格的可行点，可以定义新的约束条件混合惩罚函数法内点法：适于处理不等式约束优化设计问题；外点法：适于处理等式约束优化设计问题。混合惩罚函数法：可以处理同时含有不等式约束和等式约束的优化设计问题。对于约束优化问题：混合惩罚函数法构造惩罚函数：混合惩罚函数法式(2) 对不等式约束采用的是内点法，对等式约束采用的是外点法。另一种方法则统一采用外点法：随机方向搜索法一、概述二、基本原理三、产生随机方向的方法四、初始点的选择五、随机方向搜索法的计算步骤一、概述 在可行域内选择一个初始点； 确定第一次的搜索方向：在若干个不同的方向试探性搜索，使得函数值下降； 取适当步长因子，在不破坏约束条件的情况下，向

7、前前进一步得到一个新点： 若新点处函数值下降，将起始点移至新点，重复前面步骤； 否则缩小步长因子直到找到一个好的可行点。 重复以上步骤，直到迭代步长小于设置误差。二、基本原理 对于约束优化问题1. 在可行域 D 内选择初始点 X (0)2. 随机地产生 N 个方向 e(j) ，j = 1，2，N3. 找到 N 个点 4. 从上述 N 个点中找出满足约束条件的可行点 X(j) ，j = 1，2，Ns N 计算 f (X(j) )，j = 1，2，Ns 找出YL = min f (X(j) )，j = 1，2，Ns 二、基本原理可行域随机方向二、基本原理5. 比较 YL 、 f (X(0) ) 若

8、 YL = f (X(0) ) ，则二、基本原理三、产生随机方向的方法2、在 n 维设计空间中 i. 在 -1 ，1 区间内，产生 n N 个均匀分布的伪随机数 ii. 计算四、初始点的选择1、决定性方法 在可行域内，确定一个可行的初始点 X(0) ： 用传统的设计方法，设计一个可行的设计方案，作为初始点。 适用于约束条件比较简单的优化问题。2、随机选择法i. 利用 n 个在 -1 ，1 内均匀分布的伪随机数 和区域约束产生初始点 X(0)，ii. 检验 X(0) ： 否，重选； 是，选到。五、随机方向搜索法的计算步骤1. 给定初始步长 、计算精度 、M 0、N 02. 选择初始点3. 检验初

9、始点 可行性：是， 否，4. 随机选取新的初始点5. 计算 产生随机方向 , 6. j = 1(对所有N个随机方向进行循环)7. 产生点 检验 的可行性：否，是，8. 计算9. 若 j N， 否则五、随机方向搜索法的计算步骤9. 选择 YL = f ( XL ) = min Y(j) ，j = 1，2，Ns Y0 = YL 10. 判断Y0 Y00 ?i. 否，ii. 是，11. 确定 S = XL X (0) ，H = 1.3 H0 12. 计算 X = X (0) + H S 检验i. 是，ii. 否，13. 判断 YL = n + 1 个顶点构成的多面体，一般 k = 2n 。复合形的形

10、状不受限制，可以变形，灵活得多；复合形法的收敛速度慢；复合形法对维数不高、约束条件不多，目标函数、约束函数很复杂，且精度要求不高的优化问题，有优越性。 二、复合形法的基本原理 对约束优化问题1 确定初始复合形 选择 k = n + 2 个顶点，通常 k = 2n ，这 k 个顶点必须是可行点。2 确定搜索方向i. 计算 k 个顶点的函数值，设 记 最坏点 X (1) 为 X (H) 次坏点 X (2) 为 X (G) 最好点 X (k) 为 X (L) 二、复合形法的基本原理ii. 求出 X (2)、 X (3)、 X (k-1)、 X (k) 的点集的中心(几何中心)X (S) iii. 以

11、 X (H) 指向 X (S) 的方向作为寻优的方向，沿此方向寻找一个较好的点 X (R) 。二、复合形法的基本原理二、复合形法的基本原理4 变形i. 扩张:若f ( X (R) 1 ； 则扩张成功，以 X (E) 代替 X (H) ，构成新的复合形；否则，仍以 X (R) 代替 X (H) 。ii. 收缩:若在 X (S) 以外找不到好的映射点，则向 X (S) 以内收缩，即 式中， 为收缩系数，0 1 ； 则以 X (K) 代替 X (H) ； 否则，仍以 X (R) 代替 X (H) 。二、复合形法的基本原理若上述措施无效，则向最好点 X (L) 靠拢： 然后，再重新寻找新顶点。三、初始

12、复合形的构成1 给定 k 个初始顶点 即选择 k 个可行的设计方案，适用于设计变量不多、约束函数不太复杂的优化问题。2 给定一个初始顶点，随机产生其它顶点 按传统的设计方法设计一个可行的设计方案，作为一个顶点，其它 k-1个顶点用随机方法产生：式中 为第 i 个设计变量的上、下限； 为 0 ，1 中服从均匀分布的随机数。 满足区域约束，但不一定满足性能约束，故必须检验其可行性，若 不在可行域内，可把它移到可行域内。三、初始复合形的构成设 则 通常取3 随机产生所有( k 个) 顶点 四、复合形法的计算步骤1 给定复合形的顶点数 k ，收敛精度 ，= 10-52 产生 k 个顶点 X(i) ，i

13、=1，2，k ，检验 若 ，重新产生 X(i) 3 计算中心点 X(C) 4 计算复合形顶点 X(i) ，i=1，2，k 及中心点 X(C) 的函数值5 比较 f ( X(i) ) ，i=1，2，k ，选出6 判别 或四、复合形法的计算步骤是，输出 X* = X(L) ，f (X*) = f (X(L) )，结束否，7 计算除最坏点以外的 k-1 个顶点的几何中心点 检验i. 是，ii. 否，利用 X(S) 和 X(L) 确定一个区间，在此区间内重新产生 k-1 个顶点，与 X(L) 一起构成新的复合形：若 否则，取产生新顶点检验否，重新产生。四、复合形法的计算步骤8 找映射点 检验 否， 是

14、，计算 X(R) 比较 f (X(R) ) f (X(H) ) ? 否， 是，以 X(R) 代替 X(H) ，构成新的复合形，9 取 若 ，则以 X(G) 代替 X(H) ， 否则，四、复合形法的计算步骤四、复合形法的计算步骤构造初始复合形构造新的映射点用新映射点代替最坏点可行方向法一、概述二、可行方向法的搜索路线三、产生可行下降方向的方法四、步长的确定五、确定调整步长六、可行方向法的终止准则七、可行方向法的算法步骤（从一个约束面到另一个约束面）一、概述 可行方向法是一种求解有约束、非线性最优化问题的直接搜索法，也是求解大型约束优化问题的主要方法之一。可行方向法的基本思想： 在可行域内，沿着可

15、行下降方向，寻找目标函数的极小点。可行方向法寻找约束优化问题最优解的基本要求：（1）沿着可行下降方向寻优，而且希望沿着目标函数值下降最快的可行方向寻优；（2）沿着可行下降方向作一维搜索时，希望以较大的步幅前进，同时要求：不越过极小点不越出可行域边界 二、可行方向法的搜索路线 可行方向法的寻优路线：（1）从可行域内的一个初始点 X(0) 出发，沿 方向搜索，到达可行域边界上的一点 X(k) ；()kX二、可行方向法的搜索路线（2）此后的搜索路线可分为三种类型：I. 从边界点 X(k) 出发，沿可行下降方向 S(k) 作一维优化搜索到达 X(k+1) ：a X(k+1) 在可行域内 ，寻优结束；

16、，沿 方向作一维优化搜索；b X(k+1) 不在可行域内，把 X(k+1) 调整到约束面上若 X(k+1) 满足 K-T 条件，寻优结束；否则，重复 I 步骤 ；二、可行方向法的搜索路线二、可行方向法的搜索路线II. 从边界点 X(k) 出发，沿可行下降方向，以最大步长从一个约束面移到另一个约束面，如此反复进行，直至满足 K-T 条件；二、可行方向法的搜索路线III. 从边界点 X(k) 出发，沿着约束面进行搜索，直至满足 K-T 条件。三、产生可行下降方向的方法I. X(k) 是可行域的内点 从 X(k) 点出发，沿 方向搜索。II. X(k) 是一个边界点，有适时约束 从 X(k) 点出发

17、，沿可行下降方向 S 搜索，S 应满足： （1） 确定可行下降方向 S 的三种方法：1)、 随机法i. 在 X(k) 点产生 N 个随机搜索方向 S(j) ，j = 1，2，lii. 按式(1) 对此 N 个方向逐个进行检验，满足式(1) 的方向 S(j) 取为可行下降方向；iii. 若共有 q 个可行下降方向，则取 S(j) 为搜索方向 三、产生可行下降方向的方法2)、 线性规划法 此方法适用与只有不等式约束和线性等式约束的优化问题（不能用于含有非线性的等式约束的优化问题）。 线性规划法的基本原理对于约束优化问题 把 f (X) 在 X(k) 点附近用泰勒公式展开成近似的线性函数，即 原问题

18、转化为： 三、产生可行下降方向的方法 若上式可改为 还应满足式即： 所以，寻找 X(k) 点的可行下降方向 S(k) 的问题归结为i. 线性约束的非线性优化问题 设约束函数为三、产生可行下降方向的方法三、产生可行下降方向的方法 由式(3) 可得：三、产生可行下降方向的方法则优化问题的数学模型可写成三、产生可行下降方向的方法 设在 X(k) 点有适时约束 gj (X(k) ，j = 1，2，l ，记 显然有三、产生可行下降方向的方法三、产生可行下降方向的方法三、产生可行下降方向的方法 于是，式(2) 描述的具有线性约束的优化问题，在 X(k) 点寻找可行下降方向 S(k) 的问题，归结为下述线性

19、规划问题： ii. 非线性不等式约束的优化问题 非线性不等式约束的优化问题 设在 X(k) 点有适时约束gj (X(k) ，j = 1，2，l 则 X(k) 点的可行下降方向 S 应满足令三、产生可行下降方向的方法 于是，在 X(k) 点寻找可行下降方向 S(k) 的问题，归结为线性规划问题： 对于式(6) ，S = 0 总是一个可行解，所以 min Z(S) 0 若 min Z(S) = 0 ，则 X(k) 点已经是满足 Kuhn-Tucker 条件的一个极小点；若 min Z(S) 0 此时，需要把 X(t) 退回到约束面上；iii. X(t) 点在可行域内，则 X(t) 点满足 gu(X(t) 0 ，(u = 1，2，m)以试验步长 at沿 S(k) 方向再前进一步；从 X(t) 点出发，沿 方向搜索。 直至 X(t) 点越出可行域，再把它调整到约束面上。四、步长的确定 最大步长只能通过试探求得。 为了减少试探次数，一般可给约束面规定一个适当的容差带 (0.0010.01) 当新点进入规定的容差带 之内，即可认为已到达了约束面。 五、确定调整步长 当新点 X(k+1) 越过可行域边界，进入非可行域，则必须把它调整到约束容差带内.1. 试探法五、确定调整步长