06 第六章 约束优化方法.ppt

第1页：约束优化方法的分类

第六章 约束优化方法：根据求解方式的不同，可分为直接解法和间接解法两类。机械优化设计的问题大多属于约束优化设计问题。

直接解法是在满足不等式约束的可行设计区域内直接求出问题的约束最优解，属于这类方法的有：

• 随机实验法
• 随机方向搜索法
• 复合形法
• 可行方向法

第2页：间接解法与直接解法的思路

间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法，可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题，因而在机械优化设计中得到广泛应用，其中具有代表性的是惩罚函数法。

第3页：直接解法的基本迭代格式

直接解法的基本思想：在由 m 个不等式约束条件所确定的可行域 φ 内选择一个初始点 x⁽⁰⁾，然后确定一个可行搜索方向 S，且以适当的步长沿 S 方向进行搜索，取得一个目标函数有所改善的可行的新点 x⁽¹⁾，即完成一次迭代。

基本迭代格式：x⁽ᵏ⁺¹⁾=x⁽ᵏ⁾+α⁽ᵏ⁾S⁽ᵏ⁾（k=0,1,2,…），逐步趋向最优解，直到满足终止准则才停止迭代。

第4页：直接解法的特点

直接解法的原理简单、方法实用，其特点是：

1. 由于整个过程在可行域内进行，因此迭代计算不论何时终止，都可以获得比初始点好的设计点。
2. 若目标函数为凸函数、可行域为凸集，则可获得全域最优解；否则可能存在多个局部最优解，选择不同的初始点会搜索到不同的局部最优解。
3. 要求可行域为有界的非空集。

第5页：凸集与非凸集可行域

本页给出可行域的两种形态：a）可行域是凸集；b）可行域是非凸集，用以说明初始点选取对局部最优解的影响。

第6页：间接解法的求解思路

间接解法的求解思路：将约束函数进行特殊的加权处理后和目标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优化问题；然后对新目标函数进行无约束极小化计算。

第7页：

第8页：随机方向法

第二节 随机方向法的基本思路：在可行域内选择一个初始点，利用随机数的概率特性产生若干个随机方向，并从中选择一个能使目标函数值下降最快的随机方向作为搜索方向 d。从初始点 x⁰ 出发沿 d 方向以一定步长进行搜索，得到新点 X，新点应满足约束条件且 f(X)<f(x⁰)，至此完成一次迭代。

随机方向法程序设计简单，搜索速度快，是解决小型机械优化问题的十分有效的算法。

第9页：

第10页：随机数的产生

一、随机数的产生：介绍一种常用的产生随机数的数学模型。首先取 r=2657863，按给定步骤递推计算，得到（0，1）之间的随机数；在任意 (a,b) 区间内的随机数可由此线性变换得到。

第11页：初始点的选择

二、初始点的选择：随机方向法的初始点 x⁰ 必须是一个可行点，即满足全部不等式约束条件。初始点可以通过随机选择的方法产生：

1. 输入设计变量的下限值和上限值
2. 在区间（0，1）内产生 n 个伪随机数
3. 计算随机点 x 的各分量

第12页：可行搜索方向的产生

4. 判别随机点 x 是否可行：若可行，用 x 代替 x⁰ 为初始点；若为非可行点，转第 2 步重新产生随机点，直到可行为止。

三、可行搜索方向的产生：从 k 个随机方向中选取一个较好的方向：

1. 在 (-1,1) 区间内产生伪随机数，得随机单位向量

第13页：随机方向的检验与选取

2. 取一试验步长 α₀，按下式计算 k 个随机点
3. 检验 k 个随机点是否为可行点，除去非可行点，计算余下可行点的目标函数值并比较大小，选出目标函数最小的点 X_L
4. 比较 X_L 和 X₀ 两点的目标函数值：若 f(X_L)<f(X₀)，则取两点连线方向为可行搜索方向；若 f(X_L)>f(X₀)，则步长 α₀ 缩小后转第 1 步重新计算，直至满足为止。若 α₀ 缩小到很小仍找不到这样的点，则说明 X₀ 是一个局部极小点，此时可更换初始点重新计算。

第14页：可行搜索方向与步长确定

产生可行搜索方向的条件满足时，即可行搜索方向取为使目标函数下降的方向。

四、搜索步长的确定：步长由加速步长法确定。

第15页：复合形法的基本思路

五、随机方向法的计算步骤见本页图示。

第三节 复合形法：复合形法是求解约束优化问题的一种重要的直接解法。它的基本思路是在可行域内构造一个具有 k 个顶点的初始复合形，对各顶点的目标函数值进行比较，找到目标函数最大的顶点（最坏点），然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点构成新的复合形；复合形的形状每改变一次，就向最优点移动一步，直至逼近最优点。

第16页：

第17页：初始复合形的生成

初始复合形生成的方法：

1. 由设计者决定 k 个可行点，构成初始复合形（设计变量少时适用）
2. 由设计者选定一个可行点，其余的 k-1 个可行点用随机法产生
3. 由计算机自动生成初始复合形的所有顶点

第18页：复合形法的反射（一）

二、复合形法的搜索方法 —— 1. 反射

1. 计算复合形各顶点的目标函数值，并比较其大小，求出最好点 X_L、最坏点 X_H 及次坏点 X_G

第19页：反射中心与下降方向

2. 计算除去最坏点 X_H 外的 (k-1) 个顶点的中心 X_C
3. 从统计的观点来看，一般情况下，最坏点 X_H 和中心点 X_C 的连线方向为目标函数的下降方向

第20页：反射点判别与扩张

4. 判别反射点 X_R 的位置：若 X_R 为可行点，则比较 X_R 和 X_H 两点的目标函数值，如果 f(X_R)<f(X_H)，则用 X_R 取代 X_H 构成新的复合形，完成一次迭代；如果 f(X_R)≥f(X_H)，则将 α 缩小 0.7 倍重新计算新的反射点，直至满足为止。若为非可行点，则将 α 缩小 0.7 倍直至可行为止，再重复可行点的步骤。

2. 扩张：当反射成功且函数值下降显著时，可沿同一方向加大步长进行扩张，以加快搜索。

第21页：复合形法的收缩

3. 收缩：当反射与扩张均不能得到优于最坏点的可行点时，将复合形各顶点向最好点方向收缩，使复合形缩小后继续寻优。

第22页：

第23页：

第24页：惩罚函数法的基本原理

第五节 惩罚函数法：惩罚函数法是一种应用广泛、很有效的间接解法。它的基本原理是将约束优化问题中的约束函数经加权后和原目标函数结合为新的目标函数——惩罚函数，从而将约束优化问题转换为无约束优化问题，求解无约束优化问题的极小值，即得到原约束优化问题的最优解。

第25页：障碍项与惩罚项

惩罚函数法是按一定的法则改变加权因子的值，构成一系列的无约束优化问题，求一系列无约束最优解，并不断地逼近原约束优化问题的最优解，因此又称序列无约束极小化方法，常称 SUMT 方法。

障碍项

当迭代点在可行域内时，在迭代过程中将阻止迭代点越出可行域。

惩罚项

当迭代点在非可行域或不满足等式约束条件时，在迭代过程中将迫使迭代点逼近约束边界或等式约束曲面。

第26页：内点惩罚函数法

一、内点惩罚函数法：内点法将新目标函数定义于可行域内，这样它的初始点及后面的迭代点序列必定在可行域内。采用内点法只能求解具有不等式约束的优化问题。转化后的惩罚函数形式为原目标函数加障碍项。

第27页：例6-5 内点法求解

障碍项的作用是阻止迭代点越出可行域。

例6-5：用内点法求问题的约束最优解。

第28页：

第29页：内点惩罚函数的构造

用内点法求解，首先构造内点惩罚函数，再用解析法对函数求极小值，求解得相应的结果。

第30页：解的取舍

所求得的解中，不满足约束条件的应舍去；保留下来的即为无约束极值点。

第31页：初始点与惩罚因子初值

1. 初始点的选取：初始点应选离约束边界较远的可行点。程序设计时一般同时考虑人工输入和计算机自动生成可行初始点的两种功能。

2. 惩罚因子初值 r₀ 的选取：太大会影响迭代次数，太小会使惩罚函数的形态变坏、难以收敛到极值点。可取 r₀=1 根据试算结果再决定增减。

第32页：惩罚因子的缩减系数

2）按经验公式计算 r₀ 值，这样选取的 r₀ 可以使惩罚函数中的障碍项和原目标函数的值大致相等，不会因障碍项太大而起支配作用，也不会因太小而被忽略。

3. 惩罚因子的缩减系数 c 的选取：惩罚因子 r 是一个逐次递减到 0 的数列，相邻两次迭代的惩罚因子满足给定关系，缩减系数的通常取值范围为 0.1–0.7。

第33页：内点法的收敛条件

4. 收敛条件：本页给出内点惩罚函数法迭代终止的收敛判别条件。

第34页：

第35页：外点惩罚函数法

内点法是将惩罚函数定义于可行域内，而外点法与内点法不同，是将惩罚项函数定义于可行区域的外部，序列迭代点从可行域外部逐渐逼近约束边界上的最优点。

二、外点惩罚函数法：外点法可以用来求解含不等式和等式约束的优化问题。

第36页：外点惩罚函数

惩罚因子由小到大。由惩罚项可知：当迭代点不可行时，惩罚项的值大于零；当迭代点离约束边界越远时惩罚项愈大，这可以看成是对迭代点不满足约束条件的一种惩罚。本页给出转化后的外点惩罚函数形式。

第37页：

第38页：例6-6 外点法求解

例6-6：用外点法求问题的约束最优解。首先构造外点惩罚函数，再用解析法求解。

第39页：外点法求解结果

对外点惩罚函数求导并令其为零，求解得相应的极值点。

第40页：外点法惩罚因子的选取

外点法惩罚因子按下式递增，递增系数通常取 c=5–10。与内点法相反地计算 r₀ 值：选取的 r₀ 太大会使惩罚函数等值线偏心或变形、难以取得极小值；r₀ 太小则势必增加迭代次数。经验计算一般取 r₀=1，c=10 常常可以取得满意的效果，也可以通过经验公式获得 r₀ 值。

第41页：内点法与外点法的特点对比

第42页：混合惩罚函数法

三、混合惩罚函数法：在构造惩罚函数时，可以同时包括障碍项与惩罚项，并将惩罚因子统一用 r^(k) 表示。由于内点法容易处理不等式约束优化设计问题，而外点法又容易处理等式约束优化设计问题，因而可将内点法与外点法结合起来，处理同时具有等式约束和不等式约束的优化设计问题。

第43页：混合惩罚函数法的归类

这种同时处理等式和不等式约束的惩罚函数法称为混合惩罚函数法。混合惩罚函数法与前述内点法和外点法一样，也属于序列无约束极小化（SUMT）方法中的一种方法。