第六章约束优化方法ppt课件.ppt

《第六章约束优化方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《第六章约束优化方法ppt课件.ppt（153页珍藏版）》请在三一办公上搜索。

1、第六章 约束优化方法,约束优化方法概述随机方向法复合形法可行方向法惩罚函数法教学要求： 1、掌握随机方向法。 2、掌握复合形法的原理。 3、掌握内点法和外点法的惩罚函数的构造原理及程序设计。,6.1 约束优化方法概述,无约束优化方法是优化方法中最基本最核心的部分。在工程实际中，优化问题大都属于有约束的优化问题，即其设计变量的取值要受到一定的限制，用于求解约束优化问题最优解的方法称为约束优化方法。 约束优化设计的数序模型为： 根据求解方式的不同， 约束优化方法可以分为： 直接解法和间接解法,1、直接法 只能求解不等式约束优化问题的最优解。其根本做法是在约束条件所限制的可行域内直接求解目标函数的最

2、优解。如：约束坐标轮换法、复合形法等。 其基本要点：选取初始点x0 、确定可行搜索方向d及适当步长 。 每次迭代计算均按以下基本迭代格式进行xk+1 = xk + kdk (k = 1, 2, ) 可行搜索方向：当设计点沿该方向作微量移动时， 目标函数值下降， 且不越出可行域。,特点：1）求解在可行域内进行， 当前设计点总比初始设计点好；2）若目标函数为凸函数， 可行域为凸集， 可保证获得全域最优解；3）要求可行域为有界的非空集，即在有界可行域内存在满足全部约束条件的点， 且目标函数有定义。,2、间接法 该方法可以求解等式约束优化问题和一般约束优化问题。其基本思想是将约束优化问题通过一定的方法

3、进行改变，将约束优化问题转化为无约束优化问题，再采用无约束优化方法进行求解。如：惩罚函数法 基本迭代过程， 将约束优化问题转化成新的无约束目标函数式中 为转化后的目标函数 分别为约束函数gj(x), hk(x)经过加权处理后构成的某种形式的复合函数或泛函数 1，2为加权因子。,例6.1 求约束优化问题 minf(x) = (x12)2 + (x2 1)2 s.t. h(x) = x1 + 2x2 2 = 0 的最优解。解： 该问题的最优解为x* = 1.6 0.2T, f(x*) = 0.8。 由图6-3a可知， 约束最优点x*为目标函数等值线与等式约束函数（直线）的交点。 用间接法求解时，

4、可取1 = 0.8，转换后的新目标函数为(x, 2) = (x12)2 + (x2 1)2 + 0.8(x1 + 2x2 2 )可以用解析法求min(x, 2) , 令 = 0，得到/x1 = 2 (x12) +0.8 = 0/x2 = 2 (x12) +1.6 = 0求得的无约束最优解为x* = 1.6 0.2T, (x*，2) = 0.8。其结果与原约束最优解相同。,特点：1） 由于无约束优化方法的日趋成熟， 使得间接解法有了可靠的基础；2） 可以有效地处理具有等式约束的约束优化问题；3）存在的主要问题， 选取加权因子较为困难。 加权因子选取不当， 会影响收敛速度和计算精度，甚至会导致计算

5、失败。,6.2 随机方向法,本方法是在可行域内利用随机产生的可行方向进行搜索的一种直接解法，用于求解这类约束优化设计问题。在可行域内选择一个初始点x0， 利用随机数的概率特性， 产生若干个随机方向，并从中找出一个能使目标函数值下降最快的随机方向作为可行搜索方向， 记作d1。从初始点x0出发， 沿方向d1按给定的初始步长取试探点x = x0 + d1 检查x点的适用性和可行性，即检查f(x) f(x0), x D? 若满足， 则以x为新的起点， 即 x0 x。 继续按上面的迭代式在d1方向上获取新点。 重复上述步骤，迭代点可沿d1方向前进， 直至到达某迭代点不能同时满足适用性和可行性条件时为止，

6、退到前一点作为改方向搜索中的最终成功点， 记作x1. 将x1作为新的始点x0 x1，再产生另一随机方向d2, 以步长0重复以上过程， 直到沿d2方向得到最终成功点x3。如此循环， 点列x1、x2、必将逼近约束极值点x*。,一、随机数的产生 首先令r1 = 235, r2 = 236, r3 = 237, 取 r = 2657863 (r为小于r1的正奇数）， 然后按一下步骤计算 令 r5r 若r r3, 则rr r3 若r r2, 则rrr2 若r r1, 则rrr1则 q = r/r1q即为(0, 1)区间内的伪随机数。利用q, 容易求得任意区间(a, b)内的伪随机数， 其计算公式为x =

7、 a + q(ba),（6-5）,（6-4）,这部分内容为产生伪随机数的数学模型，可写成子程序。或者大家可以直接利用算法语言中自带的产生随机数的子程序。,二、初始点的选择 随机方向法的初始点x0必须是一个可行点，满足全部不等式约束条件。当约束条件较为复杂，用人工不易选择可行初始点时，可用计算机随机选择的方法来产生。其计算步骤如下： 1）输入设计变量的下限值和上限值，即 ai xi bi (i = 1, 2, ,n) 2）在区间（0，1）内产生n个伪随机数qi (i = 1, 2, , n) 3）计算随机点x的分量 xi = ai + qi (bi ai) (i = 1, 2, , n) 4)

8、判别随机点x是否可行，若可行取x0 x; 否则转步骤2）重新计算。直到产生的随即点是可行点为止。,（6-6）,三、可行搜索方向的产生 从k (k n) 个随机方向中，选取一个较好的方向。计算步骤为： 1）在（-1，1）区间内产生伪随机数rij ( i =1, 2, , n; j = 1, 2, , k), rij = 2qi - 1计算随机单位向量ej 2) 取一试验步长0，按下式计算k个随机点 3）检验k个随机点xj (j = 1, 2, , k)是否为可行点，除去非可行点， 计算余下的可行随机点的目标函数值， 比较其大小， 选出目标函数值最小的点xL. 4) 比较xL和x0 两点的目标函数

9、值， 若f(xL) f(x0), 取 xL和x0 的连线方向作为可行搜索方向； 若f(xL) f(x0), 则将步长0缩小， 转步骤1重新计算， 直至f(xL) f(x0)为止。 如果0缩小到很小（例如 106），仍然找不到一个xL, 使f(xL) f(x0), 则说明x0是一个局部极小点， 此时可更换初始点， 转步骤1.,（6-8）,（6-7）,产生可行搜索方向的条件可以概括为， 当xL点满足则可行搜索方向为 四、搜索方向的确定 可行搜索方向d确定后，初始点移至xL点，从xL点出发沿d方向进行搜索，所用的步长一般按加速步长法来确定。所谓加速步长法是指依次迭代的步长按一定的比例递增的方法。各次

10、迭代的步长按下式计算 = 式中 为步长加速系数，可取为1.3； 为步长，初始步长取 = 0。,（6-9）,（6-10）,五、计算步骤1）选择一个可行的初始点x0; 按式（6-7）产生k个n维随即单位向量ej (j = 1, 2, , k); 取试验步长0，按式（6-8）计算出k个随机点xj (j = 1, 2, , k); 在k个随机点中，找出满足式（6-9）的随机点xL, 产生可行搜索方向d= xLx0. 从初始点x0出发，沿可行搜索方向d以步长进行迭代计算，直到搜索到一个满足全部约束条件，且目标函数值不再下降的新点x. 若收敛条件得到满足，停止迭代。约束最优解为 。否则， 令x0 x转步骤

11、2）。,（6-12）,随机方向法的程序框图见图6-5。,例6-2 求约束优化问题的最优解。 解：用随机方向法程序， 在计算机上运行， 迭代13次， 求得约束最优解：x* = 0.0027 3.0T, f(x*) = 3。 计算机计算的结果摘录于表6-1， 该问题的图解示于图6-6.,（课外）例6-3 如图所示为平面铰接四杆机构。各杆的长度分别为l1, l2, l3, l4; 主动杆1的输入角为, 相应于摇杆3在右极位（杆1与杆2伸直位置）时， 主动杆1的初始位置角为0; 从动杆的输出角为，初始位置角为0。试确定四杆机构的运动参数， 使输出角 = f(, l1, l2, l3, l4, 0) 的

12、函数关系， 当曲柄从0位置转到m = 0 + 90o时，最佳再现下面给定的函数关系已知 l1 =1, l4 =5, 其传动角允许在45o 135o范围内变化。,(1),解： (1) 数学模型的建立已经给定了两根杆长: l1 =1, l4 =5, 且0和0不是独立的参数， 因为 所以只剩下两个独立参数l2, l3。 因此设计变量取 复演预期函数的机构设计问题， 可以按期望机构的输出函数与给定函数的均方根误差达到最小来建立目标函数， 即或者 由于和E均为输入角的连续函数， 为了进行数值计算， 可将0, m区间划分为30等分， 将上式改写为梯形近似积分计算公式,(2),(3),(4),式中 j 为当

13、 = j时机构的实际输出角； Ej 为复演预期函数当 = j时的函数值， 也是欲求机构的理论输出角。下标j为j = 0, 1, 2, , 30。 Ej 值按式（1）计算， j 值可按下式计算：目标函数是一个凸函数， 等值线如右图所示。,(5),(6),(7),(8),(9),由于要求四杆机构的杆1能做整周转动， 且机构的最小传动角min 45o、最大传动角min 135o，所以根据四杆机构的曲柄存在条件， 得不等式约束条件为根据传动角的条件有 cosmin cos45o, cos max 135o， 因所以得到不等式约束条件为在上面7个约束条件中， 式(10)-(14)的约束边界为直线， 式(

14、17)和(18)的约束边界为椭圆。在设计空间内组成一个可行设计区域， 即阴影线所包围的部分。,(10),(11),(12),(13),(14),(15),(16),(17),(18),(2) 优化设计结果 上述设计问题是属于二维的非线性规划问题， 有7个不等式约束条件， 其中主要的是g6(x) 0和g7(x) 0。现在采用随机方向法求解。 取初始点x10 = 4.5, x20 = 4, 搜索步长0 = 0.1, 目标函数值的收敛精度1 =0.0001， 步长的收敛精度2 =0.0001， 经过9次迭代， 其最优解为x1* = l2 = 4.1286, x2* = l3 = 2.3325, f(

15、x*) = 0.0156。,最终设计方案的参数为l1 =1, l2 = 4.1286, l3 = 2.3325, l4 =5, 0 = 26o28, 0 = 108o08, 机构图如下图左所示， 机构实际输出角和复演预期函数E的关系和误差见下图右。,6.3 复合形法,复合形法是求解约束优化问题的一种重要的直接解法。 一、复合形法的基本思想 其基本思路(见图6-7)是在可行域内构造一个具有k个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶点（称最坏点），然后按一定法则求出目标函数值下降的可行的新点, 并用此点代替最坏点，构成新的复合形，复合形就向最优点移动一步，直

16、至逼近最优点。,二、初始复合形的构成 要构成初始复合形，实际上就是确定k个可行点作为复合形的顶点，顶点数目一般在n+1 k 2n范围内。对于维数较低的优化问题，因顶点数目较少，可以由设计者自行凑出可行点作为复合形顶点。但对于维数较高的优化问题，这种方法常常很困难。 为此，提出构成复合形的随机方法。该方法是先产生k个随机点，然后再把那些非可行随机点调入可行域内，最终使k个随机点都称为可行点而构成初始复合形。 生成初始复合形的方法有以下几种： 1)由设计者决定k个可行点，构成初始复合形。当设计变量较多或约束函数复杂时，由设计者决定k个可行点常常很困难。只有在设计变量少，约束函数简单的情况下，这种方

17、法才被采用。,2）构成复合形的随机方法： 1、产生k个随机点 由设计者选定一个可行点， 其余的 ( k1) 个可行点用随机法产生。利用标准随机函数产生在（0，1）区间内均匀分布的随机数rj，然后产生区间a，b内的随机变量xj， xj = a+ rj（b a），j = 1，2，k (6-13)xj -复合形中的第j个顶点；a, b- 设计变量的下限和上限；rj -在 （0，1）区间内的伪随机数。 (6-14),2、将非可行点移入可行域 用上述方法的随机点不一定是可行点。但是只要它们中至少有一个点在可行域内，就可以用一定的方法将非可行点移入可行域。如果k个随机点没有一个是可行点，则应重新产生随机点

18、，直至其中有至少一个是可行点为止。 将非可行点移入可行域的方法：求出已经在可行域内的L个顶点的中心xC 然后将非可行点向中心点移动， 得 若xL+1仍为不可行点， 则利用上式， 使其继续向中心点移动。只要中心点可行， xL+1点一定可以移到可行域内。 随机产生的（k1)个点经过这样的处理后， 全部变为可行点，并构成初始复合形。,（6-14）,（6-15）,3、 由计算机自动生成初始复合形的全部顶点。其方法是首先随机产生一个可行点， 然后按第二种方法产生其余的（k-1)个可行点。,事实上，只要可行域为凸集，其中心点必为可行点，用上述方法可以成功地在可行域内构成初始复合形。如果可行域为非凸集，如图

19、6-8所示，中心点不一定在可行域之内，则上述方法可能失败。此时可以通过改变设计变量的下限和上限值，重新产生各顶点。经过多次试算，有可能在可行域内生成初始复合形。,三、复合形法的搜索算法一）反射 1、构成初始复合形； 计算个顶点函数值f(xj), j=1,2,k，并选出好点xL与坏点xH 及次坏点xG ： xL: f(xL) =minf(xL), j=1,2,k xH: f(xH) =maxf(xj), j=1,2,k xG: f(xG) =maxf(xj), j=1,2,k, GH ； 2、 计算除去最坏点xH外其余各顶点的中心点xC , 3、 反射就是沿最坏点xH 和中心点xC 的连线方向上

20、去映射点xR, 即 xR = xC +(xC xH)式中， 称为反射系数， 一般 = 1.3。反射点xR与最坏点xH、中心点xc的相对位置如图6-9所示。,4、如果xR 满足所有约束条件， 且f(xR) f(xH), 可用xR 代替xH组成新复合形， 完成一次迭代。 如果xR不满足约束条件， 或不满足f(xR) f(xH), 将 减半重新计算xR ，若仍不满足， 可以继续将 减为0.7倍重新计算xR ，直到 减得很小（例如小于105）还不满足要求时，就放弃这一方向， 改用次坏点的映射方向。,复合形法的程序框图见图6-13。,（课外）例 用复合形法求解解;1) 产生初始复合形的顶点。 取 复合形

21、顶点的数目为k = 2n = 4, 并采用认为选点的方法确定初始复合形的四个顶点为以上四点均满足约束条件2）四点的函数值分别为由此可知最坏点为x10, 好点为x40.3) 计算除去坏点后， 各点的中心点4）检查xC0点的可行性， 由于所以xc0是可行点。,5) 求反射点xr0并检查其可行性取反射系数 = 1.3， 可得反射点也是可行的。6）比较反射点与最坏点的目标函数值用xr0代替xH0，与其余3点构成新的复合形。第二轮迭代， k = 1新复合形的四个顶点为其对应的函数值为,由此可见， xH1 = x21 =1, 4T， 除去坏点后其余各点的中心为xC1 = 2.77, 4.46T, 满足所有

22、约束条件， 是可行点。 进行反射计算， 得xr1= 5.071, 5.058T, 经检验xr1也是可行点，其f(xr1) = 14.71 47 = f(xh1), 故可重新组成复合形， 再计算，直至达到精度要求停机， 最后所求得的x1k 和f(x1k)接近理论最优解x* = 6, 5T, f(x*) = 11.,6.4 可行方向法,基本原理 在可行域内选择一个初始点x0, 当确定了一个可行方向d和适当的步长之后， 按下式xk+1 = xk + dk (k=1, 2, )进行迭代进算。 在不断调整可行方向的过程中， 使迭代点逐步逼近约束最优点。,一、搜索策略 第一步从可行的初始点x0, 沿x0的

23、负梯度方向d0 = f(x0), 将初始点x0移动到某一约束面（当只有一个起作用的约束时）上或约束面的交集（有几个起作用的约束时）上。 根据约束函数和目标函数的不同性状， 可以采用如下几种策略。,1） 如图6-15， 在约束面上的迭代点xk处， 产生一个 可行方向dk, 沿此方向作一维最优化搜索， 得到的新点x在可行域内， 即令xk+1 = x, 再沿xk+1的负梯度方向dk+1 = f(xk+1)继续搜索2） 如图6-16，沿可行方向dk作一维最优化搜索，所得到的新点x在可行域外， 则设法将x点移动到约束面上， 即取dk和约束面的交点作为新的迭代点xk+1 。,3） 沿约束面搜索。如图6-1

24、7，对于只具有线性约束条件的非线性规划问题， 从 xk点出发，沿约束面移动，在有限的几步内即可搜索到约束最优点；对于非线性约束函数如图6-18， 沿约束面移动将会进入非可行域， 使问题变得复杂得多。此时， 需将进入非可行域的新点x设法调整到约束面上， 然后才能进入下一次迭代。 调整的方法是先规定约束面容差，建立新的约束边界（如6-18中虚线所示）， 然后将已离开约束面的x点， 沿起作用约束函数的负梯度方向g(x)返回到约束面上。 其计算公式为xk+1 = x + tg(x)式中的t为调整步长， 可用试探法决定， 或者用下式计算,二、产生可行方向的条件 可行方向是指沿该方向做微小移动后， 得到的

25、新点是可行点， 且目标函数值下降。 包括可行和下降两个条件。1）可行条件 如图6-19a， 若xk点在一个约束面上， 对xk点作约束面g(x) = 0的切线，显然满足可行条件的方向dk应与起作用的约束函数在该点的梯度的夹角大于或等于90o。 即 g(xk)Tdk 0 若xk点在J个约束面的交集上， 如图6-19b，为保证dk可行， 要求dk与J个约束函数在xk点的梯度gj(xk) (j = 1, 2, , J)的夹角均大于等于直角。即gj(xk)Tdk 0 (j = 1, 2, , J),dk,2）下降条件 如图6-20， 满足下降条件的方向dk应与目标函数在xk点的梯度的f(xk) 的夹角大

26、于90o。 即 f(xk)Tdk 0 同时满足可行和下降条件的方向称为可行方向。如图6-21所示，它位于约束曲面在xk点的切线和目标函数等值线在xk点的切线所围成的扇形区内， 该扇形区称为可行下降方向区。,即当xk点位于J个起作用的约束面上时，满足的方向dk称可行方向。,三、可行方向的产生方法1.优选方法 在可行下降扇形区内选择任一方向d进行搜索， 可得到一个目标函数值下降的可行点。 如何在可行下降扇形区内选择一个能使目标函数下降最快的方向作为本次迭代的方向， 是一个以搜索方向d为设计变量的约束优化问题， 这个新的约束优化问题的数学模型可写成 （6-31） 由于f(xk)和gj(xk) (j

27、= 1, 2, , J)为定值， 上述各函数均为设计变量d的线性函数。求解式(6-31)得到的最优解d*即为本次迭代的可行方向， 即dk = d*.,2 梯度投影法 当xk点目标函数的负梯度方向f(xk)不满足可行条件时， 可将其方向投影到约束面（或约束面的交集）上， 得到投影向量d， 从图6-22可以看出， 改投影向量显然满足方向的可行和下降条件。 梯度投影法就是取该方向作为本次迭代的可行方向。 可行方向的计算公式为式中， P为投影算子， 为nn阶方阵， 计算公式为式中， I为单位矩阵， nn阶矩阵； G为起作用约束函数的梯度矩阵，是 nJ 阶矩阵(J为起作用的约束函数个数)：,4、步长的确

28、定确定可行方向dk后， 计算新的迭代点: xk+1 = xk + kdk k的确定有两种方法（1）取最优步长 如图6-23所示， 从xk出发， 沿dk方向进行一维最优搜索， 取得最优步长*，计算新点的值x = xk + *dk。若新点x可行， 则取k = *。,（2）k取到约束边界的最大步长 如图6-24所示， 从xk出发， 沿dk方向进行一维最优搜索，得到的新点x不可行， 根据可行方向法的搜索策略，应改变步长，使新点x返回到约束面上来。使新点恰好位于约束面上的步长称为最大步长，记作M。则取k = M。 M的确定步骤：1） 取一试验步长t，计算试验点xt。试验步长t的值不能太大， 以免因一步走

29、得太远导致计算困难； t也不能太小，降低计算效率。依据经验， 其值应能使试验点x的目标函数值下降5-10%将目标函数f(x)在xt点展开成泰勒级数的线性式则于是得则试验点xt的计算公式为,2） 判别试验点xt的位置。 由试验步长t确定的试验点xt可能在约束面上，可行域或非可行域。若不在约束面上， 须设法将其调整到约束面上来。 使xt到达约束面gj(x) =0 (j = 1, 2, , J)常很困难。 为此， 确定一个约束允差。 若试验点xt满足 gj(x) 0 (j =1,2, ,J)时， 可认为试验点xt已经位于约束面上。 若试验点位于非可行域， 转步骤3）； 若试验点位于可行域， 应沿dk

30、方向以步长t 2t继续向前搜索， 直至新的试验点xt到达约束面或越出可行域， 再转步骤3)。,为约束面的容差值， 一般视计算精度而定， 开始可以取大一点， 0.010.001， 然后在迭代中当满足一定的收敛条件时， 在将容差值逐渐缩小， 直至当 = 105时， 则认为该点已经位于约束面上。,3）将位于非可行域的试验点xt调整到约束面上。 如图6-25所示， 在xt点处，g1(xt) 0, g2(xt) 0。应将xt点调整到g1(xt) = 0 的约束面上， 因为对于xt点来说， g1(xt) 的约束违反量比 g2(xt)大。 若设gk(xt)为约束违反量最大的约束条件， 则应满足 将试验点xt

31、调整到gk(xt) = 0的约束面上的方法有试探法和插值法两种。 试探法：当试验点位于非可行域时，将试验步长t缩短；当位于可行域时，将试验步长t加倍，直至满足 gj(x) 0 (j =1, 2, , J)，即认为试验点已经被调整到约束面上了。,图6-26所示框图表示了用试探法调整试验步长t的过程。,(b) 插值法：利用线性插值将位于非可行域的试验点xt调整到约束面上。设试验步长t，求得可性试验点当试验步长为t + 0时， 求得非可行试验点并设在该两点的约束函数分别为 gk(xt1) 0 和 gk(xt2) 0 , 如图6-27所示。 若考虑约束允差，并按允差中心/2做线性内插， 可以得到将xt

32、1调整到约束面上的步长s。本次迭代步长取为,五、收敛条件 将设计点调整到约束面上后， 需判断迭代是否收敛，即判断该迭代点是否为约束最优点。1）满足2) 满足库恩-塔克条件,六、可行方向法的计算步骤1）在可行域内选一个初始点x0，给出约束允差及收敛精度值。2）令迭代次数k = 0, 第一次迭代的搜索方向取d0 = f(x0)估算试验步长t，按式(6一38)计算试验点xt若试验点xt满足 gj(xt) 0，xt点必位于第j个约束面上， 则转步骤6）；若试验点xt 位于可行域内， 则加大试验步长t，重新计算新的试验点，直至xt 越出可行域， 再转步骤5）；若试验点位于非可行域， 则直接转步骤5）,5

33、）确定约束违反量最大的约束函数gk(xt)。用插值法计算调整步长t，使试验点xt返回到约束面上， 则完成一次迭代。再令k k+1, xk = xt, 转步骤6）6） 在新的设计点xk处产生新的可行方向dk7) 在xk点满足收敛条件， 停机。约束最优解为x* = xk, f(x*) = f(xk)。否则，改变允差的值，令可行方向法的程序框图示于图6-28。,可行方向法的程序框图示于图6-28。,例 用可行方向法求约束优化问题minf(x1, x2) = x12 + x22 - 10 x1 - x1x2 - 4x2 +60s.t. g1(x) = x1 0 g2(x) = x2 0g3(x) =

34、x1 6 0g4(x) = x2 8 0g5(x) = x1 + x2 11 0的约束最优解。解：取初始点x0 = 0 1T，为约束 边界g1(x) = 0上的一点。第一次迭代用优选方向法确定可行方向。 为此， 首先计算x0点的目标函数f(x0)和约束函数g1(x0)的梯度为在可行下降扇形区内寻找最优方向，需求解一个以可行方向d=d1 d2T为设计变量的线性规划问题，其数学模型为：,现用图解法求解，如图6-30所示。最优方向是d*=0.984 0.179T，它是目标函数等值线（直线束）和约束函数d12+d22=1（半径为1的圆）的切点。第一次迭代的可行方向为d0=d*。若步长取0=6.098，

35、则可见第一次迭代点x1在约束边界g3(x1)=0上。,第二次迭代用梯度投影法来确定可行方向。迭代点x1的目标函数负梯度-f(x1)=0.092 5.818T，不满足方向的可行条件。现将f(x1)投影到约束边界g3(x)=0上，按式（6-33）计算投影算子P本次迭代的可行方向为显然，d1为沿约束边界g3(x)=0的方向。若取1=2.909，则本次迭代点即为该问题的约束最优点x*，则得约束最优解,6.5 惩罚函数法 惩罚函数法的基本原理是将约束优化问题中的不等式约束和等式约束经过加权转化后，与原目标函数一起构成新的目标函数惩罚函数 求解该新目标函数的无约束极小值，以期得到原问题的约束最优解。为此，

36、按一定法则改变加权因子r1、r2的值，求得惩罚函数的一系列无约束最优解，并使其不断逼近原约束优化问题得最优解。 因此，惩罚函数法又称序列无约束极小化方法-SUMT法。 式(6-47)中的 称为加权转化项，并根据它们在惩罚函数中的作用，又分别称为障碍项和惩罚项。,障碍项的作用是当迭代点在可行域内时，在迭代过程中阻止迭代点越出可行域。惩罚项的作用是当迭代点在非可行域或不满足等式约束条件时，在迭代过程之中迫使迭代点逼近约束边界或等式约束曲面。 根据迭代过程是否在可行域内进行，惩罚函数法又可分为内点惩罚函数法、外点惩罚函数法、混合惩罚函数法三种。一、内点惩罚函数法 简称内点法。将新目标函数定义在可行域

37、内，序列迭代点在可行域内逐步逼近约束边界的最优点。内点法只能求解具有不等式约束的优化问题。 对于只具有不等式约束的优化问题,转化后的惩罚函数形式为或式中r为惩罚因子，它是由大到小且趋近于0的数列，即r0 r1 r2 0。 由于内点法的迭代过程在可行域内进行，障碍项的作用是阻止迭代点越出可行域。由障碍项的函数形式可知，当迭代点靠近某一约束边界时，其值趋于0，而障碍项的值陡然增加，并趋近于无穷大，好像在可行域的边界上筑起了一道“围墙”，使迭代点始终不能越出可行域。显然，只有当惩罚因子r0时，才能求得在约束边界上的最优解。,例6-5 用内点法求问题的约束最优解。 解： 如图6-31所示，该问题的约束

38、最优点为x*=1 0T，它是目标函数等值线，即x12+x22=1的圆和约束函数，即1-x1=0的直线的切点，最优值为f(x*)=1。 用内点法求解该问题时，首先按式（6-50）构造内点惩罚函数对于任意给定的惩罚因子r (r 0)，函数(x,r)为凸函数。用解析法求函数(x,r) 的极小值，即令(x,r) = 0，得方程组,当 时不满足约束条件g(x) = 1 x1 0, 应舍去。 无约束极值点为可知， 当逐步减小r值，直至趋近于0时， x*(r)逼近原问题的约束最优解。当r = 4, 1.26, 0.36时， 惩罚函数(x,r)的等值线分别如图6-32a、b、c所示。,重要参数的选取1、初始点

39、x0的选取 应选择一个离约束边界较远的可行点。 若其太靠近某一个约束边界， 构造的惩罚函数可能由于障碍项的值很大而变得畸形， 使无约束优化问题的求解发生困难。2、惩罚因子初值r0的选取 应适当选取， 否则会影响迭代计算的正常进行。 r0太大， 将增加迭代次数； 太小会使惩罚函数的性态变坏， 甚至难以收敛到极值点。 由于问题的多样化， 是的r0的取值相当困难， 目前尚无一定的有效的方法。 一般需由此试算， 来决定一个适当的初值。 可参考以下方法：1）取r0 = 1, 根据试算的结果， 再决定增加或减小r0的值。2）按经验公式计算。这样选取的r0可使惩罚函数中的障碍项和原目标函数的值大致相等， 不

40、会因障碍项的值太大起支配作用， 也不会因障碍项的值太小而被忽略。,3、惩罚因子的缩减系数c的选取rk = crk + 1 (k = 1, 2, )c称为惩罚因子的缩减系数， 一般认为其值大小在迭代过程中不起决定性作用， 通常在0.10.7范围内选取。4、收敛条件原约束问题的最优解为,内点法的计算步骤：1）选取可行的初始点x0， 惩罚因子的初值r0，缩减系数c和收敛精度1、2. 迭代次数k 0。2）构造惩罚函数(x,r)，选择适当的无约束优化方法， 求函数的无约束极值， 得x*(rk)点3）判断是否收敛，收敛则停止计算；约束最优解为否则令转步骤2）,二、外点惩罚函数法 简称外点法。其基本思想是将

41、新目标函数定义在可行域之外，序列迭代点从可行域之外逐步逼近约束边界的最优点。 外点法可以求解具有不等式约束和等式约束问题的优化问题。1、惩罚函数的形式 对于约束优化问题转化后的外点惩罚函数形式为式中 r为惩罚因子，它由小到大，且趋近于的数列，即r0 r1 r2 分别为对应于不等式约束和等式约束函数的惩罚项。,外点法的迭代过程在可行域之外进行， 惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面。有惩罚项的形式可知， 当迭代点x不可行时，惩罚项的值大于0.使得惩罚函数(x,r)大于原目标函数，这可看成是对迭代点不满足约束条件的一种惩罚。当迭代点离约束边界愈远， 惩罚项的值愈大，这种惩罚愈重。但当

42、迭代点不断接近约束边界和等式约束曲面时， 惩罚项的值减小， 且趋近于0，惩罚项的作用逐渐消失，迭代点也就趋近于约束边界上的最优点了。,例6-5 用外点法求问题的约束最优解。 解： 该问题的约束最优点为x*=1 0T，它是目标函数等值线，即x12 + x22=1的圆和约束函数，即 1-x1=0 的直线的切点，最优值为f(x*)=1。构造外点惩罚函数对于任意给定的惩罚因子r 0，函数(x,r)为凸函数。 求其无约束极小值， 令 (x,r) = 0，得求得 由计算可知，当逐渐增大r值直至无穷时，x*(r)逼近原目标函数的极值点。,初始点x0的选取,在可行域及非可行域内均可。 惩罚因子的递增系数c的选

43、取rk = crk - 1 (k = 1, 2, )c称为惩罚因子的递增系数， 通常在510范围内选取。 在外点法中， r0的合理取值也是很重要的。选取过小，则序贯无约束求解的次数就增多，收敛速度慢；反之，则在非可行域中，发函数比原目标函数要大得多，特别在起作用约束边界处产生尖点，函数性态变坏，从而限制了某些无约束优化方法的使用，致使计算失败。 取r0 = 1, c = 10常可取得满意的结果。 也可按下面的经验公式来计算r0.r0 = maxrj0 (j = 1, 2, ,m)式中,混合法,用罚函数法解决有等式约束和不等式约束的一般约束优化问题的方法，把它称为混合惩罚函数法，简称混合法。,1

44、 混合法惩罚函数的形式及特点,一般约束问题的优化模型,转化后的混合惩罚函数的形式为,为障碍项，r为惩罚因子，按内点法取r0 r1 r2 0。,为惩罚项， 为惩罚因子，当r 0时， 满足外点法对惩罚因子的要求。,例 6-7 试求点集A(x1, x2,x3)和点集B(x4, x5, x6)之间的最短距离。限制条件为由右下图可知， 表示以原点为球心， 半径为 的球体， 点集A在球面上取点。其余两个限制条件表示一圆柱体， 点集B在圆柱面上取点。 因此该问题就是求这两个几何体间的最短距离的约束优化问题， 其数学模型为解: 用混合法编程计算， 取x0 = 1 1 1 3 1 5T, r0 = 1, c =

45、 0.2. 在计算机上迭代13可求得最优解为x* = 1.0015 -0.0035 1.99 2.0 -0.0077 4.07Tf(x*) = 5.0008,（课外）例：如图所示为一对称的两杆支架，在支架的顶点承受一个荷载2F = 300000 N，支座之间的水平距离为2B = 1520 mm，若选定壁厚T = 2.5 mm的钢管，弹性模量E = 2.16105 MPa, 密度 = 8300 kg/mm3, 屈服点s =700 MPa, 要求在满足强度与稳定性条件下设计最轻的支架尺寸。,解：数学模型的建立设计变量取 目标函数为约束条件为1）圆管杆件中的压应力应小于或等于材料的屈服极限s,即于是

46、得到2）圆管杆件中的压应力应小于或等于压杆稳定的临界压力， 由欧拉公式得钢管的压杆稳定应力于是得,（2）求解结果和分析此问题的外点法惩罚函数为取初始点x0 = 15.2， f(x0) = 21.24, r0 = 10 -10, 无约束极小化， 用变尺度法求解。,(课外) 例：如6-47图所示，设有一箱形盖板，已知长度L=6000mm，宽度b=600mm，厚度ts=5mm。翼板厚度为tf（cm），它承受最大的单位载荷q=0.01MPa。弹性模量E=7104MPa，泊松比=0.3，允许弯曲应为u=70MPa，允许剪切应力=45MPa。要求在满足强度、刚度和稳定性等条件下，设计一个重量最轻的方案。解

47、：（1）设计分析 截面的惯性矩近似取,最大剪应力为最大弯曲应力（翼板中间）为式中 Q-最大剪应力，Q=18000N。翼板中的屈曲临界稳定应力为最大挠度为盖板单位长度的质量（kg/cm）为,式中 -材料的密度，t/m3。数学模型根据设计要求，建立如下 数学模型：设计变量：目标函数：式中已略去密度，因为它对目标函数极小化没有影响。设计约束：按照强度、刚度和稳定性要求建立如下约束条件。,单位长度允许挠度取f/L=1/400。 在下图中给出了问题在设计平面上的几何关系：f(x)的等值线和约束边界曲线g1(x)g6(x)。阴影线的右边为可行设计区域，其最优解在P点。,（3）求解方法和结果用内点惩罚函数法

48、来解这个问题。其惩罚函数如下式 初始点取x(0) = 1,30T，是一个可行点。取惩罚因子初始值r(0) = 3，降低系数c = 0.7，收敛精度 = 10-6，用Powell方法求函数(x,r(k)的无约束极值，其计算结果见下表。,共循环k=71次，r值由3降至0.682710-12，迭代129次，其最优解为x1*=0.6366，x2*=24.9685，f(x*)=101.3605， (x*,r)=101.3706,由于r值几乎趋近于零，所以说明取得了较精确的解答。 在下图中给出了三个r值2.1、1.47和0.48810-2 的惩罚函数(x*,r(k)等值线的图形，表明了条件极小点逐渐向真正

49、最优点靠拢。,通过本例说明，内点惩罚函数的优化解是比较精确的。但从工程实际意义来说，一般不需要如此高的精度，若按设计方案的修改量来控制计算精度，即取3=0.01，则其循环次数可以减少到k=25次，迭代78次，其解为 计算时间少一半，而所取的解仍能满足工程实际要求。可见，根据实际要求来确定收敛精度，是一项很有意义的工作。,采用内点惩罚函数法时，惩罚因子初始值r(0)的大小和下降系数c的大小，对问题的最优解影响很小。但对计算过程和收敛速度是有影响的。这可以从下表中的数据看出，当r(0)值增大时，其循环次数和迭代次数都增加了。因此，也就占用了较多的计算时间。,在下图中，给出了当取相同惩罚因子初始值r(0)=3，而取不同下降系数c值时，取得相同精度解与循环次数k的关系。所以从节省计算时间来看，选择一个适当较小的c值是有好处的。,